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

A

AdaptablePriorityQueue - interface pqueue.AdaptablePriorityQueue.

Extends the priority queue interface to support removal and reprioritization of elements.

add(Object) - Method in interface tree.CompleteBinaryTree

Adds a new external Position to the "end" of the heap tree -- as a child of an existing position, or as the root if the heap tree is empty.

addIntersection(Point, Integer) - Method in class geography.AddressFinder.Street

Add a new house number near the intersection at point p.

AddressFinder - class geography.AddressFinder.

Maps from a string like "3400 charles street" to a address nearby whose coordinates we actually know, such as 3398 N Charles St.

AddressFinder.Street - class geography.AddressFinder.Street.

A class that represents information about a particular street.

AddressFinder.Street(StreetSegment) - Constructor for class geography.AddressFinder.Street

Constructor: New street, no information about it yet.

addressFinder() - Method in class geography.Streetmap

Return an address finder for this street map.

AddressFinder() - Constructor for class geography.AddressFinder

Constructor: New address finder, contains no information yet.

addStreetSegment(StreetSegment) - Method in class geography.AddressFinder

In general, a StreetSegment specifies 2 intersections and up to 4 addresses (up to two per intersection).

addStreetSegment(StreetSegment) - Method in class geography.Streetmap

Adds a new street segment to the map.

AdjListDigraph - class graph.AdjListDigraph.

A directed graph in which each vertex stores its outgoing edges.

AdjListDigraph() - Constructor for class graph.AdjListDigraph

af - Variable in class geography.Streetmap

An object that can look up addresses on the map.

angleString(double) - Method in class geography.Route

Way to print angles for the user.

attrBestEdgeIn - Variable in class graph.Dijkstra

Backpointer attribute.

attrDist - Variable in class graph.Dijkstra

Distance attribute.

attrEntry - Variable in class graph.Dijkstra

Entry attribute.

Attribute - class container.Attribute.

An attribute of a Decorable object, such as a graph vertex.

Attribute(String) - Constructor for class container.Attribute

Constructor.

B

BinaryTree - interface tree.BinaryTree.

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

BoundaryViolationException - exception container.BoundaryViolationException.

BoundaryViolationException() - Constructor for class container.BoundaryViolationException

BoundaryViolationException(String) - Constructor for class container.BoundaryViolationException

C

children(Position) - Method in interface tree.Tree

Returns an iterator of the children of a given node.

clearAttributes(Vertex) - Method in class graph.Dijkstra

Clears this instance's attributes from v and all the vertices that can be reached from it by directed paths from v.

closestKeys(SortedMap, Object) - Static method in class geography.AddressFinder

Look up key in the SortedMap sm.

CompleteBinaryTree - interface tree.CompleteBinaryTree.

computePathTo(Vertex) - Method in class graph.Dijkstra

Run Dijkstra's algorithm until we know the shortest path from vertex vStart to vertex vEnd, or have explored the whole graph without finding such a path.

container - package container

Basic classes and interfaces that are useful for all containers (i.e., data structures meant to contain other objects).

D

DataFormatException - exception geography.DataFormatException.

Like NumberFormatException, this indicates that a string had the wrong format to be parsed by a constructor or method.

DataFormatException(String) - Constructor for class geography.DataFormatException

Decorable - interface container.Decorable.

In addition to storing its usual data, a class might allow users to "decorate" it with some extra temporary data.

degrees(double) - Static method in class geography.Point

descrip - Variable in class geography.Intersection

A description of the address, e.g., "3400 Charles St" or perhaps "Charles St at University Pkwy".

dest - Variable in class graph.StoredDirectedEdge

destination() - Method in interface graph.DirectedEdge

Vertex where this directed edge ends.

destination() - Method in class graph.StoredDirectedEdge

Digraph - interface graph.Digraph.

This is the simplest useful directed graph interface.

Dijkstra - class graph.Dijkstra.

A class to find shortest paths from a single start point to any end point.

Dijkstra(Digraph, Weighter, Object) - Constructor for class graph.Dijkstra

