2 * Copyright (C) 2007 Robin Rosenberg
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License, version 2, as published by the Free Software Foundation.
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this library; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
17 package org
.spearce
.jgit
.lib
;
19 import java
.lang
.reflect
.Array
;
20 import java
.util
.AbstractList
;
21 import java
.util
.ArrayList
;
22 import java
.util
.Collection
;
23 import java
.util
.Collections
;
24 import java
.util
.Comparator
;
25 import java
.util
.HashMap
;
26 import java
.util
.HashSet
;
27 import java
.util
.Iterator
;
28 import java
.util
.List
;
31 import java
.util
.TreeMap
;
32 import java
.util
.TreeSet
;
35 * A topological sorter. Use it by adding elemens and/or edges. Then the nodes
36 * can be retrieved in sequence by either invoking the iterator() or calling
37 * getEntries(). Both are lazy methods that do not wait for the sort to complete
38 * before returning data. The sort is executed incrementally.
40 * This object is not reusable and nodes cannot be added after sorting has
43 * The methods size() and filter() can be overridden to include only a subset of
44 * the elements in the set.
46 * @author Robin Rosenberg
49 * The node type in the graph
51 public class TopologicalSorter
<T
> {
53 private Comparator
<T
> comparator
;
55 private Set
<T
> allNodes
= new HashSet
<T
>();
57 private Map
<T
, List
<Edge
<T
>>> allEdges
= new TreeMap
<T
, List
<Edge
<T
>>>();
59 private Map
<T
, Integer
> inCount
= new HashMap
<T
, Integer
>();
61 private Collection
<T
> zeroIn
; // init later, when we know which comparator to use
63 private List
<T
> entries
;
65 private Map
<T
, Integer
> internalOrder
= new HashMap
<T
, Integer
>();
67 public List
<Lane
> currentLanes
= new ArrayList
<Lane
>();
71 Map
<T
, Lane
> lane
= new HashMap
<T
, Lane
>();
74 * Construct a topological sorter.
77 * A comparator that orders nodes that have no defined order in
78 * the graph. For those element for which the graph conclusively
79 * defined the order the result has no relevance.
81 public TopologicalSorter(final Comparator
<T
> comparator
) {
82 this.comparator
= comparator
;
86 * Construct a topological sorter. You will need to invoke setComparator to
87 * complete construction.
89 public TopologicalSorter() {
94 * Set the comparator to use. Use this method if the constructor cannot be
100 public void setComparator(final Comparator
<T
> comparator
) {
101 this.comparator
= comparator
;
104 /** Defines a directed edge
109 public static class Edge
<T
> {
115 * Construct an edge from a node to another,
120 public Edge(T from
, T to
) {
126 public String
toString() {
127 return from
+ " -> " + to
;
131 public int hashCode() {
132 return from
.hashCode() | to
.hashCode();
136 * @return the origin of this edge
143 * @return the destination of this edge
149 @SuppressWarnings("unchecked")
151 public boolean equals(Object obj
) {
152 Edge
<T
> o
= (Edge
<T
>) obj
;
153 return from
== o
.from
&& to
== o
.to
154 || from
.equals(((Edge
<T
>) obj
).from
)
155 && to
.equals(((Edge
<T
>) obj
).to
);
160 * Copy a sorter. This must be invoked <em>before</em> iteration starts.
161 * Mostly for testing.
163 * @param o Another sorter whose raw state we will copy
165 public TopologicalSorter(TopologicalSorter
<T
> o
) {
167 throw new IllegalStateException("Cannot clone after iteration starts");
168 comparator
= o
.comparator
;
169 allNodes
.addAll(o
.allNodes
);
170 allEdges
.putAll(o
.allEdges
);
171 inCount
.putAll(o
.inCount
);
175 * Add an edge to the graph
179 public void put(Edge
<T
> edge
) {
180 // System.out.println("put("+edge+")");
181 assert !edge
.from
.equals(edge
.to
);
182 List
<Edge
<T
>> edges
= allEdges
.get(edge
.from
);
183 // optimize for very small arrays, one or two parents are overwhelmingly
184 // the most common ones, the rest can be counted on one or two hands in
185 // most repos. Not even the git repo has more than ~40 merges with more than
188 edges
= Collections
.singletonList(edge
);
189 allEdges
.put(edge
.from
, edges
);
191 if (edges
.contains(edge
)) {
192 System
.out
.println("duplicate edge "+edge
+" added");
193 return; // in case the frontend feeds duplicates we ignore them
195 if (edges
.size() == 1) {
196 List
<Edge
<T
>> old
= edges
;
197 edges
= new ArrayList
<Edge
<T
>>(2);
198 edges
.add(old
.get(0));
201 allEdges
.put(edge
.from
, edges
);
203 allNodes
.add(edge
.from
);
204 allNodes
.add(edge
.to
);
205 Integer n
= inCount
.get(edge
.to
);
207 inCount
.put(edge
.to
, new Integer(1));
209 inCount
.put(edge
.to
, new Integer(n
.intValue() + 1));
214 * @return All edges from the node 'from'. may be null
216 public List
<Edge
<T
>> getEdgeFrom(T from
) {
217 return allEdges
.get(from
);
221 * Add a single node to the graph.
225 public void put(T node
) {
226 // System.out.println("put("+node+")");
230 private void removeallfrom(T from
) {
231 Collection
<Edge
<T
>> fromEdges
= allEdges
.get(from
);
232 if (fromEdges
!= null) {
233 for (Iterator
<Edge
<T
>> i
= fromEdges
.iterator(); i
.hasNext();) {
234 Edge
<T
> e
= i
.next();
235 Lane l
= lane
.get(e
.to
);
237 for (Lane m
: currentLanes
) {
238 if (m
.endsAt
== from
) {
252 Integer c
= inCount
.get(e
.to
);
253 if (c
.intValue() == 1) {
255 inCount
.remove(e
.to
);
257 inCount
.put(e
.to
, new Integer(c
.intValue() - 1));
260 // allEdges.remove(from);
261 int n
= inCount
.size();
263 System
.out
.println("node left:" + n
);
267 public Lane
getLane(T node
) {
268 return lane
.get(node
);
272 Lane ret
= new Lane();
273 currentLanes
.add(ret
);
282 private int number
= -1;
288 public boolean equals(Object obj
) {
289 return number
== ((Lane
) obj
).number
;
293 public int hashCode() {
298 public String
toString() {
299 return "L[" + number
+ "]("+startsAt
+" to "+endsAt
+")";
302 public List
<Lane
> getAllLanes() {
306 public int getNumber() {
312 public TopologicalSorter
<T
> getSorter() {
313 return TopologicalSorter
.this;
318 if (zeroIn
== null) {
319 zeroIn
= new TreeSet
<T
>(comparator
);
320 for (T i
: allNodes
) {
321 if (inCount
.get(i
) == null) {
331 if (zeroIn
.isEmpty()) {
332 if (inCount
.size() > 0)
333 throw new IllegalStateException("Topological sort failed, "
334 + inCount
.size() + " nodes left");
337 Iterator
<T
> i
= zeroIn
.iterator();
339 internalOrder
.put(ret
, new Integer(internalOrder
.size()));
345 private class TopologicalIterator
implements Iterator
<T
> {
349 TopologicalIterator() {
350 nextValue
= nextZero();
353 public boolean hasNext() {
354 return nextValue
!= null;
359 nextValue
= nextZero();
363 public void remove() {
364 throw new IllegalStateException("Cannot remove element from "
365 + getClass().getName());
368 public TopologicalSorter
<T
> getSorter() {
369 return TopologicalSorter
.this;
375 * is the candidate element from the input set
376 * @return true if the element should be included in the final result
378 @SuppressWarnings("unused")
379 protected boolean filter(T element
) {
384 * Compute the number of elements in the filtered output. This number is
385 * typically known before the order of elements is known.
387 * @return number of elements in the result set, after filtering.
390 return allNodes
.size();
394 * Get all sorted nodes as a list. The list is lazy, so nodes at the
395 * beginning may be retrieved before the full sort is completed.
397 * @return The sorted list of nodes
399 public List
<T
> getEntries() {
400 if (entries
== null) {
401 entries
= new AbstractList
<T
>() {
402 private Object
[] elements
= new Object
[TopologicalSorter
.this.size()];
404 private int fillCount
;
406 private Iterator
<T
> filler
= new TopologicalIterator();
408 public boolean add(T o
) {
409 throw new UnsupportedOperationException();
412 public void add(int index
, T element
) {
413 throw new UnsupportedOperationException();
416 public boolean addAll(Collection
<?
extends T
> c
) {
417 throw new UnsupportedOperationException();
420 public boolean addAll(int index
, Collection
<?
extends T
> c
) {
421 throw new UnsupportedOperationException();
424 public void clear() {
425 throw new UnsupportedOperationException();
428 public boolean contains(Object o
) {
429 return super.contains(o
);
432 public boolean containsAll(Collection
<?
> c
) {
433 return super.containsAll(c
);
436 @SuppressWarnings("unchecked")
437 public T
get(int index
) {
439 return (T
) elements
[index
];
442 public Iterator
<T
> iterator() {
443 return super.iterator();
446 public int lastIndexOf(Object o
) {
447 return super.lastIndexOf(o
);
450 public boolean remove(Object o
) {
451 throw new UnsupportedOperationException();
454 public T
remove(int index
) {
455 throw new UnsupportedOperationException();
458 public boolean removeAll(Collection
<?
> c
) {
459 throw new UnsupportedOperationException();
462 public boolean retainAll(Collection
<?
> c
) {
463 throw new UnsupportedOperationException();
466 public T
set(int index
, T element
) {
467 throw new UnsupportedOperationException();
471 return elements
.length
;
474 public Object
[] toArray() {
475 return toArray(new Object
[size()]);
478 @SuppressWarnings("unchecked")
479 public <AT
> AT
[] toArray(AT
[] a
) {
481 if (a
.length
!= size())
482 a
= (AT
[]) Array
.newInstance(a
.getClass()
483 .getComponentType(), size());
484 System
.arraycopy(elements
, 0, a
, 0, a
.length
);
488 private void fill(int tosize
) {
489 while (fillCount
< tosize
) {
490 if (!filler
.hasNext())
491 throw new IllegalStateException("Wrong size or filter");
494 elements
[fillCount
++] = e
;
504 * Get the internal order, before filtering, of this node. Since the algorithm is
505 * incremental a null can be returned to indicate the sorted position is not yet
509 * @return The position of a particular node
511 public Integer
getInternalPosition(T node
) {
512 return internalOrder
.get(node
);