Debian Codegraph @

protolib/include/protoTree.h

raw
1 /*********************************************************************
2 *
3 * AUTHORIZATION TO USE AND DISTRIBUTE
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that:
7 *
8 * (1) source code distributions retain this paragraph in its entirety,
9 *
10 * (2) distributions including binary code include this paragraph in
11 * its entirety in the documentation or other materials provided
12 * with the distribution, and
13 *
14 * (3) all advertising materials mentioning features or use of this
15 * software display the following acknowledgment:
16 *
17 * "This product includes software written and developed
18 * by Brian Adamson of the Naval Research Laboratory (NRL)."
19 *
20 * The name of NRL, the name(s) of NRL employee(s), or any entity
21 * of the United States Government may not be used to endorse or
22 * promote products derived from this software, nor does the
23 * inclusion of the NRL written and developed software directly or
24 * indirectly suggest NRL or United States Government endorsement
25 * of this product.
26 *
27 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
28 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
29 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
30 ********************************************************************/
31
32 #ifndef _PROTO_TREE
33 #define _PROTO_TREE
34
35 #include "protoList.h" // for ProtoIterable base class
36
37 #include <string.h>
38 #ifndef _WIN32_WCE
39 #include <sys/types.h> // for BYTE_ORDER (ENDIAN) macros for "ProtoTree::GetNativeEndian()
40 #else
41 #include <types.h>
42 #endif
43
44 /**
45 * @class ProtoTree
46 *
47 * @brief This is a general purpose prefix-based
48 * C++ Patricia tree. The code also provides
49 * an ability to iterate over items with a
50 * common prefix of arbitrary bit length.
51 *
52 * The class ProtoTree provides a relatively
53 * lightweight but good performance
54 * data storage and retrieval mechanism which
55 * might be useful in prototype protocol
56 * implementations. Thus, its inclusion
57 * in the NRL Protolib.
58 *
59 * Note: "Items" with different key sizes are
60 * now freely mixed within a single tree structure.
61 * The keys of Items within a ProtoTree must be
62 * unique. However, ProtoSortedTree (see below)
63 * allows multiple items with the same key to be
64 * inserted into it. Arbitrary length strings
65 * can be easily indexed.
66 *
67 * ProtoTree supports the notion of big
68 * or little endian byte order of the Item
69 * keys (Note however it is still a prefix
70 * tree, regardless of the "endian"). This
71 * is useful for "ProtoSortedTree::Item"
72 * subclasses that may wish to have the ordering
73 * based on a key that is a data type ordered
74 * according to the machine endian (e.g.,
75 * integers, IEEE doubles, etc).
76 * Big Endian is default.
77 *
78 */
79
80 class ProtoTree : public ProtoIterable
81 {
82 public:
83 ProtoTree();
84 virtual ~ProtoTree();
85
86 bool IsEmpty() const
87 {return (NULL == root);}
88
89 // "Empty()" doesn't delete the items, just removes them all from the tree
90 void Empty();
91
92 // "Destroy()" deletes any items in the tree
93 void Destroy();
94
95 class Item;
96
97 // Insert the "item" into the tree (will fail if item with equivalent key already in tree)
98 bool Insert(Item& item);
99
100 // Remove the "item" from the tree
101 void Remove(Item& item);
102
103 // This should be implemented as shown here. I commented it out
104 // to detect if anything was using its old, incorrect implementation
105 //bool Contains(const Item& item) const
106 // {return (&item == Find(item.GetKey(), item.GetKeysize()));}
107
108 // Find item with exact match to "key" and "keysize" (keysize is in bits)
109 ProtoTree::Item* Find(const char* key, unsigned int keysize) const;
110
111 ProtoTree::Item* FindString(const char* keyString) const
112 {return Find(keyString, (unsigned int)(8*strlen(keyString)));}
113
114 // Find shortest item to which 'key' is a prefix, or secondly the item that
115 // is the largest prefix of 'key' (i.e. the closet prefix match)
116 ProtoTree::Item* FindClosestMatch(const char* key, unsigned int keysize) const;
117
118 // Find item which is largest prefix of the "key" (keysize is in bits)
119 ProtoTree::Item* FindPrefix(const char* key, unsigned int keysize) const;
120
121 ProtoTree::Item* GetRoot() const {return root;}
122 ProtoTree::Item* GetFirstItem() const;
123 ProtoTree::Item* GetLastItem() const;
124
125 ProtoTree::Item* RemoveRoot();
126
127 class Iterator;
128 class ItemPool;
129
130 enum Endian {ENDIAN_BIG, ENDIAN_LITTLE};
131
132 // Helper static function to get "native" (hardware) endian
133 static ProtoTree::Endian GetNativeEndian()
134 {
135 #if BYTE_ORDER == LITTLE_ENDIAN
136 return ProtoTree::ENDIAN_LITTLE;
137 #else
138 return ProtoTree::ENDIAN_BIG;
139 #endif // end if/else (BYTE_ORDER == LITTLE_ENDIAN)
140 } // end ProtoTree::GetNativeEndian()
141
142 /**
143 * @class Item
144 *
145 * @brief ProtoTree::Item provides a base class
146 * for items to be stored in the tree.
147 */
148 class Item : public ProtoIterable::Item
149 {
150 friend class ProtoTree;
151 friend class Iterator;
152 friend class ItemPool;
153
154 public:
155 Item();
156 virtual ~Item();
157
158 // Required overrides
159 virtual const char* GetKey() const = 0;
160 virtual unsigned int GetKeysize() const = 0;
161
162 // Optional overrides
163 // TBD - make the GetEndian() member of ProtoTree instead
164 // i.e., just like UseSignBit() and UseComplementTwo()
165 #ifdef WIN32
166 // Some windows compilers don't like the other format
167 virtual Endian GetEndian() const
168 {return ENDIAN_BIG;} // default endian for ProtoTree
169 #else
170 virtual ProtoTree::Endian GetEndian() const
171 {return ENDIAN_BIG;} // default endian for ProtoTree
172 #endif
173 // Returns how deep in its tree this Item lies
174 unsigned int GetDepth() const;
175
176 // Debug helper for keys that are strings
177 const char* GetKeyText() const
178 {
179 static char text[256];
180 unsigned int tlen = GetKeysize() >> 3;
181 if (tlen > 255) tlen = 255;
182 #ifdef WIN32
183 strncpy_s(text, 256, GetKey(), tlen);
184 #else
185 strncpy(text, GetKey(), tlen);
186 #endif // if/else WIN32
187 text[tlen] = '\0';
188 return text;
189 }
190
191 protected:
192 Item* GetParent() const {return parent;}
193 Item* GetLeft() const {return left;}
194 Item* GetRight() const {return right;}
195 unsigned int GetBit() {return bit;}
196
197 // bitwise comparison of the two keys
198 bool IsEqual(const char* theKey, unsigned int theKeysize) const;
199 bool PrefixIsEqual(const char* prefix, unsigned int prefixSize) const;
200
201 // Methods for item pooling (accessed by class ItemPool)
202 void SetPoolNext(Item* poolNext) {right = poolNext;}
203 Item* GetPoolNext() const {return right;}
204
205 unsigned int bit;
206 Item* parent;
207 Item* left;
208 Item* right;
209
210 }; // end class ProtoTree::Item
211
212 /**
213 * @class ItemPool
214 *
215 * @brief This is useful for managing a reserved "pool" of Items (containers)
216 * even though it is not used by the ProtoTree classes themselves. We use
217 * in other classes in Protolib that use ProtoTree (e.g. ProtoGraph, ProtoQueue, etc)
218 */
219 class ItemPool
220 {
221 public:
222 ItemPool();
223 virtual ~ItemPool();
224 void Destroy();
225 bool IsEmpty() const
226 {return (NULL == head);}
227
228 Item* Get();
229
230 void Put(Item& item);
231
232 private:
233 Item* head;
234
235 }; // end class ProtoTree::ItemPool
236
237 /**
238 * @class Iterator
239 *
240 * @brief This can be used to iterate over the entire data set (default)
241 * or limited to certain prefix subtree (iterates in lexical order)
242 * NOTE: The iteration here invokes the ProtoTree::Item virtual
243 * methods (GetKey(), etc)
244 */
245 class Iterator : public ProtoIterable::Iterator
246 {
247 public:
248 Iterator(ProtoTree& tree,
249 bool reverse = false,
250 Item* cursor = NULL);
251 virtual ~Iterator();
252
253 void Reset(bool reverse = false,
254 const char* prefix = NULL,
255 unsigned int prefixSize = 0);
256
257 void SetCursor(Item& item);
258
259 Item* GetPrevItem();
260 Item* PeekPrevItem();
261
262 Item* GetNextItem();
263 Item* PeekNextItem();
264
265 //private:
266 // Required override for ProtoIterable to make sure any
267 // iterators associated with a list are updated upon
268 // Item addition or removal.
269 void Update(ProtoIterable::Item* theItem, Action theAction);
270
271 bool reversed; // true if currently iterating backwards
272 unsigned int prefix_size; // if non-zero, iterating over items of certain prefix
273 Item* prefix_item; // reference item with matching prefix for subtree iteration
274 Item* prev;
275 Item* next;
276 Item* curr_hop;
277
278 }; // end class ProtoTree::Iterator
279 friend class Iterator;
280
281
282
283 /**
284 * @class SimpleIterator
285 *
286 * @brief This can be used to iterate over the entire data set. Note
287 * it does _not_ iterate in lexical order, but also (beneficially)
288 * does _not_ make any virtual function calls (e.g. GetKey(), etc)
289 * on the ProtoTree::Item members and is thus safe to call most all
290 * of the time (i.e., such as during destructor calls)
291 */
292 class SimpleIterator : public ProtoIterable::Iterator
293 {
294 public:
295 SimpleIterator(ProtoTree& theTree);
296 virtual ~SimpleIterator();
297
298 void Reset();
299 Item* GetNextItem();
300
301 private:
302 // Required override for ProtoIterable to make sure any
303 // iterators associated with a list are updated upon
304 // Item addition or removal.
305 void Update(ProtoIterable::Item* theItem, Action theAction);
306
307 Item* next;
308
309 }; // end class ProtoTree::SimpleIterator
310
311 static bool Bit(const char* key, unsigned int keysize, unsigned int index, Endian keyEndian);
312
313 static bool ItemIsEqual(const Item& item, const char* key, unsigned int keysize);
314 static bool ItemsAreEqual(const Item& item1, const Item& item2);
315
316 protected:
317 // This finds the closest matching item with backpointer to "item"
318 ProtoTree::Item* FindPredecessor(ProtoTree::Item& item) const;
319
320 // This finds the root of a subtree of Items matching the given prefix
321 ProtoTree::Item* FindPrefixSubtree(const char* prefix,
322 unsigned int prefixLen) const;
323
324 static bool KeysAreEqual(const char* key1,
325 const char* key2,
326 unsigned int keysize,
327 Endian keyEndian);
328
329 static bool PrefixIsEqual(const char* key,
330 unsigned int keysize,
331 const char* prefix,
332 unsigned int prefixSize,
333 Endian keyEndian);
334
335 // Member variables
336 Item* root;
337
338 }; // end class ProtoTree
339
340
341 // The ITEM_TYPE here _must_ be something
342 // subclassed from ProtoTree::Item
343 template <class ITEM_TYPE>
344 class ProtoTreeTemplate : public ProtoTree
345 {
346 public:
347 ProtoTreeTemplate() {}
348 virtual ~ProtoTreeTemplate() {}
349
350 bool Insert(ITEM_TYPE& item)
351 {return ProtoTree::Insert(item);}
352
353 void Remove(ITEM_TYPE& item)
354 {ProtoTree::Remove(item);}
355
356 // Find item with exact match to "key" and "keysize" (keysize is in bits)
357 ITEM_TYPE* Find(const char* key, unsigned int keysize) const
358 {return (static_cast<ITEM_TYPE*>(ProtoTree::Find(key, keysize)));}
359
360 ITEM_TYPE* FindString(const char* keyString) const
361 {return (static_cast<ITEM_TYPE*>(ProtoTree::FindString(keyString)));}
362
363 ITEM_TYPE* FindClosestMatch(const char* key, unsigned int keysize) const
364 {return (static_cast<ITEM_TYPE*>(ProtoTree::FindClosestMatch(key, keysize)));}
365
366 // Find item which is largest prefix of the "key" (keysize is in bits)
367 ITEM_TYPE* FindPrefix(const char* key, unsigned int keysize) const
368 {return (static_cast<ITEM_TYPE*>(ProtoTree::FindPrefix(key, keysize)));}
369
370 void Destroy()
371 {ProtoTree::Destroy();}
372
373
374 class Iterator : public ProtoTree::Iterator
375 {
376 public:
377 Iterator(ProtoTreeTemplate& theTree,
378 bool reverse = false,
379 Item* cursor = NULL)
380 : ProtoTree::Iterator(theTree, reverse, cursor) {}
381 virtual ~Iterator() {}
382
383 ITEM_TYPE* GetPrevItem()
384 {return static_cast<ITEM_TYPE*>(ProtoTree::Iterator::GetPrevItem());}
385 ITEM_TYPE* PeekPrevItem()
386 {return static_cast<ITEM_TYPE*>(ProtoTree::Iterator::PeekPrevItem());}
387
388 ITEM_TYPE* GetNextItem()
389 {return static_cast<ITEM_TYPE*>(ProtoTree::Iterator::GetNextItem());}
390 ITEM_TYPE* PeekNextItem()
391 {return static_cast<ITEM_TYPE*>(ProtoTree::Iterator::PeekNextItem());}
392
393 }; // end class ProtoTreeTemplate::Iterator
394
395 class SimpleIterator : public ProtoTree::SimpleIterator
396 {
397 public:
398 SimpleIterator(ProtoTreeTemplate& theTree)
399 : ProtoTree::SimpleIterator(theTree) {}
400 virtual ~SimpleIterator() {}
401
402 ITEM_TYPE* GetNextItem()
403 {return static_cast<ITEM_TYPE*>(ProtoTree::SimpleIterator::GetNextItem());}
404
405 }; // end class ProtoTreeTemplate::SimpleIterator
406
407 class ItemPool : public ProtoTree::ItemPool
408 {
409 public:
410 ItemPool() {}
411 virtual ~ItemPool() {}
412
413 void Put(ITEM_TYPE& item)
414 {ProtoTree::ItemPool::Put(item);}
415
416 ITEM_TYPE* Get()
417 {return static_cast<ITEM_TYPE*>(ProtoTree::ItemPool::Get());}
418 }; // end class ProtoTreeTemplate::ItemPool
419
420 }; // end class ProtoTreeTemplate
421
422 // Example:
423 /*class ExampleItem : public ProtoTree::Item
424 {
425 public:
426 ExampleItem(char* theKey, unsigned int theKeysize, void* theValue): key(theKey), keysize(theKeysize), value(theValue) {}
427 ~ExampleItem() {}
428 const char* GetKey() const {return key;}
429 unsigned int GetKeysize() const {return keysize;}
430 const void* GetValue() const {return value;}
431 private:
432 const char * key;
433 unsigned int keysize;
434 const void * value;
435 };
436 class ExampleItemList : public ProtoTreeTemplate<ExampleItem> {};
437 */
438 /**
439 * @class ProtoSortedTree
440 *
441 * @brief This class extends ProtoTree::Item to provide a "threaded" tree
442 * for rapid (linked-list) iteration. Also note that entries with
443 * duplicate key values are allowed.
444 *
445 * By default, items are sorted lexically by their key. Optionally the tree may be configured
446 * to treat the first bit of the key as a "sign" bit and order the
447 * sorted list properly with a mix of positive and negative values
448 * using two's complement (e.g. "int") rules or just signed ordering
449 * (e.g. "double"). Note that the key Endian must be set properly
450 * according to what the key represents.
451 */
452 class ProtoSortedTree
453 {
454 // TBD - this should be reimplemented using ProtoList for the
455 // threaded aspect.
456 public:
457 ProtoSortedTree(bool uniqueItemsOnly = false);
458 virtual ~ProtoSortedTree();
459
460 bool IsEmpty() const
461 {return item_tree.IsEmpty();}
462
463 class Iterator;
464 class ItemPool;
465 class Item : public ProtoTree::Item, public ProtoList::Item
466 {
467 friend class ProtoSortedTree;
468 friend class Iterator;
469 friend class ItemPool;
470
471 public:
472 Item();
473 virtual ~Item();
474
475 // Required overrides
476 virtual const char* GetKey() const = 0;
477 virtual unsigned int GetKeysize() const = 0;
478
479 // TBD - move the Endian, UseComplement2, UseSignBit stuff
480 // _out_ of the ProtoSortedTree::Item and make them
481 // configurable properties of the tree class itself???
482 // Optional overrides (affect sorting)
483 virtual ProtoTree::Endian GetEndian() const
484 #ifdef WIN32
485 // some windows compilers are more restrictive
486 {return ProtoTree::Item::GetEndian();}
487 #else
488 {return ProtoTree::Item::GetEndian();}
489 #endif
490 virtual bool UseSignBit() const
491 {return false;}
492 virtual bool UseComplement2() const
493 {return true;}
494
495 private:
496 // Linked list (threading) helper
497 bool IsInTree() const
498 {return (NULL != left);}
499 }; // end class ProtoSortedTree::Item
500
501 bool Insert(Item& item);
502
503 Item* GetHead() const
504 {return item_list.GetHead();}
505 Item* RemoveHead()
506 {
507 Item* item = GetHead();
508 if (NULL != item) Remove(*item);
509 return item;
510 }
511 Item* GetTail() const
512 {return item_list.GetTail();}
513
514 Item* GetRoot() const
515 {return static_cast<Item*>(item_tree.GetRoot());}
516
517 // Random access methods (uses ProtoTree)
518 // Note that since a ProtoSortedTree can have multiple items
519 // with the same key, you should generally use the
520 // ProtoSortedTree::Iterator and set the keyMin/keysize
521 // parameters to find _all_ items for a given "key"
522 // (i.e., iterate until the next item key doesn't match)
523 Item* Find(const char* key, unsigned int keysize) const
524 {return item_tree.Find(key, keysize);}
525
526 Item* FindString(const char* keyString) const
527 {return Find(keyString, (unsigned int)(8*strlen(keyString)));}
528
529 // Find item which _is_ largest prefix of the "key" (keysize is in bits)
530 Item* FindPrefix(const char* key, unsigned int keysize) const
531 {return item_tree.FindPrefix(key, keysize);}
532
533 void Remove(Item& item);
534
535 //bool Contains(const Item& item) const
536 // {return item_tree.Contains(item);}
537
538 void Empty(); // empties tree without deleting items contained
539
540 void Destroy();
541
542 // _Unsorted_ Prepend()/Append() methods ("Find()" won't work if used)
543 // Do _not_ mix use of "Insert()" method w/ Prepend()/Append() methods!
544 void Prepend(Item& item);
545 void Append(Item& item);
546
547 protected:
548 class List : public ProtoListTemplate<Item> {};
549
550 public:
551 class Iterator
552 {
553 public:
554 Iterator(ProtoSortedTree& tree,
555 bool reverse = false,
556 const char* keyMin = NULL,
557 unsigned int keysize = 0);
558 virtual ~Iterator();
559
560 bool HasEmptyTree() const
561 {return tree.IsEmpty();}
562
563 // These methods can be used to jog back and forth as desired
564 // (i.e. reversals are automatically managed)
565 Item* GetNextItem()
566 {return list_iterator.GetNextItem();}
567 Item* GetPrevItem()
568 {return list_iterator.GetPrevItem();}
569
570 Item* PeekNextItem()
571 {return list_iterator.PeekNextItem();}
572 Item* PeekPrevItem()
573 {return list_iterator.PeekPrevItem();}
574
575 /// Note if "reverse" is "true", then "keyMin" is really "keyMax"
576 void Reset(bool reverse = false, const char* keyMin = NULL, unsigned int keysize = 0);
577
578 void SetCursor(Item* item)
579 {list_iterator.SetCursor(item);}
580 Item* GetCursor()
581 {return list_iterator.PeekNextItem();}
582
583 // This flips the reversal state, moving
584 // cursor forward or backward one item
585 void Reverse()
586 {list_iterator.Reverse();}
587
588 bool IsReversed() const
589 {return list_iterator.IsReversed();}
590
591 private:
592 /**
593 * @class TempItem
594 *
595 * @brief This is a helper class for getting iterator started, etc
596 */
597 class TempItem : public Item
598 {
599 public:
600 TempItem(const char* theKey, unsigned int theKeysize, ProtoTree::Endian keyEndian);
601 virtual ~TempItem();
602
603 const char* GetKey() const {return key;}
604 unsigned int GetKeysize() const {return keysize;}
605 ProtoTree::Endian GetEndian() const {return key_endian;}
606
607 private:
608 const char* key;
609 unsigned int keysize;
610 ProtoTree::Endian key_endian;
611 }; // end class ProtoSortedTree::Iterator::TempItem
612
613 ProtoSortedTree& tree;
614 List::Iterator list_iterator;
615
616 }; // end class ProtoSortedTree::Iterator
617 friend class Iterator;
618
619 /**
620 * @class ItemPool
621 * @brief This is useful for managing a reserved "pool" of Items (containers)
622 */
623 class ItemPool : public List::ItemPool {};
624
625 void EmptyToPool(ItemPool& itemPool);
626
627 protected:
628 class Tree : public ProtoTreeTemplate<Item> {};
629
630 bool unique_items_only; // "false" by default (i.e., allow duplicate keys)
631 Item* positive_min; // Pointer to minimum non-negative entry when useSignBit
632 Tree item_tree;
633 List item_list;
634 }; // end class ProtoSortedTree
635
636
637 // The ITEM_TYPE here _must_ be something
638 // subclassed from ProtoSortedTree::Item
639 template <class ITEM_TYPE>
640 class ProtoSortedTreeTemplate : public ProtoSortedTree
641 {
642 public:
643 ProtoSortedTreeTemplate() {}
644 virtual ~ProtoSortedTreeTemplate() {}
645
646 // Find item with exact match to "key" and "keysize"
647 ITEM_TYPE* Find(const char* key, unsigned int keysize) const
648 {return (static_cast<ITEM_TYPE*>(ProtoSortedTree::Find(key, keysize)));}
649
650 // Find item which _is_ largest prefix of the "key" (keysize is in bits)
651 ITEM_TYPE* FindPrefix(const char* key, unsigned int keysize) const
652 {return (static_cast<ITEM_TYPE*>(ProtoSortedTree::FindPrefix(key, keysize)));}
653
654 ITEM_TYPE* GetHead() const
655 {return (static_cast<ITEM_TYPE*>(ProtoSortedTree::GetHead()));}
656 ITEM_TYPE* GetTail() const
657 {return (static_cast<ITEM_TYPE*>(ProtoSortedTree::GetTail()));}
658 ITEM_TYPE* RemoveHead()
659 {return (static_cast<ITEM_TYPE*>(ProtoSortedTree::RemoveHead()));}
660
661 class Iterator : public ProtoSortedTree::Iterator
662 {
663 public:
664 Iterator(ProtoSortedTreeTemplate& theTree,
665 bool reverse = false,
666 const char* keyMin = NULL,
667 unsigned int keysize = 0)
668 : ProtoSortedTree::Iterator(theTree, reverse, keyMin, keysize) {}
669 virtual ~Iterator() {}
670
671 ITEM_TYPE* GetPrevItem()
672 {return static_cast<ITEM_TYPE*>(ProtoSortedTree::Iterator::GetPrevItem());}
673 ITEM_TYPE* PeekPrevItem()
674 {return static_cast<ITEM_TYPE*>(ProtoSortedTree::Iterator::PeekPrevItem());}
675
676 ITEM_TYPE* GetNextItem()
677 {return static_cast<ITEM_TYPE*>(ProtoSortedTree::Iterator::GetNextItem());}
678 ITEM_TYPE* PeekNextItem()
679 {return static_cast<ITEM_TYPE*>(ProtoSortedTree::Iterator::PeekNextItem());}
680
681 }; // end class ProtoSortedTreeTemplate::Iterator
682
683 class ItemPool : public ProtoSortedTree::ItemPool
684 {
685 public:
686 ItemPool() {}
687 virtual ~ItemPool() {}
688
689 void Put(ITEM_TYPE& item)
690 {ProtoSortedTree::ItemPool::Put(item);}
691
692 ITEM_TYPE* Get()
693 {return static_cast<ITEM_TYPE*>(ProtoSortedTree::ItemPool::Get());}
694 }; // end class ProtoSortedTreeTemplate::ItemPool
695
696 }; // end class ProtoSortedTreeTemplate
697
698 // Here's an example use of ProtoSortedTree configured to keep a table of items indexed
699 // by a "double" key. Note that multiple equal-valued items _can_ be included in a
700 // ProtoSortedTree (the basic ProtoTree only allows a single item with a given key).
701 /*
702 class ExampleItem : public ProtoSortedTree::Item
703 {
704 public:
705 ExampleItem(double key);
706
707 private:
708 const char* GetKey() const
709 {return (char*)&item_key;}
710 unsigned int GetKeysize() const
711 {return (sizeof(double) << 3);}
712 double item_key;
713 }; // end class ExampleItem
714
715 class ExampleTree : public ProtoSortedTreeTemplate<ExampleItem>
716 {
717 private:
718 // These configure the key interpretation to properly sort "double" type key values
719 virtual bool UseSignBit() const {return true;}
720 virtual bool UseComplement2() const {return false;}
721 virtual ProtoTree::Endian GetEndian() const {return ProtoTree::GetNativeEndian();}
722 };
723 */
724
725 #endif // PROTO_TREE