java.lang.Object
org.jgrapht.graph.DirectedAcyclicGraph.VisitedArrayListImpl
- All Implemented Interfaces:
Serializable
,DirectedAcyclicGraph.VisitedStrategy
,DirectedAcyclicGraph.VisitedStrategyFactory
- Enclosing class:
DirectedAcyclicGraph<V,
E>
protected static class DirectedAcyclicGraph.VisitedArrayListImpl
extends Object
implements DirectedAcyclicGraph.VisitedStrategy, DirectedAcyclicGraph.VisitedStrategyFactory
A visited strategy using an
ArrayList
.
This implementation seems to offer the best performance in most cases. It grows the internal ArrayList as needed to be as large as |AR|, so it will be more memory intensive than the HashSet implementation, and unlike the Array implementation, it will hold on to that memory (it expands, but never contracts).
- See Also:
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
clearVisited
(int index) Clear the visited state of the given topological index.boolean
getVisited
(int index) Get if the given topological index has been visited.getVisitedStrategy
(DirectedAcyclicGraph.Region affectedRegion) Create a new instance ofDirectedAcyclicGraph.VisitedStrategy
.void
setVisited
(int index) Mark the given topological index as visited.private int
translateIndex
(int index) We translate the topological index to an ArrayList index.
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
visited
-
affectedRegion
-
-
Constructor Details
-
VisitedArrayListImpl
public VisitedArrayListImpl()Constructor
-
-
Method Details
-
getVisitedStrategy
public DirectedAcyclicGraph.VisitedStrategy getVisitedStrategy(DirectedAcyclicGraph.Region affectedRegion) Description copied from interface:DirectedAcyclicGraph.VisitedStrategyFactory
Create a new instance ofDirectedAcyclicGraph.VisitedStrategy
.- Specified by:
getVisitedStrategy
in interfaceDirectedAcyclicGraph.VisitedStrategyFactory
- Parameters:
affectedRegion
- the affected region- Returns:
- a new instance of
DirectedAcyclicGraph.VisitedStrategy
for the affected region
-
setVisited
public void setVisited(int index) Description copied from interface:DirectedAcyclicGraph.VisitedStrategy
Mark the given topological index as visited.- Specified by:
setVisited
in interfaceDirectedAcyclicGraph.VisitedStrategy
- Parameters:
index
- the topological index
-
getVisited
public boolean getVisited(int index) Description copied from interface:DirectedAcyclicGraph.VisitedStrategy
Get if the given topological index has been visited.- Specified by:
getVisited
in interfaceDirectedAcyclicGraph.VisitedStrategy
- Parameters:
index
- the topological index- Returns:
- true if the given topological index has been visited, false otherwise
-
clearVisited
Description copied from interface:DirectedAcyclicGraph.VisitedStrategy
Clear the visited state of the given topological index.- Specified by:
clearVisited
in interfaceDirectedAcyclicGraph.VisitedStrategy
- Parameters:
index
- the index- Throws:
UnsupportedOperationException
- if the implementation doesn't support (or doesn't need) clearance. For example, if the factory creates a new instance every time, it is a waste of cycles to reset 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
-