Package org.jgrapht.experimental.dag
Class DirectedAcyclicGraph.VisitedBitSetImpl
- java.lang.Object
-
- org.jgrapht.experimental.dag.DirectedAcyclicGraph.VisitedBitSetImpl
-
- All Implemented Interfaces:
java.io.Serializable
,DirectedAcyclicGraph.Visited
,DirectedAcyclicGraph.VisitedFactory
- Enclosing class:
- DirectedAcyclicGraph<V,E>
public static class DirectedAcyclicGraph.VisitedBitSetImpl extends java.lang.Object implements DirectedAcyclicGraph.Visited, DirectedAcyclicGraph.VisitedFactory
This implementation is close to the performance of VisitedArrayListImpl, with 1/8 the memory usage.- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description private DirectedAcyclicGraph.Region
affectedRegion
private static long
serialVersionUID
private java.util.BitSet
visited
-
Constructor Summary
Constructors Constructor Description VisitedBitSetImpl()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clearVisited(int index)
Clear the visited state of the given topological indexDirectedAcyclicGraph.Visited
getInstance(DirectedAcyclicGraph.Region affectedRegion)
Create a new instance ofDirectedAcyclicGraph.Visited
.boolean
getVisited(int index)
Has the given topological index been visited?void
setVisited(int index)
Mark the given topological index as visitedprivate int
translateIndex(int index)
We translate the topological index to an ArrayList index.
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
visited
private final java.util.BitSet visited
-
affectedRegion
private DirectedAcyclicGraph.Region affectedRegion
-
-
Method Detail
-
getInstance
public DirectedAcyclicGraph.Visited getInstance(DirectedAcyclicGraph.Region affectedRegion)
Description copied from interface:DirectedAcyclicGraph.VisitedFactory
Create a new instance ofDirectedAcyclicGraph.Visited
.- Specified by:
getInstance
in interfaceDirectedAcyclicGraph.VisitedFactory
- Parameters:
affectedRegion
- the affected region- Returns:
- a new instance of
DirectedAcyclicGraph.Visited
for the affected region
-
setVisited
public void setVisited(int index)
Description copied from interface:DirectedAcyclicGraph.Visited
Mark the given topological index as visited- Specified by:
setVisited
in interfaceDirectedAcyclicGraph.Visited
- Parameters:
index
- the topological index
-
getVisited
public boolean getVisited(int index)
Description copied from interface:DirectedAcyclicGraph.Visited
Has the given topological index been visited?- Specified by:
getVisited
in interfaceDirectedAcyclicGraph.Visited
- Parameters:
index
- the topological index- Returns:
- true if the given topological index been visited, false otherwise
-
clearVisited
public void clearVisited(int index) throws java.lang.UnsupportedOperationException
Description copied from interface:DirectedAcyclicGraph.Visited
Clear the visited state of the given topological index- Specified by:
clearVisited
in interfaceDirectedAcyclicGraph.Visited
- Parameters:
index
- the index- Throws:
java.lang.UnsupportedOperationException
- if the implementation doesn't support (or doesn't need) clearance. For example, if the factory vends a new instance every time, it is a waste of cycles to clear the state after the search of the Affected Region is done, so an UnsupportedOperationException *should* be thrown.
-
translateIndex
private int translateIndex(int index)
We translate the topological index to an ArrayList index. We have to do this because topological indices can be negative, and we want to do it because we can make better use of space by only needing an ArrayList of size |AR|.- Returns:
- the ArrayList index
-
-