Convenience version of the constructor where the graph is keyed and the start vertex is specified by a key.

Dijkstra(Digraph, Weighter, Vertex) - Constructor for class graph.Dijkstra

Constructor that sets up a shortest-path problem.

DIR_NAMES - Static variable in class geography.Route

Direction names for evenly spaced points around the compass.

dirChange(DirectedEdge, DirectedEdge) - Static method in class geography.Route

Change in direction of a turn from e1 onto e2.

DirectedAdjListVertex - class graph.DirectedAdjListVertex.

A vertex in an AdjListDigraph.

DirectedAdjListVertex() - Constructor for class graph.DirectedAdjListVertex

DirectedEdge - interface graph.DirectedEdge.

A directed edge.

directionTo(Point) - Method in class geography.Point

The direction that you have to go from this point to get to p.

dirName(DirectedEdge) - Method in class geography.Route

Turns a direction into its printable name.

distanceString(double) - Method in class geography.Route

Turns a distance into printable form.

distanceTo(Point) - Method in class geography.Point

Distance from this point to another point, using the Haversine formula.

E

edgeDirection(DirectedEdge) - Static method in class geography.Streetmap

Given an edge of g, returns the direction of the street segment it represents, as a number in degrees from -180 to 180.

edgeLength(DirectedEdge) - Static method in class geography.Streetmap

Given an edge of g, returns the length in meters of the street segment it represents.

element - Variable in class graph.StoredDirectedEdge

element - Variable in class graph.StoredVertex

Element stored at this vertex.

element() - Method in interface container.Position

element() - Method in class graph.StoredDirectedEdge

Element stored on this edge.

element() - Method in class graph.StoredVertex

Get the element at this position.

elements() - Method in interface tree.Tree

Return an iterator of the elements stored in the tree.

EmptyPriorityQueueException - exception pqueue.EmptyPriorityQueueException.

Runtime exception thrown when one tries to get at the minimum element of an empty priority queue.

EmptyPriorityQueueException() - Constructor for class pqueue.EmptyPriorityQueueException

EmptyPriorityQueueException(String) - Constructor for class pqueue.EmptyPriorityQueueException

EmptyTreeException - exception tree.EmptyTreeException.

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

EmptyTreeException() - Constructor for class tree.EmptyTreeException

EmptyTreeException(String) - Constructor for class tree.EmptyTreeException

Entry - interface container.Entry.

Interface for a key-value pair entry

equal(Object, Object) - Method in interface container.EqualityTester

EqualityTester - interface container.EqualityTester.

Used to compare keys for equality, just as java.util.Comparator compares them for order.

equals(Object) - Method in class geography.Point

F

fig12_15() - Static method in class graph.HashKeyedDigraph

Returns the undirected, weighted graph from figure 12.15 of the textbook.

fig12_2() - Static method in class graph.HashKeyedDigraph

Returns the directed graph from figure 12.2 of the textbook.

finalize() - Method in class graph.Dijkstra

The finalizer for this Dijkstra instance.

findIntersectionNear(int) - Method in class geography.AddressFinder.Street

Finds the intersection closest to the given house number on this street.

findIntersectionNear(String) - Method in class geography.AddressFinder

Finds an intersection near this address.

findKeyedVertex(Object) - Method in class graph.HashKeyedDigraph

findKeyedVertex(Object) - Method in interface graph.KeyedDigraph

Return the vertex with key k.

findOrInsertKeyedVertex(Object) - Method in class graph.HashKeyedDigraph

findOrInsertKeyedVertex(Object) - Method in interface graph.KeyedDigraph

Return the vertex with key k.

findOrInsertStreet(StreetSegment) - Method in class geography.AddressFinder

Given a StreetSegment, look up its Street by name in the database.

findStreetLike(String) - Method in class geography.AddressFinder

Find the street whose name is most similar to the given name, breaking ties in favor of streets with more addresses.

G

g - Variable in class geography.Streetmap

A directed graph of the streets.

g - Variable in class graph.Dijkstra

The graph we are searching.

