trie.hpp
Go to the documentation of this file.
/*
CLAW - a C++ Library Absolutely Wonderful
CLAW is a free library without any particular aim but being useful to
anyone.
Copyright (C) 2005-2011 Julien Jorge
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
contact: julien.jorge@gamned.org
*/
#ifndef __CLAW_TRIE_HPP__
#define __CLAW_TRIE_HPP__
#include <list>
#include <functional>
#include <claw/binary_node.hpp>
namespace claw
{
template<class T, class Comp = std::equal_to<T> > class trie
{
private:
//************************ trie::trie_node ********************************
struct trie_node : public binary_node< trie_node >
{
T value;
unsigned int count;
trie_node( const T& val, unsigned int c = 0 );
trie_node( const trie_node& that );
}; // trie_node;
public:
//****************************** trie *************************************
typedef const T value_type;
typedef Comp value_equal_to;
private:
typedef trie_node* trie_node_ptr;
public:
trie();
trie( const trie<T, Comp>& that );
~trie();
unsigned int size() const;
bool empty() const;
void clear();
template<class InputIterator>
void insert(InputIterator first, InputIterator last);
template <class InputIterator>
unsigned int count(InputIterator first, InputIterator last);
private:
static value_equal_to s_value_equal_to;
trie_node_ptr m_tree;
unsigned int m_size;
}; // class trie
} // namespace claw
#include <claw/impl/trie.tpp>
#endif // __CLAW_TRIE_HPP__
claw::trie
This class is a trie tree.
Definition: trie.hpp:62
claw::first
Fuction object to get the first element of a std::pair.
Definition: functional.hpp:44
claw::binary_node
Basic binary node.
Definition: binary_node.hpp:41
binary_node.hpp
Basic binary node.
claw
This is the main namespace.
Definition: algorithm.hpp:33