00001 /* 00002 CLAW - a C++ Library Absolutely Wonderful 00003 00004 CLAW is a free library without any particular aim but being useful to 00005 anyone. 00006 00007 Copyright (C) 2005-2008 Julien Jorge 00008 00009 This library is free software; you can redistribute it and/or 00010 modify it under the terms of the GNU Lesser General Public 00011 License as published by the Free Software Foundation; either 00012 version 2.1 of the License, or (at your option) any later version. 00013 00014 This library is distributed in the hope that it will be useful, 00015 but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00017 Lesser General Public License for more details. 00018 00019 You should have received a copy of the GNU Lesser General Public 00020 License along with this library; if not, write to the Free Software 00021 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00022 00023 contact: julien_jorge@yahoo.fr 00024 */ 00030 #ifndef __CLAW_TRIE_HPP__ 00031 #define __CLAW_TRIE_HPP__ 00032 00033 #include <list> 00034 #include <functional> 00035 #include <claw/binary_node.hpp> 00036 00037 namespace claw 00038 { 00039 00062 template<class T, class Comp = std::equal_to<T> > class trie 00063 { 00064 private: 00065 //************************ trie::trie_node ******************************** 00066 00073 struct trie_node : public binary_node< trie_node > 00074 { 00076 T value; 00081 unsigned int count; 00082 00083 trie_node( const T& val, unsigned int c = 0 ); 00084 trie_node( const trie_node& that ); 00085 00086 }; // trie_node; 00087 00088 public: 00089 //****************************** trie ************************************* 00090 00091 typedef const T value_type; 00092 typedef Comp value_equal_to; 00093 00094 private: 00095 typedef trie_node* trie_node_ptr; 00096 00097 public: 00098 00099 trie(); 00100 trie( const trie<T, Comp>& that ); 00101 ~trie(); 00102 00103 unsigned int size() const; 00104 bool empty() const; 00105 00106 void clear(); 00107 00108 template<class InputIterator> 00109 void insert(InputIterator first, InputIterator last); 00110 00111 template <class InputIterator> 00112 unsigned int count(InputIterator first, InputIterator last); 00113 00114 private: 00116 static value_equal_to s_value_equal_to; 00117 00119 trie_node_ptr m_tree; 00120 00122 unsigned int m_size; 00123 }; // class trie 00124 00125 } // namespace claw 00126 00127 #include <claw/impl/trie.tpp> 00128 00129 #endif // __CLAW_TRIE_HPP__