g - Variable in class graph.HashKeyedDigraph

The underlying graph.

geography - package geography

Classes to deal with geographical objects: points on the earth, addresses, maps.

get(Attribute) - Method in interface container.Decorable

get(Attribute) - Method in class container.HashDecorable

getDist(Vertex) - Method in class graph.Dijkstra

Value of v's attrDist attribute, as a double.

getEdge(int) - Method in class geography.Route

Get a particular edge of the path.

getPathTo(Object) - Method in class graph.Dijkstra

Convenience version of getPathTo() where the end vertex is specified by a key.

getPathTo(Vertex) - Method in class graph.Dijkstra

Run Dijkstra's algorithm until we know the shortest path from vertex vStart to vertex vEnd.

GLOBE_RADIUS_EQUATOR - Static variable in class geography.Point

Radius of the earth, in meters, at the equator.

GLOBE_RADIUS_POLES - Static variable in class geography.Point

Radius of the earth, in meters, at the poles.

globeRadiusOfCurvature(double) - Static method in class geography.Point

Computes the earth's radius of curvature at a particular latitude, assuming that the earth is a squashed sphere with elliptical cross-section.

graph - package graph

Directed graphs and algorithms on them.

H

has(Attribute) - Method in interface container.Decorable

Does this object currently have any value for this attribute?

has(Attribute) - Method in class container.HashDecorable

hash(Object) - Method in interface container.EqualityTester

hashCode() - Method in class geography.Point

HashDecorable - class container.HashDecorable.

This class should typically be extended so that it implements other interfaces besides Decorable.

HashDecorable() - Constructor for class container.HashDecorable

Constructor.

HashKeyedDigraph - class graph.HashKeyedDigraph.

An implementation of KeyedDigraph that wraps another Digraph (no matter what its implementation) and adds a hash table.

HashKeyedDigraph(Digraph) - Constructor for class graph.HashKeyedDigraph

If g is an empty Digraph, this constructs a new empty KeyedDigraph.

hasLeft(Position) - Method in interface tree.BinaryTree

Returns whether a node has a left child.

hasRight(Position) - Method in interface tree.BinaryTree

Returns whether a node has a right child.

hasTurn(DirectedEdge, DirectedEdge) - Method in class geography.Route

Do we have to report a turn from e1 onto e2, or are we just continuing pretty much straight on the same street?

houseNum(String) - Method in class geography.StreetSegment

Converts a house number string like "323" or "" into an Integer like 323 or null, respectively.

housenumLeftEnd - Variable in class geography.StreetSegment

housenumLeftStart - Variable in class geography.StreetSegment

House numbers nearest the pStart end of this segment, on the left and right sides.

housenumRightEnd - Variable in class geography.StreetSegment

housenumRightStart - Variable in class geography.StreetSegment

House numbers nearest the pStart end of this segment, on the left and right sides.

I

insert(Object, Object) - Method in interface pqueue.PriorityQueue

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

insertDirectedEdge(Vertex, Vertex, Object) - Method in class graph.AdjListDigraph

insertDirectedEdge(Vertex, Vertex, Object) - Method in interface graph.Digraph

Adds a new directed edge from one vertex to another.

insertDirectedEdge(Vertex, Vertex, Object) - Method in class graph.HashKeyedDigraph

insertDistance(String, String, int) - Method in class graph.HashKeyedDigraph

insertReverseOf(DirectedEdge) - Method in class graph.AdjListDigraph

insertReverseOf(DirectedEdge) - Method in interface graph.Digraph

Convenience method: Add the reverse of the given edge, with the same element.

insertReverseOf(DirectedEdge) - Method in class graph.HashKeyedDigraph

insertVertex(Object) - Method in class graph.AdjListDigraph

insertVertex(Object) - Method in interface graph.Digraph

Insert and return a new vertex.

insertVertex(Object) - Method in class graph.HashKeyedDigraph

Intersection - class geography.Intersection.

One kind of object that can be returned by address lookup (see the AddressFinder class).

Intersection(Point, String) - Constructor for class geography.Intersection

