|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Program 
defines two more operations
of the OrderedListAsArray class,
findPosition and __getitem__.
In addition to self,
the findPosition method takes as its argument an object, obj.
The purpose of this method is to search the ordered list
for an item which matches the object,
and to return the position in the form of a Cursor.
In this case,
the result is an instance of the OrderedListAsArray.Cursor class.
Program: OrderedListAsArray class findPosition and and __getitem__ methods.
The search algorithm used in findPosition is identical to that
used in the find method (Program ).
The findPosition uses the == operator to locate
a contained object which is equal to the search target.
Note that if no match is found,
the _offset is set to the value _count,
which is one position to the right of the last item in the ordered list.
The running time of findPosition is identical to that of
find: 
, where 
.
In addition to self, the __getitem__ method takes an int argument and returns the object in the ordered list at the specified position. In this case, the position is specified using an integer-valued subscript expression. The implementation of this method is trivial--it simply indexes into the array. Assuming the specified offset is valid, the running time of this method is O(1).
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.