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

A

A - Variable in class net.datastructures.HashTable

AVAILABLE - Static variable in class net.datastructures.HashTable

AVLTree - class net.datastructures.AVLTree.

AVLTree class - implements an AVL Tree by extending a binary search tree.

AVLTree(Comparator) - Constructor for class net.datastructures.AVLTree

AVLTree() - Constructor for class net.datastructures.AVLTree

AVLTree.AVLNode - class net.datastructures.AVLTree.AVLNode.

Nested class for the nodes of an AVL tree.

AdaptablePriorityQueue - interface net.datastructures.AdaptablePriorityQueue.

Interface for an adaptable priority queue.

AdjacencyListGraph - class net.datastructures.AdjacencyListGraph.

An realization of a graph according to adjacency list structure.

AdjacencyListGraph() - Constructor for class net.datastructures.AdjacencyListGraph

Default constructor that creates an empty graph

AdjacencyListGraph.MyEdge - class net.datastructures.AdjacencyListGraph.MyEdge.

Implementation of an edge for an undirected adjacency list graph.

AdjacencyListGraph.MyPosition - class net.datastructures.AdjacencyListGraph.MyPosition.

Implementation of a decorable position by means of a hash table.

AdjacencyListGraph.MyPosition() - Constructor for class net.datastructures.AdjacencyListGraph.MyPosition

AdjacencyListGraph.MyVertex - class net.datastructures.AdjacencyListGraph.MyVertex.

Implementation of a vertex for an undirected adjacency list graph.

ArrayStack - class net.datastructures.ArrayStack.

Implementation of the Stack interface using a fixed-length array.

ArrayStack() - Constructor for class net.datastructures.ArrayStack

Initialize the stack to use an array of default length CAPACITY.

ArrayStack(int) - Constructor for class net.datastructures.ArrayStack

Initialize the stack to use an array of given length.

ArrayVector - class net.datastructures.ArrayVector.

Realization of a vector by means of an array.

ArrayVector() - Constructor for class net.datastructures.ArrayVector

Creates the vector with initial capacity 16.

actionPos - Variable in class net.datastructures.BinarySearchTree

actionPos - Variable in class net.datastructures.SortedListPriorityQueue

add(Object) - Method in interface net.datastructures.CompleteBinaryTree

Adds an element to the tree just after the last node.

add(Object) - Method in class net.datastructures.VectorCompleteBinaryTree

Add an element just after the last node (in a level numbering).

addAll(List, Position, Object) - Method in class net.datastructures.BinarySearchTree

Adds to L all entries in the subtree rooted at v having keys equal to k.

addRoot(Object) - Method in class net.datastructures.LinkedBinaryTree

Adds a root node to an empty tree

areAdjacent(Vertex, Vertex) - Method in class net.datastructures.AdjacencyListGraph

Test whether two vertices are adjacent

areAdjacent(Vertex, Vertex) - Method in interface net.datastructures.Graph

Test whether two vertices are adjacent

atRank(int) - Method in class net.datastructures.NodeSequence

Returns the position containing the element at the given rank; O(n) time.

atRank(int) - Method in interface net.datastructures.Sequence

Returns the position containing the element at the given rank.

attach(Position, BinaryTree, BinaryTree) - Method in class net.datastructures.LinkedBinaryTree

Attaches two trees to be subtrees of an external node.

B

BTNode - class net.datastructures.BTNode.

Class implementing a node of a binary tree by storing references to an element, a parent node, a left node, and a right node.

BTNode() - Constructor for class net.datastructures.BTNode

Default constructor

BTNode(Object, BTPosition, BTPosition, BTPosition) - Constructor for class net.datastructures.BTNode

Main constructor

BTPosition - interface net.datastructures.BTPosition.

Interface for a node of a binary tree.

BinarySearchTree - class net.datastructures.BinarySearchTree.

Realization of a dictionary by means of a binary search tree.

BinarySearchTree() - Constructor for class net.datastructures.BinarySearchTree

Creates a BinarySearchTree with a default comparator.

BinarySearchTree(Comparator) - Constructor for class net.datastructures.BinarySearchTree

Creates a BinarySearchTree with the given comparator.

BinarySearchTree.BSTEntry - class net.datastructures.BinarySearchTree.BSTEntry.

Nested class for location-aware binary search tree entries

BinaryTree - interface net.datastructures.BinaryTree.

An interface for a binary tree, where each node can have zero, one, or two children.

BoundaryViolationException - exception net.datastructures.BoundaryViolationException.

Signals that the boundaries of a data structure have been illegally traversed (e.g. past the end of a list).

BoundaryViolationException(String) - Constructor for class net.datastructures.BoundaryViolationException

C

C - Variable in class net.datastructures.BinarySearchTree

CAPACITY - Static variable in class net.datastructures.ArrayStack

Default length of the array used to implement the stack.

CompleteBinaryTree - interface net.datastructures.CompleteBinaryTree.

An interface for a complete binary tree.

ConnectivityDFS - class net.datastructures.ConnectivityDFS.

This class specializes DFS to determine whether the graph is connected.

ConnectivityDFS() - Constructor for class net.datastructures.ConnectivityDFS

c - Variable in class net.datastructures.SortedListPriorityQueue

capacity - Variable in class net.datastructures.ArrayStack

Length of the array used to implement the stack.

checkEdge(Edge) - Method in class net.datastructures.AdjacencyListGraph

Determines whether a given edge is valid.

checkEntry(Entry) - Method in class net.datastructures.BinarySearchTree

Check whether a given entry is valid.

checkEntry(Entry) - Method in class net.datastructures.HeapAdaptablePriorityQueue

Check whether a given entry is valid.

checkEntry(Entry) - Method in class net.datastructures.SortedListAdaptablePriorityQueue

Determines whether a given entry is valid.

checkKey(Object) - Method in class net.datastructures.BinarySearchTree

Check whether a given key is valid.

checkKey(Object) - Method in class net.datastructures.HashTable

Determines whether a key is valid.

checkKey(Object) - Method in class net.datastructures.HeapPriorityQueue

Determines whether a given key is valid.

checkKey(Object) - Method in class net.datastructures.SortedListPriorityQueue

Determines whether a key is valid.

checkPosition(Position) - Method in class net.datastructures.AdjacencyListGraph

Determines whether a given position is valid.

checkPosition(Position) - Method in class net.datastructures.LinkedBinaryTree

If v is a good binary tree node, cast to BTPosition, else throw exception

checkPosition(Position) - Method in class net.datastructures.NodeList

Checks if position is valid for this list and converts it to DNode if it is valid; O(1) time