InvalidEntryException - exception container.InvalidEntryException.

Runtime exception thrown when someone tries to modify/remove an entry in an adaptable data structure.

InvalidEntryException() - Constructor for class container.InvalidEntryException

InvalidEntryException(String) - Constructor for class container.InvalidEntryException

InvalidKeyException - exception container.InvalidKeyException.

Runtime exception thrown when someone tries to add a (key,element) entry to a sorted collection that doesn't know how to sort this key.

InvalidKeyException() - Constructor for class container.InvalidKeyException

InvalidKeyException(String) - Constructor for class container.InvalidKeyException

InvalidPositionException - exception container.InvalidPositionException.

InvalidPositionException() - Constructor for class container.InvalidPositionException

InvalidPositionException(String) - Constructor for class container.InvalidPositionException

isctArbitrary - Variable in class geography.AddressFinder.Street

isEmpty() - Method in interface pqueue.PriorityQueue

Returns whether the priority queue is empty.

isEmpty() - Method in interface tree.Tree

Returns whether the tree is empty.

isExternal(Position) - Method in interface tree.Tree

Returns whether a given node is external.

isInternal(Position) - Method in interface tree.Tree

Returns whether a given node is internal.

isRoot(Position) - Method in interface tree.Tree

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

K

key() - Method in interface container.Entry

KeyedDigraph - interface graph.KeyedDigraph.

A Digraph with keyed vertices.

keyedInsertDirectedEdge(Object, Object, Object) - Method in class graph.HashKeyedDigraph

keyedInsertDirectedEdge(Object, Object, Object) - Method in interface graph.KeyedDigraph

Convenience method: Add a directed edge between two keyed vertices, which are looked up or added using findOrInsertKeyedVertex().

keyFromStreetName(String) - Static method in class geography.AddressFinder

L

latitude - Variable in class geography.Point

Latitude of this point, in degrees.

lcpLength(String, String) - Static method in class geography.AddressFinder

left(Position) - Method in interface tree.BinaryTree

Returns the left child of a node.

longitude - Variable in class geography.Point

Longitude of this point, in degrees.

longlat(String) - Method in class geography.StreetSegment

Converts a longitude or latitude string like +39210703 into a double like 39.210703.

M

m - Variable in class container.HashDecorable

Maps attributes of this object to their values.

m - Variable in class graph.HashKeyedDigraph

Maps keys to vertices.

main(String[]) - Static method in class geography.Point

main(String[]) - Static method in class geography.Streetmap

A simple interaction with the user.

main(String[]) - Static method in class graph.Dijkstra

main(String[]) - Static method in class graph.HashKeyedDigraph

This test method does some work but doesn't actually print anything.

makeSuperStreetSegment() - Method in class geography.StreetSegment

MERGE_ANGLE_TOLERANCE - Static variable in class geography.Route

Two segments of the same street need not be separately reported unless their direction changes by more than plus or minus this many degrees.

min() - Method in interface pqueue.PriorityQueue

Returns but does not remove an entry with minimum key.

N

name - Variable in class container.Attribute

A name supplied by the user for printing this attribute.

name - Variable in class geography.StreetSegment

Name of the street, e.g., "N Charles St".

nameSuper - Variable in class geography.StreetSegment

Base name of the "superstreet" that this is part of, e.g., "Charles St".

NegativeWeightException - exception graph.NegativeWeightException.

Runtime exception thrown when a method discovers a negative weight in a graph that wasn't supposed to have negative weights.

NegativeWeightException() - Constructor for class graph.NegativeWeightException

NegativeWeightException(String) - Constructor for class graph.NegativeWeightException

NoSuchVertexException - exception graph.NoSuchVertexException.

Runtime exception thrown when the user attempts to look up a vertex in a KeyedDigraph by a nonexistent key.

NoSuchVertexException() - Constructor for class graph.NoSuchVertexException

NoSuchVertexException(String) - Constructor for class graph.NoSuchVertexException

numEdges() - Method in class graph.AdjListDigraph

