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

The `.__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 ```
O(log
n)
```

time.

mazeratty

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

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