Spinning Topp Logo BlackTopp Studios
inc
trie.h
1 // © Copyright 2010 - 2016 BlackTopp Studios Inc.
2 /* This file is part of The Mezzanine Engine.
3 
4  The Mezzanine Engine is free software: you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation, either version 3 of the License, or
7  (at your option) any later version.
8 
9  The Mezzanine Engine is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with The Mezzanine Engine. If not, see <http://www.gnu.org/licenses/>.
16 */
17 /* The original authors have included a copy of the license specified above in the
18  'Docs' folder. See 'gpl.txt'
19 */
20 /* We welcome the use of the Mezzanine engine to anyone, including companies who wish to
21  Build professional software and charge for their product.
22 
23  However there are some practical restrictions, so if your project involves
24  any of the following you should contact us and we will try to work something
25  out:
26  - DRM or Copy Protection of any kind(except Copyrights)
27  - Software Patents You Do Not Wish to Freely License
28  - Any Kind of Linking to Non-GPL licensed Works
29  - Are Currently In Violation of Another Copyright Holder's GPL License
30  - If You want to change our code and not add a few hundred MB of stuff to
31  your distribution
32 
33  These and other limitations could cause serious legal problems if you ignore
34  them, so it is best to simply contact us or the Free Software Foundation, if
35  you have any questions.
36 
37  Joseph Toppi - toppij@gmail.com
38  John Blackwood - makoenergy02@gmail.com
39 */
40 /*
41  * Copyright (c) 2012, Ranjith TV
42  * All rights reserved.
43  *
44  * Licensed under the BSD 3-Clause ("BSD New" or "BSD Simplified") license.
45  * You may obtain a copy of the License at
46  *
47  * http://www.opensource.org/licenses/BSD-3-Clause
48  *
49  */
50 
51 #ifndef TRIE_H
52 #define TRIE_H
53 
54 /// @cond false
55 
56 #include "datatypes.h"
57 
58 namespace Mezzanine
59 {
60 
61 template < typename T,
62 typename V,
63 typename Cmp,
64 typename Items > class Node;
65 
66 template < typename T,
67 typename V,
68 typename Cmp,
69 typename Items > class NodeItem
70 {
71 private:
72  typedef Node<T, V, Cmp, Items> NodeClass;
73  typedef NodeItem<T, V, Cmp, Items> NodeItemClass;
74 
75 public:
76  NodeItem(const T &endSymbol, T const &key)
77  : mEndSymbol(endSymbol),
78  mKey(key),
79  mChilds(0) {}
80 
81  virtual ~NodeItem() {
82  delete mChilds;
83  }
84 
85  bool operator<(NodeItemClass const &oth) const {
86  return Cmp()(this->mKey, oth.mKey);
87  }
88 
89  bool operator<(T const &key) const {
90  return Cmp()(this->mKey, key);
91  }
92 
93  bool operator==(T const &key) const {
94  return !Cmp()(this->mKey, key) && !Cmp()(key, this->mKey);
95  }
96 
97  bool operator==(NodeItemClass const &oth) const {
98  return !Cmp()(this->mKey, oth.mKey) && !Cmp()(oth.mKey, this->mKey);
99  }
100 
101  bool operator!=(T const &key) const {
102  return !((*this) == key);
103  }
104 
105  bool operator!=(NodeItemClass const &oth) const {
106  return !((*this) == oth);
107  }
108 
109  void set(T const &key) {
110  mKey = key;
111  }
112 
113  const T &get() const {
114  return mKey;
115  }
116 
117  const NodeClass *getChilds() const {
118  return mChilds;
119  }
120 
121  NodeClass *getChilds() {
122  return mChilds;
123  }
124 
125  NodeClass *getOrCreateChilds(NodeClass * parent) {
126  createChilds(parent);
127  return mChilds;
128  }
129 
130 private:
131  void createChilds(NodeClass * parent) {
132  if (!mChilds) {
133  mChilds = new NodeClass(mEndSymbol, parent);
134  }
135  }
136 
137  NodeItem(NodeItem const &);
138  NodeItem &operator=(NodeItem const &);
139 
140 private:
141  const T mEndSymbol;
142  T mKey;
143  NodeClass *mChilds;
144 };
145 
146 template < typename T,
147 typename V,
148 typename Cmp,
149 typename Items > class EndNodeItem: public NodeItem<T, V, Cmp, Items>
150 {
151 private:
152  typedef NodeItem<T, V, Cmp, Items> ParentClass;
153 
154 public:
155  EndNodeItem(const T &endSymbol, T const &key)
156  : ParentClass(endSymbol, key) {}
157 
158  EndNodeItem(const T &endSymbol, T const &key, V const &value)
159  : ParentClass(endSymbol, key),
160  mValue(value) {}
161 
162  void set(T const &key, V const &value) {
163  ParentClass::set(key);
164  mValue = value;
165  }
166 
167  const V &getValue() const {
168  return mValue;
169  }
170 
171  V &getValue() {
172  return mValue;
173  }
174 
175 private:
176  EndNodeItem(EndNodeItem const &);
177  EndNodeItem &operator=(EndNodeItem const &);
178 
179 private:
180  V mValue;
181 };
182 
183 template < typename T,
184 typename V,
185 typename Cmp,
186 typename Items > class NodeItemPtrCompare
187 {
188 private:
189  typedef NodeItem<T, V, Cmp, Items> NodeItemClass;
190 
191 public:
192  bool operator()(const NodeItemClass *v1, const NodeItemClass *v2) {
193  return *v1 < *v2;
194  }
195 };
196 
197 template < typename T,
198 typename V,
199 typename Cmp,
200 typename Items > class Node
201 {
202 public:
203  typedef NodeItem<T, V, Cmp, Items> NodeItemClass;
204  typedef EndNodeItem<T, V, Cmp, Items> EndNodeItemClass;
205  typedef Node<T, V, Cmp, Items> NodeClass;
206 private:
207  typedef typename Items::iterator ItemsContainerIter;
208  typedef typename Items::const_iterator ItemsContainerConstIter;
209 
210 public:
211 
212  class const_iterator
213  {
214  protected:
215  typedef std::pair<const T *, const V *> KeyValuePair;
216  typedef typename NodeClass::ItemsContainerConstIter ItemsContainerConstIter;
217 
218  public:
219  const_iterator(const NodeClass *node, const NodeClass * root, const T * key = 0, bool mooveToEnd = false)
220  : mRootNode(root),
221  mCurrentNode(node),
222  mCheckKeyLeft(false),
223  mCheckKeyRight(true),
224  mEndReached(false) {
225  if (!root) {
226  mRootNode = node;
227  }
228  pushNode(node, key, mooveToEnd);
229  if (!mooveToEnd) {
230  next();
231  }
232  }
233 
234  const_iterator(const const_iterator & oth)
235  : mRootNode(oth.mRootNode),
236  mCurrentNode(oth.mCurrentNode),
237  mCurrentPos(oth.mCurrentPos),
238  mKeyStack(oth.mKeyStack),
239  mCheckKeyLeft(oth.mCheckKeyLeft),
240  mCheckKeyRight(oth.mCheckKeyRight),
241  mEndReached(oth.mEndReached) {
242  if (!mKeyStack.empty()) {
243  mKeyValuePair = std::make_pair(&mKeyStack[0], oth.mKeyValuePair.second);
244  }
245  }
246 
247  const_iterator & operator=(const const_iterator & oth) {
248  if (this != &oth) {
249  mRootNode = oth.mRootNode;
250  mCurrentNode = oth.mCurrentNode;
251  mCurrentPos = oth.mCurrentPos;
252  mKeyStack = oth.mKeyStack;
253  if (!mKeyStack.empty()) {
254  mKeyValuePair = std::make_pair(&mKeyStack[0], oth.mKeyValuePair.second);
255  }
256  mCheckKeyLeft = oth.mCheckKeyLeft;
257  mCheckKeyRight = oth.mCheckKeyRight;
258  mEndReached = oth.mEndReached;
259  }
260  return *this;
261  }
262 
263  const KeyValuePair &operator*() const {
264  return this->mKeyValuePair;
265  }
266 
267  const KeyValuePair *operator->() const {
268  return &this->mKeyValuePair;
269  }
270 
271  bool operator==(const_iterator const &oth) const {
272  return this->equals(oth);
273  }
274 
275  bool operator!=(const_iterator const &oth) const {
276  return !(*this == oth);
277  }
278 
279  const_iterator operator++(int) {
280  const_iterator iter = *this;
281  ++(*this);
282  return iter;
283  }
284 
285  const_iterator &operator++() {
286  this->next();
287  return *this;
288  }
289 
290  const_iterator operator--(int) {
291  const_iterator iter = *this;
292  --(*this);
293  return iter;
294  }
295 
296  const_iterator &operator--() {
297  this->previous();
298  return *this;
299  }
300 
301  protected:
302  friend class Node<T, V, Cmp, Items>;
303 
304  const NodeClass * mRootNode;
305  const NodeClass * mCurrentNode;
306  ItemsContainerConstIter mCurrentPos;
307  std::vector<T> mKeyStack;
308  KeyValuePair mKeyValuePair;
309  bool mCheckKeyLeft;
310  bool mCheckKeyRight;
311  bool mEndReached;
312 
313  protected:
314  void previous() {
315  if (!mCurrentNode->mItems.empty() && mCurrentPos == mCurrentNode->mItems.end()) {
316  --mCurrentPos;
317  }
318 
319  bool newNode = false;
320  bool oldNode = false;
321 
322  while (mEndReached || !isLeftEnd()) {
323  mEndReached = false;
324  ItemsContainerConstIter iterBegin = mCurrentNode->mItems.begin();
325  if (!mKeyStack.empty()) {
326  if (mKeyStack.back() == mCurrentNode->endSymbol()) {
327  mKeyStack.pop_back();
328  mCurrentPos = mCurrentNode->mItems.begin();
329  if (isLeftEnd()) {
330  break;
331  }
332  }
333  }
334 
335  if (!newNode && !mKeyStack.empty()) {
336  if (mCheckKeyLeft) {
337  mCurrentNode = mCurrentNode->parent();
338  mCurrentPos = mCurrentNode->mItems.find(mKeyStack.back());
339  iterBegin = mCurrentNode->mItems.begin();
340  mKeyStack.pop_back();
341  mCheckKeyLeft = false;
342  if (mCurrentPos != iterBegin) {
343  --mCurrentPos;
344  oldNode = false;
345  } else {
346  oldNode = true;
347  }
348  } else {
349  ItemsContainerConstIter iter = mCurrentNode->mItems.find(mCurrentNode->endSymbol());
350  if (iter != mCurrentNode->mItems.end()) {
351  mCurrentPos = iter;
352  const NodeItemClass & item = *(const NodeItemClass *) * mCurrentPos;
353  mKeyStack.push_back(item.get());
354  mKeyValuePair.first = &(mKeyStack[0]);
355  mKeyValuePair.second = &(((const EndNodeItemClass &)item).getValue());
356  mCheckKeyLeft = true;
357  return;
358  } else {
359  mCurrentNode = mCurrentNode->parent();
360  mCurrentPos = mCurrentNode->mItems.find(mKeyStack.back());
361  iterBegin = mCurrentNode->mItems.begin();
362  mKeyStack.pop_back();
363  mCheckKeyLeft = false;
364  if (mCurrentPos != iterBegin) {
365  --mCurrentPos;
366  oldNode = false;
367  } else {
368  oldNode = true;
369  }
370  }
371  }
372  }
373 
374  newNode = false;
375  for (; mCurrentPos != iterBegin; --mCurrentPos) {
376  if (*mCurrentPos) {
377  const NodeItemClass &item = *(const NodeItemClass *) * mCurrentPos;
378  if (item != mCurrentNode->endSymbol()) {
379  mKeyStack.push_back(item.get());
380  pushNode(item.getChilds(), 0, true);
381  --mCurrentPos;
382  newNode = true;
383  break;
384  }
385  }
386  oldNode = false;
387  }
388  if (!newNode && !oldNode) {
389  if (*mCurrentPos) {
390  const NodeItemClass &item = *(const NodeItemClass *) * mCurrentPos;
391  if (item != mCurrentNode->endSymbol()) {
392  mKeyStack.push_back(item.get());
393  pushNode(item.getChilds(), 0, true);
394  --mCurrentPos;
395  newNode = true;
396  }
397  }
398  }
399 
400  }
401  mCurrentPos = mCurrentNode->mItems.end();
402  mEndReached = true;
403  }
404 
405  void next() {
406  while (!isEnd()) {
407  ItemsContainerConstIter iterEnd = mCurrentNode->mItems.end();
408 
409  if (!mKeyStack.empty()) {
410  if (mKeyStack.back() == mCurrentNode->endSymbol()) {
411  mKeyStack.pop_back();
412  mCurrentPos = mCurrentNode->mItems.begin();
413  }
414  }
415 
416  if (mCurrentPos == iterEnd && !mKeyStack.empty()) {
417  mCurrentNode = mCurrentNode->parent();
418  mCurrentPos = mCurrentNode->mItems.find(mKeyStack.back());
419  ++mCurrentPos;
420  iterEnd = mCurrentNode->mItems.end();
421  mKeyStack.pop_back();
422  }
423 
424  for (; mCurrentPos != iterEnd; ++mCurrentPos) {
425  if (mCheckKeyRight) {
426  mCheckKeyRight = false;
427  ItemsContainerConstIter iter = mCurrentNode->mItems.find(mCurrentNode->endSymbol());
428  if (iter != iterEnd) {
429  mCurrentPos = iter;
430  const NodeItemClass & item = *(const NodeItemClass *) * mCurrentPos;
431  mKeyStack.push_back(item.get());
432  mKeyValuePair.first = &(mKeyStack[0]);
433  mKeyValuePair.second = &(((const EndNodeItemClass &)item).getValue());
434  mCheckKeyLeft = true;
435  return;
436  }
437  }
438 
439  if (*mCurrentPos) {
440  const NodeItemClass &item = *(const NodeItemClass *) * mCurrentPos;
441  if (item != mCurrentNode->endSymbol()) {
442  mKeyStack.push_back(item.get());
443  pushNode(item.getChilds());
444  break;
445  }
446  }
447  }
448  }
449  mEndReached = true;
450  }
451 
452  bool isEnd() const {
453  if (this->mRootNode == this->mCurrentNode &&
454  this->mCurrentPos == this->mCurrentNode->mItems.end()) {
455  return true;
456  }
457  return false;
458  }
459 
460  bool isLeftEnd() const {
461  if (this->mRootNode == this->mCurrentNode &&
462  this->mCurrentPos == this->mCurrentNode->mItems.begin()) {
463  return true;
464  }
465  return false;
466  }
467 
468  bool equals(const const_iterator & oth) const {
469  if (this->isEnd() && oth.isEnd()) {
470  return true;
471  }
472 
473  if (this->mCurrentNode == oth.mCurrentNode &&
474  this->mCurrentPos == oth.mCurrentPos) {
475  return true;
476  }
477 
478  return false;
479  }
480 
481  void pushNode(const NodeClass *node, const T * key = 0, bool mooveToEnd = false) {
482  mCurrentNode = node;
483  mCheckKeyLeft = false;
484  if (mooveToEnd) {
485  mCurrentPos = mCurrentNode->mItems.end();
486  mEndReached = true;
487  mCheckKeyRight = false;
488  } else {
489  if (key) {
490  for (int i = 0; key[i] != node->endSymbol(); ++i) {
491  mKeyStack.push_back(key[i]);
492  }
493  }
494  mCurrentPos = node->mItems.begin();
495  mCheckKeyRight = true;
496  }
497  }
498  };
499 
500  class iterator : public const_iterator
501  {
502  private:
503  typedef std::pair<const T *, V *> MutableKeyValuePair;
504  MutableKeyValuePair mMutableKeyValuePair;
505 
506  private:
507  MutableKeyValuePair & getPair() {
508  mMutableKeyValuePair.first = this->mKeyValuePair.first;
509  mMutableKeyValuePair.second = const_cast<V *>(this->mKeyValuePair.second);
510  return this->mMutableKeyValuePair;
511  }
512 
513  public:
514  iterator(NodeClass *node, NodeClass *root, const T * key = 0, bool mooveToEnd = false)
515  : const_iterator(node, root, key, mooveToEnd) {}
516 
517  MutableKeyValuePair &operator*() {
518  return getPair();
519  }
520 
521  MutableKeyValuePair *operator->() {
522  return &(getPair());
523  }
524 
525  iterator operator++(int) {
526  iterator iter = *this;
527  ++(*this);
528  return iter;
529  }
530 
531  iterator &operator++() {
532  this->next();
533  return *this;
534  }
535 
536  iterator operator--(int) {
537  iterator iter = *this;
538  --(*this);
539  return iter;
540  }
541 
542  iterator &operator--() {
543  this->previous();
544  return *this;
545  }
546  };
547 
548 private:
549  Node(Node const &);
550  Node &operator=(Node const &);
551 
552  static void deleteItem(NodeItemClass *item) {
553  delete item;
554  }
555 
556 
557  NodeClass * nodeWithKey(const T *key) {
558  return const_cast<NodeClass *>(const_cast<const NodeClass *>(this)->nodeWithKey(key));
559  }
560 
561  const NodeClass * nodeWithKey(const T *key) const {
562  const NodeClass * node = nodeWithPrefix(key);
563  if (node) {
564  if (node->mItems.getItem(mEndSymbol)) {
565  return node;
566  }
567  }
568  return 0;
569  }
570 
571  const NodeClass * nodeWithPrefix(const T *prefix) const {
572  int i=0;
573  const NodeClass * node = this;
574 
575  while (node) {
576  if (prefix[i] == mEndSymbol) {
577  return node;
578  }
579  const NodeItemClass *item = node->mItems.getItem(prefix[i]);
580  if (!item) {
581  break;
582  }
583 
584  node = item->getChilds();
585  ++i;
586  }
587  return 0;
588  }
589 
590  bool erase(NodeClass * node, const T * key) {
591  bool erased = false;
592  int keyIndex = 0;
593 
594  if (node && key) {
595  bool finished = false;
596  int count = 0;
597  erased = true;
598 
599  if (!keyIndex) {
600  while (key[keyIndex] != node->endSymbol()) {
601  ++ keyIndex;
602  }
603  }
604 
605  while (node && !finished && erased) {
606  ItemsContainerIter iterEnd = node->mItems.end();
607 
608  count = 0;
609  for (ItemsContainerIter iter = node->mItems.begin(); iter != iterEnd; ++iter) {
610  if (*iter != 0) {
611  ++count;
612  }
613  }
614 
615  if (count > 1) {
616  erased = node->mItems.eraseItem(key[keyIndex]);
617  finished = true;
618  } else if (count == 1) {
619  erased = node->mItems.eraseItem(key[keyIndex]);
620  }
621 
622  --keyIndex;
623  node = node->parent();
624  }
625 
626  }
627  if (erased) {
628  --mSize;
629  }
630  return erased;
631  }
632 
633 public:
634  Node(const T &eSymbol, NodeClass * parent = 0)
635  : mItems(eSymbol),
636  mEndSymbol(eSymbol),
637  mSize(0),
638  mParent(parent) {}
639 
640  ~Node() {
641  clear();
642  }
643 
644  T endSymbol() const {
645  return mEndSymbol;
646  }
647 
648  void clear() {
649  std::for_each(mItems.begin(), mItems.end(), deleteItem);
650  mItems.clear();
651  mSize = 0;
652  }
653 
654  bool empty() const {
655  return size() == 0;
656  }
657 
658  unsigned int size() const {
659  return mSize;
660  }
661 
662  std::pair<iterator, bool> insert(const T *key, V const &value) {
663  std::pair<iterator, bool> result(end(), false);
664  int i = 0;
665  NodeClass * node = this;
666 
667  while (true) {
668  std::pair<typename Items::Item *, bool> itemPair = node->mItems.insertItem(key[i]);
669  NodeItemClass *item = itemPair.first;
670  if (itemPair.second) {
671  result.first = iterator(node, this, key);
672  break;
673  }
674  if (!item) {
675  break;
676  } else if (key[i] == mEndSymbol) {
677  ((EndNodeItemClass *)item)->set(key[i], value);
678  result.first = iterator(node, this, key);
679  result.second = true;
680  ++mSize;
681  break;
682  } else {
683  node = item->getOrCreateChilds(node);
684  }
685  ++i;
686  }
687 
688  return result;
689  }
690 
691  bool erase(iterator pos) {
692  if (pos.mCurrentNode && pos.mCurrentPos != pos.mCurrentNode->mItems.end()) {
693  return erase(const_cast<NodeClass *>(pos.mCurrentNode), pos->first);
694  }
695  return false;
696  }
697 
698  bool erase(const T *key) {
699  NodeClass * node = nodeWithKey(key);
700  if (node) {
701  return erase(node, key);
702  }
703  return false;
704  }
705 
706  const V *get(const T *key) const {
707  return const_cast<NodeClass *>(this)->get(key);
708  }
709 
710  V *get(const T *key) {
711  NodeClass * node = nodeWithKey(key);
712  if (node) {
713  NodeItemClass *item = node->mItems.getItem(mEndSymbol);
714  return &(((EndNodeItemClass *)item)->getValue());
715  }
716  return 0;
717  }
718 
719 
720  bool hasKey(const T *key) const {
721  return get(key) != (V *)0;
722  }
723 
724  const NodeClass * parent() const {
725  return mParent;
726  }
727 
728  NodeClass * parent() {
729  return mParent;
730  }
731 
732  const_iterator begin() const {
733  return const_iterator(this, this);
734  }
735 
736  const_iterator end() const {
737  return const_iterator(this, this, 0, true);
738  }
739 
740  iterator begin() {
741  return iterator(this, this);
742  }
743 
744  iterator end() {
745  return iterator(this, this, 0, true);
746  }
747 
748  const_iterator find(const T *key) const {
749  NodeClass * node = const_cast<NodeClass *>(this)->nodeWithKey(key);
750  if (!node) {
751  return const_iterator(this, this, 0, true);
752  } else {
753  return const_iterator(node, this, key);
754  }
755  }
756 
757  iterator find(const T *key) {
758  NodeClass * node = this->nodeWithKey(key);
759  if (!node) {
760  return iterator(this, this, 0, true);
761  } else {
762  return iterator(node, this, key);
763  }
764  }
765 
766  iterator startsWith(const T *prefix) {
767  const NodeClass * node = const_cast<const NodeClass *>(this)->nodeWithPrefix(prefix);
768  if (!node) {
769  return iterator(this, this, 0, true);
770  } else {
771  return iterator(const_cast<NodeClass *>(node), const_cast<NodeClass *>(node), prefix);
772  }
773  }
774 
775  const_iterator startsWith(const T *prefix) const {
776  const NodeClass * node = nodeWithPrefix(prefix);
777  if (!node) {
778  return const_iterator(this, this, 0, true);
779  } else {
780  return const_iterator(node, node, prefix);
781  }
782  }
783 
784 private:
785  Items mItems;
786  const T mEndSymbol;
787  unsigned int mSize;
788  NodeClass * mParent;
789 };
790 
791 /*!
792  *
793  */
794 template <typename T> class SymbolToIndexMapper
795 {
796 public:
797  unsigned int operator()(const T & c) const {
798  return static_cast<unsigned int>(c);
799  }
800 };
801 
802 /*!
803  * @brief Container representing each node in the Trie.
804  *
805  *
806  * With this class the container used for storing node item is STL vector.
807  * Here each node will use a space propotional to Max.
808  * For searching only constant time taken at each node.
809  * @tparam T Type for each element in the key
810  * @tparam V Type of the value that the key will be representing
811  * @tparam Cmp Comparison functor
812  * @tparam Max Maximum element that a Trie node can have
813  */
814 template < typename T,
815 typename V,
816 typename Cmp,
817 int Max = 256,
818 typename M = SymbolToIndexMapper<T> > class VectorItems
819 {
820 public:
821  typedef NodeItem<T, V, Cmp, VectorItems<T, V, Cmp, Max, M> > Item;
822  typedef std::vector<Item *> Items;
823  typedef typename Items::iterator iterator;
824  typedef typename Items::const_iterator const_iterator;
825  typedef Node<T, V, Cmp, VectorItems<T, V, Cmp, Max, M> > NodeClass;
826  typedef typename NodeClass::NodeItemClass NodeItemClass;
827  typedef typename NodeClass::EndNodeItemClass EndNodeItemClass;
828 
829 public:
830  VectorItems(T const &endSymbol)
831  : mEndSymbol(endSymbol),
832  mItems(Max, (Item *)0) {}
833 
834  const_iterator find(const T & k) const {
835  const Item * item = getItem(k);
836  if (item) {
837  return mItems.begin() + mSymolToIndex(k);
838  }
839  return mItems.end();
840  }
841 
842  iterator find(const T & k) {
843  const Item * item = getItem(k);
844  if (item) {
845  return mItems.begin() + mSymolToIndex(k);
846  }
847  return mItems.end();
848  }
849 
850  iterator begin() {
851  return mItems.begin();
852  }
853 
854  const_iterator begin() const {
855  return mItems.begin();
856  }
857 
858  iterator end() {
859  return mItems.end();
860  }
861 
862  const_iterator end() const {
863  return mItems.end();
864  }
865 
866  void clear() {
867  std::fill(mItems.begin(), mItems.end(), (Item *)0);
868  }
869 
870  bool empty() const {
871  return mItems.empty();
872  }
873 
874  std::pair<Item *, bool> insertItem(T const &k) {
875  std::pair<Item *, bool> ret((Item *)0, false);
876  if (!getItem(k)) {
877  assignItem(k, createNodeItem(k));
878  ret.first = getItem(k);
879  } else {
880  ret.first = getItem(k);
881  if (k == mEndSymbol) {
882  ret.second = true;
883  }
884  }
885  return ret;
886  }
887 
888  bool eraseItem(T const &k) {
889  Item * item = getItem(k);
890  if (item) {
891  delete item;
892  assignItem(k, (Item *)0);
893  return true;
894  } else {
895  return false;
896  }
897  }
898 
899  Item *getItem(T const &k) {
900  return mItems[mSymolToIndex(k)];
901  }
902 
903  const Item *getItem(T const &k) const {
904  return mItems[mSymolToIndex(k)];
905  }
906 
907  void assignItem(T k, Item *i) {
908  mItems[mSymolToIndex(k)] = i;
909  }
910 
911  NodeItemClass *createNodeItem(T const &k) {
912  if (k == mEndSymbol) {
913  return new EndNodeItemClass(mEndSymbol, k);
914  } else {
915  return new NodeItemClass(mEndSymbol, k);
916  }
917  }
918 
919 protected:
920  const T mEndSymbol;
921  Items mItems;
922  M mSymolToIndex;
923 };
924 
925 /*!
926  * @brief Container representing each node in the Trie.
927  *
928  *
929  * With this class the container used for storing node item is STL set.
930  * Here no extra space will used for storing node item.
931  * For searching in each node the time taken is propotional to number of item in the node.
932  * @tparam T Type for each element in the key
933  * @tparam V Type of the value that the key will be representing
934  * @tparam Cmp Comparison functor
935  */
936 template < typename T,
937 typename V,
938 typename Cmp > class SetItems
939 {
940 public:
941  typedef NodeItem<T, V, Cmp, SetItems<T, V, Cmp> > Item;
942  typedef std::set<Item *, NodeItemPtrCompare<T, V, Cmp, SetItems<T, V, Cmp> > > Items;
943  typedef typename Items::iterator iterator;
944  typedef typename Items::const_iterator const_iterator;
945  typedef Node<T, V, Cmp, SetItems<T, V, Cmp> > NodeClass;
946  typedef typename NodeClass::NodeItemClass NodeItemClass;
947  typedef typename NodeClass::EndNodeItemClass EndNodeItemClass;
948 
949 public:
950  SetItems(T const &endSymbol)
951  : mEndSymbol(endSymbol) {}
952 
953  const_iterator find(const T & k) const {
954  return const_cast<SetItems<T, V, Cmp> *>(this)->find(k);
955  }
956 
957  iterator find(const T & k) {
958  Item tmp(mEndSymbol, k);
959  return mItems.find(&tmp);
960  }
961 
962  iterator begin() {
963  return mItems.begin();
964  }
965 
966  const_iterator begin() const {
967  return mItems.begin();
968  }
969 
970  iterator end() {
971  return mItems.end();
972  }
973 
974  const_iterator end() const {
975  return mItems.end();
976  }
977 
978  bool empty() const {
979  return mItems.empty();
980  }
981 
982  void clear() {
983  mItems.clear();
984  }
985 
986  std::pair<Item *, bool> insertItem(T const &k) {
987  std::pair<Item *, bool> ret((Item*)0, false);
988  Item tmp(mEndSymbol, k);
989  iterator iter = mItems.find(&tmp);
990  if (iter == mItems.end()) {
991  Item *v = createNodeItem(k);
992  mItems.insert(v);
993  ret.first = v;
994  } else {
995  ret.first = (Item *) * iter;
996  if (k == mEndSymbol) {
997  ret.second = true;
998  }
999  }
1000  return ret;
1001  }
1002 
1003  bool eraseItem(T const &k) {
1004  Item tmp(mEndSymbol, k);
1005  iterator iter = mItems.find(&tmp);
1006  if (iter != mItems.end()) {
1007  delete *iter;
1008  mItems.erase(iter);
1009  return true;
1010  } else {
1011  return false;
1012  }
1013  }
1014 
1015  const Item *getItem(T const &k) const {
1016  return const_cast<SetItems *>(this)->getItem(k);
1017  }
1018 
1019  Item *getItem(T const &k) {
1020  Item tmp(mEndSymbol, k);
1021 
1022  iterator iter = mItems.find(&tmp);
1023  if (iter == mItems.end()) {
1024  return 0;
1025  }
1026  return (Item *)(*iter);
1027  }
1028 
1029  NodeItemClass *createNodeItem(T const &k) {
1030  if (k == mEndSymbol) {
1031  return new EndNodeItemClass(mEndSymbol, k);
1032  } else {
1033  return new NodeItemClass(mEndSymbol, k);
1034  }
1035  }
1036 
1037 protected:
1038  const T mEndSymbol;
1039  Items mItems;
1040 };
1041 
1042 /*!
1043  * @page simple_trie Simple Trie
1044  * @section trie_intro_sec Introduction
1045  * This is an implementation of prefix Trie data structure. This implementation is in C++ and using template.
1046  * @section trie_features Features
1047  * Following are the main operations provided by the Trie.
1048  * <ul>
1049  * <li>Adding key, value pair
1050  * <li>Removing an element by key
1051  * <li>Checking the existence of a key
1052  * <li>Retrieving value by key
1053  * <li>Find elements with common prefix
1054  * <li>Iterator
1055  * </ul>
1056  */
1057 
1058 
1059 /*!
1060  * @brief Trie main class
1061  * @tparam T Type for each element in the key
1062  * @tparam V Type of the value that the key will be representing
1063  * @tparam Cmp Comparison functor
1064  * @tparam Items The data structure that represents each node in the Trie.
1065  * Items can be Mezzanine::SetItems<T, V, Cmp> or Mezzanine::VectorItems<T, V, Cmp, Max>,
1066  * Max is the integer representing number of elements in each Trie node.
1067  *
1068  * @section usage_sec Usage of the Trie
1069  * @subsection usage_declaration Declarating the Trie
1070  * A Trie with key as chars and value as std::string can be declared as given below
1071  * @code
1072  * #include <string>
1073  * #include <trie.h>
1074  *
1075  * int main(int argc, char ** argv) {
1076  *
1077  * Mezzanine::Trie<char, std::string> dictionary('$');
1078  *
1079  * return 0;
1080  * }
1081  * @endcode
1082  *
1083  * @subsection usage_population Populatiion and deletion from the Trie
1084  * Trie can be populated by using the Trie::insert method and element can be removed using Trie::erase.
1085  * @code
1086  * #include <trie.h>
1087  * #include <string>
1088  * #include <iostream>
1089  *
1090  * int main(int argc, char ** argv) {
1091  *
1092  * Mezzanine::Trie<char, std::string> dictionary('$');
1093  *
1094  * // adding key value pair to the Trie
1095  * if (dictionary.insert("karma$", "Destiny or fate, following as effect from cause").second) {
1096  * std::cout << "added karma" << std::endl;
1097  * }
1098  *
1099  * // removing key from the Trie
1100  * if (dictionary.erase("karma$")) {
1101  * std::cout << "removed karma" << std::endl;
1102  * }
1103  *
1104  * return 0;
1105  * }
1106  *
1107  * @endcode
1108  * @subsection usage_retrieval Retrieval of Value
1109  * Value for a key can be retrieved using Trie::get method and
1110  * the existence of the key can be tested using Trie::hasKey method.
1111  * @code
1112  * #include <trie.h>
1113  * #include <string>
1114  * #include <iostream>
1115  *
1116  * int main(int argc, char ** argv) {
1117  *
1118  * Mezzanine::Trie<char, std::string> dictionary('$');
1119  *
1120  * dictionary.insert("karma$", "Destiny or fate, following as effect from cause");
1121  *
1122  * if (dictionary.hasKey("karma$")) {
1123  * std::cout << "key karma found" << std::endl;
1124  * }
1125  * std::string * result = dictionary.get("karma$");
1126  * if (result) {
1127  * std::cout << result->c_str() << std::endl;
1128  * }
1129  *
1130  * return 0;
1131  * }
1132  * @endcode
1133  *
1134  * @subsection usage_searching Searching keys which have common prefix
1135  * Keys which begins with a specific charactars can be retrieved using Trie::startsWith method
1136  * @code
1137  * #include <trie.h>
1138  * #include <string>
1139  * #include <iostream>
1140  * #include <vector>
1141  *
1142  * int main(int argc, char ** argv) {
1143  *
1144  * Mezzanine::Trie<char, std::string> dictionary('\0');
1145  *
1146  * dictionary.insert("karma", "Destiny or fate, following as effect from cause");
1147  * Mezzanine::Trie<char, std::string>::iterator iter = dictionary.startsWith("kar");
1148  *
1149  * for (; iter != dictionary.end(); ++iter) {
1150  * std::cout << iter->first << " : " << iter->second->c_str() << std::endl;
1151  * }
1152  *
1153  * return 0;
1154  * }
1155  * @endcode
1156  *
1157  * @subsection usage_array_of_node Trie with each Node as an array
1158  * Here each node of the Trie is an array. The advantage is that the searching of a symbol in the array takes O(1) time (is constant time).
1159  * The disadvantage is that the array will have empty elements so the space used will more than actually required.
1160  *
1161  * @code
1162  *
1163  * #include <trie.h>
1164  * #include <string>
1165  * #include <iostream>
1166  * #include <vector>
1167  *
1168  * int main(int argc, char ** argv) {
1169  *
1170  * // Here 256 is the size of array in each node
1171  * Mezzanine::Trie<char, std::string, std::less<char>,
1172  * Mezzanine::VectorItems<char, std::string, std::less<char>, 256> > dictionary('$');
1173  *
1174  * return 0;
1175  * }
1176  * @endcode
1177  *
1178  * @subsection usage_vector_item Efficient use of Trie for alphabets
1179  * Below example shows how to use Trie to operate on alphabets efficiently.
1180  * Here VectorItems is used to store alphabets with size of 28 (26 alphabets + space + end symbol).
1181  *
1182  * @code
1183  * #include <trie.h>
1184  * #include <string>
1185  * #include <iostream>
1186  * #include <vector>
1187  * #include <cctype>
1188  *
1189  * class TrieCaseInsensitiveCompare
1190  * {
1191  * public:
1192  * bool operator()(char v1, char v2) {
1193  * int i1 = std::tolower(v1);
1194  * int i2 = std::tolower(v2);
1195  * return i1 < i2;
1196  * }
1197  * };
1198  *
1199  * // key to vector index converter
1200  * // case insensitive and includes alphabets, space and end symbol
1201  * class AlphaToIndex
1202  * {
1203  * public:
1204  * unsigned int operator()(const char & c) const {
1205  * unsigned int index = 0;
1206  * if (c == ' ') {
1207  * index = 27;
1208  * } else if (c >= 'A' && c <= 'Z') {
1209  * index = c - 'A' + 1;
1210  * } else if (c >= 'a' && c <= 'z') {
1211  * index = c - 'a' + 1;
1212  * }
1213  * return index;
1214  * }
1215  * };
1216  *
1217  * int main(int argc, char ** argv) {
1218  *
1219  * Mezzanine::Trie<char, std::string,
1220  * TrieCaseInsensitiveCompare,
1221  * Mezzanine::VectorItems<char, std::string, TrieCaseInsensitiveCompare, 28, AlphaToIndex>
1222  * > dictionary('\0');
1223  *
1224  * // adding key value pair to the Trie
1225  * if (dictionary.insert("karma", "Destiny or fate, following as effect from cause").second) {
1226  * std::cout << "added karma" << std::endl;
1227  * }
1228  *
1229  * // removing key from the Trie
1230  * if (dictionary.erase("karma")) {
1231  * std::cout << "removed karma" << std::endl;
1232  * }
1233  *
1234  * return 0;
1235  * }
1236  *
1237  * @endcode
1238  *
1239  * @subsection usage_set_of_node Trie with each Node as a set
1240  * Here each node will be an ordered set.
1241  * Here there will be no extra usage of space but search for a symbol in the node takes logarithmic time.
1242  * Trie with this feature can also be used for caseinsensitive symbol handling.
1243  * @code
1244  *
1245  * #include <trie.h>
1246  * #include <string>
1247  * #include <iostream>
1248  * #include <set>
1249  *
1250  * int main(int argc, char ** argv) {
1251  *
1252  * Mezzanine::Trie<char, std::string, std::less<char>,
1253  * Mezzanine::SetItems<char, std::string, std::less<char> > > dictionary('$');
1254  *
1255  * return 0;
1256  * }
1257  * @endcode
1258  * @subsection usage_iterator Using Trie::iterator
1259  * Trie iterator can be used the same way as STL iterator.
1260  * Key and value can be accessed from iterator using first and secod member.
1261  * first is vector of key characters and second is a pointer to the value.
1262  * @code
1263  * #include <trie.h>
1264  * #include <string>
1265  * #include <iostream>
1266  * #include <vector>
1267  *
1268  * int main(int argc, char ** argv) {
1269  *
1270  * Mezzanine::Trie<char, std::string> dictionary('\0');
1271  *
1272  * dictionary.insert("karma$", "Destiny or fate, following as effect from cause");
1273  *
1274  * Mezzanine::Trie<char, std::string>::iterator iter = dictionary.begin();
1275  * Mezzanine::Trie<char, std::string>::iterator iend = dictionary.end();
1276  *
1277  * for (; iter != iend; ++iter) {
1278  *
1279  * std::cout << iter->first << " " << iter->second->c_str() << std::endl;
1280  * }
1281  *
1282  * return 0;
1283  * }
1284  * @endcode
1285  */
1286 template < typename T,
1287 typename V,
1288 typename Cmp = std::less<T>,
1289 typename Items = SetItems<T, V, Cmp> > class Trie
1290 {
1291 public:
1292  typedef typename Node<T, V, Cmp, Items>::iterator iterator;
1293  typedef typename Node<T, V, Cmp, Items>::const_iterator const_iterator;
1294 
1295 public:
1296  /*!
1297  * @param endSymbol The symbol which marks the end of key input
1298  */
1299  Trie(const T &endSymbol)
1300  : mRoot(endSymbol) {}
1301 
1302  /*!
1303  * Add a key with value in to the Trie
1304  * @param key Key which should be inserted, should be terminated by 'end' symbol
1305  * @param value The value that is to be set with the key
1306  * @return An std::pair with pair::first set to the iterator points to the element and pair::second to true is key is newly inserted, false otherwise
1307  */
1308  std::pair<iterator, bool> insert(const T *key, V const &value) {
1309  return mRoot.insert(key, value);
1310  }
1311 
1312  /*!
1313  * Add a key with value in to the Trie
1314  * @param key Key which should be inserted, should be terminated by 'end' symbol
1315  * @param value The value that is to be set with the key
1316  * @return An std::pair with pair::first set to the iterator points to the element and pair::second to true is key is newly inserted, false otherwise
1317  */
1318  std::pair<iterator, bool> insert(const std::vector<T>& key, V const &value) {
1319  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1320  return this->insert(&key[0], value);
1321  }
1322 
1323  /*!
1324  * Remove the entry with the given key from the Trie
1325  * @param key Key which should be erased, should be terminated by 'end' symbol
1326  * @return true if the given key is erased from the Trie, false otherwise
1327  */
1328  bool erase(const T *key) {
1329  return mRoot.erase(key);
1330  }
1331 
1332  /*!
1333  * Remove the entry with the given key from the Trie
1334  * @param key Key which should be erased, should be terminated by 'end' symbol
1335  * @return true if the given key is erased from the Trie, false otherwise
1336  */
1337  bool erase(const std::vector<T>& key) {
1338  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1339  return this->erase(&key[0]);
1340  }
1341 
1342  /*!
1343  * Remove the entry with the given key from the Trie
1344  * @param pos iterator pointing to a single element to be removed from the Trie
1345  * @return true if the given key is erased form the Trie, false otherwise
1346  */
1347  bool erase(iterator pos) {
1348  return mRoot.erase(pos);
1349  }
1350 
1351  /*!
1352  * Retrieves the value for the given key
1353  * @param key Key to be searched for, should be terminated by 'end' symbol
1354  * @return Constant pointer to value for the given key, 0 on failure
1355  */
1356  const V *get(const T *key) const {
1357  return mRoot.get(key);
1358  }
1359 
1360  /*!
1361  * Retrieves the value for the given key
1362  * @param key Key to be searched for, should be terminated by 'end' symbol
1363  * @return Constant pointer to value for the given key, 0 on failure
1364  */
1365  const V *get(const std::vector<T>& key) const {
1366  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1367  return this->get(&key[0]);
1368  }
1369 
1370  /*!
1371  * Retrieves the value for the given key
1372  * @param key Key to be searched for, should be terminated by 'end' symbol
1373  * @return Pointer to value for the given key, 0 on failure
1374  */
1375  V *get(const T *key) {
1376  return mRoot.get(key);
1377  }
1378 
1379  /*!
1380  * Retrieves the value for the given key
1381  * @param key Key to be searched for, should be terminated by 'end' symbol
1382  * @return Pointer to value for the given key, 0 on failure
1383  */
1384  V *get(const std::vector<T>& key) {
1385  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1386  return this->get(&key[0]);
1387  }
1388 
1389  /*!
1390  * Retrieves the value for the given key,
1391  * If key does not match the key of any element in the Trie,
1392  * the function inserts a new element with that key and returns a reference to its mapped value
1393  * @param key Key to be searched for, should be terminated by 'end' symbol
1394  * @return Reference to value for the given key
1395  */
1396  V &operator[](const T *key) {
1397  return *(insert(key, V()).first->second);
1398  }
1399 
1400  /*!
1401  * Retrieves the value for the given key,
1402  * If key does not match the key of any element in the Trie,
1403  * the function inserts a new element with that key and returns a reference to its mapped value
1404  * @param key Key to be searched for, should be terminated by 'end' symbol
1405  * @return Reference to value for the given key
1406  */
1407  V &operator[](const std::vector<T>& key) {
1408  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1409  return this->operator[](&key[0]);
1410  }
1411 
1412  /*!
1413  * Checks whether the given key is present in the Trie
1414  * @param key Key to be searched for, should be terminated by 'end' symol
1415  * @return true if the key is present
1416  */
1417  bool hasKey(const T *key) const {
1418  return mRoot.hasKey(key);
1419  }
1420 
1421  /*!
1422  * Checks whether the given key is present in the Trie
1423  * @param key Key to be searched for, should be terminated by 'end' symol
1424  * @return true if the key is present
1425  */
1426  bool hasKey(const std::vector<T>& key) const {
1427  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1428  return this->hasKey(&key[0]);
1429  }
1430 
1431  /*!
1432  * Test whether Trie is empty
1433  * @return true if the Trie size is 0, false otherwise
1434  */
1435  bool empty() const {
1436  return mRoot.empty();
1437  }
1438 
1439  /*!
1440  * Returns the number of elements in the Trie
1441  * @return Number of key value pair in the Trie
1442  */
1443  unsigned int size() const {
1444  return mRoot.size();
1445  }
1446 
1447  /*!
1448  * All the elements in the Trie are dropped, leaving the Trie with a size of 0.
1449  */
1450  void clear() {
1451  mRoot.clear();
1452  }
1453 
1454  /*!
1455  * Retrieves iterator to the elements with common prefix
1456  * @param prefix Part of the key which should be searched, should be terminated by 'end' symbol
1457  * @return Iterator to the elements with prefix specified in 'prefix'
1458  */
1459  iterator startsWith(const T *prefix) {
1460  return mRoot.startsWith(prefix);
1461  }
1462 
1463  /*!
1464  * Retrieves iterator to the elements with common prefix
1465  * @param prefix Part of the key which should be searched, should be terminated by 'end' symbol
1466  * @return Iterator to the elements with prefix specified in 'prefix'
1467  */
1468  iterator startsWith(const std::vector<T>& prefix) {
1469  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1470  return this->startsWith(&prefix[0]);
1471  }
1472 
1473  /*!
1474  * Retrieves const_iterator to the elements with common prefix
1475  * @param prefix Part of the key which should be searched, should be terminated by 'end' symbol
1476  * @return const_iterator to the elements with prefix specified in 'prefix'
1477  */
1478  const_iterator startsWith(const T *prefix) const {
1479  return mRoot.startsWith(prefix);
1480  }
1481 
1482  /*!
1483  * Retrieves const_iterator to the elements with common prefix
1484  * @param prefix Part of the key which should be searched, should be terminated by 'end' symbol
1485  * @return const_iterator to the elements with prefix specified in 'prefix'
1486  */
1487  const_iterator startsWith(const std::vector<T>& prefix) const {
1488  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1489  return this->startsWith(&prefix[0]);
1490  }
1491 
1492  /*!
1493  * Retrieves the end symbol
1494  * @return end symbol
1495  */
1496  T endSymbol() const {
1497  return mRoot.endSymbol();
1498  }
1499 
1500  /*!
1501  * Returns an iterator referring to the first element in the Trie
1502  * @return An iterator to the first element in the Trie
1503  */
1504  iterator begin() {
1505  return mRoot.begin();
1506  }
1507 
1508  /*!
1509  * Returns an iterator referring to the past-the-end element in the Trie
1510  * @return An iterator to the element past the end of the Trie
1511  */
1512  iterator end() {
1513  return mRoot.end();
1514  }
1515 
1516  /*!
1517  * Searches the Trie for an element with 'key' as key
1518  * @param key Key to be searched for, should be terminated by 'end' symbol
1519  * @return Iterator to the element with key 'key' if found, otherwise an iterator to Trie::end
1520  */
1521  iterator find(const T *key) {
1522  return mRoot.find(key);
1523  }
1524 
1525  /*!
1526  * Searches the Trie for an element with 'key' as key
1527  * @param key Key to be searched for, should be terminated by 'end' symbol
1528  * @return Iterator to the element with key 'key' if found, otherwise an iterator to Trie::end
1529  */
1530  iterator find(const std::vector<T>& key) {
1531  /// @todo Currently this uses a hack that isn't safe for all types and circumstances. This should be changed to use "data()" function member new to C++11 when we make that dive.
1532  return this->find(&key[0]);
1533  }
1534 
1535  /*!
1536  * Searches the Trie for an element with 'key' as key
1537  * @param key Key to be searched for, should be terminated by 'end' symbol
1538  * @return const_iterator to the element with key 'key' if found, otherwise an const_iterator to Trie::end
1539  */
1540  const_iterator find(const T *key) const {
1541  return mRoot.find(key);
1542  }
1543 
1544  /*!
1545  * Searches the Trie for an element with 'key' as key
1546  * @param key Key to be searched for, should be terminated by 'end' symbol
1547  * @return const_iterator to the element with key 'key' if found, otherwise an const_iterator to Trie::end
1548  */
1549  const_iterator find(const std::vector<T>& key) const {
1550  return this->find(&key[0]);
1551  }
1552 
1553  /*!
1554  * Returns an constant iterator referring to the first element in the Trie
1555  * @return An constant iterator to the first element in the Trie
1556  */
1557  const_iterator begin() const {
1558  return mRoot.begin();
1559  }
1560 
1561  /*!
1562  * Returns an constant iterator referring to the past-the-end element in the Trie
1563  * @return An constant iterator to the element past the end of the Trie
1564  */
1565  const_iterator end() const {
1566  return mRoot.end();
1567  }
1568 
1569 private:
1570  Trie(Trie const &);
1571  Trie &operator=(Trie const &);
1572 
1573 private:
1574  Node<T, V, Cmp, Items> mRoot;
1575 };
1576 
1577 }
1578 
1579 /// @endcond
1580 
1581 #endif
All the definitions for datatypes as well as some basic conversion functions are defined here...
Mezzanine::Vector3 operator*(const btVector3 &Vec, const Mezzanine::Vector3 &lhs)
Right Hand Multiplication Operator for Bullet Vectors with a Mezzanine::Vector3.
Definition: vector3.cpp:651
The bulk of the engine components go in this namspace.
Definition: actor.cpp:56