We begin the implementation of the Bag ADT with the constructor. The constructor defines a single data field, which is initialized to an empty list. This corresponds to the definition of the constructor for the Bag ADT in which the container is initially created empty.
class Bag :
def __init__( self ):
self._theItems = list()
A sample instance of the Bag class created from the example checkdates2.py program provided earlier is illustrated in Figure 2.3.1.
Figure 2.3.1: Sample instance of the Bag class implemented using a list.
Most of the implementation details for the remaining methods follow the specifics discussed in the previous section.
def __len__(self) :
return len(self._theItems)
def __contains__(self, item) :
return item in self._theItems
def add(self, item) :
self._theItems.append(item)
There are some additional details, however. First, the ADT definition of the remove operation specifies the precondition that the item must exist in the bag in order to be removed. Thus, we must first assert that condition and verify the existence of the item.
def remove(self, item) :
assert item in self._theItems, "The item must be in the bag."
ndx = self._theItems.index(item)
return self._theItems.pop(ndx)
Second, we need to provide an iteration mechanism that allows us to iterate over the individual items in the bag. We delay the implementation of this operation until the next section where we discuss the creation and use of iterators in Python.
The complete implementation of the Bag ADT using a list is provided in the program listing below. Note that instances of the Bag class are mutable objects. That is, the contents of the object can be changed. The objects created from all of the classes presented in the previous chapter were immutable objects. See the Special Topic at the bottom of the page for a refresher on the difference between mutable and immutable objects.
Program Listing
# Implements the Bag ADT container using a Python list. class Bag : # Constructs an empty bag. def __init__(self) : self._theItems = list() # Returns the number of items in the bag. def __len__(self) : return len(self._theItems) # Determines if an item is contained in the bag. def __contains__(self, item) : return item in self._theItems # Adds a new item to the bag. def add(self, item) : self._theItems.append(item) # Removes and returns an instance of the item from the bag. def remove(self, item) : assert item in self._theItems, "The item must be in the bag." ndx = self._theItems.index(item) return self._theItems.pop(ndx) # Returns an iterator for traversing the list of items. def __iter__(self, item) : ......
|
A list stores references to objects and technically would be illustrated as shown in the figure below.
To conserve space and reduce the clutter that can result in some of the figures, however, we illustrate objects in the text as boxes with rounded edges and show them stored directly within the list structure. Variables will be illustrated as square boxes with a bullet in the middle and the name of the variable printed nearby.
Mutable versus Immutable Objects |
Any object that stores data in instance variables is said to have a state. The object's state is the current set of values that it contains. Objects are divided into two distinct categories: mutable and immutable. An immutable object is one in which the state cannot be changed once it has been created. If the instance variables of the object can be changed after the object has been created, the object is said to be mutable object.
The methods defined for a class can be grouped into four different categories:
- constructors
-
create and initialize new instances of the class.
- accessors
-
return or use data contained in an instance of the class without modifying it. These methods are also sometime known as getters.
- mutators
-
modify the data contained in an instance of the class resulting in a change of its state. These methods are also sometime known as setters. A class that contains at least one mutator type method produces mutable objects.
- iterators
-
sequentially access individual data components stored in an instance of the class without modifying the data.
The objects created from the LineSegment class implemented in this section have been immutable because we have no way of changing the coordinates stored in the objects. Suppose we modified the definition of the shift operation to have it adjust or shift the line segment itself instead of creating and returning a new line segment instance.
def shift(self, xInc, yInc) :
self._xCoordA = self._xCoordA + xInc
self._yCoordA = self._yCoordA + yInc
self._xCoordB = self._xCoordB + xInc
self._yCoordB = self._yCoordB + yInc
This would now make the objects created from the LineSegment class mutable since the instance variables can be modified after the object is created. For example, consider the following code segment
lineA = LineSegment(0, 0, 10, 20)
print(lineA)
lineA.shift(5, 2)
print(lineA)
When the shift method is executed in the third line, the instance variables stored inside the lineA object itself are modified. Thus, when this code segment is executed, it produces the following output:
(0, 0)#(10, 20)
(5, 2)#(15, 22)
|
