Next / Previous / Contents / TCC Help System / NM Tech homepage

13. class Path: The solution path

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.

mazeratty
# - - - - -   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.

mazeratty
      State/Invariants:
        .__pathList:
          [ list of cell-keys in self, in traversal order ]
        .__pathSet:
          [ set of cell-keys in self ]
    '''

13.1. Path.__init__()

mazeratty
# - - -   P a t h . _ _ i n i t

    def __init__ ( self ):
        '''Constructor
        '''
        self.__pathList = []
        self.__pathSet = set()

13.2. Path.add(): Add the next cell in sequence

mazeratty
# - - -   P a t h . a d d

    def add(self, cellKey):
        '''Add a new last point.
        '''
        self.__pathList.append(cellKey)
        self.__pathSet.add(cellKey)

13.3. Path.__iter__(): Return an iterator for the path

mazeratty
# - - -   P a t h . _ _ i t e r _ _

    def __iter__(self):
        '''Return an iterator for self's sequence.
        '''
        return iter(self.__pathList)

13.4. Path.__len__(): How many cells are in the path?

mazeratty
# - - -   P a t h . _ _ l e n _ _

    def __len__(self):
        '''Return the number of cells in self.
        '''
        return len(self.__pathList)

13.5. Path.__getitem__(): Get one cell in the path

mazeratty
# - - -   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]

13.6. Path.__contains__(): Test whether a cell is in the path

This special method is used to implement Python's “in” and “not in” operators.

mazeratty
# - - -   P a t h . _ _ c o n t a i n s _ _

    def __contains__(self, cellKey):
        '''Define set membership.
        '''
        return cellKey in self.__pathSet