We'll look at some extensions we might make to Python's built-in container classes. We won't show an example of extending each container.
We'll pick an example of extending a specific container and see how the process works:
- Define the requirements. This may include research on Wikipedia, generally starting here: http://en.wikipedia.org/wiki/Data_structure. Designs of data structures often involve complex edge cases around missing items and duplicate items.
- If necessary, look at the collections.abc module to see what methods must be implemented to create the new functionality.
- Create some test cases. This also requires careful study of the algorithms to ensure that the edge cases are properly covered.
- Write code based on the previous research steps.
We need to emphasize the importance of researching the fundamentals before trying to invent a new kind of data structure. In addition to searching the web for overviews and summaries, details will be necessary. See any of the following:
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
- Data Structures and Algorithms by Aho, Ullman, and Hopcroft
- The Algorithm Design Manual by Steven Skiena
As we saw earlier, the ABCs define three broad kinds of collections: sequences, mappings, and sets. We have three design strategies that we can use to create new kinds of collections of our own:
- Extend: This is an existing sequence.
- Wrap: This is an existing sequence.
- Invent: This is a new sequence created from scratch.
In principle, we could give as many as nine examples – each basic flavor of collection with each basic design strategy. We won't beat this subject to death like that. We'll dig deep to create new kinds of sequences, learning how to extend and wrap
existing sequences.
As there are so many extended mappings (such as ChainMap, OrderedDict, defaultdict, and Counter), we'll only touch lightly on creating new kinds of mappings. We'll also dig deep to create a new kind of ordered multiset or bag.
Let's narrow a collection's type in the next section.