ps3.graph
Interface Path<N,P extends Path<N,P>>

All Superinterfaces:

Comparable<Path<?,?>>, Iterable<N>

All Known Implementing Classes:

NodeCountingPath, WeightedNodePath

public interface Path<N,P extends Path<N,P>>
extends Iterable<N>, Comparable<Path<?,?>>

A Path models a sequence of nodes and the cost for travelling along such a sequence.

Paths are immutable.

Specification Fields

• cost - : double // cost of traversing this Path
• elements - : sequence // the nodes in this Path

  The cost of traversing a path must not decrease as the path is extended with new nodes. Additionally, if p1.cost() < p2.cost(), then for all nodes n, we must have that p1.extend(n).cost() < p2.extend(n).cost()

  The first generic argument (N) is the type of nodes in the path. The second generic argument (P) should be the name of the implementing class itself (see WeightedNodePath for an example). Why is this second argument necessary? Imagine that this interface was defined as public interface Path<N>. Then the extend function would be defined as returning a Path<N>. But this is not specific enough; for example, the extend method on WeightedNodePath could return a NodeCountingPath, or vice versa! The second generic argument lets us force the implementing class to define an extend method that returns an element of the same type.

Method Summary

double	cost()
N	end()
P	extend(N n) Creates an extended path by adding a new node to its end.
Iterator<N>	iterator()

Methods inherited from interface java.lang.Comparable

compareTo

Method Detail

extend

P extend(N n)

Creates an extended path by adding a new node to its end.

Returns:

a new Path p such that p.elements = this.elements + [ n ] && p.cost >= this.cost

Requires:

n != null && n is a valid node type for this particular path implementation

cost

double cost()

Returns:

this.cost

end

N end()

Returns:

the end of the path

iterator

Iterator<N> iterator()

Specified by:

iterator in interface Iterable<N>

Returns:

an Iterator over the elements in the path in order from start to end.