1 // Copyright 2009 The Archiveopteryx Developers <info@aox.org> 2 3 #include "patriciatree.h" 4 5 /*! \class PatriciaTree patriciatree.h 6 7 Implements a modified Patricia Tree. 8 9 Our implementation of this data structure stores objects of a 10 single type based on a bit string. The bit string can have any 11 length, it need not be an integer number of bytes. Our 12 implementation differs from that described by Knuth in supporting 13 keys that are prefixes of other keys. 14 15 The class is optimised for fast retrieval. Inserting is a little 16 slower. 17 18 There are three common public operations: insert(), find() and 19 remove(). There's also a clear(), which is fast but relies on GC 20 to tidy up slowly later. 21 22 A few subclasses (with bad names for historical reasons) use 23 PatriciaTree to provide maps from integers and strings, Dict, 24 UDict and Map. 25 26 Two virtual functions, node() and free(), must be reimplemented in 27 order to avoid relying on Allocator. 28 */ 29 30 31 /*! \fn PatriciaTree::PatriciaTree() 32 33 Creates an empty tree. 34 */ 35 36 37 38 /*! \fn void PatriciaTree::find( const char * k, uint l ) 39 40 Looks up the item with key \a k of length \a l. A one-byte key 41 must have \a l 8. 42 43 Returns 0 if there is no such item. 44 */ 45 46 47 /*! \fn T * PatriciaTree::remove( const char * k, uint l ) 48 49 Removes the item with key \a k of length \a l. A one-byte key 50 must have \a l 8. 51 52 Returns a pointer to the removed item, or a null pointer if there 53 was no such item in the tree. 54 */ 55 56 57 /*! \fn void PatriciaTree::insert( const char * k, uint l, T * t ) 58 59 Inserts the item \a t using key \a k of length \a l. A one-byte key 60 must have \a l 8. 61 62 If there already was an item with that key, the old item is 63 silently forgotten. 64 */ 65 66 /*! \fn bool PatriciaTree::isEmpty() 67 68 Returns true if the tree is empty, and false otherwise. Fast (much 69 faster than !count()). 70 */ 71 72 /*! \fn uint PatriciaTree::count() const 73 74 Returns the number of items in the tree. 75 */ 76 77 78 /*! \fn void PatriciaTree::clear() 79 80 Instantly forgets everything in the tree. 81 */ 82 83 84 /*! \fn void PatriciaTree::free( PatriciaTree::Node * n ) 85 86 This virtual function is called when \a n is no longer needed. 87 */ 88 /*! \fn PatriciaTree::Node * PatriciaTree::node() 89 90 This virtual function allocates and returns a new tree node. 91 */ 92