checkPosition(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Determine whether v is a valid node.

checkRank(int, int) - Method in class net.datastructures.ArrayVector

Checks whether the given rank is in the range [0, n - 1]

checkRank(int, int) - Method in class net.datastructures.NodeSequence

Checks whether the given rank is in the range [0, n - 1]

checkVertex(Vertex) - Method in class net.datastructures.AdjacencyListGraph

Determines whether a given vertex is valid.

children(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns an iterator of the children of a node.

children(Position) - Method in interface net.datastructures.Tree

Returns an iterator of the children of a given node.

children(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns an iterator of the children of v.

comp - Variable in class net.datastructures.HeapPriorityQueue

compare(Object, Object) - Method in class net.datastructures.DefaultComparator

Compares a to b.

compare(Object, Object) - Method in class net.datastructures.HeapPriorityQueue.DefaultComparator

compare(Object, Object) - Method in class net.datastructures.SortedListPriorityQueue.DefaultComparator

createNode(Object, BTPosition, BTPosition, BTPosition) - Method in class net.datastructures.AVLTree

Creates a new binary search tree node (overrides super's version).

createNode(Object, BTPosition, BTPosition, BTPosition) - Method in class net.datastructures.LinkedBinaryTree

Creates a new binary tree node

createNode(Object, BTPosition, BTPosition, BTPosition) - Method in class net.datastructures.RBTree

Creates a new tree node.

cur - Variable in class net.datastructures.PositionIterator

cursor - Variable in class net.datastructures.ElementIterator

cycle - Variable in class net.datastructures.FindCycleDFS

cycleStart - Variable in class net.datastructures.FindCycleDFS

D

DFS - class net.datastructures.DFS.

Generic depth first search traversal of a graph using the template method pattern.

DFS() - Constructor for class net.datastructures.DFS

DIST - Variable in class net.datastructures.Dijkstra

Attribute for vertex distances

DLNode - class net.datastructures.DLNode.

A simple node class for a doubly-linked list.

DNode - class net.datastructures.DNode.

A simple node class for a doubly-linked list.

DNode(DNode, DNode, Object) - Constructor for class net.datastructures.DNode

DecorablePosition - interface net.datastructures.DecorablePosition.

An interface for a position that can be marked with an arbitrary number of decorations.

DefaultComparator - class net.datastructures.DefaultComparator.

A default comparator, which uses the natural ordering

DefaultComparator() - Constructor for class net.datastructures.DefaultComparator

Deque - interface net.datastructures.Deque.

Interface for a deque (double-ended queue).

Dictionary - interface net.datastructures.Dictionary.

An interface for a dictionary storing (key-value) pairs.

Dijkstra - class net.datastructures.Dijkstra.

Dijkstra's algorithm for the single-source shortest path problem in an undirected graph whose edges have integer weights.

Dijkstra() - Constructor for class net.datastructures.Dijkstra

degree() - Method in class net.datastructures.AdjacencyListGraph.MyVertex

Return the degree of a given vertex

degree(Vertex) - Method in class net.datastructures.AdjacencyListGraph

Return the degree of a given vertex

dequeue() - Method in class net.datastructures.NodeQueue

dequeue() - Method in interface net.datastructures.Queue

Removes the element at the front of the queue.

dfsTraversal(Vertex) - Method in class net.datastructures.DFS

Recursive template method for a generic DFS traversal.

dijkstraVisit(Vertex) - Method in class net.datastructures.Dijkstra

The actual execution of Dijkstra's algorithm.

done - Variable in class net.datastructures.FindCycleDFS

done - Variable in class net.datastructures.FindPathDFS

downHeap(Position) - Method in class net.datastructures.HeapPriorityQueue

Performs down-heap bubbling.

E

E - Variable in class net.datastructures.AdjacencyListGraph

ENTRY - Variable in class net.datastructures.Dijkstra

Decoration key for entries in the priority queue

Edge - interface net.datastructures.Edge.

An interface for an edge of a graph.

ElementIterator - class net.datastructures.ElementIterator.

A simple iterator class for lists.

ElementIterator() - Constructor for class net.datastructures.ElementIterator

ElementIterator(List) - Constructor for class net.datastructures.ElementIterator

Creates an element iterator over the given list.

EmptyDequeException - exception net.datastructures.EmptyDequeException.

Runtime exception thrown when one tries to perform an access or removal operation on an empty deque.

EmptyDequeException(String) - Constructor for class net.datastructures.EmptyDequeException

EmptyListException - exception net.datastructures.EmptyListException.

Thrown when a list cannot fulfill the requested operation because it is empty.

EmptyListException(String) - Constructor for class net.datastructures.EmptyListException

EmptyPriorityQueueException - exception net.datastructures.EmptyPriorityQueueException.

Thrown when a priority queue cannot fulfill the requested operation because it is empty.

EmptyPriorityQueueException(String) - Constructor for class net.datastructures.EmptyPriorityQueueException

EmptyQueueException - exception net.datastructures.EmptyQueueException.

Runtime exception thrown when one tries to perform operation front or dequeue on an empty queue.

EmptyQueueException(String) - Constructor for class net.datastructures.EmptyQueueException

EmptyStackException - exception net.datastructures.EmptyStackException.

Runtime exception thrown when one tries to perform operation top or pop on an empty stack.

EmptyStackException(String) - Constructor for class net.datastructures.EmptyStackException

EmptyTreeException - exception net.datastructures.EmptyTreeException.

Runtime exception thrown when one tries to access the root of an empty tree.

EmptyTreeException(String) - Constructor for class net.datastructures.EmptyTreeException

Entry - interface net.datastructures.Entry.

Interface for a key-value pair entry

EqualityTester - interface net.datastructures.EqualityTester.

An interface for an equality tester, used to determine whether two objects are equal.

edges() - Method in class net.datastructures.AdjacencyListGraph

Return an iterator over the edges of the graph

edges() - Method in interface net.datastructures.Graph

Return an iterator over the edges of the graph

elem - Variable in class net.datastructures.AdjacencyListGraph.MyPosition

The element stored at this position.

elemAtRank(int) - Method in class net.datastructures.ArrayVector

Returns the element stored at the given rank.

elemAtRank(int) - Method in class net.datastructures.NodeSequence

Returns the element stored at the given rank; O(n) time

elemAtRank(int) - Method in interface net.datastructures.Vector

Returns the element stored at the given rank.

element() - Method in class net.datastructures.AdjacencyListGraph.MyPosition

Returns the element stored at this position.

element() - Method in class net.datastructures.BTNode

element() - Method in class net.datastructures.DNode

element() - Method in interface net.datastructures.Position

Returns the element stored at this position.

element() - Method in class net.datastructures.VectorCompleteBinaryTree.VectorNode

elements() - Method in class net.datastructures.LinkedBinaryTree

Returns an iterator of the elements stored at the nodes

elements() - Method in interface net.datastructures.List

Returns an iterator of all the elements in the list.

elements() - Method in class net.datastructures.NodeList

Returns an iterator of all the elements in the list.

elements() - Method in interface net.datastructures.Tree

Return an iterator of the elements stored in the tree.

elements() - Method in class net.datastructures.VectorCompleteBinaryTree

Returns an iterator of the elements stored at all nodes in the tree.

endVertices() - Method in class net.datastructures.AdjacencyListGraph.MyEdge

Returns the end vertices of the edge.

endVertices(Edge) - Method in class net.datastructures.AdjacencyListGraph

Return the endvertices of a edge in an array of length 2

endVertices(Edge) - Method in interface net.datastructures.Graph

Return the endvertices of a vertex as an array of length 2

enqueue(Object) - Method in class net.datastructures.NodeQueue

enqueue(Object) - Method in interface net.datastructures.Queue

Inserts an element at the rear of the queue.

entries() - Method in class net.datastructures.BinarySearchTree

Returns an iterator containing all entries in the tree.

entries() - Method in interface net.datastructures.Dictionary

Returns an iterator containing all the entries in the dictionary.

entry(Position) - Method in class net.datastructures.BinarySearchTree

Extract the entry at a given node of the tree.

entry(Position) - Method in class net.datastructures.HeapPriorityQueue

Returns the entry stored at a heap node.

execute(Graph, Vertex, Object) - Method in class net.datastructures.ConnectivityDFS

Executes the DFS algorithm.

execute(Graph, Vertex, Object) - Method in class net.datastructures.DFS

Execute a depth first search traversal on graph g, starting from a vertex v, optionally passing in an information object (info)

execute(Graph, Vertex, Object) - Method in class net.datastructures.Dijkstra

Executes Dijkstra's algorithm.

execute(Graph, Vertex, Object) - Method in class net.datastructures.FindCycleDFS

Executes the DFS algorithm.

execute(Graph, Vertex, Object) - Method in class net.datastructures.FindPathDFS

expandExternal(Position, Object, Object) - Method in class net.datastructures.LinkedBinaryTree

Expand an external node into an internal node with two external node children

F

FindCycleDFS - class net.datastructures.FindCycleDFS.

A specialization of a generic DFS used to find a cycle in a graph.

FindCycleDFS() - Constructor for class net.datastructures.FindCycleDFS

FindPathDFS - class net.datastructures.FindPathDFS.

This class specializes DFS to find a path between the start vertex and a given target vertex.

FindPathDFS() - Constructor for class net.datastructures.FindPathDFS

FullStackException - exception net.datastructures.FullStackException.

Runtime exception thrown when the capacity of the array used by an ArrayStack has been exceeded.

FullStackException(String) - Constructor for class net.datastructures.FullStackException

find(Object) - Method in class net.datastructures.BinarySearchTree

Returns an entry containing the given key.

find(Object) - Method in interface net.datastructures.Dictionary

Returns an entry containing the given key, or null if no such entry exists.

findAll(Object) - Method in class net.datastructures.BinarySearchTree

Returns an iterator containing all entries containing the given key.

findAll(Object) - Method in interface net.datastructures.Dictionary

Returns an iterator containing all the entries containing the given key, or an empty iterator if no such entries exist.

findEntry(Object) - Method in class net.datastructures.HashTable

Helper search method - returns index of found key or -index-1, where index is the index of an empty or available slot.

finishVisit(Vertex) - Method in class net.datastructures.DFS

Called after we finish the visit for a vertex (v).

finishVisit(Vertex) - Method in class net.datastructures.FindCycleDFS

finishVisit(Vertex) - Method in class net.datastructures.FindPathDFS

first() - Method in interface net.datastructures.Deque

Gets the first element (without modifying the deque).

first() - Method in interface net.datastructures.List

Returns the first node in the list.

first() - Method in class net.datastructures.NodeDeque

Inspect the first element without modifying the deque.

first() - Method in class net.datastructures.NodeList

Returns the first position in the list; O(1) time

front() - Method in class net.datastructures.NodeQueue

front() - Method in interface net.datastructures.Queue

Inspects the element at the front of the queue.

G

G - Variable in class net.datastructures.DFS

Graph - interface net.datastructures.Graph.

An interface for a graph.

get(Object) - Method in class net.datastructures.HashTable

Returns the value associated with a key.

get(Object) - Method in interface net.datastructures.Map

Returns the value associated with a key.

getDist(Vertex) - Method in class net.datastructures.Dijkstra

Get the distance of a vertex from the source vertex.

getDist(Entry) - Method in class net.datastructures.Dijkstra

Get the distance of a vertex given its entry

getElement() - Method in class net.datastructures.DLNode

getElement() - Method in class net.datastructures.Node

getEntry(Vertex) - Method in class net.datastructures.Dijkstra

Get the entry decoration of a vertex.

getEntry(Position) - Method in class net.datastructures.HeapAdaptablePriorityQueue

Returns the entry stored at a heap node.

getHeight() - Method in class net.datastructures.AVLTree.AVLNode

getLeft() - Method in class net.datastructures.BTNode

getLeft() - Method in interface net.datastructures.BTPosition

getNext() - Method in class net.datastructures.DLNode

getNext() - Method in class net.datastructures.DNode

getNext() - Method in class net.datastructures.Node

getParent() - Method in class net.datastructures.BTNode

getParent() - Method in interface net.datastructures.BTPosition

getPrev() - Method in class net.datastructures.DLNode

getPrev() - Method in class net.datastructures.DNode

getRight() - Method in class net.datastructures.BTNode

getRight() - Method in interface net.datastructures.BTPosition

getVertex(Entry) - Method in class net.datastructures.Dijkstra

Get the vertex associated with an entry

graph - Variable in class net.datastructures.Dijkstra

Input graph.

H

HashTable - class net.datastructures.HashTable.

A hash table data structure that uses linear probing to handle collisions.

HashTable() - Constructor for class net.datastructures.HashTable

Creates a hash table with initial capacity 1023.

HashTable(int, EqualityTester) - Constructor for class net.datastructures.HashTable

Creates a hash table with the given capacity and equality tester.

HashTable.DefaultEqualityTester - class net.datastructures.HashTable.DefaultEqualityTester.

An inner class for a simple equality tester.

HashTable.HashEntry - class net.datastructures.HashTable.HashEntry.

Nested class for an entry in a hash table.

HeapAdaptablePriorityQueue - class net.datastructures.HeapAdaptablePriorityQueue.

Realization of an adaptable priority queue by means of a heap.

HeapAdaptablePriorityQueue() - Constructor for class net.datastructures.HeapAdaptablePriorityQueue

Creates an empty heap with a default comparator.

HeapAdaptablePriorityQueue(Comparator) - Constructor for class net.datastructures.HeapAdaptablePriorityQueue

Creates an empty heap with the given comparator.

HeapAdaptablePriorityQueue.LocationAwareEntry - class net.datastructures.HeapAdaptablePriorityQueue.LocationAwareEntry.

Inner class for a location-aware entry.

HeapAdaptablePriorityQueue.LocationAwareEntry(Object, Object) - Constructor for class net.datastructures.HeapAdaptablePriorityQueue.LocationAwareEntry

HeapAdaptablePriorityQueue.LocationAwareEntry(Object, Object, Position) - Constructor for class net.datastructures.HeapAdaptablePriorityQueue.LocationAwareEntry

HeapPriorityQueue - class net.datastructures.HeapPriorityQueue.

Realization of a priority queue by means of a heap.

HeapPriorityQueue() - Constructor for class net.datastructures.HeapPriorityQueue

Creates an empty heap with the default comparator.

HeapPriorityQueue(Comparator) - Constructor for class net.datastructures.HeapPriorityQueue

Creates an empty heap with the given comparator.

HeapPriorityQueue.DefaultComparator - class net.datastructures.HeapPriorityQueue.DefaultComparator.

Inner class for a comparator that uses the natural ordering of keys.

HeapPriorityQueue.DefaultComparator() - Constructor for class net.datastructures.HeapPriorityQueue.DefaultComparator

HeapPriorityQueue.MyEntry - class net.datastructures.HeapPriorityQueue.MyEntry.

Inner class for heap entries.

HeapPriorityQueue.MyEntry(Object, Object) - Constructor for class net.datastructures.HeapPriorityQueue.MyEntry

hasLeft(Position) - Method in interface net.datastructures.BinaryTree

Returns whether a node has a left child.

hasLeft(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns whether a node has a left child.

hasLeft(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns whether v has a left child.

hasNext() - Method in class net.datastructures.ElementIterator

Returns whether the iterator has a next object.

hasNext() - Method in class net.datastructures.PositionIterator

Returns whether the iterator has a next object.

hasRedChild(Position) - Method in class net.datastructures.RBTree

Returns whether a node has a red child.

hasRight(Position) - Method in interface net.datastructures.BinaryTree

Returns whether a node has a right child.

hasRight(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns whether a node has a right child.

hasRight(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns whether v has a right child.

hashValue(Object) - Method in class net.datastructures.HashTable

Hash function applying MAD method to default hash code.

head - Variable in class net.datastructures.NodeQueue

header - Variable in class net.datastructures.NodeDeque

header - Variable in class net.datastructures.NodeList

height - Variable in class net.datastructures.AVLTree.AVLNode

height(Position) - Method in class net.datastructures.AVLTree

Returns the height of a node (call back to an AVLNode).

I

I - Variable in class net.datastructures.AdjacencyListGraph.MyEdge

The positions of the entries for the edge in the incidence containers of the end vertices.

I - Variable in class net.datastructures.AdjacencyListGraph.MyVertex

Incidence container of the vertex.

INFINITE - Static variable in class net.datastructures.Dijkstra

Infinity value.

InvalidEntryException - exception net.datastructures.InvalidEntryException.

Thrown when an entry is discovered to be invalid.

InvalidEntryException(String) - Constructor for class net.datastructures.InvalidEntryException

InvalidKeyException - exception net.datastructures.InvalidKeyException.

Thrown when a key is determined to be invalid.

InvalidKeyException(String) - Constructor for class net.datastructures.InvalidKeyException

InvalidPositionException - exception net.datastructures.InvalidPositionException.

Thrown when a position is determined to be invalid.

InvalidPositionException(String) - Constructor for class net.datastructures.InvalidPositionException

InvalidPositionException() - Constructor for class net.datastructures.InvalidPositionException

incidences() - Method in class net.datastructures.AdjacencyListGraph.MyEdge

Returns the positions of the edge in the incidence containers of its end vertices.

incidentEdges() - Method in class net.datastructures.AdjacencyListGraph.MyVertex

Returns the incident edges on this vertex.

incidentEdges(Vertex) - Method in class net.datastructures.AdjacencyListGraph

Return an iterator over the edges incident on a vertex

incidentEdges(Vertex) - Method in interface net.datastructures.Graph

Return an iterator over the edges incident on a vertex

index() - Method in class net.datastructures.VectorCompleteBinaryTree.VectorNode

init(Graph) - Method in class net.datastructures.DFS

Initialize the graph g for a traversal.

initResult() - Method in class net.datastructures.DFS

Initializes result (called first, once per vertex visited).

inorderPositions(Position, List) - Method in class net.datastructures.LinkedBinaryTree

Creates a list storing the the nodes in the subtree of a node, ordered according to the inorder traversal of the subtree.

inorderPositions(Position, List, int) - Method in class net.datastructures.VectorCompleteBinaryTree

Fills a list according to an inorder traversal.

insert(Object, Object) - Method in class net.datastructures.AVLTree

Inserts an item into the dictionary and returns the newly created entry.

insert(Object, Object) - Method in class net.datastructures.BinarySearchTree

Inserts an entry into the tree and returns the newly created entry.

insert(Object, Object) - Method in interface net.datastructures.Dictionary

Inserts an item into the dictionary.

insert(Object, Object) - Method in class net.datastructures.HeapAdaptablePriorityQueue

Inserts a key-value pair and returns the entry created.

insert(Object, Object) - Method in class net.datastructures.HeapPriorityQueue

Inserts a key-value pair and return the entry created.

insert(Object, Object) - Method in interface net.datastructures.PriorityQueue

Inserts a key-value pair and return the entry created.

insert(Object, Object) - Method in class net.datastructures.RBTree

Inserts an item into the dictionary and returns the newly created entry.

insert(Object, Object) - Method in class net.datastructures.SortedListAdaptablePriorityQueue

Inserts a key-value pair and returns the entry created.

insert(Object, Object) - Method in class net.datastructures.SortedListPriorityQueue

Inserts a key-value pair and return the entry created.

insertAfter(Position, Object) - Method in interface net.datastructures.List

Inserts an element after the given node in the list.

insertAfter(Position, Object) - Method in class net.datastructures.NodeList

Insert the given element after the given position, returning the new position; O(1) time

insertAtExternal(Position, Entry) - Method in class net.datastructures.BinarySearchTree

Auxiliary method for inserting an entry at an external node

insertAtRank(int, Object) - Method in class net.datastructures.ArrayVector

Inserts an element at the given rank.

insertAtRank(int, Object) - Method in class net.datastructures.NodeSequence

Inserts an element at the given rank; O(n) time.

insertAtRank(int, Object) - Method in interface net.datastructures.Vector

Inserts an element at the given rank.

insertBefore(Position, Object) - Method in interface net.datastructures.List

Inserts an element before the given node in the list.

insertBefore(Position, Object) - Method in class net.datastructures.NodeList

Insert the given element before the given position, returning the new position; O(1) time

insertEdge(Vertex, Vertex, Object) - Method in class net.datastructures.AdjacencyListGraph

Insert and return a new edge with a given element between two vertices

insertEdge(Vertex, Vertex, Object) - Method in interface net.datastructures.Graph

Insert and return a new edge with a given element between two vertices

insertEntry(Entry) - Method in class net.datastructures.SortedListPriorityQueue

Auxiliary method used for insertion.

insertFirst(Object) - Method in interface net.datastructures.Deque

Insert an element at the beginning.

insertFirst(Object) - Method in interface net.datastructures.List

Inserts an element at the front of the list.

insertFirst(Object) - Method in class net.datastructures.NodeDeque

insertFirst(Object) - Method in class net.datastructures.NodeList

Insert the given element at the beginning of the list, returning the new position; O(1) time

insertIncidence(Edge) - Method in class net.datastructures.AdjacencyListGraph.MyVertex

Inserts an edge into the incidence container of this vertex.

insertLast(Object) - Method in interface net.datastructures.Deque

Insert an element at the end.

insertLast(Object) - Method in interface net.datastructures.List

Inserts and element at the back of the list.

insertLast(Object) - Method in class net.datastructures.NodeDeque

insertLast(Object) - Method in class net.datastructures.NodeList

Insert the given element at the end of the list, returning the new position; O(1) time

insertLeft(Position, Object) - Method in class net.datastructures.LinkedBinaryTree

Inserts a left child at a given node.

insertRight(Position, Object) - Method in class net.datastructures.LinkedBinaryTree

Inserts a right child at a given node.

insertVertex(Object) - Method in class net.datastructures.AdjacencyListGraph

Insert and return a new vertex with a given element

insertVertex(Object) - Method in interface net.datastructures.Graph

Insert and return a new vertex with a given element

isBalanced(Position) - Method in class net.datastructures.AVLTree

Returns whether a node has balance factor between -1 and 1.

isDone() - Method in class net.datastructures.DFS

Determines whether the traversal is done early.

isDone() - Method in class net.datastructures.FindCycleDFS

isDone() - Method in class net.datastructures.FindPathDFS

isEmpty() - Method in class net.datastructures.ArrayStack

O(1) time.

isEmpty() - Method in class net.datastructures.ArrayVector

Returns whether the vector is empty.

isEmpty() - Method in class net.datastructures.BinarySearchTree

Returns whether the tree is empty.

isEmpty() - Method in interface net.datastructures.Deque

Tests if this deque is empty

isEmpty() - Method in interface net.datastructures.Dictionary

Returns whether the dictionary is empty.

isEmpty() - Method in class net.datastructures.HashTable

Returns whether or not the table is empty.

isEmpty() - Method in class net.datastructures.HeapPriorityQueue

Returns whether the heap is empty.

isEmpty() - Method in class net.datastructures.LinkedBinaryTree

Returns whether the tree is empty.

isEmpty() - Method in interface net.datastructures.List

Returns whether the list is empty.

isEmpty() - Method in interface net.datastructures.Map

Returns whether the map is empty.

isEmpty() - Method in class net.datastructures.NodeDeque

This function returns true if and only if the deque is empty

isEmpty() - Method in class net.datastructures.NodeList

Returns whether the list is empty; O(1) time

isEmpty() - Method in class net.datastructures.NodeQueue

isEmpty() - Method in class net.datastructures.NodeStack

isEmpty() - Method in interface net.datastructures.PriorityQueue

Returns whether the priority queue is empty.

isEmpty() - Method in interface net.datastructures.Queue

Returns whether the queue is empty.

isEmpty() - Method in class net.datastructures.SortedListPriorityQueue

Returns whether the priority queue is empty.

isEmpty() - Method in interface net.datastructures.Stack

Return whether the stack is empty.

isEmpty() - Method in interface net.datastructures.Tree

Returns whether the tree is empty.

isEmpty() - Method in interface net.datastructures.Vector

Returns whether the vector is empty.

isEmpty() - Method in class net.datastructures.VectorCompleteBinaryTree

Returns whether the tree is empty.

isEqualTo(Object, Object) - Method in interface net.datastructures.EqualityTester

Returns whether two objects are equal.

isEqualTo(Object, Object) - Method in class net.datastructures.HashTable.DefaultEqualityTester

Returns whether the two objects are equal.

isExternal(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns whether a node is external.

isExternal(Position) - Method in interface net.datastructures.Tree

Returns whether a given node is external.

isExternal(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns whether v is an external node.

isFirst(Position) - Method in class net.datastructures.NodeList

Returns whether a position is the first one; O(1) time

isInternal(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns whether a node is internal.

isInternal(Position) - Method in interface net.datastructures.Tree

Returns whether a given node is internal.

isInternal(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns whether v is an internal node.

isLast(Position) - Method in class net.datastructures.NodeList

Returns whether a position is the last one; O(1) time

isPosRed(Position) - Method in class net.datastructures.RBTree

Returns whether a node is red.

isRed - Variable in class net.datastructures.RBTree.RBNode

isRed() - Method in class net.datastructures.RBTree.RBNode

isRoot(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns whether a node is the root.

isRoot(Position) - Method in interface net.datastructures.Tree

Returns whether a given node is the root of the tree.

isRoot(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns whether v is the root node.

isVisited(DecorablePosition) - Method in class net.datastructures.DFS

Test if a position has been visited.

K

k - Variable in class net.datastructures.SortedListPriorityQueue.MyEntry

key - Variable in class net.datastructures.BinarySearchTree.BSTEntry

key() - Method in class net.datastructures.BinarySearchTree.BSTEntry

key(Position) - Method in class net.datastructures.BinarySearchTree

Extract the key of the entry at a given node of the tree.

key() - Method in interface net.datastructures.Entry

Returns the key stored in this entry.

key() - Method in class net.datastructures.HashTable.HashEntry

key - Variable in class net.datastructures.HeapPriorityQueue.MyEntry

key() - Method in class net.datastructures.HeapPriorityQueue.MyEntry

key(Position) - Method in class net.datastructures.HeapPriorityQueue

Returns the key stored at a heap node.

key() - Method in class net.datastructures.SortedListPriorityQueue.MyEntry

key(Position) - Method in class net.datastructures.SortedListPriorityQueue

Returns the key stored at a given node.

keys() - Method in class net.datastructures.HashTable

Returns an iterator of keys.

keys() - Method in interface net.datastructures.Map

Returns an iterator of all keys in the map.

L

L - Variable in class net.datastructures.SortedListPriorityQueue

LinkedBinaryTree - class net.datastructures.LinkedBinaryTree.

An implementation of the BinaryTree interface by means of a linked structure.

LinkedBinaryTree() - Constructor for class net.datastructures.LinkedBinaryTree

Creates an empty binary tree.

List - interface net.datastructures.List.

An interface for a list.

last() - Method in interface net.datastructures.Deque

Gets the last element (without modifying the deque).

last() - Method in interface net.datastructures.List

Returns the last node in the list.

last() - Method in class net.datastructures.NodeDeque

last() - Method in class net.datastructures.NodeList

Returns the last position in the list; O(1) time

left(Position) - Method in interface net.datastructures.BinaryTree

Returns the left child of a node.

left(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns the left child of a node.

left(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns the left child of v.

list - Variable in class net.datastructures.ElementIterator

list - Variable in class net.datastructures.PositionIterator

loc - Variable in class net.datastructures.AdjacencyListGraph.MyEdge

The position of the edge in the edge container of the graph.

loc - Variable in class net.datastructures.AdjacencyListGraph.MyVertex

Position of the vertex in the vertex container of the graph.

loc - Variable in class net.datastructures.HeapAdaptablePriorityQueue.LocationAwareEntry

location() - Method in class net.datastructures.AdjacencyListGraph.MyEdge

Returns the position of the edge in the edge container of the graph.

location() - Method in class net.datastructures.AdjacencyListGraph.MyVertex

Returns the position of this vertex in the vertex container of the graph.

location() - Method in class net.datastructures.HeapAdaptablePriorityQueue.LocationAwareEntry

location() - Method in class net.datastructures.SortedListAdaptablePriorityQueue.LocationAwareEntry

M

Map - interface net.datastructures.Map.

An interface for a map which binds a key uniquely to a value.

main(String[]) - Static method in class net.datastructures.Sort

makeBlack() - Method in class net.datastructures.RBTree.RBNode

makeRed() - Method in class net.datastructures.RBTree.RBNode

merge(List, List, Comparator, List) - Static method in class net.datastructures.Sort

Merge two sorted lists, L1 and L2, into a sorted list L.

merge(Object[], Object[], Comparator, int, int) - Static method in class net.datastructures.Sort

mergeSort(List, Comparator) - Static method in class net.datastructures.Sort

Sort the elements of list L in nondecreasing order according to comparator c, using the merge-sort algorithm.

mergeSort(Object[], Comparator) - Static method in class net.datastructures.Sort

Sort an array of objects with a comparator using nonrecursive merge sort.

min() - Method in class net.datastructures.HeapPriorityQueue

Returns but does not remove an entry with minimum key.

min() - Method in interface net.datastructures.PriorityQueue

Returns but does not remove an entry with minimum key.

min() - Method in class net.datastructures.SortedListPriorityQueue

Returns but does not remove an entry with minimum key.

N

N - Variable in class net.datastructures.HashTable

Node - class net.datastructures.Node.

Node of a singly linked list, which stores references to its element and to the next node in the list.

Node() - Constructor for class net.datastructures.Node

Creates a node with null references to its element and next node.

Node(Object, Node) - Constructor for class net.datastructures.Node

Creates a node with the given element and next node.

NodeDeque - class net.datastructures.NodeDeque.

Implementation of the Deque interface by means of a doubly linked list.

NodeDeque() - Constructor for class net.datastructures.NodeDeque

Creates an empty deque.

NodeList - class net.datastructures.NodeList.

Realization of a List using a doubly-linked list of nodes.

NodeList() - Constructor for class net.datastructures.NodeList

Constructor that creates an empty list; O(1) time

NodeQueue - class net.datastructures.NodeQueue.

Realization of a queue by means of a singly-linked list of nodes.

NodeQueue() - Constructor for class net.datastructures.NodeQueue

Creates an empty queue.

NodeSequence - class net.datastructures.NodeSequence.

Implementation of a sequence by means of a doubly linked list.

NodeSequence() - Constructor for class net.datastructures.NodeSequence

NodeStack - class net.datastructures.NodeStack.

Implementation of a stack by means of a singly linked list.

NodeStack() - Constructor for class net.datastructures.NodeStack

Creates an empty stack.

NonEmptyTreeException - exception net.datastructures.NonEmptyTreeException.

Runtime exception thrown when one tries to create the root of a tree that is not empty.

NonEmptyTreeException(String) - Constructor for class net.datastructures.NonEmptyTreeException

n - Variable in class net.datastructures.HashTable

net.datastructures - package net.datastructures

next() - Method in class net.datastructures.ElementIterator

Returns the next object in the iterator.

next(Position) - Method in interface net.datastructures.List

Returns the node after a given node in the list.

next(Position) - Method in class net.datastructures.NodeList

Returns the position after the given one; O(1) time

next() - Method in class net.datastructures.PositionIterator

Returns the next object in the iterator.

numElts - Variable in class net.datastructures.NodeList

numEntries - Variable in class net.datastructures.BinarySearchTree

O

opposite(Vertex, Edge) - Method in class net.datastructures.AdjacencyListGraph

Return the other endvertex of an incident edge

opposite(Vertex, Edge) - Method in interface net.datastructures.Graph

Return the other endvertex of an incident edge

P

Position - interface net.datastructures.Position.

An interface for a position, which is a holder object storing a single element.

PositionIterator - class net.datastructures.PositionIterator.

A simple iterator class for lists.

PositionIterator() - Constructor for class net.datastructures.PositionIterator

PositionIterator(List) - Constructor for class net.datastructures.PositionIterator

Creates an iterator over the given list.

PriorityQueue - interface net.datastructures.PriorityQueue.

Interface for the priority queue ADT

parent(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns the parent of a node.

parent(Position) - Method in interface net.datastructures.Tree

Returns the parent of a given node.

parent(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns the parent of v.

path - Variable in class net.datastructures.FindPathDFS

pop() - Method in class net.datastructures.ArrayStack

O(1) time.

pop() - Method in class net.datastructures.NodeStack

pop() - Method in interface net.datastructures.Stack

Remove the top element from the stack.

pos - Variable in class net.datastructures.BinarySearchTree.BSTEntry

position() - Method in class net.datastructures.BinarySearchTree.BSTEntry

positions() - Method in class net.datastructures.LinkedBinaryTree

Returns an iterator of the tree nodes.

positions() - Method in interface net.datastructures.List

Returns an iterator of all the nodes in the list.

positions() - Method in class net.datastructures.NodeList

Returns an iterator of all the nodes in the list.

positions() - Method in interface net.datastructures.Tree

Returns an iterator of the nodes stored in the tree.

positions() - Method in class net.datastructures.VectorCompleteBinaryTree

Returns an iterator of all nodes in the tree.

prev(Position) - Method in interface net.datastructures.List

Returns the node before a given node in the list.

prev(Position) - Method in class net.datastructures.NodeList

Returns the position before the given one; O(1) time

push(Object) - Method in class net.datastructures.ArrayStack

O(1) time.

push(Object) - Method in class net.datastructures.NodeStack

push(Object) - Method in interface net.datastructures.Stack

Insert an element at the top of the stack.

put(Object, Object) - Method in class net.datastructures.HashTable

Put a key-value pair in the map, replacing previous one if it exists.

put(Object, Object) - Method in interface net.datastructures.Map

Put a key-value pair in the map, replacing previous one if it exists.

Q

Q - Variable in class net.datastructures.Dijkstra

Auxiliary priority queue.

Queue - interface net.datastructures.Queue.

Interface for a queue: a collection of elements that are inserted and removed according to the first-in first-out principle.

quickSort(List, Comparator) - Static method in class net.datastructures.Sort

Sort the elements of list L in nondecreasing order according to comparator c, using a list-based implementation of the quicksort algorithm.

quickSort(Object[], Comparator) - Static method in class net.datastructures.Sort

Sort the elements of array S in nondecreasing order according to comparator c, using the quick-sort algorithm.

R

RBTree - class net.datastructures.RBTree.

Realization of a dictionary by means of a red-black tree.

RBTree() - Constructor for class net.datastructures.RBTree

RBTree(Comparator) - Constructor for class net.datastructures.RBTree

RBTree.RBNode - class net.datastructures.RBTree.RBNode.

Nested class for the nodes of a red-black tree

rankOf(Position) - Method in class net.datastructures.NodeSequence

Returns the rank of the element stored at the given position; O(n) time.

rankOf(Position) - Method in interface net.datastructures.Sequence

Returns the rank of the element stored at the given position.

reached - Variable in class net.datastructures.ConnectivityDFS

rebalance(Position) - Method in class net.datastructures.AVLTree

Rebalance method called by insert and remove.

redChild(Position) - Method in class net.datastructures.RBTree

Returns a red child of a node.

rehash() - Method in class net.datastructures.HashTable

Doubles the size of the hash table and rehashes all the entries.

remedyDoubleBlack(Position) - Method in class net.datastructures.RBTree

Remedies a double black violation at a given node caused by removal.

remedyDoubleRed(Position) - Method in class net.datastructures.RBTree

Remedies a double red violation at a given node caused by insertion.

remove(Entry) - Method in class net.datastructures.AVLTree

Removes and returns an entry from the dictionary.

remove(Entry) - Method in interface net.datastructures.AdaptablePriorityQueue

Removes and returns an entry from the priority queue.

remove(Entry) - Method in class net.datastructures.BinarySearchTree

Removes and returns a given entry.

remove() - Method in interface net.datastructures.CompleteBinaryTree

Removes and returns the element stored in the last node of the tree.

remove(Entry) - Method in interface net.datastructures.Dictionary

Removes and returns the given entry from the dictionary.

remove() - Method in class net.datastructures.ElementIterator

Throws an UnsupportedOperationException in all cases, because removal is not a supported operation in this iterator.

remove(Object) - Method in class net.datastructures.HashTable

Removes the key-value pair with a specified key.

remove(Entry) - Method in class net.datastructures.HeapAdaptablePriorityQueue

Removes and returns the given entry from the heap.

remove(Position) - Method in class net.datastructures.LinkedBinaryTree

Removes a node with zero or one child.

remove(Position) - Method in interface net.datastructures.List

Removes a node from the list.

remove(Object) - Method in interface net.datastructures.Map

Removes the key-value pair with a specified key.

remove(Position) - Method in class net.datastructures.NodeList

Remove the given position from the list; O(1) time

remove() - Method in class net.datastructures.PositionIterator

Throws an UnsupportedOperationException in all cases, because removal is not a supported operation in this iterator.

remove(Entry) - Method in class net.datastructures.RBTree

Removes and returns the given entry from the dictionary.

remove(Entry) - Method in class net.datastructures.SortedListAdaptablePriorityQueue

Removes and returns the given entry.

remove() - Method in class net.datastructures.VectorCompleteBinaryTree

Removes and returns the element at the last node.

removeAboveExternal(Position) - Method in class net.datastructures.LinkedBinaryTree

Remove an external node v and replace its parent with v's sibling

removeAtRank(int) - Method in class net.datastructures.ArrayVector

Removes the element stored at the given rank.

removeAtRank(int) - Method in class net.datastructures.NodeSequence

Removes the element stored at the given rank; O(n) time.

removeAtRank(int) - Method in interface net.datastructures.Vector

Removes the element stored at the given rank.

removeEdge(Edge) - Method in class net.datastructures.AdjacencyListGraph

Remove an edge and return its element

removeEdge(Edge) - Method in interface net.datastructures.Graph

Remove an edge and return its element

removeEntry(Vertex) - Method in class net.datastructures.Dijkstra

Remove the entry decoration of a vertex

removeExternal(Position) - Method in class net.datastructures.BinarySearchTree

Auxiliary method for removing an external node and its parent

removeFirst() - Method in interface net.datastructures.Deque

Remove the element at the beginning.

removeFirst() - Method in class net.datastructures.NodeDeque

removeIncidence(Position) - Method in class net.datastructures.AdjacencyListGraph.MyVertex

Removes an edge from the incidence container of this vertex.

removeLast() - Method in interface net.datastructures.Deque

Remove the element at the end.

removeLast() - Method in class net.datastructures.NodeDeque

removeMin() - Method in class net.datastructures.HeapPriorityQueue

Removes and returns an entry with minimum key.

removeMin() - Method in interface net.datastructures.PriorityQueue

Removes and returns an entry with minimum key.

removeMin() - Method in class net.datastructures.SortedListPriorityQueue

Removes and returns an entry with minimum key.

removeVertex(Vertex) - Method in class net.datastructures.AdjacencyListGraph

Remove a vertex and all its incident edges and return the element stored at the removed vertex

removeVertex(Vertex) - Method in interface net.datastructures.Graph

Remove a vertex and all its incident edges and return the element stored at the removed vertex

replace(Position, Object) - Method in class net.datastructures.AdjacencyListGraph

Replace the element a given position (vertex or edge) with a new element and return the old element

replace(Position, Object) - Method in interface net.datastructures.Graph

Replace the element a given position (vertex or edge) with a new element and return the old element

replace(Position, Object) - Method in class net.datastructures.LinkedBinaryTree

Replaces the element at a node.

replace(Position, Object) - Method in interface net.datastructures.List

Replaces the element stored at the given node.

replace(Position, Object) - Method in class net.datastructures.NodeList

Replace the element at the given position with the new element and return the old element; O(1) time

replace(Position, Object) - Method in interface net.datastructures.Tree

Replaces the element stored at a given node.

replace(Position, Object) - Method in class net.datastructures.VectorCompleteBinaryTree

Replaces the element at v.

replaceAtRank(int, Object) - Method in class net.datastructures.ArrayVector

Replaces the element stored at the given rank.

replaceAtRank(int, Object) - Method in class net.datastructures.NodeSequence

Replaces the element stored at the given rank; O(n) time.

replaceAtRank(int, Object) - Method in interface net.datastructures.Vector

Replaces the element stored at the given rank.

replaceEntry(Position, Entry) - Method in class net.datastructures.BinarySearchTree

Replace an entry with a new entry (and reset the entry's location)

replaceEntry(Position, HeapAdaptablePriorityQueue.LocationAwareEntry) - Method in class net.datastructures.HeapAdaptablePriorityQueue

Replaces the element of the given position with the given location-aware entry.

replaceKey(Entry, Object) - Method in interface net.datastructures.AdaptablePriorityQueue

Replaces the key of an entry and returns the old key.

replaceKey(Entry, Object) - Method in class net.datastructures.HeapAdaptablePriorityQueue

Replaces the key of the given entry.

replaceKey(Entry, Object) - Method in class net.datastructures.SortedListAdaptablePriorityQueue

Replaces the key of the given entry.

replaceValue(Entry, Object) - Method in interface net.datastructures.AdaptablePriorityQueue

Replaces the value of an entry and returns the old value.

replaceValue(Entry, Object) - Method in class net.datastructures.HeapAdaptablePriorityQueue

Replaces the value of the given entry.

replaceValue(Entry, Object) - Method in class net.datastructures.SortedListAdaptablePriorityQueue

Replaces the value of the given entry.

restructure(Position) - Method in class net.datastructures.BinarySearchTree

Performs a tri-node restructuring.

result() - Method in class net.datastructures.DFS

Returns a result of a visit (if needed).

right(Position) - Method in interface net.datastructures.BinaryTree

Returns the right child of a node.

right(Position) - Method in class net.datastructures.LinkedBinaryTree

Returns the right child of a node.

right(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns the right child of v.

root - Variable in class net.datastructures.LinkedBinaryTree

root() - Method in class net.datastructures.LinkedBinaryTree

Returns the root of the tree.

root() - Method in interface net.datastructures.Tree

Returns the root of the tree.

root() - Method in class net.datastructures.VectorCompleteBinaryTree

Returns the root of the tree.

S

S - Variable in class net.datastructures.ArrayStack

Array used to implement the stack.

STATUS - Static variable in class net.datastructures.DFS

Sequence - interface net.datastructures.Sequence.

An interface for a sequence, a data structure supporting all operations of a vector and a list.

Sort - class net.datastructures.Sort.

Class containing various sorting algorithms.

Sort() - Constructor for class net.datastructures.Sort

SortedListAdaptablePriorityQueue - class net.datastructures.SortedListAdaptablePriorityQueue.

Implementation of a priority queue by means of a sorted list

SortedListAdaptablePriorityQueue() - Constructor for class net.datastructures.SortedListAdaptablePriorityQueue

Creates the priority queue with the default comparator.

SortedListAdaptablePriorityQueue(Comparator) - Constructor for class net.datastructures.SortedListAdaptablePriorityQueue

Creates the priority queue with the given comparator.

SortedListAdaptablePriorityQueue(List, Comparator) - Constructor for class net.datastructures.SortedListAdaptablePriorityQueue

Creates the priority queue with the given comparator and list.

SortedListAdaptablePriorityQueue.LocationAwareEntry - class net.datastructures.SortedListAdaptablePriorityQueue.LocationAwareEntry.

Inner class for a location-aware entry.

SortedListAdaptablePriorityQueue.LocationAwareEntry(Object, Object) - Constructor for class net.datastructures.SortedListAdaptablePriorityQueue.LocationAwareEntry

SortedListAdaptablePriorityQueue.LocationAwareEntry(Object, Object, Position) - Constructor for class net.datastructures.SortedListAdaptablePriorityQueue.LocationAwareEntry

SortedListPriorityQueue - class net.datastructures.SortedListPriorityQueue.

Realization of a priority queue by means of a sorted linked-list in nondecreasing order.

SortedListPriorityQueue() - Constructor for class net.datastructures.SortedListPriorityQueue

Creates the priority queue with the default comparator.

SortedListPriorityQueue(Comparator) - Constructor for class net.datastructures.SortedListPriorityQueue

Creates the priority queue with the given comparator.

SortedListPriorityQueue(List, Comparator) - Constructor for class net.datastructures.SortedListPriorityQueue

Creates the priority queue with the given comparator and list.

SortedListPriorityQueue.DefaultComparator - class net.datastructures.SortedListPriorityQueue.DefaultComparator.

Inner class for a default comparator using the natural ordering

SortedListPriorityQueue.DefaultComparator() - Constructor for class net.datastructures.SortedListPriorityQueue.DefaultComparator

SortedListPriorityQueue.MyEntry - class net.datastructures.SortedListPriorityQueue.MyEntry.

Inner class for entries

SortedListPriorityQueue.MyEntry(Object, Object) - Constructor for class net.datastructures.SortedListPriorityQueue.MyEntry

Stack - interface net.datastructures.Stack.

Interface for a stack: a collection of objects that are inserted and removed according to the last-in first-out principle.

scale - Variable in class net.datastructures.HashTable

setBlack(Position) - Method in class net.datastructures.RBTree

Colors a node black.

setColor(boolean) - Method in class net.datastructures.RBTree.RBNode

setColor(Position, boolean) - Method in class net.datastructures.RBTree

Sets the color of a node.

setComparator(Comparator) - Method in class net.datastructures.HeapPriorityQueue

Sets the comparator used for comparing items in the heap.

setComparator(Comparator) - Method in class net.datastructures.SortedListPriorityQueue

Sets the comparator for this priority queue.

setDist(Vertex, int) - Method in class net.datastructures.Dijkstra

Set the distance of a vertex.

setElement(Object) - Method in class net.datastructures.AdjacencyListGraph.MyPosition

Sets the element stored at this position.

setElement(Object) - Method in class net.datastructures.BTNode

setElement(Object) - Method in interface net.datastructures.BTPosition

setElement(Object) - Method in class net.datastructures.DLNode

setElement(Object) - Method in class net.datastructures.DNode

setElement(Object) - Method in class net.datastructures.Node

setElement(Object) - Method in class net.datastructures.VectorCompleteBinaryTree.VectorNode

setEntry(Vertex, Entry) - Method in class net.datastructures.Dijkstra

Set the entry decoration of a vertex

setHeight(int) - Method in class net.datastructures.AVLTree.AVLNode

setHeight(Position) - Method in class net.datastructures.AVLTree

Sets the height of an internal node (call back to an AVLNode).

setIncidences(Position, Position) - Method in class net.datastructures.AdjacencyListGraph.MyEdge

Sets the positions of the edge in the incidence containers of its end vertices.

setKey(Object) - Method in class net.datastructures.HeapAdaptablePriorityQueue.LocationAwareEntry

setKey(Object) - Method in class net.datastructures.SortedListAdaptablePriorityQueue.LocationAwareEntry

setLeft(BTPosition) - Method in class net.datastructures.BTNode

setLeft(BTPosition) - Method in interface net.datastructures.BTPosition

setLocation(Position) - Method in class net.datastructures.AdjacencyListGraph.MyEdge

Sets the position of the edge in the edge container of the graph.

setLocation(Position) - Method in class net.datastructures.AdjacencyListGraph.MyVertex

Sets the position of this vertex in the vertex container of the graph.

setLocation(Position) - Method in class net.datastructures.HeapAdaptablePriorityQueue.LocationAwareEntry

setLocation(Position) - Method in class net.datastructures.SortedListAdaptablePriorityQueue.LocationAwareEntry

setNext(DLNode) - Method in class net.datastructures.DLNode

setNext(DNode) - Method in class net.datastructures.DNode

setNext(Node) - Method in class net.datastructures.Node

setParent(BTPosition) - Method in class net.datastructures.BTNode

setParent(BTPosition) - Method in interface net.datastructures.BTPosition

setPrev(DLNode) - Method in class net.datastructures.DLNode

setPrev(DNode) - Method in class net.datastructures.DNode

setRed(Position) - Method in class net.datastructures.RBTree

Colors a node red.

setRight(BTPosition) - Method in class net.datastructures.BTNode

setRight(BTPosition) - Method in interface net.datastructures.BTPosition

setValue(Object) - Method in class net.datastructures.HashTable.HashEntry

setValue(Object) - Method in class net.datastructures.HeapAdaptablePriorityQueue.LocationAwareEntry

setValue(Object) - Method in class net.datastructures.SortedListAdaptablePriorityQueue.LocationAwareEntry

shift - Variable in class net.datastructures.HashTable

sibling(Position) - Method in class net.datastructures.LinkedBinaryTree

Return the sibling of a node

sibling(Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Returns the sibling of v.

size() - Method in class net.datastructures.ArrayStack

O(1) time.

size() - Method in class net.datastructures.ArrayVector

Returns the number of elements in the vector.

size() - Method in class net.datastructures.BinarySearchTree

Returns the number of entries in the tree.

size() - Method in interface net.datastructures.Deque

Gets the number of elements.

size() - Method in interface net.datastructures.Dictionary

Returns the number of entries in the dictionary.

size() - Method in class net.datastructures.HashTable

Returns the number of entries in the hash table.

size() - Method in class net.datastructures.HeapPriorityQueue

Returns the size of the heap.

size - Variable in class net.datastructures.LinkedBinaryTree

size() - Method in class net.datastructures.LinkedBinaryTree

Returns the number of nodes in the tree.

size() - Method in interface net.datastructures.List

Returns the number of elements in this list.

size() - Method in interface net.datastructures.Map

Returns the number of items in the map.

size - Variable in class net.datastructures.NodeDeque

size() - Method in class net.datastructures.NodeDeque

Return the size of the deque, that is the number of elements it has.

size() - Method in class net.datastructures.NodeList

Returns the number of elements in the list; O(1) time

size - Variable in class net.datastructures.NodeQueue

size() - Method in class net.datastructures.NodeQueue

size - Variable in class net.datastructures.NodeStack

size() - Method in class net.datastructures.NodeStack

size() - Method in interface net.datastructures.PriorityQueue

Returns the number of items in the priority queue.

size() - Method in interface net.datastructures.Queue

Returns the number of elements in the queue.

size() - Method in class net.datastructures.SortedListPriorityQueue

Returns the number of elements in the priority queue.

size() - Method in interface net.datastructures.Stack

Return the number of elements in the stack.

size() - Method in interface net.datastructures.Tree

Returns the number of nodes in the tree.

size() - Method in interface net.datastructures.Vector

Returns the number of elements in the vector.

size() - Method in class net.datastructures.VectorCompleteBinaryTree

Returns the number of (internal and external) nodes.

startVisit(Vertex) - Method in class net.datastructures.ConnectivityDFS

startVisit(Vertex) - Method in class net.datastructures.DFS

Called when we encounter a vertex (v).

startVisit(Vertex) - Method in class net.datastructures.FindCycleDFS

startVisit(Vertex) - Method in class net.datastructures.FindPathDFS

swap(Position, Position) - Method in class net.datastructures.RBTree

Swaps the colors and elements at the two nodes.

swapColor(Position, Position) - Method in class net.datastructures.RBTree

Swaps the colors of a and b if they are different and returns whether a was red.

swapElements(Position, Position) - Method in class net.datastructures.HeapAdaptablePriorityQueue

Swaps the elements of the two positions.

swapElements(Position, Position) - Method in class net.datastructures.HeapPriorityQueue

Swaps the elements of the two positions.

swapElements(Position, Position) - Method in class net.datastructures.LinkedBinaryTree

Swap the elements at two nodes

swapElements(Position, Position) - Method in class net.datastructures.NodeList

Swap the elements of two give positions; O(1) time

swapElements(Position, Position) - Method in class net.datastructures.VectorCompleteBinaryTree

Swaps the elements at two nodes.

T

T - Variable in class net.datastructures.HashTable

T - Variable in class net.datastructures.HeapPriorityQueue

T - Variable in class net.datastructures.VectorCompleteBinaryTree

Tree - interface net.datastructures.Tree.

An interface for a tree where nodes can have an arbitrary number of children.

tail - Variable in class net.datastructures.NodeQueue

tallerChild(Position) - Method in class net.datastructures.AVLTree

Return a child of p with height no smaller than that of the other child.

target - Variable in class net.datastructures.FindPathDFS

toString() - Method in class net.datastructures.AdjacencyListGraph.MyEdge

Returns a string representation of the edge via a tuple of vertices.

toString() - Method in class net.datastructures.AdjacencyListGraph.MyVertex

Returns a string representation of the element stored at this vertex.

toString() - Method in class net.datastructures.AdjacencyListGraph

Returns a string representation of the vertex and edge lists, separated by a newline.

toString() - Method in class net.datastructures.HeapPriorityQueue.MyEntry

toString() - Method in class net.datastructures.HeapPriorityQueue

Text visualization for debugging purposes

toString() - Method in class net.datastructures.NodeList

Returns a textual representation of the list

toString() - Method in class net.datastructures.NodeQueue

toString() - Method in class net.datastructures.SortedListPriorityQueue.MyEntry

toString() - Method in class net.datastructures.SortedListPriorityQueue

toString() - Method in class net.datastructures.VectorCompleteBinaryTree

Returns a String representing this complete binary tree.

top - Variable in class net.datastructures.ArrayStack

Index of the top element of the stack in the array.

top() - Method in class net.datastructures.ArrayStack

O(1) time.

top - Variable in class net.datastructures.NodeStack

top() - Method in class net.datastructures.NodeStack

top() - Method in interface net.datastructures.Stack

Inspect the element at the top of the stack.

trailer - Variable in class net.datastructures.NodeDeque

trailer - Variable in class net.datastructures.NodeList

traverseBack(Edge, Vertex) - Method in class net.datastructures.DFS

Called when we traverse a back edge (e) from a vertex (from).

traverseBack(Edge, Vertex) - Method in class net.datastructures.FindCycleDFS

traverseDiscovery(Edge, Vertex) - Method in class net.datastructures.DFS

Called when we traverse a discovery edge (e) from a vertex (from).

traverseDiscovery(Edge, Vertex) - Method in class net.datastructures.FindCycleDFS

traverseDiscovery(Edge, Vertex) - Method in class net.datastructures.FindPathDFS

treeSearch(Object, Position) - Method in class net.datastructures.BinarySearchTree

Auxiliary method used by find, insert, and remove.

U

UNVISITED - Static variable in class net.datastructures.DFS

unVisit(DecorablePosition) - Method in class net.datastructures.DFS

Mark a position as unvisited.

upHeap(Position) - Method in class net.datastructures.HeapPriorityQueue

Performs up-heap bubbling.

V

V - Variable in class net.datastructures.AdjacencyListGraph.MyEdge

The end vertices of the edge.

V - Variable in class net.datastructures.AdjacencyListGraph

VISITED - Static variable in class net.datastructures.DFS

Vector - interface net.datastructures.Vector.

Interface for a vector.

VectorCompleteBinaryTree - class net.datastructures.VectorCompleteBinaryTree.

A speedy implementation of the CompleteBinaryTree interface using a vector.

VectorCompleteBinaryTree() - Constructor for class net.datastructures.VectorCompleteBinaryTree

default constructor

VectorCompleteBinaryTree.VectorNode - class net.datastructures.VectorCompleteBinaryTree.VectorNode.

Nested class for a vector-based complete binary tree node.

VectorCompleteBinaryTree.VectorNode(Object, int) - Constructor for class net.datastructures.VectorCompleteBinaryTree.VectorNode

Vertex - interface net.datastructures.Vertex.

An interface for a vertex of a graph.

v - Variable in class net.datastructures.SortedListPriorityQueue.MyEntry

value - Variable in class net.datastructures.BinarySearchTree.BSTEntry

value() - Method in class net.datastructures.BinarySearchTree.BSTEntry

value(Position) - Method in class net.datastructures.BinarySearchTree

Extract the value of the entry at a given node of the tree.

value() - Method in interface net.datastructures.Entry

Returns the value stored in this entry.

value() - Method in class net.datastructures.HashTable.HashEntry

value - Variable in class net.datastructures.HeapPriorityQueue.MyEntry

value() - Method in class net.datastructures.HeapPriorityQueue.MyEntry

value() - Method in class net.datastructures.SortedListPriorityQueue.MyEntry

values() - Method in class net.datastructures.HashTable

Returns an iterator of values.

values() - Method in interface net.datastructures.Map

Returns an iterator of all values in the map.

vertices() - Method in class net.datastructures.AdjacencyListGraph

Return an iterator over the vertices of the graph

vertices() - Method in interface net.datastructures.Graph

Return an iterator over the vertices of the graph

visit(DecorablePosition) - Method in class net.datastructures.DFS

Mark a position as visited.

visitResult - Variable in class net.datastructures.DFS

W

WEIGHT - Variable in class net.datastructures.Dijkstra

Decoration key for edge weights

weight(Edge) - Method in class net.datastructures.Dijkstra

Get the weight of an edge

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