numEdges() - Method in interface graph.Digraph

Return the size of the graph (number of edges, m).

numEdges() - Method in class graph.HashKeyedDigraph

numKnownAddresses() - Method in class geography.AddressFinder.Street

Total number of addresses known for this street.

numKnownStreets() - Method in class geography.AddressFinder

Number of street names that this AddressFinder knows about.

numVertices() - Method in class graph.AdjListDigraph

numVertices() - Method in interface graph.Digraph

Return the order of the graph (number of vertices, n).

numVertices() - Method in class graph.HashKeyedDigraph

O

orig - Variable in class graph.StoredDirectedEdge

origin() - Method in interface graph.DirectedEdge

Vertex where this directed edge starts.

origin() - Method in class graph.StoredDirectedEdge

outIncidentEdges(Vertex) - Method in class graph.AdjListDigraph

outIncidentEdges(Vertex) - Method in interface graph.Digraph

Return an iterator over all the directed edges from a vertex.

outIncidentEdges(Vertex) - Method in class graph.HashKeyedDigraph

P

parent(Position) - Method in interface tree.Tree

Returns the parent of a given node.

path - Variable in class geography.Route

The path, or null if no path exists.

Path - class graph.Path.

A sequence of directed edges laid end to end.

Path() - Constructor for class graph.Path

pathTo(Vertex) - Method in class graph.Dijkstra

Get the current best path from vStart to v, according to the backpointers.

pEnd - Variable in class geography.StreetSegment

Physical start and end points of this segment

point - Variable in class geography.Intersection

Physical location of the address.

Point - class geography.Point.

A point on the surface of the earth.

Point(double, double) - Constructor for class geography.Point

Point(String, String) - Constructor for class geography.Point

Position - interface container.Position.

positions() - Method in interface tree.Tree

Returns an iterator of the nodes stored in the tree.

pq - Variable in class graph.Dijkstra

A priority queue of vertices that still have to be relaxed, keyed by their attrDist.

pqueue - package pqueue

Priority queues, including locator-based priority queues ("repriority queues").

PriorityQueue - interface pqueue.PriorityQueue.

Interface for the priority queue ADT

pStart - Variable in class geography.StreetSegment

Physical start and end points of this segment

put(Attribute, Object) - Method in interface container.Decorable

Makes this object store o as the value of attribute a.

put(Attribute, Object) - Method in class container.HashDecorable

R

radians(double) - Static method in class geography.Point

readIntersection(BufferedReader, String) - Method in class geography.Streetmap

Get an address from the user on the input stream underlying br, and return the corresponding intersection if we can find it.

recordNewPathTo(Vertex, double, DirectedEdge) - Method in class graph.Dijkstra

We'll call this method when we find a new, shorter path to v.

remove() - Method in interface tree.CompleteBinaryTree

Removes the "last" position in the heap tree.

remove(Attribute) - Method in interface container.Decorable

Removes attribute a and its associated value from this object.

remove(Attribute) - Method in class container.HashDecorable

remove(Entry) - Method in interface pqueue.AdaptablePriorityQueue

Remove an entry, and return that entry (for convenience).

removeMin() - Method in interface pqueue.PriorityQueue

Removes and returns an entry with minimum key.

removeMinVertex() - Method in class graph.Dijkstra

Remove and return the Vertex at the front of the priority queue.

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

Replaces the element stored at a given node.

replaceElement(Object) - Method in class graph.StoredVertex

Replace the element at this position.

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

Replace the key of the given entry.

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

Replace the value of the given entry.

right(Position) - Method in interface tree.BinaryTree

Returns the right child of a node.

root() - Method in interface tree.Tree

Returns the root of the tree.

Route - class geography.Route.

A route in a Streetmap.

Route(Path) - Constructor for class geography.Route

Turns a Path into a Route.

Route(Path, int) - Constructor for class geography.Route

Turns a Path into a Route.

S

shortestRoute(Intersection, Intersection) - Method in class geography.Streetmap

Returns a shortest route between two intersections.

