| /* |
| * Copyright 2000-2014 JetBrains s.r.o. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package com.intellij.vcs.log.graph.impl.print; |
| |
| import com.intellij.util.SmartList; |
| import com.intellij.util.containers.SLRUMap; |
| import com.intellij.vcs.log.graph.api.LinearGraphWithElementInfo; |
| import com.intellij.vcs.log.graph.api.elements.GraphEdge; |
| import org.jetbrains.annotations.NotNull; |
| |
| import java.util.HashSet; |
| import java.util.List; |
| import java.util.Set; |
| |
| public class EdgesInRowGenerator { |
| private static final int CACHE_SIZE = 10; |
| private static final int BLOCK_SIZE = 40; |
| |
| private final int WALK_SIZE; |
| |
| @NotNull |
| private final LinearGraphWithElementInfo myGraph; |
| |
| @NotNull |
| private final SLRUMap<Integer, GraphEdges> cacheNU = new SLRUMap<Integer, GraphEdges>(CACHE_SIZE, CACHE_SIZE * 2); |
| private final SLRUMap<Integer, GraphEdges> cacheND = new SLRUMap<Integer, GraphEdges>(CACHE_SIZE, CACHE_SIZE * 2); |
| |
| public EdgesInRowGenerator(@NotNull LinearGraphWithElementInfo graph) { |
| this(graph, 1000); |
| } |
| |
| public EdgesInRowGenerator(@NotNull LinearGraphWithElementInfo graph, int walk_size) { |
| myGraph = graph; |
| WALK_SIZE = walk_size; |
| } |
| |
| @NotNull |
| public Set<GraphEdge> getEdgesInRow(int rowIndex) { |
| GraphEdges neighborU = getNeighborU(rowIndex); |
| while (neighborU.myRow < rowIndex) { |
| neighborU = oneDownStep(neighborU); |
| } |
| |
| GraphEdges neighborD = getNeighborD(rowIndex); |
| while (neighborD.myRow > rowIndex) { |
| neighborD = oneUpStep(neighborD); |
| } |
| |
| Set<GraphEdge> result = neighborU.myEdges; |
| result.addAll(neighborD.myEdges); |
| return result; |
| } |
| |
| public void invalidate() { |
| cacheNU.clear(); |
| cacheND.clear(); |
| } |
| |
| @NotNull |
| private GraphEdges getNeighborU(int rowIndex) { |
| int upNeighborIndex = getUpNeighborIndex(rowIndex); |
| GraphEdges graphEdges = cacheNU.get(upNeighborIndex); |
| if (graphEdges == null) { |
| graphEdges = getUCorrectEdges(upNeighborIndex); |
| cacheNU.put(upNeighborIndex, graphEdges); |
| } |
| return graphEdges.newInstance(); |
| } |
| |
| @NotNull |
| private GraphEdges getNeighborD(int rowIndex) { |
| int downNeighborIndex = getUpNeighborIndex(rowIndex) + BLOCK_SIZE; |
| |
| if (downNeighborIndex >= myGraph.nodesCount()) { |
| return new GraphEdges(myGraph.nodesCount() - 1); |
| } |
| |
| GraphEdges graphEdges = cacheND.get(downNeighborIndex); |
| if (graphEdges == null) { |
| graphEdges = getDCorrectEdges(downNeighborIndex); |
| cacheND.put(downNeighborIndex, graphEdges); |
| } |
| return graphEdges.newInstance(); |
| } |
| |
| private static int getUpNeighborIndex(int rowIndex) { |
| return (rowIndex / BLOCK_SIZE) * BLOCK_SIZE; |
| } |
| |
| @NotNull |
| private GraphEdges getUCorrectEdges(int rowIndex) { |
| int startCalculateIndex = Math.max(rowIndex - WALK_SIZE, 0); |
| GraphEdges graphEdges = new GraphEdges(startCalculateIndex); |
| |
| for (int i = startCalculateIndex; i < rowIndex; i++) { |
| graphEdges = oneDownStep(graphEdges); |
| } |
| return graphEdges; |
| } |
| |
| @NotNull |
| private GraphEdges getDCorrectEdges(int rowIndex) { |
| int endCalculateIndex = Math.min(rowIndex + WALK_SIZE, myGraph.nodesCount() - 1); |
| GraphEdges graphEdges = new GraphEdges(endCalculateIndex); |
| |
| for (int i = endCalculateIndex; i > rowIndex; i--) { |
| graphEdges = oneUpStep(graphEdges); |
| } |
| return graphEdges; |
| } |
| |
| @NotNull |
| private GraphEdges oneDownStep(@NotNull GraphEdges graphEdges) { |
| Set<GraphEdge> edgesInCurrentRow = graphEdges.myEdges; |
| int currentRow = graphEdges.myRow; |
| |
| edgesInCurrentRow.addAll(createDownEdges(currentRow)); |
| edgesInCurrentRow.removeAll(createUpEdges(currentRow + 1)); |
| |
| return new GraphEdges(edgesInCurrentRow, currentRow + 1); |
| } |
| |
| @NotNull |
| private GraphEdges oneUpStep(@NotNull GraphEdges graphEdges) { |
| Set<GraphEdge> edgesInCurrentRow = graphEdges.myEdges; |
| int currentRow = graphEdges.myRow; |
| |
| edgesInCurrentRow.addAll(createUpEdges(currentRow)); |
| edgesInCurrentRow.removeAll(createDownEdges(currentRow - 1)); |
| return new GraphEdges(edgesInCurrentRow, currentRow - 1); |
| } |
| |
| public List<GraphEdge> createUpEdges(int nodeIndex) { |
| List<GraphEdge> result = new SmartList<GraphEdge>(); |
| for (int upNode : myGraph.getUpNodes(nodeIndex)) { |
| GraphEdge.Type type = myGraph.getEdgeType(upNode, nodeIndex); |
| result.add(new GraphEdge(upNode, nodeIndex, type)); |
| } |
| return result; |
| } |
| |
| public List<GraphEdge> createDownEdges(int nodeIndex) { |
| List<GraphEdge> result = new SmartList<GraphEdge>(); |
| for (int downNode : myGraph.getDownNodes(nodeIndex)) { |
| GraphEdge.Type type = myGraph.getEdgeType(nodeIndex, downNode); |
| result.add(new GraphEdge(nodeIndex, downNode, type)); |
| } |
| return result; |
| } |
| |
| private static class GraphEdges { |
| // this must be mutably set |
| @NotNull |
| private final Set<GraphEdge> myEdges; |
| private final int myRow; |
| |
| private GraphEdges(int row) { |
| this(new HashSet<GraphEdge>(), row); |
| } |
| |
| private GraphEdges(@NotNull Set<GraphEdge> edges, int row) { |
| myEdges = edges; |
| myRow = row; |
| } |
| |
| @NotNull |
| GraphEdges newInstance() { |
| return new GraphEdges(new HashSet<GraphEdge>(myEdges), myRow); |
| } |
| } |
| } |