trie.tpp

Go to the documentation of this file.
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 #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()

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1