shortestRoute(Point, Point) - Method in class geography.Streetmap

Returns a shortest route between two points.

shortestRoute(String, String) - Method in class geography.Streetmap

Given two addresses, returns a shortest route between them.

size() - Method in interface pqueue.PriorityQueue

Returns the number of items in the priority queue.

size() - Method in interface tree.Tree

Returns the number of nodes in the tree.

smIntersections - Variable in class geography.AddressFinder.Street

Maps house numbers to Intersections along this street.

smStreets - Variable in class geography.AddressFinder

The "big map" that stores Streets, keyed by simplified versions of their names (see simplify()).

square(double) - Static method in class geography.Point

ssArbitrary - Variable in class geography.AddressFinder.Street

One arbitrary segment of the street.

StoredDirectedEdge - class graph.StoredDirectedEdge.

A straightforward implementation of the DirectedEdge interface.

StoredDirectedEdge(Vertex, Vertex, Object) - Constructor for class graph.StoredDirectedEdge

Creates a new edge from orig to dest, labeled with element.

StoredVertex - class graph.StoredVertex.

A straightforward implementation of the Vertex interface.

StoredVertex(Object) - Constructor for class graph.StoredVertex

Construct a new vertex storing object o.

streetChange(DirectedEdge, DirectedEdge) - Method in class geography.Route

Does the transition from e1 to e2 represent a change of street?

Streetmap - class geography.Streetmap.

A street map.

Streetmap() - Constructor for class geography.Streetmap

Constructs an empty streetmap (empty graph).

Streetmap(String) - Constructor for class geography.Streetmap

Constructs a streetmap from a .map file.

streetName(DirectedEdge) - Method in class geography.Route

Given an edge, returns a printable street name for the street segment it represents.

StreetSegment - class geography.StreetSegment.

A street segment corresponding to a line in a .map file.

StreetSegment(StreetSegment) - Constructor for class geography.StreetSegment

Copy constructor.

StreetSegment(String) - Constructor for class geography.StreetSegment

Constructs a StreetSegment from a line in a .map file.

superStreet - Variable in class geography.AddressFinder.Street

A street of which this street is a mere segment.

T

test(double, double, double, double) - Static method in class geography.Point

toString() - Method in class container.Attribute

A printable representation of this attribute, such as "[attribute @12345 - color]" for a color attribute.

toString() - Method in class geography.Intersection

toString() - Method in class geography.Point

toString() - Method in class geography.Route

Describes the route as a long string of several \n-terminated lines.

toString() - Method in class graph.Path

Constructs a concise string representation of the path.

toString() - Method in class graph.StoredDirectedEdge

A printable representation of this edge, such as [directed edge 999 from [vertex @12345 - xyz] to [vertex @54321 - abc]]; here 999 is the element stored on the edge.

toString() - Method in class graph.StoredVertex

A printable representation of this vertex, such as [vertex @12345 - xyz].

tree - package tree

Trees, such as a binary heap tree.

Tree - interface tree.Tree.

TURN_CUTOFFS - Static variable in class geography.Route

Cutoffs for the different descriptions in TURN_NAMES.

TURN_NAMES - Static variable in class geography.Route

To describe a turn of d degrees, we use the first description in TURN_NAMES whose corresponding cutoff in TURN_CUTOFFS is >= d.

turnName(DirectedEdge, DirectedEdge) - Method in class geography.Route

Turns a change in direction into its printable name: describes a turn from ss1 onto ss2.

V

value() - Method in interface container.Entry

verbosity - Variable in class geography.Route

See Route.Route(Path,int).

Vertex - interface graph.Vertex.

A vertex in a graph.

vStart - Variable in class graph.Dijkstra

The start vertex.

W

weight(Object) - Method in interface graph.Weighter

Find the weight of this object in an appropriate way.

weighter - Variable in class geography.Streetmap

For finding the weights of edges in g.

weighter - Variable in class graph.Dijkstra

An object that can compute the weight function on edges.

Weighter - interface graph.Weighter.

A class used to find the weight of objects, such as graph edges.

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