Implements a modified Patricia Tree.
Our implementation of this data structure stores objects of a single type based on a bit string. The bit string can have any length, it need not be an integer number of bytes. Our implementation differs from that described by Knuth in supporting keys that are prefixes of other keys.
The class is optimised for fast retrieval. Inserting is a little slower.
Creates an empty tree.
Instantly forgets everything in the tree.
Returns the number of items in the tree.
Looks up the item with key k of length l. A one-byte key must have l 8.
Returns 0 if there is no such item.
This virtual function is called when n is no longer needed.
Inserts the item t using key k of length l. A one-byte key must have l 8.
If there already was an item with that key, the old item is silently forgotten.
Returns true if the tree is empty, and false otherwise. Fast (much faster than !count()).
This virtual function allocates and returns a new tree node.
Removes the item with key k of length l. A one-byte key must have l 8.
Returns a pointer to the removed item, or a null pointer if there was no such item in the tree.
This web page based on source code belonging to The Archiveopteryx Developers. All rights reserved.