Claw
1.7.0
|
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-2011 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@gamned.org 00024 */ 00030 #include <iostream> 00031 #include <cassert> 00032 00033 //*************************** trie::trie_node ********************************* 00034 00035 00036 /*---------------------------------------------------------------------------*/ 00043 template<class T, class Comp> 00044 claw::trie<T, Comp>::trie_node::trie_node( const T& val, 00045 unsigned int c /*= 0*/ ) 00046 : claw::binary_node< typename claw::trie<T, Comp>::trie_node >(), value(val), 00047 count(0) 00048 { 00049 00050 } // trie_node() [constructor] 00051 00052 /*---------------------------------------------------------------------------*/ 00057 template<class T, class Comp> 00058 claw::trie<T, Comp>::trie_node::trie_node( const trie_node& that ) 00059 : claw::binary_node< typename claw::trie<T, Comp>::trie_node >(that), 00060 value(that.value), count(that.count) 00061 { 00062 00063 } // trie_node [copy constructor] 00064 00065 //********************************* trie ************************************** 00066 00067 /*---------------------------------------------------------------------------*/ 00068 template<class T, class Comp> 00069 typename claw::trie<T, Comp>::value_equal_to 00070 claw::trie<T, Comp>::s_value_equal_to; 00071 00072 /*---------------------------------------------------------------------------*/ 00077 template<class T, class Comp> 00078 claw::trie<T, Comp>::trie() 00079 { 00080 m_size = 0; 00081 m_tree = NULL; 00082 00083 assert(empty()); 00084 } // trie() [constructor] 00085 00086 /*---------------------------------------------------------------------------*/ 00087 /* 00088 * \brief Trie copy constructor. 00089 */ 00090 template<class T, class Comp> 00091 claw::trie<T, Comp>::trie( const claw::trie<T, Comp>& that ) 00092 { 00093 if (that.m_tree) 00094 m_tree = new trie_node( *that.m_tree ); 00095 else 00096 m_tree = NULL; 00097 00098 m_size = that.m_size; 00099 } // trie() [copy constructor] 00100 00101 /*---------------------------------------------------------------------------*/ 00105 template<class T, class Comp> 00106 claw::trie<T, Comp>::~trie() 00107 { 00108 if (m_tree) 00109 delete m_tree; 00110 } // ~trie() [destructor] 00111 00112 /*---------------------------------------------------------------------------*/ 00116 template<class T, class Comp> 00117 unsigned int claw::trie<T, Comp>::size() const 00118 { 00119 return m_size; 00120 } // size() 00121 00122 /*---------------------------------------------------------------------------*/ 00126 template<class T, class Comp> 00127 bool claw::trie<T, Comp>::empty() const 00128 { 00129 return m_tree==NULL; 00130 } // empty() 00131 00132 /*---------------------------------------------------------------------------*/ 00137 template<class T, class Comp> 00138 void claw::trie<T, Comp>::clear() 00139 { 00140 if (m_tree) 00141 { 00142 delete m_tree; 00143 m_tree = NULL; 00144 m_size = 0; 00145 } 00146 } // clear() 00147 00148 /*---------------------------------------------------------------------------*/ 00158 template<class T, class Comp> 00159 template<class InputIterator> 00160 void claw::trie<T, Comp>::insert(InputIterator first, InputIterator last) 00161 { 00162 assert( first != last ); 00163 00164 trie_node_ptr* p = &m_tree; // for tree search 00165 trie_node_ptr last_node = NULL; // last node of the inserted word 00166 00167 // Try to insert a maximum of items 00168 while ( *p && (first!=last) ) 00169 if ( s_value_equal_to((*p)->value, *first) ) 00170 { 00171 last_node = *p; 00172 p = & (*p)->right; 00173 ++first; 00174 } 00175 else 00176 p = & (*p)->left; 00177 00178 // If we haven't inserted the full word, 00179 // create the whole subtree. 00180 while (first != last) 00181 { 00182 *p = new trie_node(*first); 00183 last_node = *p; 00184 00185 ++first; 00186 p = & (*p)->right; 00187 } 00188 00189 ++(last_node->count); 00190 00191 // Don't forget to increase words count. 00192 ++m_size; 00193 } // insert() 00194 00195 /*---------------------------------------------------------------------------*/ 00204 template<class T, class Comp> 00205 template <class InputIterator> 00206 unsigned int claw::trie<T, Comp>::count(InputIterator first, 00207 InputIterator last) 00208 { 00209 assert( first != last ); 00210 00211 trie_node_ptr* p = & m_tree; // for tree search 00212 trie_node_ptr last_node = NULL; // last node of the word 00213 00214 // Try to find the word 00215 while ( *p && (first!=last) ) 00216 if ( s_value_equal_to((*p)->value, *first) ) 00217 { 00218 last_node = *p; 00219 p = & (*p)->right; 00220 ++first; 00221 } 00222 else 00223 p = & (*p)->left; 00224 00225 // found ? 00226 if (first==last) 00227 return last_node->count; 00228 else 00229 return 0; 00230 } // count()