|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
A regular set may contain either zero or one instance of a particular item. As shown in the preceding section if the number of possible items is not excessive, we may use an array of bool variables to keep track of the number of instances of a particular item in a regular set. The natural extension of this idea for a multiset is to keep a separate count of the number of instances of each item in the multiset.
Program 
introduces the MultisetAsArray class.
The MultisetAsArray class extends
the abstract Multiset class
defined in Program .
The multiset is implemented using
an array of 
counters.
Each counter is an int in this case.
Program: MultisetAsArray class __init__ method.
In addition to self,
the __init__ method takes a single argument,
,
and initializes an array of length N counters all to zero.
The running time of the __init__ method is O(N).
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.