blob: d6ff4230b4df49c25cda3d03c863d42b48c852ee (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
/*
* 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.visible;
import com.intellij.util.ArrayUtil;
import com.intellij.util.SmartList;
import com.intellij.util.containers.MultiMap;
import org.jetbrains.annotations.NotNull;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class DottedEdges {
@NotNull
public static DottedEdges newInstance(@NotNull MultiMap<Integer, Integer> delegate) {
int[] nodesWithEdges = ArrayUtil.toIntArray(delegate.keySet());
Arrays.sort(nodesWithEdges);
int[] startIndexes = new int[nodesWithEdges.length + 1];
int[] edges = new int[delegate.values().size()];
int start = 0;
for (int i = 0; i < startIndexes.length - 1; i++) {
startIndexes[i] = start;
for (int toNode : delegate.get(nodesWithEdges[i])) {
edges[start] = toNode;
start++;
}
}
startIndexes[startIndexes.length - 1] = start;
return new DottedEdges(nodesWithEdges, startIndexes, edges);
}
@NotNull private final int[] sortedStartNodes; // graph is not oriented => end nodes are there as well
@NotNull private final int[] startEdgesPosition;
@NotNull private final int[] endNodes;
public DottedEdges(@NotNull int[] sortedStartNodes, @NotNull int[] startEdgesPosition, @NotNull int[] endNodes) {
this.sortedStartNodes = sortedStartNodes;
this.startEdgesPosition = startEdgesPosition;
this.endNodes = endNodes;
}
public List<Integer> getAdjacentNodes(int nodeIndex) {
int smallIndex = Arrays.binarySearch(sortedStartNodes, nodeIndex);
if (smallIndex < 0)
return Collections.emptyList();
List<Integer> result = new SmartList<Integer>();
for (int i = startEdgesPosition[smallIndex]; i < startEdgesPosition[smallIndex + 1]; i++)
result.add(endNodes[i]);
return result;
}
}
|
