Index (Docs for JDSL 2.1.1)

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV NEXT

FRAMES NO FRAMES

A B C D E F G H I J K L M N O P Q R S T U V W Z _

A

AbstractArrayIterator - class jdsl.core.ref.AbstractArrayIterator.: A class abstracting the common parts of ArrayPositionIterator and ArrayLocatorIterator.
AbstractArrayIterator(Accessor[]) - Constructor for class jdsl.core.ref.AbstractArrayIterator: Uses the array to store the elements that this iterator traverses.
AbstractArrayIterator(Accessor[], int) - Constructor for class jdsl.core.ref.AbstractArrayIterator: Traverses through the array until the first num elements have been returned.
AbstractComparator - class jdsl.core.ref.AbstractComparator.: An abstract class implementing some methods of the Comparator interface.
AbstractComparator() - Constructor for class jdsl.core.ref.AbstractComparator
AbstractDictionary - class jdsl.core.ref.AbstractDictionary.: An abstraction of the Dictionary implementations that ensures the existence of a method to insert Locators back into the data structure.
AbstractDictionary() - Constructor for class jdsl.core.ref.AbstractDictionary
AbstractGraph - class jdsl.graph.ref.AbstractGraph.: An implementation of many of the methods of InspectableGraph in terms of a few primitives.
AbstractGraph() - Constructor for class jdsl.graph.ref.AbstractGraph
AbstractGraph.OO_to_O_MergerIterator - class jdsl.graph.ref.AbstractGraph.OO_to_O_MergerIterator.
AbstractGraph.OO_to_O_MergerIterator(ObjectIterator, ObjectIterator) - Constructor for class jdsl.graph.ref.AbstractGraph.OO_to_O_MergerIterator: Assumes neither iterator is null
AbstractPositionalContainer - class jdsl.core.ref.AbstractPositionalContainer.: An abstract positional container that others may extend if they do not wish to deal with some of the more mundane aspects of positional containers and/or if they wish to avoid implementing themselves some of the methods of container that aren't terribly pertinent to a PositionalContainer.
AbstractPositionalContainer() - Constructor for class jdsl.core.ref.AbstractPositionalContainer
AbstractTopologicalSort - class jdsl.graph.algo.AbstractTopologicalSort.: This abstract class is the foundation for both types of topological sorts, that is, the standard variety where each vertex is given a unique number, and the level-numbering variety in which numbers attached to vertices are not unique.
AbstractTopologicalSort() - Constructor for class jdsl.graph.algo.AbstractTopologicalSort: Constructor.
Accessor - interface jdsl.core.api.Accessor.: All JDSL core containers provide a way to access their internal structure; Accessor is the interface that embodies this concept.
AnachronismException - exception jdsl.graph.algo.AnachronismException.: This is an exception thrown specifically by the DFS to signify that an internal error has arisen in the computation of start/finish times.
AnachronismException(String) - Constructor for class jdsl.graph.algo.AnachronismException: A constructor that takes a String that (hopefully) contains a relevant message about the circumstances under which this exception was thrown.
AnachronismException(String, Throwable) - Constructor for class jdsl.graph.algo.AnachronismException
AnachronismException(Throwable) - Constructor for class jdsl.graph.algo.AnachronismException
ArrayHeap - class jdsl.core.ref.ArrayHeap.: An array implementation of a heap.
ArrayHeap(Comparator) - Constructor for class jdsl.core.ref.ArrayHeap: Creates a new heap.
ArrayHeap(Comparator, boolean) - Constructor for class jdsl.core.ref.ArrayHeap: Creates a new heap.
ArrayHeap(Comparator, int, boolean) - Constructor for class jdsl.core.ref.ArrayHeap: Creates a new heap.
ArrayLocatorIterator - class jdsl.core.ref.ArrayLocatorIterator.: An array-based locator iterator.
ArrayLocatorIterator(Locator[]) - Constructor for class jdsl.core.ref.ArrayLocatorIterator: Uses the array to store the elements that this iterator traverses.
ArrayLocatorIterator(Locator[], int) - Constructor for class jdsl.core.ref.ArrayLocatorIterator: Traverses through the array, which is not copied, until num elements have been returned.
ArrayMergeSort - class jdsl.core.algo.sorts.ArrayMergeSort.: Performs a merge-sort in O(n log n) time, provided that the atRank(int) method of the Sequence works in O(1) time.
ArrayMergeSort() - Constructor for class jdsl.core.algo.sorts.ArrayMergeSort
ArrayObjectIterator - class jdsl.core.ref.ArrayObjectIterator.: An array-based object iterator.
ArrayObjectIterator(Object[]) - Constructor for class jdsl.core.ref.ArrayObjectIterator: Uses the array to store the elements that this iterator traverses.
ArrayObjectIterator(Object[], int) - Constructor for class jdsl.core.ref.ArrayObjectIterator: Traverses through the array, which is not copied, until num elements have been returned.
ArrayPositionIterator - class jdsl.core.ref.ArrayPositionIterator.: An array-based positional iterator.
ArrayPositionIterator(Position[]) - Constructor for class jdsl.core.ref.ArrayPositionIterator: Uses the array to store the elements that this iterator traverses.
ArrayPositionIterator(Position[], int) - Constructor for class jdsl.core.ref.ArrayPositionIterator: Traverses through the array, which is not copied, until num elements have been returned.
ArrayQuickSort - class jdsl.core.algo.sorts.ArrayQuickSort.: Performs an in-place quicksort in expected O(n log n) time, provided that the atRank(int) method of the Sequence operates in O(1) time.
ArrayQuickSort() - Constructor for class jdsl.core.algo.sorts.ArrayQuickSort
ArraySequence - class jdsl.core.ref.ArraySequence.: A Sequence implemented on top of an array.
ArraySequence() - Constructor for class jdsl.core.ref.ArraySequence: The default constructor for ArraySequence Initial array capacity defaults to 16.
ArraySequence(int) - Constructor for class jdsl.core.ref.ArraySequence: Creates an empty Sequence.
ArraySequence(boolean) - Constructor for class jdsl.core.ref.ArraySequence: Creates an empty Sequence.
ArraySequence(int, boolean) - Constructor for class jdsl.core.ref.ArraySequence: Creates an empty Sequence.
Assertion - class jdsl.core.ref.Assertion.: Deprecated. Starting with Java 2 version 1.4 assertions are part of the language, and thus this class is no longer necessary.
AssertionException - exception jdsl.core.ref.AssertionException.: Deprecated. Starting with Java 2 version 1.4 assertions are part of the language, and thus this class is no longer necessary.
AssertionException() - Constructor for class jdsl.core.ref.AssertionException: Deprecated.
AssertionException(String) - Constructor for class jdsl.core.ref.AssertionException: Deprecated.
AssertionException(String, Throwable) - Constructor for class jdsl.core.ref.AssertionException: Deprecated.
AssertionException(Throwable) - Constructor for class jdsl.core.ref.AssertionException: Deprecated.
aCommonVertex(Edge, Edge) - Method in interface jdsl.graph.api.InspectableGraph
aCommonVertex(Edge, Edge) - Method in class jdsl.graph.ref.AbstractGraph: Built on endVertices(.)
aConnectingEdge(Vertex, Vertex) - Method in interface jdsl.graph.api.InspectableGraph: Gives an arbitrary edge from among those connecting the two specified vertices.
aConnectingEdge(Vertex, Vertex) - Method in class jdsl.graph.ref.AbstractGraph: Built on incidentEdges(.)
aVertex() - Method in interface jdsl.graph.api.InspectableGraph
aVertex() - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
adjacentVertices(Vertex) - Method in interface jdsl.graph.api.InspectableGraph: Lists all vertices adjacent to a particular vertex by any kind of edge, with repeats corresponding to parallel edges.
adjacentVertices(Vertex, int) - Method in interface jdsl.graph.api.InspectableGraph: Lists all vertices adjacent to a particular vertex by all edges of the types specified.
adjacentVertices(Vertex) - Method in class jdsl.graph.ref.AbstractGraph: Built on incidentEdges(.)
adjacentVertices(Vertex, int) - Method in class jdsl.graph.ref.AbstractGraph: Built on incidentEdges(.)
after(Locator) - Method in interface jdsl.core.api.InspectableOrderedDictionary: Returns the Locator that is sequentially after another Locator in this Container.
after(Position) - Method in interface jdsl.core.api.InspectableSequence: The next position in the sequence.
after(Position) - Method in class jdsl.core.ref.ArraySequence: O(1) time.
after(Position) - Method in class jdsl.core.ref.NodeSequence: O(1) time
after(Locator) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- may need to traverse the height of the tree to find the next note that we do not return color-locators in the leaves -- we only return key locators.
allVertices() - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden to consider a subset of the vertices in the graph, although I can't think of any reason to do so.
anEdge() - Method in interface jdsl.graph.api.InspectableGraph
anEdge() - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
anIncidentEdge(Vertex) - Method in interface jdsl.graph.api.InspectableGraph
anIncidentEdge(Vertex, int) - Method in interface jdsl.graph.api.InspectableGraph
anIncidentEdge(Vertex) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
anIncidentEdge(Vertex, int) - Method in class jdsl.graph.ref.IncidenceListGraph: O(degree)
areAdjacent(Vertex, Vertex) - Method in interface jdsl.graph.api.InspectableGraph
areAdjacent(Edge, Edge) - Method in interface jdsl.graph.api.InspectableGraph: Checks whether two edges have at least one common endpoint.
areAdjacent(Vertex, Vertex) - Method in class jdsl.graph.ref.AbstractGraph: Built on incidentEdges(.)
areAdjacent(Edge, Edge) - Method in class jdsl.graph.ref.AbstractGraph: Built on endVertices(.)
areIncident(Vertex, Edge) - Method in interface jdsl.graph.api.InspectableGraph
areIncident(Vertex, Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
arrayToSequence(Object[], Sequence) - Static method in class jdsl.core.util.Converter: Places the contents of an array into a sequence, preserving order.
atRank(int) - Method in interface jdsl.core.api.InspectableSequence: Get the position in the sequence with the specified rank
atRank(int) - Method in class jdsl.core.ref.ArraySequence: O(1) time.
atRank(int) - Method in class jdsl.core.ref.NodeSequence: O(1) time if the positions_ cache is valid (no modifications since cache was generated) O(N) if cache is invalid (must traverse up to half of Sequence)
attachVertex(Vertex, Object, Object) - Method in interface jdsl.graph.api.Graph: Attaches a new vertex, containing an object, to an existing vertex by inserting a new undirected edge.
attachVertex(Vertex, Object, Object) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
attachVertexFrom(Vertex, Object, Object) - Method in interface jdsl.graph.api.Graph: Attaches a new vertex, containing an object, by inserting a new directed edge from an existing vertex.
attachVertexFrom(Vertex, Object, Object) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
attachVertexTo(Vertex, Object, Object) - Method in interface jdsl.graph.api.Graph: Attaches a new vertex, containing an object, by inserting a new directed edge to an existing vertex.
attachVertexTo(Vertex, Object, Object) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
attributes() - Method in interface jdsl.core.api.Decorable: Returns an iterator over all the attributes attached to this decorable.
attributes() - Method in class jdsl.core.ref.HashtableDecorable
attributes() - Method in class jdsl.graph.api.Edge.NONEEdge
attributes() - Method in class jdsl.graph.api.Vertex.NONEVertex

B

BACK_EDGE - Static variable in class jdsl.graph.algo.DFS: Constant signifying that a marked edge is a back edge.
BLACK - Static variable in class jdsl.core.ref.RedBlackTree
BOUNDARY_VIOLATION - Static variable in interface jdsl.core.api.InspectableOrderedDictionary: Object returned from all four methodsof InspectableOrderedDictionary to indicate that the user tried to access before the first element of the dictionary or after the last.
BinaryTree - interface jdsl.core.api.BinaryTree.: A modifiable tree in which each node has either zero or two children.
BoundaryViolationException - exception jdsl.core.api.BoundaryViolationException.: A BoundaryViolationException indicates that a Container's edges were trespassed somehow: off the end, over the top, beyond the bottom, etc.
BoundaryViolationException(String) - Constructor for class jdsl.core.api.BoundaryViolationException
BoundaryViolationException(String, Throwable) - Constructor for class jdsl.core.api.BoundaryViolationException
BoundaryViolationException(Throwable) - Constructor for class jdsl.core.api.BoundaryViolationException
badWeight(Vertex, Edge, int) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden to handle edges that have zero or negative weights.
before(Locator) - Method in interface jdsl.core.api.InspectableOrderedDictionary: Returns the Locator that is sequentially before another Locator in this Container.
before(Position) - Method in interface jdsl.core.api.InspectableSequence: The previous position in the sequence.
before(Position) - Method in class jdsl.core.ref.ArraySequence: O(1) time.
before(Position) - Method in class jdsl.core.ref.NodeSequence: O(1) time
before(Locator) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- may need to traverse the height of the tree to find the next note that we do not return color-locators in the leaves -- we only return key locators.

C

CROSS_EDGE - Static variable in class jdsl.graph.algo.DFS: Constant signifying that a marked edge is a cross edge.
ComparableComparator - class jdsl.core.ref.ComparableComparator.: Implementation of JDSL's Comparator interface in terms of the JDK's Comparable interface.
ComparableComparator() - Constructor for class jdsl.core.ref.ComparableComparator
Comparator - interface jdsl.core.api.Comparator.: Defines a total ordering for a set of objects.
ComparatorExtender - class jdsl.core.ref.ComparatorExtender.: Takes a java.util.Comparator and adapts it to the jdsl.core.api.Comparator.
ComparatorExtender(Comparator) - Constructor for class jdsl.core.ref.ComparatorExtender: Constructs a new comparator which adapts the given java.util.Comparator.
ComparatorReverser - class jdsl.core.ref.ComparatorReverser.: Takes a Comparator and reverses the ordering with respect to which the elements are compared.
ComparatorReverser(Comparator) - Constructor for class jdsl.core.ref.ComparatorReverser
Container - interface jdsl.core.api.Container.: The common interface for all the mutable containers in JDSL.
Converter - class jdsl.core.util.Converter.: Provides for conversion of JDSL data structures to java.util Collections and Java base types and for conversion of java.util Collections to JDSL data structures.
Converter() - Constructor for class jdsl.core.util.Converter
CoreException - exception jdsl.core.api.CoreException.: This is the class from which all exceptions of the core package are descended.
CoreException(String) - Constructor for class jdsl.core.api.CoreException
CoreException(String, Throwable) - Constructor for class jdsl.core.api.CoreException
CoreException(Throwable) - Constructor for class jdsl.core.api.CoreException
capacity() - Method in class jdsl.core.ref.HashtableDecorable: Gets the capacity of this hashtable.
case1(Position, Position) - Method in class jdsl.core.ref.RedBlackTree: Takes O(1) time Implements case 1, the Restructuring case Protected for purposes of allowing snapshots during visualization
case2(Position) - Method in class jdsl.core.ref.RedBlackTree: Takes O(1) time Implements case 2, the Recoloring case Protected for purposes of allowing snapshots during visualization
case3(Position) - Method in class jdsl.core.ref.RedBlackTree: Takes O(1) time Implements case 3, the Adjustment case Protected for purposes of allowing snapshots during visualization
check(boolean) - Static method in class jdsl.core.ref.Assertion: Deprecated. Never use this method to indicate bad user input; this method is for asserting internal correctness of the implementation only.
check(boolean, String) - Static method in class jdsl.core.ref.Assertion: Deprecated. Never use this method to indicate bad user input; this method is for asserting internal correctness of the implementation only.
checkBeforeStart() - Method in class jdsl.core.ref.AbstractArrayIterator
checkDoubleRed(Position) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Check for double reds, then rotate or promote if necessary Protected for purposes of allowing snapshots during visualization
checkPosition(Accessor) - Method in class jdsl.core.ref.NodeBinaryTree: Casts the accessor passed in to the appropriate node class for this container; also checks if it is null.
childAtRank(Position, int) - Method in interface jdsl.core.api.InspectableTree
childAtRank(Position, int) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
childAtRank(Position, int) - Method in class jdsl.core.ref.NodeTree: O(1) time
children(Position) - Method in interface jdsl.core.api.InspectableTree: Returns an iterator over the children of the node in order.
children(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
children(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time if cache exists, O(the number of children of the node) otherwise.
cleanup() - Method in class jdsl.graph.algo.AbstractTopologicalSort: Cleans up all decorations that this algorithm was storing in the provided graph.
cleanup() - Method in class jdsl.graph.algo.DFS: Cleans up all decorations stored in the provided graph.
cleanup() - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Removes the decorations from the vertices.
closestAfter(Object) - Method in interface jdsl.core.api.InspectableOrderedDictionary: Returns the locator with smallest key greater than or equal to the search key.
closestAfter(Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- traverses the height of the tree once.
closestBefore(Object) - Method in interface jdsl.core.api.InspectableOrderedDictionary: Returns the locator with largest key less than or equal to the search key.
closestBefore(Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- traverses the height of the tree once.
colorPromotion(Position, Position) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Do a color promotion and then check if colors are now wrong higher up Protected for purposes of allowing snapshots during visualization
compare(Object, Object) - Method in interface jdsl.core.api.Comparator: A C-style comparison function that returns a negative value if the first object is less than the second, a positive value if the second object is less, and 0 if the two objects are equal.
compare(Object, Object) - Method in class jdsl.core.ref.AbstractComparator
compare(Object, Object) - Method in class jdsl.core.ref.ComparableComparator: Invokes the compareTo method of x1 on x2.
compare(Object, Object) - Method in class jdsl.core.ref.ComparatorExtender: Adapts the comparator method of the underlying comparator.
compare(Object, Object) - Method in class jdsl.core.ref.ComparatorReverser
compare(Object, Object) - Method in class jdsl.core.ref.IntegerComparator
connectingEdges(Vertex, Vertex) - Method in interface jdsl.graph.api.InspectableGraph: Gives all edges connecting two vertices.
connectingEdges(Vertex, Vertex) - Method in class jdsl.graph.ref.AbstractGraph: Built on incidentEdges(.)
container() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time
container() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode
contains(Accessor) - Method in interface jdsl.core.api.InspectableContainer: Checks whether this container contains accessor a
contains(Accessor) - Method in class jdsl.core.ref.ArrayHeap: time complexity = worst-case O(1)
contains(Accessor) - Method in class jdsl.core.ref.ArraySequence: O(1) time.
contains(Accessor) - Method in class jdsl.core.ref.HashtableDictionary: O(1)
contains(Accessor) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
contains(Accessor) - Method in class jdsl.core.ref.NodeSequence: O(1) time
contains(Accessor) - Method in class jdsl.core.ref.NodeTree: O(1) time
contains(Accessor) - Method in class jdsl.core.ref.RedBlackTree: Takes O(1) time
contains(Accessor) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
contract(Position) - Method in interface jdsl.core.api.Tree: Replaces a node with its children in the appropriate order.
contract(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
cut(Position) - Method in interface jdsl.core.api.BinaryTree: Position node and all its children are removed from this binary tree and replaced with a new external node with a null element.
cut(Position) - Method in interface jdsl.core.api.Tree: Cuts this tree above the given node, and replaces this position with an external node with a null element.
cut(Position) - Method in class jdsl.core.ref.NodeBinaryTree: Takes O(S) time, where S is the number of positions in the subtree to cut
cut(Position) - Method in class jdsl.core.ref.NodeTree: O(size of the cut subtree) time
cycleStart_ - Variable in class jdsl.graph.algo.DirectedFindCycleDFS: The Vertex which has been encountered twice on one path, proving that a cycle exists.
cycleStart_ - Variable in class jdsl.graph.algo.FindCycleDFS: The Vertex which has been encountered twice on one path, proving that a cycle exists.

D

DFS - class jdsl.graph.algo.DFS.: algorithmic template may be extended to solve a variety of problems on either directed or undirected graphs.
DFS() - Constructor for class jdsl.graph.algo.DFS
DOUBLEBLACK - Static variable in class jdsl.core.ref.RedBlackTree
Decorable - interface jdsl.core.api.Decorable.: Decorability is the ability to attach extra pieces of information to an object.
Dictionary - interface jdsl.core.api.Dictionary.: A container that accepts (key,element) pairs and allows later lookup of the element associated with a particular key.
DirectedDFS - class jdsl.graph.algo.DirectedDFS.
DirectedDFS() - Constructor for class jdsl.graph.algo.DirectedDFS
DirectedFindCycleDFS - class jdsl.graph.algo.DirectedFindCycleDFS.: This class specializes DFS to determine if the connected component of the start vertex contains a cycle and if so return it.
DirectedFindCycleDFS() - Constructor for class jdsl.graph.algo.DirectedFindCycleDFS: Simple constructor initializes instance variables.
defaultInitialCapacity - Static variable in class jdsl.core.ref.ArrayHeap
degree(Vertex) - Method in interface jdsl.graph.api.InspectableGraph: Gives the degree of a vertex, counting both directed and undirected edges.
degree(Vertex, int) - Method in interface jdsl.graph.api.InspectableGraph: Gives the degree of a vertex, counting all edges of the specified type.
degree(Vertex) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
degree(Vertex, int) - Method in class jdsl.graph.ref.IncidenceListGraph: O(degree)
destination(Vertex, Edge) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to supply the destination of an edge, although I can't think of any reason to do so.
destination(Vertex, Edge) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden to supply the destination of an edge, although I can't think of any reason to do so.
destination(Edge) - Method in interface jdsl.graph.api.InspectableGraph
destination(Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
destroy(Object) - Method in interface jdsl.core.api.Decorable: Removes the (attribute, value) entry associated with a certain attribute, attr, from the decorable object.
destroy(Object) - Method in class jdsl.core.ref.HashtableDecorable: Destroys a decoration.
destroy(Object) - Method in class jdsl.graph.api.Edge.NONEEdge
destroy(Object) - Method in class jdsl.graph.api.Vertex.NONEVertex
dfsVisit(Vertex) - Method in class jdsl.graph.algo.DFS: Performs a recursive depth-first search starting at v
dictionaryToMap(InspectableDictionary, Map) - Static method in class jdsl.core.util.Converter: Places the contents of a dictionary into a map.
dictionaryToSortedMap(InspectableDictionary, SortedMap) - Static method in class jdsl.core.util.Converter: Places the contents of a dictionary into a sorted map.
directedEdges() - Method in interface jdsl.graph.api.InspectableGraph
directedEdges() - Method in class jdsl.graph.ref.AbstractGraph: Built on edges() and isDirected(.)
distance(Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Returns the distance of a vertex from the source.
doOneIteration() - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be called manually to single-step the algorithm, but you must call init(.) before the first call to this method.
doOneIteration() - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be called manually to single-step the algorithm, but you must call init(.) before the first call to this method.
done_ - Variable in class jdsl.graph.algo.DirectedFindCycleDFS: This is set to true if a cycle is found, alerting the DFS to finish early
done_ - Variable in class jdsl.graph.algo.FindCycleDFS: This is set to true if a cycle is found, alerting the DFS to finish early

E

EDGE_TYPE - Static variable in class jdsl.graph.algo.DFS: Constant used as key to look up an edge's type.
Edge - interface jdsl.graph.api.Edge.: Empty, typing interface for Positions that are edges.
Edge.NONEEdge - class jdsl.graph.api.Edge.NONEEdge.: A dummy class, used to implement the constant Edge.NONE
.
EdgeDirection - interface jdsl.graph.api.EdgeDirection.: Interface containing constants for specifying which edges are desired in graph-query methods.
EdgeIterator - interface jdsl.graph.api.EdgeIterator.: Iterator over a set of edges.
EdgeIteratorAdapter - class jdsl.graph.ref.EdgeIteratorAdapter.: Takes an ObjectIterator known to be iterating over things that are edges, and makes it appear as an EdgeIterator.
EdgeIteratorAdapter(ObjectIterator) - Constructor for class jdsl.graph.ref.EdgeIteratorAdapter
EmptyContainerException - exception jdsl.core.api.EmptyContainerException.: An EmptyContainerException indicates that the Container can't fulfill the requested operation because it is empty.
EmptyContainerException(String) - Constructor for class jdsl.core.api.EmptyContainerException
EmptyContainerException(String, Throwable) - Constructor for class jdsl.core.api.EmptyContainerException
EmptyContainerException(Throwable) - Constructor for class jdsl.core.api.EmptyContainerException
EqualityComparator - interface jdsl.core.api.EqualityComparator.: This interface defines an equality comparison on a set of objects.
EulerTour - class jdsl.core.algo.traversals.EulerTour.: The EulerTour algorithm is a tree traversal that can be informally described as a walk around tree T, where we start by going from the root towards its left child, viewing the edges of T as being "walls" that we always keep to our left.
EulerTour() - Constructor for class jdsl.core.algo.traversals.EulerTour: The constructor for the algorithm.
edge() - Method in interface jdsl.graph.api.EdgeIterator
edge() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
edgeRelaxed(Vertex, int, Edge, int, Vertex, int) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden in any application where the edges considered for the shortest-path tree matter.
edge_in_rt_style - Static variable in class jdsl.graph.ref.ToString
edges() - Method in interface jdsl.graph.api.InspectableGraph
edges() - Method in class jdsl.graph.ref.IncidenceListGraph: O(E)
element() - Method in interface jdsl.core.api.Accessor: Gets the element currently associated with this accessor.
element() - Method in class jdsl.core.api.InspectableDictionary.InvalidLocator
element() - Method in interface jdsl.core.api.LocatorIterator: Shortcut for locator().element().
element() - Method in interface jdsl.core.api.PositionIterator: Shortcut for position().element().
element() - Method in class jdsl.core.ref.AbstractArrayIterator
element() - Method in class jdsl.core.ref.InOrderIterator: Takes O(1) time
element() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time
element() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
element() - Method in class jdsl.core.ref.NodeSequence.FNSNode
element() - Method in class jdsl.core.ref.PostOrderIterator: Takes O(1) time
element() - Method in class jdsl.core.ref.PreOrderIterator: Takes O(1) time
element() - Method in class jdsl.graph.api.Edge.NONEEdge
element() - Method in class jdsl.graph.api.Vertex.NONEVertex
element() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
element() - Method in class jdsl.graph.ref.VertexIteratorAdapter
elements() - Method in interface jdsl.core.api.InspectableContainer: Returns an iterator over all the elements stored in this container.
elements() - Method in class jdsl.core.ref.ArrayHeap: Cached for constant factor efficiency.
elements() - Method in class jdsl.core.ref.ArraySequence: O(1) time if the cache already exists.
elements() - Method in class jdsl.core.ref.HashtableDictionary: O(1) if structure *AND* elements haven't changed, O(N) otherwise.
elements() - Method in class jdsl.core.ref.NodeBinaryTree: Takes O(N) time from the need to iterate through the tree during snapshot, where N is the number of elements in the tree
elements() - Method in class jdsl.core.ref.NodeSequence: O(1) time if the cache already exists Otherwise O(N) to construct it
elements() - Method in class jdsl.core.ref.NodeTree: O(1) time if cache already exists, O(size of the tree) otherwise
elements() - Method in class jdsl.core.ref.RedBlackTree: Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful
elements() - Method in class jdsl.graph.ref.IncidenceListGraph: O(V+E)
endVertices(Edge) - Method in interface jdsl.graph.api.InspectableGraph
endVertices(Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
execute(InspectableTree) - Method in class jdsl.core.algo.traversals.EulerTour: This method should be called after construction.
execute(InspectableGraph) - Method in class jdsl.graph.algo.AbstractTopologicalSort: The client calls this method to execute the algorithm.
execute(InspectableGraph, Vertex) - Method in class jdsl.graph.algo.DFS: Runs the depth first search algorithm on a graph.
execute(InspectableGraph) - Method in class jdsl.graph.algo.DFS: Execute a DFS without specifying an initial source vertex.
execute(InspectableGraph, Vertex) - Method in class jdsl.graph.algo.DirectedFindCycleDFS
execute(InspectableGraph, Vertex) - Method in class jdsl.graph.algo.FindCycleDFS
execute(InspectableGraph, Vertex, Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraPathfinder
execute(InspectableGraph, Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: The easiest way to use the algorithm is to use this method.
executeAll(InspectableGraph, Vertex, int) - Method in class jdsl.graph.algo.IntegerPrimTemplate: The easiest way to use the algorithm is to use this method.
executeAll(InspectableGraph, Vertex) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Just like the other version of executeAll(.), but with infinity=Integer.MAX_VALUE
expand(Position, Position, Object) - Method in interface jdsl.core.api.Tree: Replaces a set of consecutive children with a new node having those children as its children in the appropriate order.
expand() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Expands this node into an internal node Asserts if this node is external
expand() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
expand(Position, Position, Object) - Method in class jdsl.core.ref.NodeTree: O(number of children of a new node) time
expandExternal(Position) - Method in interface jdsl.core.api.BinaryTree: The external position specified is transformed into an internal, and it gains two external children.
expandExternal(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time

F

FINISH_TIME - Static variable in class jdsl.graph.algo.DFS: Constant used as key to look up the finish time of a vertex.
FORWARD_EDGE - Static variable in class jdsl.graph.algo.DFS: Constant signifying that a marked edge is a forward edge.
FindCycleDFS - class jdsl.graph.algo.FindCycleDFS.: This class specializes DFS to determine if the connected component of the start vertex contains a cycle and if so return it.
FindCycleDFS() - Constructor for class jdsl.graph.algo.FindCycleDFS: Simple constructor initializes instance variables.
FullContainerException - exception jdsl.core.ref.FullContainerException.: A FullContainerException indicates that the Container can't fulfill the requested operation because it is full.
FullContainerException(String) - Constructor for class jdsl.core.ref.FullContainerException
FullContainerException(String, Throwable) - Constructor for class jdsl.core.ref.FullContainerException
FullContainerException(Throwable) - Constructor for class jdsl.core.ref.FullContainerException
find(Object) - Method in interface jdsl.core.api.InspectableDictionary: Finds an object that is mapped to a particular key.
find(Object) - Method in class jdsl.core.ref.HashtableDictionary: O(1) -- expected, O(N) worst case with excessive chaining.
find(Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Takes the time to traverse the tree's height, which is O(logN)
findAll(Object) - Method in interface jdsl.core.api.InspectableDictionary: Finds all elements mapped to a particular key.
findAll(Object) - Method in class jdsl.core.ref.HashtableDictionary: O(#elts with target key), worst case O(N)
findAll(Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN+R) time -- where N = the number of locators in the tree and O(logN) = the height of the tree, and R = the number of instances of key in the tree O(log N) for one element; in theory, for each element, taking its inorder prev or next may take up to O(log N).
finishTime(Vertex) - Method in class jdsl.graph.algo.DFS: Returns the "Finish time" of a Vertex.
finishVisit(Vertex) - Method in class jdsl.graph.algo.DFS: Called when the search has finished with the vertex.
finishVisit(Vertex) - Method in class jdsl.graph.algo.DirectedFindCycleDFS: Once the visit has ended, they are removed from the prospective cyclic path.
finishVisit(Vertex) - Method in class jdsl.graph.algo.FindCycleDFS: Once the visit has ended, they are removed from the prospective cyclic path.
first() - Method in interface jdsl.core.api.InspectableOrderedDictionary: Returns the Locator that is sequentially before any other Locator in this Container.
first() - Method in interface jdsl.core.api.InspectableSequence: The first position of the sequence.
first() - Method in class jdsl.core.ref.ArraySequence: O(1) time.
first() - Method in class jdsl.core.ref.NodeSequence: O(1) time
first() - Method in class jdsl.core.ref.PostOrderIterator: Takes O(1) time Sets the current node to the first node.
first() - Method in class jdsl.core.ref.RedBlackTree: Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree
firstChild(Position) - Method in interface jdsl.core.api.InspectableTree
firstChild(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
firstChild(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time

G

G - Variable in class jdsl.graph.algo.IntegerPrimTemplate
Graph - interface jdsl.graph.api.Graph.: An interface describing a combinatorial graph.
GraphException - exception jdsl.graph.api.GraphException.: jdsl.graph.api package.
GraphException(String) - Constructor for class jdsl.graph.api.GraphException
GraphException(String, Throwable) - Constructor for class jdsl.graph.api.GraphException
GraphException(Throwable) - Constructor for class jdsl.graph.api.GraphException
g_ - Variable in class jdsl.graph.algo.IntegerDijkstraTemplate
get(Object) - Method in interface jdsl.core.api.Decorable: Returns the value in the (attribute, value) entry associated with a certain attribute, attr, in this decorable object.
get(Object) - Method in class jdsl.core.ref.HashtableDecorable: Gets the value of a decoration.
get(Object) - Method in class jdsl.graph.api.Edge.NONEEdge
get(Object) - Method in class jdsl.graph.api.Vertex.NONEVertex
getCycle() - Method in class jdsl.graph.algo.DirectedFindCycleDFS: Returns an ObjectIterator containing all of the Vertices in the found cycle.
getCycle() - Method in class jdsl.graph.algo.FindCycleDFS: Returns an ObjectIterator containing all of the Vertices in the found cycle.
getEdgeToParent(Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to supply a way of storing and retrieving one edge per vertex.
getLocator(Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to supply a way of storing and retrieving one locator per vertex.
getLocator(Vertex) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden to supply a way of storing and retrieving one locator per vertex.
graftOnLeft(Position, Object, BinaryTree) - Method in interface jdsl.core.api.BinaryTree: Position subtreeRoot of this binary tree is demoted one level, with all the positions and elements unchanged, and becomes the right child of a new node storing the given element.
graftOnLeft(Position, Object, BinaryTree) - Method in class jdsl.core.ref.NodeBinaryTree: Takes O(S) time, where S is the number of positions in the new subtree to graft on You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)
graftOnRight(Position, Object, BinaryTree) - Method in interface jdsl.core.api.BinaryTree: Position subtreeRoot of this binary tree is demoted one level, with all the positions and elements unchanged, and becomes the left child of a new node, storing the given element.
graftOnRight(Position, Object, BinaryTree) - Method in class jdsl.core.ref.NodeBinaryTree: Takes O(S) time, where S is the number of positions in the new subtree to graft on You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)
graph_ - Variable in class jdsl.graph.algo.AbstractTopologicalSort: The Graph that the algorithm executes upon.
graph_ - Variable in class jdsl.graph.algo.DFS: The graph being traversed.

H

HashComparator - interface jdsl.core.api.HashComparator.: This interface provides a way of mapping any object in a set to an integer, for purposes of implementing hash tables.
HashtableDecorable - class jdsl.core.ref.HashtableDecorable.: An implementation of Decorable using a hashtable.
HashtableDecorable() - Constructor for class jdsl.core.ref.HashtableDecorable
HashtableDictionary - class jdsl.core.ref.HashtableDictionary.: An implementation of Dictionary using a chaining hashtable.
HashtableDictionary(HashComparator) - Constructor for class jdsl.core.ref.HashtableDictionary: This constructor takes a Comparator which can determine if it can compare a key, and if two keys are equal, nothing more.
HashtableDictionary(HashComparator, int) - Constructor for class jdsl.core.ref.HashtableDictionary: This constructor takes a Comparator which can determine if it can compare a key, and if two keys are equal, nothing more, and an integer denoting the initial capacity.
HeapSort - class jdsl.core.algo.sorts.HeapSort.: Performs a heap-sort in O(n log n) time, provided only that the replaceElement(.) method of the Sequence works in O(1) time (and thus the style of implementation of the Sequence is not relevant).
HeapSort() - Constructor for class jdsl.core.algo.sorts.HeapSort
has(Object) - Method in interface jdsl.core.api.Decorable: Tests whether there is an (attribute, value) entry associated with a certain attribute in this decorable object.
has(Object) - Method in class jdsl.core.ref.HashtableDecorable: Tests if a decoration exists.
has(Object) - Method in class jdsl.graph.api.Edge.NONEEdge
has(Object) - Method in class jdsl.graph.api.Vertex.NONEVertex
hasNext() - Method in interface jdsl.core.api.ObjectIterator
hasNext() - Method in class jdsl.core.ref.AbstractArrayIterator
hasNext() - Method in class jdsl.core.ref.ArrayObjectIterator: Takes O(1) time
hasNext() - Method in class jdsl.core.ref.InOrderIterator: Takes O(1) time
hasNext() - Method in class jdsl.core.ref.PostOrderIterator: Takes O(1) time
hasNext() - Method in class jdsl.core.ref.PreOrderIterator: Takes O(1) time
hasNext() - Method in class jdsl.graph.ref.AbstractGraph.OO_to_O_MergerIterator
hasNext() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
hasNext() - Method in class jdsl.graph.ref.VertexIteratorAdapter
hash(Object) - Method in class jdsl.core.ref.HashtableDecorable: Gets the hashcode for a particular object.
hashValue(Object) - Method in interface jdsl.core.api.HashComparator: Returns the hash code value to be used for the object in this comparator.
hashValue(Object) - Method in class jdsl.core.ref.IntegerHashComparator: defines a mapping f: Integer -> \mathbb{Z} \cap [0, 2^{31} -1]
hashValue(Object) - Method in class jdsl.core.ref.ObjectHashComparator

I

IN - Static variable in interface jdsl.graph.api.EdgeDirection
INFINITY - Variable in class jdsl.graph.algo.IntegerPrimTemplate
InOrderIterator - class jdsl.core.ref.InOrderIterator.: The inorder iterator gives an inorder iteration of a binary tree.
InOrderIterator(InspectableBinaryTree) - Constructor for class jdsl.core.ref.InOrderIterator: Constructs a new InOrderIterator to iterate over the given container Puts a reference to each position into the array -- takes O(N) time where N = the number of positions in the container (given assumptions discussed in header)
IncidenceListGraph - class jdsl.graph.ref.IncidenceListGraph.: An implementation of the Graph interface, including self-loops, parallel edges, and mixed directed and undirected edges.
IncidenceListGraph() - Constructor for class jdsl.graph.ref.IncidenceListGraph: Creates a new IncidenceListGraph with default parameters.
InspectableBinaryTree - interface jdsl.core.api.InspectableBinaryTree.: Please refer to the documentation of the BinaryTree interface.
InspectableContainer - interface jdsl.core.api.InspectableContainer.: A "read only" interface to a container; please see Container for more details.
InspectableDictionary - interface jdsl.core.api.InspectableDictionary.: A read-only lookup structure; please refer to the documentation of Dictionary for more details.
InspectableDictionary.InvalidLocator - class jdsl.core.api.InspectableDictionary.InvalidLocator.: A locator that is always invalid.
InspectableDictionary.InvalidLocator(String) - Constructor for class jdsl.core.api.InspectableDictionary.InvalidLocator
InspectableDictionary.InvalidLocator() - Constructor for class jdsl.core.api.InspectableDictionary.InvalidLocator
InspectableGraph - interface jdsl.graph.api.InspectableGraph.: An interface describing the accessor methods of a combinatorial graph.
InspectableKeyBasedContainer - interface jdsl.core.api.InspectableKeyBasedContainer.: Please refer to the documentation of KeyBasedContainer.
InspectableOrderedDictionary - interface jdsl.core.api.InspectableOrderedDictionary.: A read-only lookup structure in which an ordering of the keys is maintained; please refer to the documentation of OrderedDictionary for more details.
InspectablePositionalContainer - interface jdsl.core.api.InspectablePositionalContainer.: Please refer to the documentation of PositionalContainer.
InspectableSequence - interface jdsl.core.api.InspectableSequence.: Please refer to the documentation of Sequence.
InspectableTree - interface jdsl.core.api.InspectableTree.: Please refer to the documentation of Tree
IntegerComparator - class jdsl.core.ref.IntegerComparator.: Compares java.lang.Integers.
IntegerComparator() - Constructor for class jdsl.core.ref.IntegerComparator
IntegerDijkstraPathfinder - class jdsl.graph.algo.IntegerDijkstraPathfinder.: using Dijkstra's algorithm.
IntegerDijkstraPathfinder() - Constructor for class jdsl.graph.algo.IntegerDijkstraPathfinder
IntegerDijkstraTemplate - class jdsl.graph.algo.IntegerDijkstraTemplate.: Implementation of Dijkstra's algorithm using the template-method pattern: the core functionality is coded in a few final methods that call overridable methods to do some of the work.
IntegerDijkstraTemplate() - Constructor for class jdsl.graph.algo.IntegerDijkstraTemplate
IntegerHashComparator - class jdsl.core.ref.IntegerHashComparator.: An implementation of a HashComparator for java.lang.Integers
IntegerHashComparator() - Constructor for class jdsl.core.ref.IntegerHashComparator
IntegerPrimTemplate - class jdsl.graph.algo.IntegerPrimTemplate.: Implementation of the algorithm of Prim and Jarnik for finding a minimum spanning tree, using the template-method pattern: the core functionality is coded in a few final methods that call overridable methods to do some of the work.
IntegerPrimTemplate() - Constructor for class jdsl.graph.algo.IntegerPrimTemplate
InvalidAccessorException - exception jdsl.core.api.InvalidAccessorException.: Used when an accessor (position or locator) is invalid, either internally invalid or invalid with respect to a particular container.
InvalidAccessorException(String) - Constructor for class jdsl.core.api.InvalidAccessorException
InvalidAccessorException(String, Throwable) - Constructor for class jdsl.core.api.InvalidAccessorException
InvalidAccessorException(Throwable) - Constructor for class jdsl.core.api.InvalidAccessorException
InvalidAttributeException - exception jdsl.core.api.InvalidAttributeException.: Used when the key for an attribute lookup is not supported by the implementation's lookup mechanism.
InvalidAttributeException(String) - Constructor for class jdsl.core.api.InvalidAttributeException
InvalidAttributeException(String, Throwable) - Constructor for class jdsl.core.api.InvalidAttributeException
InvalidAttributeException(Throwable) - Constructor for class jdsl.core.api.InvalidAttributeException
InvalidContainerException - exception jdsl.core.api.InvalidContainerException.: Used to indicate that a container passed to a function is of the wrong type or otherwise invalid for that function call.
InvalidContainerException(String) - Constructor for class jdsl.core.api.InvalidContainerException
InvalidContainerException(String, Throwable) - Constructor for class jdsl.core.api.InvalidContainerException
InvalidContainerException(Throwable) - Constructor for class jdsl.core.api.InvalidContainerException
InvalidEdgeException - exception jdsl.graph.api.InvalidEdgeException.: An object of this class gets thrown when topological information related to Edges is somehow incorrect.
InvalidEdgeException(String) - Constructor for class jdsl.graph.api.InvalidEdgeException
InvalidEdgeException(String, Throwable) - Constructor for class jdsl.graph.api.InvalidEdgeException
InvalidEdgeException(Throwable) - Constructor for class jdsl.graph.api.InvalidEdgeException
InvalidKeyException - exception jdsl.core.api.InvalidKeyException.: Used when a key passed to a key-based container is not supported by the implementation's lookup mechanism.
InvalidKeyException(String) - Constructor for class jdsl.core.api.InvalidKeyException
InvalidKeyException(String, Throwable) - Constructor for class jdsl.core.api.InvalidKeyException
InvalidKeyException(Throwable) - Constructor for class jdsl.core.api.InvalidKeyException
InvalidMethodCallException - exception jdsl.core.api.InvalidMethodCallException.: InvalidMethodCallException is intended for use only in methods that you expect never to be called -- for instance, in the prev() method of the head node in a sequence.
InvalidMethodCallException(String) - Constructor for class jdsl.core.api.InvalidMethodCallException
InvalidMethodCallException(String, Throwable) - Constructor for class jdsl.core.api.InvalidMethodCallException
InvalidMethodCallException(Throwable) - Constructor for class jdsl.core.api.InvalidMethodCallException
InvalidQueryException - exception jdsl.graph.algo.InvalidQueryException.: This exception is currently used only by the two subclasses of AbstractTopologicalSort.
InvalidQueryException(String) - Constructor for class jdsl.graph.algo.InvalidQueryException
InvalidQueryException(String, Throwable) - Constructor for class jdsl.graph.algo.InvalidQueryException
InvalidQueryException(Throwable) - Constructor for class jdsl.graph.algo.InvalidQueryException
InvalidVertexException - exception jdsl.graph.api.InvalidVertexException.: An object of this class gets thrown when topological information related to vertices is incorrect.
InvalidVertexException(String) - Constructor for class jdsl.graph.api.InvalidVertexException
InvalidVertexException(String, Throwable) - Constructor for class jdsl.graph.api.InvalidVertexException
InvalidVertexException(Throwable) - Constructor for class jdsl.graph.api.InvalidVertexException
iCurrentIndex_ - Variable in class jdsl.core.ref.AbstractArrayIterator
iCurrentIndex_ - Variable in class jdsl.core.ref.ArrayObjectIterator
iLastIndex_ - Variable in class jdsl.core.ref.AbstractArrayIterator
iLastIndex_ - Variable in class jdsl.core.ref.ArrayObjectIterator
incidentEdges(Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden in any application where the default choice of edges to consider at any vertex is not satisfactory.
incidentEdges(Vertex) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden in any application where the default choice of edges to consider at any vertex is not satisfactory.
incidentEdges(Vertex) - Method in interface jdsl.graph.api.InspectableGraph
incidentEdges(Vertex, int) - Method in interface jdsl.graph.api.InspectableGraph
incidentEdges(Vertex) - Method in class jdsl.graph.ref.IncidenceListGraph: O(degree)
incidentEdges(Vertex, int) - Method in class jdsl.graph.ref.IncidenceListGraph: O(degree)
init() - Method in class jdsl.core.algo.traversals.EulerTour: Called in execute(.), before algorithm is executed.
init(InspectableGraph) - Method in class jdsl.graph.algo.AbstractTopologicalSort: This helper method is called by the execute(.) method.
init(InspectableGraph, Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Called automatically by executeAll(); must be called by the client prior to the first call to doOneIteration() if finer-grained control of the algorithm is needed.
init(InspectableGraph, Vertex, int) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Called automatically by executeAll(); must be called by the client prior to the first call to doOneIteration() if finer-grained control of the algorithm is needed.
initMap() - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to initialize a locator-lookup data structure of your choosing, but the default implementation, which decorates each vertex with its locator, is probably sufficient for most purposes.
initMap() - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden to initialize a locator-lookup data structure of your choosing, but the default implementation, which uses a java.util.Hashtable, is probably sufficient for most purposes.
insert(Object, Object) - Method in interface jdsl.core.api.KeyBasedContainer: Inserts a (key,element) pair into this container.
insert(Object, Object) - Method in class jdsl.core.ref.ArrayHeap: If the array is full, its capacity is doubled before the insertion by copying the elements into a new array.
insert(Object, Object) - Method in class jdsl.core.ref.HashtableDictionary: O(1) expected, O(N) if insertion pushes the size above the rehashing threshhold.
insert(Object, Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case insertion would restructure once each step up the tree.
insertAfter(Position, Object) - Method in interface jdsl.core.api.Sequence: Inserts an object after a position in the sequence.
insertAfter(Position, Object) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
insertAfter(Position, Object) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
insertAfterSibling(Position, Object) - Method in interface jdsl.core.api.Tree: Inserts a new sibling after a given node
insertAfterSibling(Position, Object) - Method in class jdsl.core.ref.NodeTree: O(1) time
insertAtRank(int, Object) - Method in interface jdsl.core.api.Sequence: Inserts based on an integer rank similar to array indices.
insertAtRank(int, Object) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
insertAtRank(int, Object) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
insertBefore(Position, Object) - Method in interface jdsl.core.api.Sequence: Inserts an object before a position in the sequence.
insertBefore(Position, Object) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
insertBefore(Position, Object) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
insertBeforeSibling(Position, Object) - Method in interface jdsl.core.api.Tree: Inserts a new sibling before a given node.
insertBeforeSibling(Position, Object) - Method in class jdsl.core.ref.NodeTree: O(1) time
insertChildAtRank(Position, int, Object) - Method in interface jdsl.core.api.Tree: Inserts a new child of node at the specified rank.
insertChildAtRank(Position, int, Object) - Method in class jdsl.core.ref.NodeTree: O(the number of children of the node) time
insertDirectedEdge(Vertex, Vertex, Object) - Method in interface jdsl.graph.api.Graph: Inserts a new directed edge from an existing vertex to another.
insertDirectedEdge(Vertex, Vertex, Object) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
insertEdge(Vertex, Vertex, Object) - Method in interface jdsl.graph.api.Graph: Inserts a new undirected edge between two existing vertices.
insertEdge(Vertex, Vertex, Object) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
insertFirst(Object) - Method in interface jdsl.core.api.Sequence: Inserts an object as first element of the sequence
insertFirst(Object) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
insertFirst(Object) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
insertFirstChild(Position, Object) - Method in interface jdsl.core.api.Tree: Inserts a new child of node as the first child.
insertFirstChild(Position, Object) - Method in class jdsl.core.ref.NodeTree: O(1) time
insertLast(Object) - Method in interface jdsl.core.api.Sequence: Inserts an object as last element of the sequence.
insertLast(Object) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
insertLast(Object) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
insertLastChild(Position, Object) - Method in interface jdsl.core.api.Tree: Inserts a new child of node as the last child.
insertLastChild(Position, Object) - Method in class jdsl.core.ref.NodeTree: O(1) time
insertVertex(Object) - Method in interface jdsl.graph.api.Graph: Inserts a new isolated vertex.
insertVertex(Object) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
inspectableBinaryTree() - Method in class jdsl.core.ref.ArrayHeap: Creates an InspectableBinaryTree snapshot view of the heap.
inspectableBinaryTree() - Method in class jdsl.core.ref.RedBlackTree: Used for visualization and testers
interestingIncidentEdges(Vertex) - Method in class jdsl.graph.algo.DFS: A method that returns an iterator over those edges incident to the parameter vertex in the graph which should be considered for exploration.
interestingIncidentEdges(Vertex) - Method in class jdsl.graph.algo.DirectedDFS: This implementation of interestingEdges(Vertex) returns all of the directed edges originating at the parameter Vertex.
interestingIncidentEdges(Vertex) - Method in class jdsl.graph.algo.FindCycleDFS: This method tells the DFS which graph edges to check.
isBackEdge(Edge) - Method in class jdsl.graph.algo.DFS: Tests if an edge is a back edge.
isBlack(Position) - Method in class jdsl.core.ref.RedBlackTree: Returns whether or not the given position of the underlying tre is black; for visualization/testing purposes.
isComparable(Object) - Method in interface jdsl.core.api.EqualityComparator: Allows a container (or any client) to find out whether an object is a member of the ordered set over which this comparator is defined.
isComparable(Object) - Method in class jdsl.core.ref.ComparableComparator
isComparable(Object) - Method in class jdsl.core.ref.ComparatorExtender: Tests if an object is comparator by asking the comparator if compare(o,o)
isComparable(Object) - Method in class jdsl.core.ref.ComparatorReverser
isComparable(Object) - Method in class jdsl.core.ref.IntegerComparator
isComparable(Object) - Method in class jdsl.core.ref.IntegerHashComparator: determines if the Comparator can use this Object
isComparable(Object) - Method in class jdsl.core.ref.ObjectHashComparator
isCrossEdge(Edge) - Method in class jdsl.graph.algo.DFS: Tests if an edge is a cross edge.
isCyclic() - Method in class jdsl.graph.algo.AbstractTopologicalSort: Query method for asking whether the Graph is cyclic, (and therefore inappropriate for a topological ordering).
isDirected(Edge) - Method in interface jdsl.graph.api.InspectableGraph
isDirected(Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
isDone() - Method in class jdsl.graph.algo.DFS: Tests if the depth first search is done.
isDone() - Method in class jdsl.graph.algo.DirectedFindCycleDFS: Returns true iff a cycle has been found.
isDone() - Method in class jdsl.graph.algo.FindCycleDFS: Returns true iff a cycle has been found.
isDoubleBlack(Position) - Method in class jdsl.core.ref.RedBlackTree: Returns whether or not the given position of the underlying tre is double-black; for visualization/testing purposes.
isEmpty() - Method in interface jdsl.core.api.InspectableContainer: Checks whether this container holds zero elements.
isEmpty() - Method in class jdsl.core.ref.AbstractPositionalContainer: Checks if this container is empty.
isEmpty() - Method in class jdsl.core.ref.ArrayHeap: time complexity = worst-case O(1)
isEmpty() - Method in class jdsl.core.ref.HashtableDictionary: O(1)
isEmpty() - Method in class jdsl.core.ref.NodeBinaryTree: Overridden from AbstractPositionalContainer to be O(1) time.
isEmpty() - Method in class jdsl.core.ref.NodeTree: O(1) time
isEmpty() - Method in class jdsl.core.ref.RedBlackTree: Takes O(1) time
isEqualTo(Object, Object) - Method in interface jdsl.core.api.EqualityComparator: Tests the two parameter objects in the set over which the comparator is defined for equality.
isEqualTo(Object, Object) - Method in class jdsl.core.ref.AbstractComparator
isEqualTo(Object, Object) - Method in class jdsl.core.ref.IntegerHashComparator: tests equality on two Integers
isEqualTo(Object, Object) - Method in class jdsl.core.ref.ObjectHashComparator: returns x1.equals(x2)
isExternal(Position) - Method in interface jdsl.core.api.InspectableTree: Checks if a position is a leaf of this tree.
isExternal(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
isExternal(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
isFinished(Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Tests whether a vertex has been reached.
isFirst(Position) - Method in interface jdsl.core.api.InspectableSequence: Check if the given position is the first.
isFirst(Position) - Method in class jdsl.core.ref.ArraySequence: O(1) time.
isFirst(Position) - Method in class jdsl.core.ref.NodeSequence: O(1) time
isForwardEdge(Edge) - Method in class jdsl.graph.algo.DFS: Tests if an edge is a forward edge.
isGreaterThan(Object, Object) - Method in interface jdsl.core.api.Comparator: Tests the strict order of two objects in the set over which this comparator is defined.
isGreaterThan(Object, Object) - Method in class jdsl.core.ref.AbstractComparator
isGreaterThanOrEqualTo(Object, Object) - Method in interface jdsl.core.api.Comparator: Tests non-strict order of two objects in the universe over which this comparator is defined.
isGreaterThanOrEqualTo(Object, Object) - Method in class jdsl.core.ref.AbstractComparator
isInternal(Position) - Method in interface jdsl.core.api.InspectableTree: Checks if a position is an internal node of this tree.
isInternal() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time
isInternal() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
isInternal(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
isInternal(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
isLast(Position) - Method in interface jdsl.core.api.InspectableSequence: Check if the given position is the last.
isLast(Position) - Method in class jdsl.core.ref.ArraySequence: O(1) time.
isLast(Position) - Method in class jdsl.core.ref.NodeSequence: O(1) time
isLeftChild() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time
isLessThan(Object, Object) - Method in interface jdsl.core.api.Comparator: Tests the strict order of two objects in the set over which this comparator is defined.
isLessThan(Object, Object) - Method in class jdsl.core.ref.AbstractComparator
isLessThanOrEqualTo(Object, Object) - Method in interface jdsl.core.api.Comparator: Tests non-strict order of two objects in the universe over which this comparator is defined.
isLessThanOrEqualTo(Object, Object) - Method in class jdsl.core.ref.AbstractComparator
isReachable(Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Tests whether a vertex is reachable from the source.
isRed(Position) - Method in class jdsl.core.ref.RedBlackTree: Returns whether or not the given position of the underlying tre is red; for visualization/testing purposes.
isRoot(Position) - Method in interface jdsl.core.api.InspectableTree: Checks if a position is the root of this tree.
isRoot(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
isRoot(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
isSuperNode() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: Used to determine if this node is the super node
isSuperNode() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Used to determine if this node is the super node (overridden)
isTreeEdge(Edge) - Method in class jdsl.graph.algo.DFS: Tests if an edge is a tree edge.
isUnseen(Edge) - Method in class jdsl.graph.algo.DFS: Tests if an edge has been seen yet.
isUnvisited(Vertex) - Method in class jdsl.graph.algo.DFS: Tests if a vertex has not been visited.
isValid() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
isVisited(Vertex) - Method in class jdsl.graph.algo.DFS: Tests if a vertex has been visited.
isVisiting(Vertex) - Method in class jdsl.graph.algo.DFS: Tests if a vertex is being visited.
is_cyclic_ - Variable in class jdsl.graph.algo.AbstractTopologicalSort: Whether the graph has cycles or not.
iteratorToDictionary(Iterator, Dictionary) - Static method in class jdsl.core.util.Converter: Places the contents of a java.util iterator into a dictionary.
iteratorToList(ObjectIterator, List) - Static method in class jdsl.core.util.Converter: Places the contents of a JDSL iterator into a List, preserving order.
iteratorToMap(ObjectIterator, Map) - Static method in class jdsl.core.util.Converter: Places the contents of a JDSL iterator into a Map.
iteratorToPriorityQueue(Iterator, PriorityQueue) - Static method in class jdsl.core.util.Converter: Places the contents of a java.util iterator into a PQ.
iteratorToSequence(Iterator, Sequence) - Static method in class jdsl.core.util.Converter: Places the contents of a java.util iterator into a sequence.
iteratorToSet(ObjectIterator, Set) - Static method in class jdsl.core.util.Converter: Places the contents of a JDSL iterator into a Set.

J

jdsl.core.algo.sorts - package jdsl.core.algo.sorts: Package of sorting algorithms that operate on Sequences (defined in jdsl.core.api).
jdsl.core.algo.traversals - package jdsl.core.algo.traversals: Package of traversal algorithms that operate on jdsl.core.api.InspectableTree objects.
jdsl.core.api - package jdsl.core.api: Package of interfaces and exceptions that compose the API for JDSL's core data structures: sequences, trees, priority queues, and dictionaries (a/k/a maps or associative arrays).
jdsl.core.ref - package jdsl.core.ref: Package of implementations of the interfaces in jdsl.core.api.
jdsl.core.util - package jdsl.core.util: Package that provides convenient conversions between data structure types, including those in java.util.
jdsl.graph.algo - package jdsl.graph.algo: Package of basic graph algorithms, including algorithms for depth-first search, single-source shortest paths (Dijkstra's), topological sort (Knuth), and minimum spanning trees (Prim-Jarnik).
jdsl.graph.api - package jdsl.graph.api: Package of container and accessor interfaces for graphs.
jdsl.graph.ref - package jdsl.graph.ref: Package of implementations of the interfaces in jdsl.graph.api.

K

KeyBasedContainer - interface jdsl.core.api.KeyBasedContainer.: Key-based containers are containers that store (key,element) pairs; each pair is represented by a Locator.
key() - Method in class jdsl.core.api.InspectableDictionary.InvalidLocator
key() - Method in interface jdsl.core.api.Locator
key() - Method in interface jdsl.core.api.LocatorIterator: Shortcut for locator().key()
key() - Method in class jdsl.core.ref.ArrayLocatorIterator
keys() - Method in interface jdsl.core.api.InspectableKeyBasedContainer: Returns an iterator over all the keys stored in this container.
keys() - Method in class jdsl.core.ref.ArrayHeap: Cached for constant factor efficiency.
keys() - Method in class jdsl.core.ref.HashtableDictionary: O(1) if structure hasn't changed, O(N) otherwise.
keys() - Method in class jdsl.core.ref.RedBlackTree: Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful

L

ListMergeSort - class jdsl.core.algo.sorts.ListMergeSort.: Performs a merge-sort in O(n log n) time, provided that isEmpty(), first(), insertLast(), and removeFirst() all operate in O(1) time.
ListMergeSort() - Constructor for class jdsl.core.algo.sorts.ListMergeSort
Locator - interface jdsl.core.api.Locator.: A locator is a coat-check, of sorts, for a (key,element) pair inside a KeyBasedContainer.
LocatorIterator - interface jdsl.core.api.LocatorIterator.: Iterator over a set of locators.
last() - Method in interface jdsl.core.api.InspectableOrderedDictionary: Returns the Locator that is sequentially after any other Locator in this Container.
last() - Method in interface jdsl.core.api.InspectableSequence: The last position of the sequence.
last() - Method in class jdsl.core.ref.ArraySequence: O(1) time.
last() - Method in class jdsl.core.ref.NodeSequence: O(1) time
last() - Method in class jdsl.core.ref.RedBlackTree: Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree
lastChild(Position) - Method in interface jdsl.core.api.InspectableTree
lastChild(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
lastChild(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
left() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time
left() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
leftChild(Position) - Method in interface jdsl.core.api.InspectableBinaryTree: Provides the left child of a given node.
leftChild(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
link(Position, BinaryTree) - Method in interface jdsl.core.api.BinaryTree: Links binary tree newSubtree at external node node by replacing node with the root of newSubtree.
link(Position, Tree) - Method in interface jdsl.core.api.Tree: Links tree t at external node extNode by replacing ExtNode with the root of t.
link(Position, BinaryTree) - Method in class jdsl.core.ref.NodeBinaryTree: Takes O(S) time, where S is the number of positions in this subtree You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)
link(Position, Tree) - Method in class jdsl.core.ref.NodeTree: O(size of the new subtree to be linked in) time
listToSequence(List, Sequence) - Static method in class jdsl.core.util.Converter: Places the contents of a list into a sequence, preserving order.
locArray_ - Variable in class jdsl.core.ref.ArrayLocatorIterator
loc_to_collections_style_s - Static variable in class jdsl.core.ref.ToString
locator() - Method in interface jdsl.core.api.LocatorIterator
locator() - Method in class jdsl.core.ref.ArrayLocatorIterator
locators() - Method in interface jdsl.core.api.InspectableKeyBasedContainer: Allows access to all the locators stored by this container.
locators() - Method in class jdsl.core.ref.ArrayHeap: Cached for constant factor efficiency.
locators() - Method in class jdsl.core.ref.HashtableDictionary: O(1) if structure hasn't changed, O(N) otherwise.
locators() - Method in class jdsl.core.ref.RedBlackTree: Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful
locators - Variable in class jdsl.graph.algo.IntegerPrimTemplate

M

ModifiableGraph - interface jdsl.graph.api.ModifiableGraph.: An interface describing the modifier methods of a combinatorial graph that can safely be inherited by more restricted graphs.
makeUncontained() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Makes this node uncontained
makeUncontained() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
makeUndirected(Edge) - Method in interface jdsl.graph.api.ModifiableGraph: Makes a directed edge undirected.
makeUndirected(Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
mapToDictionary(Map, Dictionary) - Static method in class jdsl.core.util.Converter: Places the contents of a map into a dictionary.
min() - Method in interface jdsl.core.api.PriorityQueue: Allows access to element with highest priority without removing it from the priority queue.
min() - Method in class jdsl.core.ref.ArrayHeap: time complexity = worst-case O(1)

N

NONE - Static variable in interface jdsl.graph.api.Edge: Used when a function requires an edge to be specified but there is no edge to specify, or when a function needs to return an edge but there is no edge to return.
NONE - Static variable in interface jdsl.graph.api.Vertex: Used when a function needs to return a vertex but there is no vertex to return.
NO_SUCH_KEY - Static variable in interface jdsl.core.api.InspectableDictionary: This Locator is returned when a method that should return a locator with a given key can find no such key within the data structure
NUMBER_KEY_ - Variable in class jdsl.graph.algo.AbstractTopologicalSort: This Object is the key for the numbering Decoration.
NoSuchEdgeException - exception jdsl.graph.api.NoSuchEdgeException.: An object of this class gets thrown when an Edge object with certain properties does not exist in the graph.
NoSuchEdgeException(String) - Constructor for class jdsl.graph.api.NoSuchEdgeException
NoSuchEdgeException(String, Throwable) - Constructor for class jdsl.graph.api.NoSuchEdgeException
NoSuchEdgeException(Throwable) - Constructor for class jdsl.graph.api.NoSuchEdgeException
NoSuchVertexException - exception jdsl.graph.api.NoSuchVertexException.: An object of this class gets thrown when a Vertex object with certain properties does not exist in the graph.
NoSuchVertexException(String) - Constructor for class jdsl.graph.api.NoSuchVertexException
NoSuchVertexException(String, Throwable) - Constructor for class jdsl.graph.api.NoSuchVertexException
NoSuchVertexException(Throwable) - Constructor for class jdsl.graph.api.NoSuchVertexException
NodeBinaryTree - class jdsl.core.ref.NodeBinaryTree.: A node-based Binary Tree.
NodeBinaryTree() - Constructor for class jdsl.core.ref.NodeBinaryTree: Create a tree.
NodeBinaryTree(NodeBinaryTree.NBTNode) - Constructor for class jdsl.core.ref.NodeBinaryTree: Create a tree from a set of nodes.
NodeBinaryTree.NBTNode - class jdsl.core.ref.NodeBinaryTree.NBTNode.: This is the class for all user-visible nodes It contains links for its parent, children, and element.
NodeBinaryTree.NBTNode(NodeBinaryTree.NBTNode, Object) - Constructor for class jdsl.core.ref.NodeBinaryTree.NBTNode: make a new external node
NodeBinaryTree.NBTSuperNode - class jdsl.core.ref.NodeBinaryTree.NBTSuperNode.: This is the supernode.
NodeBinaryTree.NBTSuperNode(NodeBinaryTree, NodeBinaryTree.NBTNode) - Constructor for class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Constructs the super node with its tree and root
NodeSequence - class jdsl.core.ref.NodeSequence.: A Sequence based on a doubly-linked-list implementation.
NodeSequence() - Constructor for class jdsl.core.ref.NodeSequence: The default constructor for NodeSequence, as well as the only one.
NodeSequence.FNSNode - class jdsl.core.ref.NodeSequence.FNSNode.: This nested class is the node for NodeSequence.
NodeSequence.FNSNode(Object) - Constructor for class jdsl.core.ref.NodeSequence.FNSNode: Default constructor for the Node.
NodeTree - class jdsl.core.ref.NodeTree.: A node-based Tree.
NodeTree() - Constructor for class jdsl.core.ref.NodeTree: The default constructor for NodeTree, which creates a tree with one node whose element is null.
NonEmptyContainerException - exception jdsl.core.api.NonEmptyContainerException.: A NonEmptyContainerException indicates that the Container can't fulfill the requested operation because it is not empty.
NonEmptyContainerException(String) - Constructor for class jdsl.core.api.NonEmptyContainerException
NonEmptyContainerException(String, Throwable) - Constructor for class jdsl.core.api.NonEmptyContainerException
NonEmptyContainerException(Throwable) - Constructor for class jdsl.core.api.NonEmptyContainerException
newContainer() - Method in interface jdsl.core.api.Container: Creates a new, empty container of the same class as this one (and therefore of the same interface as this one).
newContainer() - Method in class jdsl.core.ref.ArrayHeap: time complexity = worst-case O(1)
newContainer() - Method in class jdsl.core.ref.ArraySequence: Returns an empty ArraySequence.
newContainer() - Method in class jdsl.core.ref.HashtableDictionary: O(1)
newContainer() - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
newContainer() - Method in class jdsl.core.ref.NodeSequence
newContainer() - Method in class jdsl.core.ref.NodeTree: O(1) time
newContainer() - Method in class jdsl.core.ref.RedBlackTree: Takes O(1) time
newContainer() - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
newPQ() - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to supply a priority queue of your choosing, but the default implementation, which gives an empty jdsl.core.ref.ArrayHeap, is probably sufficient for most purposes.
newPQ() - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden to supply a priority queue of your choosing, but the default implementation, which gives an empty jdsl.core.ref.ArrayHeap, is probably sufficient for most purposes.
nextAccessor() - Method in class jdsl.core.ref.AbstractArrayIterator
nextEdge() - Method in interface jdsl.graph.api.EdgeIterator
nextEdge() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
nextLocator() - Method in interface jdsl.core.api.LocatorIterator
nextLocator() - Method in class jdsl.core.ref.ArrayLocatorIterator
nextObject() - Method in interface jdsl.core.api.ObjectIterator
nextObject() - Method in class jdsl.core.ref.AbstractArrayIterator: Takes O(1) time
nextObject() - Method in class jdsl.core.ref.ArrayObjectIterator: Takes O(1) time
nextObject() - Method in class jdsl.core.ref.InOrderIterator: Takes O(1) time
nextObject() - Method in class jdsl.core.ref.PostOrderIterator: Takes O(1) time
nextObject() - Method in class jdsl.core.ref.PreOrderIterator
nextObject() - Method in class jdsl.graph.ref.AbstractGraph.OO_to_O_MergerIterator
nextObject() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
nextObject() - Method in class jdsl.graph.ref.VertexIteratorAdapter
nextPosition() - Method in interface jdsl.core.api.PositionIterator
nextPosition() - Method in class jdsl.core.ref.ArrayPositionIterator
nextPosition() - Method in class jdsl.core.ref.InOrderIterator: Takes O(1) time
nextPosition() - Method in class jdsl.core.ref.PostOrderIterator: Takes O(1) time
nextPosition() - Method in class jdsl.core.ref.PreOrderIterator: Takes O(1) time
nextPosition() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
nextPosition() - Method in class jdsl.graph.ref.VertexIteratorAdapter
nextVertex() - Method in interface jdsl.graph.api.VertexIterator
nextVertex() - Method in class jdsl.graph.ref.VertexIteratorAdapter
numChildren(Position) - Method in interface jdsl.core.api.InspectableTree
numChildren(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time Can be determined by the inherent nature of the type of node rather than by counting
numChildren(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
numEdges() - Method in interface jdsl.graph.api.InspectableGraph
numEdges() - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
numVertices() - Method in interface jdsl.graph.api.InspectableGraph
numVertices() - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
number(Vertex) - Method in class jdsl.graph.algo.AbstractTopologicalSort: Used for retrieving the topological order-number associated with the given Vertex.

O

OUT - Static variable in interface jdsl.graph.api.EdgeDirection
ObjectHashComparator - class jdsl.core.ref.ObjectHashComparator.: Implements the JDSL HashComparator interface in terms of Java's native Object methods equals(.) and hashCode().
ObjectHashComparator() - Constructor for class jdsl.core.ref.ObjectHashComparator
ObjectIterator - interface jdsl.core.api.ObjectIterator.: Iterator over a set of objects.
OrderedDictionary - interface jdsl.core.api.OrderedDictionary.: A Dictionary in which the keys are totally ordered.
object() - Method in interface jdsl.core.api.ObjectIterator
object() - Method in class jdsl.core.ref.AbstractArrayIterator: Takes O(1) time
object() - Method in class jdsl.core.ref.ArrayObjectIterator: Takes O(1) time
object() - Method in class jdsl.core.ref.InOrderIterator: Takes O(1) time
object() - Method in class jdsl.core.ref.PostOrderIterator: Takes O(1) time
object() - Method in class jdsl.core.ref.PreOrderIterator
object() - Method in class jdsl.graph.ref.AbstractGraph.OO_to_O_MergerIterator
object() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
object() - Method in class jdsl.graph.ref.VertexIteratorAdapter
opposite(Vertex, Edge) - Method in interface jdsl.graph.api.InspectableGraph
opposite(Vertex, Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
origin(Edge) - Method in interface jdsl.graph.api.InspectableGraph
origin(Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
otherChild(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time
otherChild(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called

P

PARENT - Static variable in class jdsl.graph.algo.DFS: Constant used as key to look up the parent of a vertex.
Position - interface jdsl.core.api.Position.: An abstraction of the notion of a "place" in a container -- where an element is stored relative to other elements in the container.
PositionIterator - interface jdsl.core.api.PositionIterator.: Iterator over a set of positions.
PositionalContainer - interface jdsl.core.api.PositionalContainer.: Positional containers (for example, sequences, trees, and graphs) are containers in which elements are related to each other through adjacency information.
PostOrderIterator - class jdsl.core.ref.PostOrderIterator.: The postorder iterator gives a postorder traversal of any tree.
PostOrderIterator(InspectableBinaryTree) - Constructor for class jdsl.core.ref.PostOrderIterator: Constructs a new PostOrderIterator to iterate over the given container Puts a reference to each position into the array -- takes O(N) time where N = the number of positions in the container
PostOrderIterator(InspectableTree) - Constructor for class jdsl.core.ref.PostOrderIterator: Constructs a new PostOrderIterator to iterate over the given container Puts a reference to each position into the array -- takes O(N) time where N = the number of positions in the container
PreOrderIterator - class jdsl.core.ref.PreOrderIterator.: The preorder iterator gives a preorder iteration of the tree.
PreOrderIterator(InspectableBinaryTree) - Constructor for class jdsl.core.ref.PreOrderIterator: Constructs a new PreOrderIterator to iterate over the given binary tree Puts a reference to each position into the array -- takes O(N) time where N = the number of positions in the tree
PreOrderIterator(InspectableTree) - Constructor for class jdsl.core.ref.PreOrderIterator: Constructs a new PreOrderIterator to iterate over the given general tree Puts a reference to each position into the array -- takes O(N) time where N = the number of positions in the tree
PriorityQueue - interface jdsl.core.api.PriorityQueue.: A partially-ordered container that allows for removal of the element with highest priority.
parent(Position) - Method in interface jdsl.core.api.InspectableTree: Gets the parent of a given node.
parent() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time
parent() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
parent(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
parent(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
parent(Vertex) - Method in class jdsl.graph.algo.DFS: Retrieves the parent Vertex of a Vertex
pathExists() - Method in class jdsl.graph.algo.IntegerDijkstraPathfinder: Returns whether a path between the source and the destination exists
posArray_ - Variable in class jdsl.core.ref.ArrayPositionIterator
posInsertAfter(Position, Position) - Method in class jdsl.core.ref.ArraySequence: Makes toInsert the predecessor of willBeSuccessor.
posInsertAfter(Position, Position) - Method in class jdsl.core.ref.NodeSequence: Make toInsert the successor of willBePredecessor
posInsertAtRank(int, Position) - Method in class jdsl.core.ref.ArraySequence: Makes toInsert to rank'th Position in this Sequence.
posInsertAtRank(int, Position) - Method in class jdsl.core.ref.NodeSequence: Make toInsert the rank'th position in this sequence
posInsertBefore(Position, Position) - Method in class jdsl.core.ref.ArraySequence: Makes toInsert the predecessor of willBeSuccessor.
posInsertBefore(Position, Position) - Method in class jdsl.core.ref.NodeSequence: Make toInsert the predecessor of willBeSuccessor
posInsertFirst(Position) - Method in class jdsl.core.ref.ArraySequence: Makes toInsert the first Position of this Sequence.
posInsertFirst(Position) - Method in class jdsl.core.ref.NodeSequence: Make toInsert the first position of this sequence
posInsertLast(Position) - Method in class jdsl.core.ref.ArraySequence: Makes toInsert the last Position of this Sequence.
posInsertLast(Position) - Method in class jdsl.core.ref.NodeSequence: Make toInsert the last position of this sequence
pos_to_element_s - Static variable in class jdsl.core.ref.ToString
position() - Method in interface jdsl.core.api.PositionIterator
position() - Method in class jdsl.core.ref.ArrayPositionIterator
position() - Method in class jdsl.core.ref.InOrderIterator: Takes O(1) time
position() - Method in class jdsl.core.ref.PostOrderIterator: Takes O(1) time
position() - Method in class jdsl.core.ref.PreOrderIterator: Takes O(1) time
position() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
position() - Method in class jdsl.graph.ref.VertexIteratorAdapter
positions() - Method in interface jdsl.core.api.InspectablePositionalContainer: Provides an iterator over all of the positions of the container.
positions() - Method in class jdsl.core.ref.ArraySequence: O(1) time if the cache already exitsts.
positions() - Method in class jdsl.core.ref.NodeBinaryTree: Takes O(N) time from the need to iterate through the tree during snapshot, where N is the number of positions in the tree
positions() - Method in class jdsl.core.ref.NodeSequence: O(1) time if the cache already exists Otherwise O(N) to construct it
positions() - Method in class jdsl.core.ref.NodeTree: O(1) time if cache already exists, O(size of the tree) otherwise
positions() - Method in class jdsl.graph.ref.AbstractGraph: Built on vertices() and edges().
pq_ - Variable in class jdsl.graph.algo.IntegerDijkstraTemplate
prospectiveCycle_ - Variable in class jdsl.graph.algo.DirectedFindCycleDFS: This stores a list of Vertices which are being checked to see if there is a cycle among them.
prospectiveCycle_ - Variable in class jdsl.graph.algo.FindCycleDFS: This stores a list of Vertices which are being checked to see if there is a cycle among them.

Q

Q - Variable in class jdsl.graph.algo.IntegerPrimTemplate
queue_ - Variable in class jdsl.graph.algo.AbstractTopologicalSort: Sequence used as a queue by the sort() method.

R

RED - Static variable in class jdsl.core.ref.RedBlackTree
RedBlackTree - class jdsl.core.ref.RedBlackTree.: A Dictionary implemented as a red-black tree.
RedBlackTree(Comparator) - Constructor for class jdsl.core.ref.RedBlackTree: Takes O(1) time This constructor creates the tree with a single no-element-stored-here locator.
rankOf(Position) - Method in interface jdsl.core.api.InspectableSequence: Get the rank of a given position.
rankOf(Position) - Method in class jdsl.core.ref.ArraySequence: O(1) time.
rankOf(Position) - Method in class jdsl.core.ref.NodeSequence: O(1) time if the positions_ cache is valid (no modifications since cache was generated) O(N) if cache is invalid (must traverse rank elements of Sequence)
rankOfChild(Position) - Method in interface jdsl.core.api.InspectableTree
rankOfChild(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
rankOfChild(Position) - Method in class jdsl.core.ref.NodeTree: O(the number of children of the node) time
recolorAfterRemove(Position) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree.
rehash() - Method in class jdsl.core.ref.HashtableDecorable
relaxingEdge(Vertex, Edge, int, Vertex, int) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden in any application where the edges considered for the minimum spanning tree matter.
remove(Locator) - Method in interface jdsl.core.api.KeyBasedContainer: Removes a (key,element) pair from the container.
remove(Position) - Method in interface jdsl.core.api.Sequence: Removes and invalidates the specified position
remove(Locator) - Method in class jdsl.core.ref.ArrayHeap: If array-shrinking is specified at construction time and the load factor of the array is 0.25 after the removal, the capacity of the array is halved by copying the elements into a new array.
remove(Position) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
remove(Locator) - Method in class jdsl.core.ref.HashtableDictionary: O(1) expected: strictly O(1) unless removal reduces size below the downhashing threshhold, in which case it is O(N)
remove(Position) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
remove(Locator) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case removal would restructure once each step up the tree.
removeAboveExternal(Position) - Method in interface jdsl.core.api.BinaryTree: The parent of node is deleted, and the sibling of node, with all its children, is installed in its place; node is also deleted.
removeAboveExternal(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
removeAfter(Position) - Method in interface jdsl.core.api.Sequence: Remove and invalidates the position after the position specified
removeAfter(Position) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
removeAfter(Position) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
removeAll(Object) - Method in interface jdsl.core.api.Dictionary: Removes all the (key,element) pairs matching the parameter key.
removeAll(Object) - Method in class jdsl.core.ref.HashtableDictionary: O(#elts with target key) expected, worst case O(N) with excessive chaining, or if removeAll drops the size below the downhashing threshhold.
removeAll(Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(RlogN) time where R = the number of objects with key key and log N = the height of the tree (N locators in the tree) (one removal case per each object)
removeAtRank(int) - Method in interface jdsl.core.api.Sequence: Removes and invalidates the position at the specified rank
removeAtRank(int) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
removeAtRank(int) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
removeBefore(Position) - Method in interface jdsl.core.api.Sequence: Removes and invalidates the position before the position specified.
removeBefore(Position) - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
removeBefore(Position) - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
removeEdge(Edge) - Method in interface jdsl.graph.api.Graph
removeEdge(Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
removeExternal(Position) - Method in interface jdsl.core.api.Tree: Removes an external node (a leaf).
removeExternal(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
removeFirst() - Method in interface jdsl.core.api.Sequence: Removes and invalidates the first position of this.
removeFirst() - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
removeFirst() - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
removeKey(Object) - Method in class jdsl.core.ref.HashtableDictionary: Removes the first element found with the given key from the hashtable.
removeKey(Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case removal would restructure once each step up the tree.
removeLast() - Method in interface jdsl.core.api.Sequence: Removes and invalidates the last position of this.
removeLast() - Method in class jdsl.core.ref.ArraySequence: This method also clears the Position and element caches.
removeLast() - Method in class jdsl.core.ref.NodeSequence: This method also clears the position cache.
removeMin() - Method in interface jdsl.core.api.PriorityQueue: Pops the highest-priority element off the priority queue and updates the priority queue.
removeMin() - Method in class jdsl.core.ref.ArrayHeap: If array-shrinking is specified at construction time and the load factor of the array is 0.25 after the removal, the capacity of the array is halved by copying the elements into a new array.
removeSelfAndAbove() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time This method removes this node and its parent, replacing its parent with my sibling This is the asymmetric opposite of expand.
removeSelfAndAbove() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
removeVertex(Vertex) - Method in interface jdsl.graph.api.Graph: Removes a vertex and all its incident edges.
removeVertex(Vertex) - Method in class jdsl.graph.ref.IncidenceListGraph: O(degree)
replaceElement(Accessor, Object) - Method in interface jdsl.core.api.Container: Changes the element stored at an accessor.
replaceElement(Accessor, Object) - Method in class jdsl.core.ref.ArrayHeap: time complexity = worst-case O(1)
replaceElement(Accessor, Object) - Method in class jdsl.core.ref.ArraySequence: This method also invalidates the elements cache.
replaceElement(Accessor, Object) - Method in class jdsl.core.ref.HashtableDictionary: O(1)
replaceElement(Object) - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Replaces my element, returning the old element
replaceElement(Object) - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
replaceElement(Accessor, Object) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
replaceElement(Accessor, Object) - Method in class jdsl.core.ref.NodeSequence: O(1) time
replaceElement(Accessor, Object) - Method in class jdsl.core.ref.NodeTree: O(1) time
replaceElement(Accessor, Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(1) time
replaceElement(Accessor, Object) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
replaceKey(Locator, Object) - Method in interface jdsl.core.api.KeyBasedContainer: Replaces the key in the given (key,element) pair, adjusting the container as necessary.
replaceKey(Locator, Object) - Method in class jdsl.core.ref.ArrayHeap: time complexity = worst-case O(log n)
replaceKey(Locator, Object) - Method in class jdsl.core.ref.HashtableDictionary: O(1)
replaceKey(Locator, Object) - Method in class jdsl.core.ref.RedBlackTree: Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Takes the running time it would take to execute both remove and insert.
replaceSelf(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Replaces me with a new node, as far as my parent is concerned protected so restructurable trees can use it
replaceSelf(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
replaceSubtree(Position, BinaryTree) - Method in interface jdsl.core.api.BinaryTree: Swaps a subtree of this binary tree with a binary tree passed in.
replaceSubtree(Position, Tree) - Method in interface jdsl.core.api.Tree: Replaces the subtree rooted at node with the tree t.
replaceSubtree(Position, BinaryTree) - Method in class jdsl.core.ref.NodeBinaryTree: Takes O(S1+S2) time, where S1 and S2 are the number of positions in each subtree You are only allowed to link in and replaceSubtree with other instances of NodeBinaryTree (or subclasses thereof)
replaceSubtree(Position, Tree) - Method in class jdsl.core.ref.NodeTree: O(size of the new subtree + size of the cut tree) time
reportPath() - Method in class jdsl.graph.algo.IntegerDijkstraPathfinder
reset() - Method in interface jdsl.core.api.ObjectIterator: Puts the iterator back in its initial, before-the-first state
reset() - Method in class jdsl.core.ref.AbstractArrayIterator: Takes O(1) time
reset() - Method in class jdsl.core.ref.ArrayObjectIterator: Takes O(1) time
reset() - Method in class jdsl.core.ref.InOrderIterator: Takes O(1) time Sets the current node to the first node.
reset() - Method in class jdsl.core.ref.PostOrderIterator: Takes O(1) time Sets the current node to the first node.
reset() - Method in class jdsl.core.ref.PreOrderIterator: Takes O(1) time Sets the current node to the first node.
reset() - Method in class jdsl.graph.ref.AbstractGraph.OO_to_O_MergerIterator
reset() - Method in class jdsl.graph.ref.EdgeIteratorAdapter
reset() - Method in class jdsl.graph.ref.VertexIteratorAdapter
resetToEmpty() - Method in class jdsl.core.ref.NodeBinaryTree: Used for resetting the tree to an empty tree after a link or replaceSubtree operation.
reverseDirection(Edge) - Method in interface jdsl.graph.api.ModifiableGraph: Reverse the direction of an edge.
reverseDirection(Edge) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
right() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time
right() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
rightChild(Position) - Method in interface jdsl.core.api.InspectableBinaryTree: Provides the right child of a given node.
rightChild(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
root() - Method in interface jdsl.core.api.InspectableTree: Gets the root of this tree.
root() - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
root() - Method in class jdsl.core.ref.NodeTree: O(1) time
runUntil() - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Repeatedly calls method doOneIteration() until either the priority queue is empty or method shouldContinue() returns false.

S

START_TIME - Static variable in class jdsl.graph.algo.DFS: Constant used as key to look up the start time of a vertex.
Sequence - interface jdsl.core.api.Sequence.: A positional container whose elements are linearly organized.
SerializableObject - class jdsl.core.ref.SerializableObject.: An object which can be used as a key for decorations, but which is Serializable.
SerializableObject() - Constructor for class jdsl.core.ref.SerializableObject
SortObject - interface jdsl.core.algo.sorts.SortObject.: Algorithm interface for sorting a sequence according to a given comparator of elements.
sequenceToList(InspectableSequence, List) - Static method in class jdsl.core.util.Converter: Places the contents of a sequence into a list, preserving order.
sequenceToSet(InspectableSequence, Set) - Static method in class jdsl.core.util.Converter: Places the contents of a sequence into a set.
set(Object, Object) - Method in interface jdsl.core.api.Decorable: Sets the value in the (attribute, value) entry associated with a certain attribute in this decorable object.
set(Object, Object) - Method in class jdsl.core.ref.HashtableDecorable: Sets the value of a decoration.
set(Object, Object) - Method in class jdsl.graph.api.Edge.NONEEdge
set(Object, Object) - Method in class jdsl.graph.api.Vertex.NONEVertex
setArrayShrinkability(boolean) - Method in class jdsl.core.ref.ArraySequence: A public convenience method that allows the user to toggle the shrinkability of the array.
setChild(NodeBinaryTree.NBTNode, NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Replaces one of my children with a new node protected to allow SuperNode to override it
setChild(NodeBinaryTree.NBTNode, NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: O(1) time Sets this node's root; any other use of this method is invalid
setContainer(NodeBinaryTree) - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Sets the parameter container as this node's container
setDirectionFrom(Edge, Vertex) - Method in interface jdsl.graph.api.ModifiableGraph: Sets the direction of an edge away from a vertex.
setDirectionFrom(Edge, Vertex) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
setDirectionTo(Edge, Vertex) - Method in interface jdsl.graph.api.ModifiableGraph: Sets the direction of an edge towards a vertex.
setDirectionTo(Edge, Vertex) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
setEdgeToParent(Vertex, Edge) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to supply a way of storing and retrieving one edge per vertex.
setElement(Object) - Method in class jdsl.core.ref.NodeSequence.FNSNode: Sets the position's element
setLeft(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Sets the parameter node as this node's left child
setLeft() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
setLocator(Vertex, Locator) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to supply a way of storing and retrieving one locator per vertex.
setLocator(Vertex, Locator) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden to supply a way of storing and retrieving one locator per vertex.
setParent(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Sets the parameter node as this node's parent
setParent() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
setRight(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode: O(1) time Sets the parameter node as this node's right child
setRight() - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called
setRoot(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: O(1) time Sets this node's root
setToSequence(Set, Sequence) - Static method in class jdsl.core.util.Converter: Places the contents of a set into a sequence.
shortestPathFound(Vertex, int) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to give you a notification when the shortest path to a vertex is determined.
shouldContinue() - Method in class jdsl.graph.algo.IntegerDijkstraPathfinder
shouldContinue() - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden in any application where the full shortest-path tree is not needed and the algorithm should terminate early.
shouldContinue() - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden in any application where the full minimum spanning tree is not needed and the algorithm should terminate early.
sibling(Position) - Method in interface jdsl.core.api.InspectableBinaryTree: Provides the sibling of a given node (the other child of the node's parent)
sibling(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
siblingAfter(Position) - Method in interface jdsl.core.api.InspectableTree
siblingAfter(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
siblingAfter(Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
siblingBefore(Position) - Method in interface jdsl.core.api.InspectableTree
siblingBefore(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
siblingBefore(Position) - Method in class jdsl.core.ref.NodeTree: O(the number of children of the node) time
siblings(Position) - Method in interface jdsl.core.api.InspectableTree: Returns an iterator over the siblings of the node in order.
siblings(Position) - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
siblings(Position) - Method in class jdsl.core.ref.NodeTree: O(the number of children of the node) time
size() - Method in interface jdsl.core.api.InspectableContainer: Gives the number of elements stored in the container.
size() - Method in class jdsl.core.ref.ArrayHeap: time complexity = worst-case O(1)
size() - Method in class jdsl.core.ref.ArraySequence: O(1) time.
size() - Method in class jdsl.core.ref.HashtableDecorable: Gets the size.
size() - Method in class jdsl.core.ref.HashtableDictionary: O(1)
size() - Method in class jdsl.core.ref.NodeBinaryTree: O(1) time
size() - Method in class jdsl.core.ref.NodeSequence: O(1) time
size() - Method in class jdsl.core.ref.NodeTree: O(1) time
size() - Method in class jdsl.core.ref.RedBlackTree: Takes O(1) time
size() - Method in class jdsl.graph.ref.AbstractGraph: Built on numVertices() and numEdges().
sort(Sequence, Comparator) - Method in class jdsl.core.algo.sorts.ArrayMergeSort
sort(Sequence, Comparator) - Method in class jdsl.core.algo.sorts.ArrayQuickSort
sort(Sequence, Comparator) - Method in class jdsl.core.algo.sorts.HeapSort
sort(Sequence, Comparator) - Method in class jdsl.core.algo.sorts.ListMergeSort: Recursively divides a Sequence into (roughly) equal subsequences and merges them back together once sorted.
sort(Sequence, Comparator) - Method in interface jdsl.core.algo.sorts.SortObject: Method that actually sorts the sequence, with the first element after the sort being the one that the comparator reported was smallest.
sort() - Method in class jdsl.graph.algo.AbstractTopologicalSort: This abstract method is overridden in the subclasses.
sort() - Method in class jdsl.graph.algo.TopologicalSort: The meat of the algorithm.
sort() - Method in class jdsl.graph.algo.UnitWeightedTopologicalNumbering: The meat of the algorithm.
sortedVertices() - Method in class jdsl.graph.algo.TopologicalSort: Returns a VertexIterator containing all the Vertices in topologically sorted order.
sortedmapToOrderedDictionary(SortedMap, OrderedDictionary) - Static method in class jdsl.core.util.Converter: Places the contents of a sorted map into an ordered dictionary.
source - Variable in class jdsl.graph.algo.IntegerPrimTemplate
source_ - Variable in class jdsl.graph.algo.IntegerDijkstraTemplate
splitEdge(Edge, Object) - Method in interface jdsl.graph.api.ModifiableGraph: Splits an existing edge by inserting a new vertex and two new edges, and removing the old edge.
splitEdge(Edge, Object) - Method in class jdsl.graph.ref.IncidenceListGraph: O(1)
startTime(Vertex) - Method in class jdsl.graph.algo.DFS: Returns the "Start time" of a Vertex.
startVisit(Vertex) - Method in class jdsl.graph.algo.DFS: Called when a vertex is visited.
startVisit(Vertex) - Method in class jdsl.graph.algo.DirectedFindCycleDFS: As new vertices are visited, they are added to the prospective cyclic path.
startVisit(Vertex) - Method in class jdsl.graph.algo.FindCycleDFS: As new vertices are visited, they are added to the prospective cyclic path.
status(Vertex) - Method in class jdsl.graph.algo.DFS: Accesses the current status of the given Vertex.
stringfor(Locator) - Method in class jdsl.core.ref.ToString.LocatorCollectionsStyle
stringfor(Locator) - Method in interface jdsl.core.ref.ToString.LocatorToString
stringfor(Position) - Method in interface jdsl.core.ref.ToString.PositionToString
stringfor(Position) - Method in class jdsl.core.ref.ToString.PositionWritesElementOnly
stringfor(InspectableSequence, ToString.PositionToString) - Static method in class jdsl.core.ref.ToString: Gives string representation of a sequence, parameterized by how to represent each position (i.e., constructs a string by iterating over all positions of the sequence, concatenating the specified string representation of each position).
stringfor(InspectableSequence) - Static method in class jdsl.core.ref.ToString: Default version of stringfor( InspSeq, PTS ).
stringfor(InspectableTree, ToString.PositionToString) - Static method in class jdsl.core.ref.ToString: Gives string representation of a tree, parametrized by how to represent each position.
stringfor(InspectableTree) - Static method in class jdsl.core.ref.ToString: Default version of stringfor( InspTree, PTS ).
stringfor(InspectableKeyBasedContainer, ToString.LocatorToString) - Static method in class jdsl.core.ref.ToString: Gives string representation of a dictionary or priority queue, parameterized by how to represent each locator (i.e., constructs a string by iterating over all locators of the container, concatenating the specified string representation of each locator).
stringfor(InspectableKeyBasedContainer) - Static method in class jdsl.core.ref.ToString: Default version of stringfor( InspKBC, LTS ).
stringfor(Position) - Static method in class jdsl.core.ref.ToString
stringfor(Locator) - Static method in class jdsl.core.ref.ToString
stringfor(Edge, InspectableGraph) - Method in class jdsl.graph.ref.ToString.EdgeInRTStyle
stringfor(Edge, InspectableGraph) - Method in class jdsl.graph.ref.ToString.EdgeToEmptyString
stringfor(Edge, InspectableGraph) - Method in interface jdsl.graph.ref.ToString.EdgeToString
stringfor(Vertex) - Method in class jdsl.graph.ref.ToString.VertexToEmptyString
stringfor(Vertex) - Method in interface jdsl.graph.ref.ToString.VertexToString
stringfor(Vertex) - Method in class jdsl.graph.ref.ToString.VertexWritesElementOnly
stringfor(InspectableGraph, ToString.VertexToString, ToString.EdgeToString) - Static method in class jdsl.graph.ref.ToString: Code lifted shamelessly from rt's corresponding class in jdsltools.testers.graph, then adapted to the style of my jdsl.core.ref.ToString.
stringfor(InspectableGraph) - Static method in class jdsl.graph.ref.ToString
stringfor(Edge) - Static method in class jdsl.graph.ref.ToString
stringfor(Vertex) - Static method in class jdsl.graph.ref.ToString
swapElements(Position, Position) - Method in interface jdsl.core.api.PositionalContainer: Swaps the elements associated with the two positions, leaving the positions themselves "where" they were.
swapElements(Position, Position) - Method in class jdsl.core.ref.AbstractPositionalContainer: Works on top of PositionalContainer method replaceElement(Position, Object) and InspectableContainer method contains().
swapElements(Position, Position) - Method in class jdsl.core.ref.NodeTree: O(1) time
swapWithNode(NodeBinaryTree.NBTNode) - Method in class jdsl.core.ref.NodeBinaryTree.NBTSuperNode: Should never be called

T

TREE_EDGE - Static variable in class jdsl.graph.algo.DFS: Constant signifying that a marked edge is a tree edge.
TREE_NUMBER - Static variable in class jdsl.graph.algo.DFS: Constant used as key to look up the tree to which a Vertex belongs.
ToString - class jdsl.core.ref.ToString.: Collection of static methods that generate a string representing a container or accessor.
ToString - class jdsl.graph.ref.ToString.: string representing a graph.
ToString.EdgeInRTStyle - class jdsl.graph.ref.ToString.EdgeInRTStyle.
ToString.EdgeToEmptyString - class jdsl.graph.ref.ToString.EdgeToEmptyString.
ToString.EdgeToEmptyString() - Constructor for class jdsl.graph.ref.ToString.EdgeToEmptyString
ToString.EdgeToString - interface jdsl.graph.ref.ToString.EdgeToString.
ToString.LocatorCollectionsStyle - class jdsl.core.ref.ToString.LocatorCollectionsStyle.: Stringifies a locator in the Java Collections style: (key)=(element).
ToString.LocatorCollectionsStyle() - Constructor for class jdsl.core.ref.ToString.LocatorCollectionsStyle
ToString.LocatorToString - interface jdsl.core.ref.ToString.LocatorToString.: Way to parameterize the stringifying of a locator, within the stringifying of a container.
ToString.PositionToString - interface jdsl.core.ref.ToString.PositionToString.: Way to parametrize the stringifying of a position, within the stringifying of a container.
ToString.PositionWritesElementOnly - class jdsl.core.ref.ToString.PositionWritesElementOnly.: Stringifies a position by giving the string representation of the position's element.
ToString.PositionWritesElementOnly() - Constructor for class jdsl.core.ref.ToString.PositionWritesElementOnly
ToString.VertexToEmptyString - class jdsl.graph.ref.ToString.VertexToEmptyString.
ToString.VertexToEmptyString() - Constructor for class jdsl.graph.ref.ToString.VertexToEmptyString
ToString.VertexToString - interface jdsl.graph.ref.ToString.VertexToString.
ToString.VertexWritesElementOnly - class jdsl.graph.ref.ToString.VertexWritesElementOnly.
ToString.VertexWritesElementOnly() - Constructor for class jdsl.graph.ref.ToString.VertexWritesElementOnly
TopologicalSort - class jdsl.graph.algo.TopologicalSort.: This algorithm class performs a topological ordering on a given DAG.
TopologicalSort() - Constructor for class jdsl.graph.algo.TopologicalSort: Constructor
Tree - interface jdsl.core.api.Tree.: A positional container representing an ordered tree.
toString() - Method in class jdsl.core.ref.ArrayHeap: time complexity = worst-case O(n)
toString() - Method in class jdsl.core.ref.ArraySequence: O(n) time.
toString() - Method in class jdsl.core.ref.HashtableDictionary: O(N) human readable description of the contents of this dictionary, conforming to the Collections spec for key-element structures.
toString() - Method in class jdsl.core.ref.NodeBinaryTree.NBTNode
toString() - Method in class jdsl.core.ref.NodeBinaryTree
toString() - Method in class jdsl.core.ref.NodeSequence.FNSNode
toString() - Method in class jdsl.core.ref.NodeSequence
toString() - Method in class jdsl.core.ref.NodeTree
toString() - Method in class jdsl.core.ref.RedBlackTree
toString() - Method in class jdsl.graph.api.Edge.NONEEdge
toString() - Method in class jdsl.graph.api.Vertex.NONEVertex
toString() - Method in class jdsl.graph.ref.IncidenceListGraph
traverseBackEdge(Edge, Vertex) - Method in class jdsl.graph.algo.DFS: Called when a back edge is traversed.
traverseBackEdge(Edge, Vertex) - Method in class jdsl.graph.algo.DirectedFindCycleDFS: When a back edge has been encountered, the graph has a cycle.
traverseBackEdge(Edge, Vertex) - Method in class jdsl.graph.algo.FindCycleDFS: When a back edge has been encountered, the graph has a cycle.
traverseCrossEdge(Edge, Vertex) - Method in class jdsl.graph.algo.DFS: Called when a cross edge is traversed.
traverseForwardEdge(Edge, Vertex) - Method in class jdsl.graph.algo.DFS: Called when a forward edge is traversed.
traverseTreeEdge(Edge, Vertex) - Method in class jdsl.graph.algo.DFS: Called when a discovery edge is traversed.
treeEdgeFound(Vertex, Edge, int) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden to give you a notification when a vertex is added to the minimum spanning tree.
treeNum_ - Variable in class jdsl.graph.algo.DFS: The number of the DFS tree being traversed.
treeNumber(Vertex) - Method in class jdsl.graph.algo.DFS: Retrieves an index representing a connected DFS component.
treeToSet(InspectableTree, Set) - Static method in class jdsl.core.util.Converter: Places the contents of a tree into a set.
treeWeight - Variable in class jdsl.graph.algo.IntegerPrimTemplate
tree_ - Variable in class jdsl.core.algo.traversals.EulerTour: The tree on which the algorithm executes.
type(Edge) - Method in class jdsl.graph.algo.DFS: Accesses the current type of the given Edge.

U

UNDIR - Static variable in interface jdsl.graph.api.EdgeDirection
UNSEEN - Static variable in class jdsl.graph.algo.DFS: Constant signifying that an edge has not yet been seen.
UNVISITED - Static variable in class jdsl.graph.algo.DFS: Constant signifying that an vertex has not been visited
UnitWeightedTopologicalNumbering - class jdsl.graph.algo.UnitWeightedTopologicalNumbering.: This algorithm class computes the optimal unit-weighted topological numbering for a given DAG.
UnitWeightedTopologicalNumbering() - Constructor for class jdsl.graph.algo.UnitWeightedTopologicalNumbering: Constructor
undirectedEdges() - Method in interface jdsl.graph.api.InspectableGraph
undirectedEdges() - Method in class jdsl.graph.ref.AbstractGraph: Built on edges() and isDirected(.)
unsplitEdge(Vertex, Object) - Method in interface jdsl.graph.api.ModifiableGraph: Transforms edge-vertex-edge into a single edge.
unsplitEdge(Vertex, Object) - Method in class jdsl.graph.ref.IncidenceListGraph: Note: the "two" edges incident on v cannot be the same edge.
updateContainer(Accessor) - Method in class jdsl.core.ref.NodeBinaryTree: Recursively changes the container of all nodes in the subtree anchored at root to this container, adding to _size for each node whose container we change Takes O(S) time -- where S is the number of elements in the subtree

V

VERTEX_STATUS - Static variable in class jdsl.graph.algo.DFS: Constant used as key to look up an vertex's status.
VISITED - Static variable in class jdsl.graph.algo.DFS: Constant signifying that an vertex has been visited
VISITING - Static variable in class jdsl.graph.algo.DFS: Constant signifying that an vertex is being visited
Vertex - interface jdsl.graph.api.Vertex.: Empty, typing interface for vertices.
Vertex.NONEVertex - class jdsl.graph.api.Vertex.NONEVertex.: A dummy class, used to implement the constant Vertex.NONE
.
VertexIterator - interface jdsl.graph.api.VertexIterator.: Iterator over a set of vertices.
VertexIteratorAdapter - class jdsl.graph.ref.VertexIteratorAdapter.: Takes an ObjectIterator known to be iterating over things that are Vertices, and makes it appear as an VertexIterator.
VertexIteratorAdapter(ObjectIterator) - Constructor for class jdsl.graph.ref.VertexIteratorAdapter
vert_to_element_s - Static variable in class jdsl.graph.ref.ToString
vertex() - Method in interface jdsl.graph.api.VertexIterator
vertex() - Method in class jdsl.graph.ref.VertexIteratorAdapter
vertexNotReachable(Vertex) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden in any application that involves unreachable vertices.
vertexNotReachable(Vertex) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Can be overridden in any application that involves unreachable vertices.
vertices() - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Can be overridden to consider a subset of the vertices in the graph, although I can't think of any reason to do so.
vertices() - Method in interface jdsl.graph.api.InspectableGraph
vertices() - Method in class jdsl.graph.ref.IncidenceListGraph: O(V)
visitBetweenChildren(Position) - Method in class jdsl.core.algo.traversals.EulerTour: Called during execution when a node is visited between visits to its children.
visitExternal(Position) - Method in class jdsl.core.algo.traversals.EulerTour: Called during execution when an external node is visited during the Euler tour.
visitFirstTime(Position) - Method in class jdsl.core.algo.traversals.EulerTour: Called during execution when a node is first visited in the Euler tour.
visitLastTime(Position) - Method in class jdsl.core.algo.traversals.EulerTour: Called during execution when a node is visted for the last time in the Euler tour.
visitResult_ - Variable in class jdsl.graph.algo.DFS: The result of the traversal.

W

weight(Edge) - Method in class jdsl.graph.algo.IntegerDijkstraTemplate: Must be overridden to supply a way of getting a positive weight for every edge in the graph.
weight(Edge) - Method in class jdsl.graph.algo.IntegerPrimTemplate: Must be overridden to supply a way of getting a positive weight for every edge in the graph.
writeNodeAndChildren(Position, ToString.PositionToString, DataOutputStream, InspectableTree, int, int) - Static method in class jdsl.core.ref.ToString: Recursively dumps a byte representation of a subtree onto a stream.

Z

ZERO - Variable in class jdsl.graph.algo.IntegerPrimTemplate

_

_size - Variable in class jdsl.core.ref.NodeBinaryTree: The size of the tree protected so that RestructurableNodeBinaryTree can access it

A B C D E F G H I J K L M N O P Q R S T U V W Z _

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV NEXT

FRAMES NO FRAMES