#if !defined (TRIE_H)
#define TRIE_H
#include <string>
#include <limits>
#include <queue>
#include <set>
#if !defined (NO_BOOST)
#include <boost/lexical_cast.hpp>
#else
#include <sstream>
#endif
namespace lexical
{
//////////////////////////////////////////////////
// Debugging instrumentation
//////////////////////////////////////////////////
#if !defined (NDEBUG)
namespace detail
{
//! Provides a way to precompile out debug code.
#define TRIE_DEBUG(op) op
static std::size_t throw_count; //!< Countdown to throwing an exception.
static bool debug_enabled = false; //!< Only throw if this is true.
static const std::size_t tests_count = 11; //!< Number of can_throw()ing functions.
static std::size_t tested_count = 0; //!< How many can_throw()ers tested.
//! Marks places where the following code can throw an exception.
void
can_throw()
{
if (debug_enabled && throw_count-- <= 0)
{
throw 0;
}
}
//! Tests the strong exception safety guarantee.
template<typename T, class Operation>
void strong_check(const T &v, const Operation &op)
{
bool succeeded = false;
for (std::size_t count = 0; !succeeded; ++count)
{
T duplicate = v;
debug_enabled = true;
try
{
throw_count = count;
op (duplicate);
succeeded = true;
++tested_count;
debug_enabled = false;
}
catch (...)
{
debug_enabled = false;
bool unchanged = duplicate == v;
assert (unchanged);
}
}
}
}
#else
#define TRIE_DEBUG(op) ((void*)0)
#endif
//////////////////////////////////////////////////
// trie policies
//////////////////////////////////////////////////
//! Namespace for implementation details that should not be known to users of trie.
namespace detail
{
//! \brief Length policy for determining the lexicographical length of a given value.
template<typename T, typename SizeT>
struct length
: public std::unary_function<const T&, SizeT>
{
//! Default implementation uses boost::lexical_cast or stringstreams
//! to determine length of the value once it has been cast to a std::string.
//! \return The size (length) of given value.
SizeT
operator()(const T &value) const
{
TRIE_DEBUG (detail::can_throw ());
#if !defined (NO_BOOST)
return boost::lexical_cast<std::string> (value).length ();
#else
std::ostringstream oss;
oss << value;
return oss.str ().length ();
#endif
}
};
//! \brief Policy for determining a lexicographical prefix for a given value.
template<typename T, typename SizeT>
struct prefix
: public std::binary_function<const T&, SizeT, T>
{
//! Default implementation uses boost::lexical_cast or stringstreams to cast
//! the value as a std::string and then return an un-cast substring of that string.
//! \return The prefix value of given length.
T
operator()(const T &value, SizeT length) const
{
TRIE_DEBUG (detail::can_throw ());
bool neg = value < 0;
#if !defined (NO_BOOST)
using boost::lexical_cast;
T r = lexical_cast<T> (
lexical_cast<std::string> (neg ? -value : value).substr (0, length));
#else
std::stringstream ss;
ss << (neg ? -value : value);
std::string prefix = ss.str ().substr (0, length);
ss.str (std::string ());
ss << prefix;
T r;
ss >> r;
#endif
return (neg ? -r : r);
}
};
}
//////////////////////////////////////////////////
// trie definition
//////////////////////////////////////////////////
//! \brief A generic trie class that supports any type so long as it is provided
//! appropriate Compare, Length, and Prefix policies.
//!
//! \li T is the data type that the trie will store.
//! \li Compare is the policy by which values in the trie will be compared to one another.
//! \li Length is the policy that determines lexicographical lengths of the values.
//! \li Prefix is the policy that determines lexicographical prefixes of values.
//!
//! The defaults for Compare, Length, and Prefix are setup to accommodate any type that
//! can be cast to a std::string via boost::lexical_cast. Specific std::string
//! defaults are also provided to optimize string tries.
template<typename T, class Compare = std::less<T>,
class Length = detail::length<T, std::size_t>,
class Prefix = detail::prefix<T, std::size_t> >
class trie
{
private:
typedef trie* trie_node; //!< Child node type.
typedef const trie* const_trie_node; //!< Const child node type.
public:
class const_iterator;
//! It makes sense for trie::const_iterator to be the same as a trie::iterator only
//! because it doesn't make sense to offer a non-const iterator for a trie container.
//! Arbitrarily changing node values could mess up a trie's internal ordering causing
//! undefined behavior. Thus all trie iterators are const iterators.
typedef const_iterator iterator;
// Value types
typedef T value_type;
typedef std::size_t size_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef Compare value_compare;
typedef value_compare key_compare;
trie();
trie(const trie ©);
trie& operator=(const trie ©);
~trie() throw();
template<class InputIterator>
trie(const InputIterator &first, const InputIterator &last);
size_type size() const;
size_type max_size() const;
std::pair<iterator, bool> insert(const_reference word);
iterator insert(const iterator &i, const_reference word);
const_iterator begin() const;
const_iterator end() const;
iterator begin();
iterator end();
bool has(const_reference word) const;
bool has_prefix(const_reference word) const;
void swap(trie &from) throw();
void clear() throw ();
bool empty() const;
iterator erase(const iterator &i);
iterator erase(const iterator &begin, const iterator &end);
void remove(const_reference word);
void remove_prefix(const_reference word);
iterator find(const_reference word) const;
iterator find_prefix(const_reference word) const;
trie clone(const iterator &i) const;
void insert(const iterator &begin, const iterator &end);
value_compare value_comp() const;
key_compare key_comp() const;
template<class InputIterator>
void insert(const InputIterator &first,
const InputIterator &last);
//! \brief Provides an iterator over trie values.
class const_iterator
: public std::iterator<std::forward_iterator_tag, value_type>
{
public:
explicit const_iterator(trie_node copy);
const_iterator& operator=(const const_iterator &rhs);
bool operator==(const const_iterator &rhs) const;
bool operator!=(const const_iterator &rhs) const;
const_iterator& operator++();
const_iterator operator++(int);
const_reference operator*() const;
const_pointer operator->() const;
// Observers
bool word() const;
bool leaf() const;
private:
friend class trie;
const_trie_node node; //!< Current trie node pointer.
std::deque<const_trie_node> parents; //!< Parents of current node.
};
private:
typedef Prefix value_prefix; //!< Prefix policy for values.
typedef Length value_length; //!< Length policy for values.
//! \brief Provides implementation for comparison of trie nodes.
struct trie_node_less
: public std::binary_function<trie_node, trie_node, bool>
{
bool operator()(trie_node lhs, trie_node rhs) const;
};
typedef std::set<trie_node, trie_node_less> subtrie; //<! Children subtrie type.
trie(const_reference value, size_type depth);
iterator insert_helper(value_type word, size_type depth,
size_type &children_added = 0);
void reduce_childs(trie_node node) throw();
bool root() const;
bool leaf() const;
iterator find_helper(const_reference word, size_type depth, bool whole) const;
//! \brief Provides implementation for safely deleting a given trie node.
struct trie_node_delete
{
void operator()(trie_node const &node) throw();
};
subtrie children; //!< Subtrie of children of this node.
size_type childs; //!< Number of all children below this node.
trie_node parent; //!< Parent node of this node.
value_type value; //!< Value of this node.
size_type depth; //!< Depth from root of this node.
bool endpoint; //!< True if node is a word endpoint.
public:
// More value types
typedef typename iterator::difference_type difference_type;
};
template<typename T, class Compare, class Length, class Prefix>
bool operator==(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs);
template<typename T, class Compare, class Length, class Prefix>
bool operator!=(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs);
template<typename T, class Compare, class Length, class Prefix>
bool operator<(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs);
template<typename T, class Compare, class Length, class Prefix>
bool operator>(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs);
template<typename T, class Compare, class Length, class Prefix>
bool operator<=(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs);
template<typename T, class Compare, class Length, class Prefix>
bool operator>=(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs);
//////////////////////////////////////////////////
// trie implementation
//////////////////////////////////////////////////
//! Create default empty trie.
template<typename T, class Compare, class Length, class Prefix>
trie<T, Compare, Length, Prefix>::trie()
: childs(0), parent(NULL), value(), depth(0), endpoint(false)
{
TRIE_DEBUG (detail::can_throw ());
}
//! Create trie as a copy of given trie.
template<typename T, class Compare, class Length, class Prefix>
trie<T, Compare, Length, Prefix>::trie(const trie ©)
: childs(0), parent(NULL), value(), depth(0), endpoint(false)
{
TRIE_DEBUG (detail::can_throw ());
insert (copy.begin (), copy.end ());
}
//! Create trie from given range of values.
template<typename T, class Compare, class Length, class Prefix>
template<class InputIterator>
trie<T, Compare, Length, Prefix>::trie(const InputIterator &first, const InputIterator &last)
: childs(0), parent(NULL), value(), depth(0), endpoint(false)
{
insert (first, last);
}
//! Assign this trie to be a copy of given trie.
template<typename T, class Compare, class Length, class Prefix>
trie<T, Compare, Length, Prefix>&
trie<T, Compare, Length, Prefix>::operator=(const trie ©)
{
if (this == ©)
{
return *this;
}
TRIE_DEBUG (detail::can_throw ());
trie temp = copy;
swap (temp);
// Note here that the direct children of temp will have parent pointers that point
// to a temporary. We must re-parent these pointers now.
for (typename subtrie::iterator i = this->children.begin ();
i != this->children.end (); ++i)
{
(*i)->parent = this;
}
return *this;
}
//! Compares two given trie values according to policy.
//! \return Boolean value of comparison.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::trie_node_less::operator()(trie_node lhs,
trie_node rhs) const
{
return value_compare () (lhs->value, rhs->value);
}
//! Does not throw, safely deletes a given trie node.
template<typename T, class Compare, class Length, class Prefix>
inline void
trie<T, Compare, Length, Prefix>::trie_node_delete::operator()(trie_node const &node) throw()
{
delete node;
}
//! Safely deletes this trie and it's children. Does not throw.
template<typename T, class Compare, class Length, class Prefix>
trie<T, Compare, Length, Prefix>::~trie() throw()
{
for_each (this->children.begin (), this->children.end (), trie_node_delete ());
reduce_childs (this->parent);
}
//! Inserts given value into trie.
//! \return iterator to node whose value equals given value.
template<typename T, class Compare, class Length, class Prefix>
inline std::pair<typename trie<T, Compare, Length, Prefix>::iterator, bool>
trie<T, Compare, Length, Prefix>::insert(const_reference word)
{
TRIE_DEBUG (detail::can_throw ());
size_type new_childs = 0;
iterator r = insert_helper (word, 1, new_childs);
return std::make_pair<iterator, bool> (r, new_childs);
}
//! Inserts given value into trie using given iterator as a suggestion. If the suggestion is
//! good this will be faster than insert(const_reference), however if it is not, then
//! this method will be slightly slower. Returns iterator to last inserted node.
//! \return iterator to node whose value equals given value.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::insert(const iterator &i, const_reference word)
{
TRIE_DEBUG (detail::can_throw ());
if (i.node != NULL &&
i.node->value == value_prefix () (word, value_length () (i.node->value)))
{
size_type new_childs = 0;
return const_cast<trie_node&> (i.node)->insert_helper (
word, value_length () (i.node->value) + 1, new_childs);
}
return insert (word).first;
}
//! Helps insert() do it's job. Begins trying to insert given value at given depth.
//! \post children_added equals number of children nodes added to trie.
//! \return iterator to node whose value equals given value.
template<typename T, class Compare, class Length, class Prefix>
typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::insert_helper(value_type word, size_type depth,
size_type &children_added)
{
if (depth - 1 == value_length () (word))
{
// word already in trie.
children_added = 0;
this->endpoint = true;
return iterator (this);
}
trie target (word, depth);
typename subtrie::iterator i = this->children.find (&target);
// If next node in line to target does not exist,
if (i == this->children.end ())
{
// then create it and continue insert on new node.
iterator r (NULL);
trie_node node = NULL;
try
{
TRIE_DEBUG (detail::can_throw ());
node = new trie (word, depth);
size_type new_childs = 0;
TRIE_DEBUG (detail::can_throw ());
r = node->insert_helper (word, depth + 1, new_childs);
this->children.insert (node);
this->childs += ++new_childs ;
node->parent = this;
children_added += new_childs;
}
catch (...)
{
if (node)
{
delete node;
}
throw;
}
return r;
}
// else continue insert on already existing node.
size_type new_childs = 0;
TRIE_DEBUG (detail::can_throw ());
iterator r = (*i)->insert_helper (word, depth + 1, new_childs);
this->childs += new_childs;
children_added = new_childs;
return r;
}
//! Reduces the children counter for parent nodes of the given node.
//! For use when the given node is erased from the trie.
template<typename T, class Compare, class Length, class Prefix>
inline void
trie<T, Compare, Length, Prefix>::reduce_childs(trie_node node) throw()
{
if (node == NULL)
{
return;
}
if (node->childs > 0)
{
--node->childs;
}
reduce_childs (node->parent);
}
//! Creates trie node with given value and given depth.
template<typename T, class Compare, class Length, class Prefix>
inline trie<T, Compare, Length, Prefix>::trie(const_reference word, size_type depth)
: childs(0), parent(NULL), depth(depth), endpoint(false)
{
this->value = value_prefix () (word, depth);
}
//! \return iterator to first node in this trie.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::const_iterator
trie<T, Compare, Length, Prefix>::begin() const
{
if (root ())
{
return ++iterator (const_cast<trie_node> (this));
}
return iterator (const_cast<trie_node> (this));
}
//! \return iterator to one past last node in this trie.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::const_iterator
trie<T, Compare, Length, Prefix>::end() const
{
return iterator (NULL);
}
//! \return const_iterator to first node in this trie.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::begin()
{
typedef const_iterator (trie::*const_begin)() const;
return (this->*static_cast<const_begin> (&trie::begin)) ();
}
//! \return const_iterator to one past last node in this trie.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::end()
{
typedef const_iterator (trie::*const_end)() const;
return (this->*static_cast<const_end> (&trie::end)) ();
}
//! Swap one trie with another.
template<typename T, class Compare, class Length, class Prefix>
void
trie<T, Compare, Length, Prefix>::swap(trie &from) throw()
{
using std::swap;
swap (from.children, this->children);
swap (from.childs, this->childs);
swap (from.value, this->value);
swap (from.parent, this->parent);
swap (from.endpoint, this->endpoint);
}
//! Compares one trie to another. Runs in O(N) time.
//! \return True if and only if this trie is strictly less than given trie, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
operator<(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs)
{
return std::lexicographical_compare (lhs.begin (), lhs.end (), rhs.begin (), rhs.end ());
}
//! Compares one trie to another. Runs in O(N) time.
//! \return True if and only if this trie is strictly greater than given trie, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
operator>(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs)
{
return std::lexicographical_compare (lhs.begin (), lhs.end (), rhs.begin (), rhs.end (),
std::greater<typename trie<T, Compare, Length, Prefix>::value_type> ());
}
//! Compares one trie to another. Runs in O(N) time.
//! \return True if and only if this trie exactly equal to given trie, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
operator==(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs)
{
return std::equal (lhs.begin (), lhs.end (), rhs.begin ());
}
//! Compares one trie to another. Runs in O(N) time.
//! \return True if and only if this trie is not equal to given trie, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
operator!=(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs)
{
return !(lhs == rhs);
}
//! Compares one trie to another. Runs in O(N) time.
//! \return True if and only if this trie less than or equal to given trie, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
operator<=(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs)
{
return std::lexicographical_compare (lhs.begin (), lhs.end (), rhs.begin (), rhs.end (),
std::less_equal<typename trie<T, Compare, Length, Prefix>::value_type> ());
}
//! Compares one trie to another. Runs in O(N) time.
//! \return True if and only if this trie greater than or equal to given trie, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
operator>=(const trie<T, Compare, Length, Prefix> &lhs,
const trie<T, Compare, Length, Prefix> &rhs)
{
return std::lexicographical_compare (lhs.begin (), lhs.end (), rhs.begin (), rhs.end (),
std::greater_equal<typename trie<T, Compare, Length, Prefix>::value_type> ());
}
//! \return True if this node is the root node of this trie.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::root() const
{
return this->depth == 0;
}
//! \return Size of trie in O(1) time.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::size_type
trie<T, Compare, Length, Prefix>::size() const
{
return this->childs + (root () ? 0 : 1);
}
//! \return Maximum size of a trie.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::size_type
trie<T, Compare, Length, Prefix>::max_size() const
{
return std::numeric_limits<size_type>::max ();
}
//! Clear this trie and its children.
template<typename T, class Compare, class Length, class Prefix>
void
trie<T, Compare, Length, Prefix>::clear() throw ()
{
for_each (this->children.begin (), this->children.end (), trie_node_delete ());
this->children.clear ();
this->childs = 0;
}
//! \return True if and only if trie is empty, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
bool
trie<T, Compare, Length, Prefix>::empty() const
{
return (root () && this->childs == 0);
}
//! Removes node of given value (and all its children) pointed to by given iterator from trie.
//! \return The iterator to the node one past last deleted node.
template<typename T, class Compare, class Length, class Prefix>
typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::erase(const iterator &i)
{
if (i == iterator (NULL))
{
return i;
}
// Find element after the last element erased
trie_node target = const_cast<trie_node> (i.node);
typename subtrie::iterator this_child = target->parent->children.find (target);
iterator next = iterator (NULL);
if (this_child == target->parent->children.end ())
{
clear ();
return end ();
}
if (++this_child != target->parent->children.end ())
{
next = iterator (*this_child);
}
// Remove target from target's parent's children.
target->parent->children.erase (target);
delete target;
return next;
}
//! Erase range of node from begin (inclusive) to end (exclusive).
//! \return The iterator to the node one past last deleted node.
template<typename T, class Compare, class Length, class Prefix>
typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::erase(const iterator &begin, const iterator &end)
{
iterator i = begin;
iterator ob = iterator (NULL);
while (i != end && i != ob)
{
i = erase (i);
}
return i;
}
//! \return True if and only if given word value is in our trie, otherwise false.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::has(const_reference word) const
{
return (find_helper (word, 1, true) != end ());
}
//! \return True if and only if given value is in our trie, otherwise false.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::has_prefix(const_reference word) const
{
return (find_helper (word, 1, false) != end ());
}
//! Insert a range of values into trie given iterators to those values.
template<typename T, class Compare, class Length, class Prefix>
template<class InputIterator>
void
trie<T, Compare, Length, Prefix>::insert(const InputIterator &first, const InputIterator &last)
{
TRIE_DEBUG (detail::can_throw ());
using std::copy;
copy (first, last, inserter (*this, this->begin ()));
}
//! Specialized range insert for copying from a trie iterator.
template<typename T, class Compare, class Length, class Prefix>
void
trie<T, Compare, Length, Prefix>::insert(const iterator &begin, const iterator &end)
{
TRIE_DEBUG (detail::can_throw ());
for (iterator i = begin; i != end; ++i)
{
// We only have to insert endpoint nodes since the rest are constructed automatically.
if (i.node->endpoint)
{
insert (*i);
}
}
}
//! Creates a clone of this trie from the given iterator using only the value of the given
//! iterator and its children as nodes.
//! \return The cloned trie.
template<typename T, class Compare, class Length, class Prefix>
trie<T, Compare, Length, Prefix>
trie<T, Compare, Length, Prefix>::clone(const iterator &i) const
{
TRIE_DEBUG (detail::can_throw ());
trie r;
r.insert (i, end ());
return r;
}
//! Convenience method to easily remove a given word value from this trie.
template<typename T, class Compare, class Length, class Prefix>
inline void
trie<T, Compare, Length, Prefix>::remove(const_reference word)
{
erase (find_helper (word, 1, true));
}
//! Convenience method to easily remove a given value from this trie.
template<typename T, class Compare, class Length, class Prefix>
inline void
trie<T, Compare, Length, Prefix>::remove_prefix(const_reference word)
{
erase (find_helper (word, 1, false));
}
//! \return An iterator to a subtrie of this trie or end() if value is not found or not a word.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::find(const_reference word) const
{
return find_helper (word, 1, true);
}
//! \return An iterator to a subtrie of this trie or end() if value is not found.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::find_prefix(const_reference word) const
{
return find_helper (word, 1, false);
}
//! Looks for given value at given depth in this trie, if not found continues search and
//! ultimately returns end() if value is not found.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::iterator
trie<T, Compare, Length, Prefix>::find_helper(const_reference word, size_type depth,
bool whole) const
{
if ((whole && this->endpoint && this->value == word) ||
(!whole && this->value == word))
{
return iterator (const_cast<trie_node> (this));
}
trie target (word, depth);
typename subtrie::iterator i = this->children.find (&target);
if (i != this->children.end ())
{
return (*i)->find_helper (word, depth + 1, whole);
}
return end ();
}
//! \return True if and only if this trie node is a leaf node, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::leaf() const
{
return this->children.empty ();
}
//! \return The value_compare object used by the trie.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::value_compare
trie<T, Compare, Length, Prefix>::value_comp() const
{
return value_compare ();
}
//! \return The key_compare object used by the trie (same as value_compare object).
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::key_compare
trie<T, Compare, Length, Prefix>::key_comp() const
{
return key_compare ();
}
//////////////////////////////////////////////////
// const_iterator implementation
//////////////////////////////////////////////////
//! Create an iterator to a given node.
template<typename T, class Compare, class Length, class Prefix>
inline trie<T, Compare, Length, Prefix>::const_iterator::const_iterator(trie_node copy)
: node(copy)
{
;
}
//! \return This iterator which is a copy of the given iterator.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::const_iterator&
trie<T, Compare, Length, Prefix>::const_iterator::operator=(const const_iterator &rhs)
{
if (this == &rhs)
{
return *this;
}
using std::swap;
const_iterator temp = rhs;
swap (this->node, temp.node);
swap (this->parents, temp.parents);
return *this;
}
//! \return True if and only if this iterator points to the same object as the given iterator,
//! false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::const_iterator::operator==(const const_iterator &rhs) const
{
return this->node == rhs.node;
}
//! \return True if and only if this iterator points to a different object as the given
//! iterator, false otherwise.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::const_iterator::operator!=(const const_iterator &rhs) const
{
return this->node != rhs.node;
}
//! Steps through trie in pre-order.
//! \return An iterator to next object in trie.
template<typename T, class Compare, class Length, class Prefix>
typename trie<T, Compare, Length, Prefix>::const_iterator&
trie<T, Compare, Length, Prefix>::const_iterator::operator++()
{
// After we've fallen off the trie, we're always at the end.
if (this->node == NULL)
{
return *this;
}
// Step through children in pre-order.
if (!this->node->leaf ())
{
this->parents.push_back (this->node);
// Get pointer to child trie object.
this->node = *this->node->children.begin ();
return *this;
}
// Peel off parents and step through their children in pre-order.
typedef typename subtrie::iterator child;
while (!this->parents.empty ())
{
child end = this->parents.back ()->children.end ();
// Recursively step through parents' children.
child next = ++(this->parents.back ()->children.find (
const_cast<trie_node> (this->node)));
if (next != end)
{
this->node = *next;
return *this;
}
else
{
this->node = &(*this->parents.back ());
this->parents.pop_back ();
}
}
// End of trie has been reached.
this->node = NULL;
return *this;
}
//! Steps through trie in pre-order.
//! \return An iterator to the current object that this iterator points to.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::const_iterator
trie<T, Compare, Length, Prefix>::const_iterator::operator++(int)
{
const_iterator temp (*this);
++(*this);
return temp;
}
//! \return The value of the trie object pointer to by this iterator.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::const_reference
trie<T, Compare, Length, Prefix>::const_iterator::operator*() const
{
return this->node->value;
}
//! \return A pointer to the trie object pointer to by this iterator.
template<typename T, class Compare, class Length, class Prefix>
inline typename trie<T, Compare, Length, Prefix>::const_pointer
trie<T, Compare, Length, Prefix>::const_iterator::operator->() const
{
return &this->node->value;
}
//! \return True if and only if this node is a word, as in not-a-prefix.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::const_iterator::word() const
{
return this->node->endpoint;
}
//! \return True if and only if this node is a leaf node.
template<typename T, class Compare, class Length, class Prefix>
inline bool
trie<T, Compare, Length, Prefix>::const_iterator::leaf() const
{
return this->node->leaf ();
}
//////////////////////////////////////////////////
// trie<std::string> optimization
//////////////////////////////////////////////////
namespace detail
{
//! \brief std::string specialization for the length policy.
template<>
struct length<std::string, std::string::size_type>
{
//! Simply uses std::string::length() to determine length.
std::string::size_type operator()(const std::string &value) const
{
TRIE_DEBUG (detail::can_throw ());
return value.length ();
}
};
//! \brief std::string specialization for the prefix policy.
template<>
struct prefix<std::string, std::string::size_type>
{
//! Simply uses std::string::substr() to make prefixes.
std::string operator()(const std::string &value, std::string::size_type length) const
{
TRIE_DEBUG (detail::can_throw ());
return value.substr (0, length);
}
};
}
} // namespace lexical
#undef TRIE_DEBUG
#endif // #if !defined (TRIE_H)