An instance of this class represents a sequence of cells such that each cell in sequence is an immediate neighbor (up, down, left, or right) of the previous cell, and no cell is reused.
# - - - - - c l a s s P a t h class Path(object): '''Represents a path through the maze. Exports: Path(): [ return a new, empty path ] .add(cellKey): [ cellKey is a cell-key -> self := self with cellKey added as its next cell ] .__iter__(self): [ return an iterator that generates the cell-keys in self in order ] .__len__(self): [ return the number of cells in self ] .__getitem__(self, k): [ if 0 <= k < len(self) -> return the (k)th element of self's path else -> raise KeyError ] .__contains__(self, cellKey): [ cellKey is a cell-key -> if cellKey is in self -> return True else -> return False ]
Internally, the path is represented as both a list and as a set.
.__pathList attribute contains all
the cell keys in order from start to finish.
We also keep the keys in a set,
.__pathSet, so that the solution algorithm can test a cell to
see if it is in the path in
State/Invariants: .__pathList: [ list of cell-keys in self, in traversal order ] .__pathSet: [ set of cell-keys in self ] '''
# - - - P a t h . _ _ i n i t def __init__ ( self ): '''Constructor ''' self.__pathList =  self.__pathSet = set()
# - - - P a t h . a d d def add(self, cellKey): '''Add a new last point. ''' self.__pathList.append(cellKey) self.__pathSet.add(cellKey)
# - - - P a t h . _ _ i t e r _ _ def __iter__(self): '''Return an iterator for self's sequence. ''' return iter(self.__pathList)
# - - - P a t h . _ _ l e n _ _ def __len__(self): '''Return the number of cells in self. ''' return len(self.__pathList)
# - - - P a t h . _ _ g e t i t e m _ _ def __getitem__(self, k): '''Return self's (k)th element. ''' return self.__pathList[k]