• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • Directories
  • File List
  • File Members

trie.hpp

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 #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__

Generated on Wed Sep 29 2010 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.7.1