|
|
Boost-Commit : |
From: chintanraoh_at_[hidden]
Date: 2008-07-03 14:03:31
Author: chintanraoh
Date: 2008-07-03 14:03:30 EDT (Thu, 03 Jul 2008)
New Revision: 47050
URL: http://svn.boost.org/trac/boost/changeset/47050
Log:
half documented trie class
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp | 265 +++++++++++++++++++++++++++++++++++----
1 files changed, 237 insertions(+), 28 deletions(-)
Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp (original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp 2008-07-03 14:03:30 EDT (Thu, 03 Jul 2008)
@@ -14,6 +14,14 @@
namespace dsearch{
//TODO size(), ==,erase (iterator,iterator)
+///The trie class.
+/**
+ \param Key is the trie's key type.
+ \param Mapped is the trie's data type.
+ \param trie_node is the node type to be used.
+ \param Key_traits is the traits of the key.
+ \param Alloc is the allocator to be used for allocation.
+ */
template<class Key,class Mapped,
template<class K,class M,class K_t,class A > class trie_node,
class Key_traits,
@@ -21,44 +29,74 @@
class trie
{
private:
+ /// node_type of every ndoe in the trie.
typedef trie_node<Key,Mapped,Key_traits,Alloc> node_type;
- friend class trie_node<Key,Mapped,Key_traits,Alloc>;
+ /// the type of allocator for the node
typedef typename Alloc::template rebind<node_type>::other node_allocator_type;
+ /// node_allocator object for the node.
node_allocator_type node_allocator;
+ /// root of the patricithe trie.
node_type *node_root;
public:
+ /// type of the key used by the trie
typedef Key key_type;
+ /// type which key maps to
typedef Mapped data_type;
+ /// value type which can be used to insert. Note, unlike map, this is not the type
+ /// of a deferenced iterator
typedef std::pair<Key,Mapped> value_type;
+ /// self type
typedef trie<Key,Mapped,trie_node,Key_traits,Alloc> type;
-
+ ///trie's allocator type.
typedef typename Alloc::template rebind<value_type>::other allocator_type;
- typedef typename allocator_type::pointer pointer;
- typedef typename allocator_type::const_pointer const_pointer;
+ ///pointer to value_type.
+ typedef typename allocator_type::pointer pointer;
+ ///const pointer to value_type.
+ typedef typename allocator_type::const_pointer const_pointer;
+ ///reference to value_type.
typedef typename allocator_type::reference reference;
+ ///const reference to value_type.
typedef typename allocator_type::const_reference const_reference;
- typedef typename allocator_type::size_type size_type;//should actually depend on iterator(.|?)
+ ///return type of size()
+ typedef typename std::size_t size_type;
+ ///represents distance between two iterators.
typedef typename allocator_type::difference_type difference_type; //should actually depend on iterator(.|?)
+ ///trie's cursor which represents the trie node.
typedef trie_cursor<key_type,data_type,node_type> cursor;
+ ///trie's const_cursor which represents the const trie node.
typedef trie_cursor<key_type,data_type,const node_type> const_cursor;
+ ///iterator used to iterate through a map. dereferencing this gives data_type.
typedef trie_iterator<key_type,data_type,cursor> iterator;
+ ///const_iterator used to iterate through a map. dereferencing this gives const data_type.
typedef trie_iterator<key_type,const data_type,const_cursor> const_iterator;
+ ///reverse_iterator used to iterate through a map. dereferencing this gives data_type.
typedef trie_reverse_iterator<key_type,data_type,cursor> reverse_iterator;
+ ///const_reverse_iterator used to iterate through a map. dereferencing this gives const data_type.
typedef trie_reverse_iterator<key_type,const data_type,const_cursor> const_reverse_iterator;
+ ///default contructor
trie()
{
node_root=node_allocator.allocate(1);
new(node_root) node_type();
}
+ ///copy constructor
+ /**
+ \param other is the trie to be copied
+ */
trie ( const type &other )
{
copy_trie_preserve(const_cast<node_type *>(other.node_root) );
}
+ ///Assignment operator
+ /**
+ \returns reference to self.
+ \param other is the trie to be copied
+ */
type &operator = ( const type &other )
{
if(node_root==other.node_root) return *this;
@@ -70,70 +108,111 @@
return *this;
}
+ ///works std::maps's [ ] operator
+ /**
+ \returns reference to data_type correspoding to the key.
+ \param k is the key whose data type is to be found.
+ */
data_type &operator [] (const key_type &k)
{
return insert_(k)->get_value_ref();
}
+ ///insert a value_type
+ /**
+ \param v is std::pair<key_type,data_type> to be inserted.
+ */
void insert(const value_type &v)
{
this->operator[](v.first)=v.second;
}
+ ///determines the size of the trie
+ /**
+ \returns the size of the trie
+ */
std::size_t size() const
{
return const_cast<type *>(this)->size_();
}
- private:
- std::size_t size_()
- {
- int num=0;
- iterator it,end_it=this->end();
- for(it=this->begin();it!=end_it;it++,num++);
- return num;
- }
+
public:
+ ///maximum size of the trie
+ /**
+ \returns maximum possible size of the trie. Thats is maximum value of an integer.
+ */
std::size_t max_size()
{
return std::numeric_limits<std::size_t>::max();
}
+ ///determines whether the trie is empty or not.
+ /**
+ \returns true if it is empty and false otherwise.
+ */
bool empty()
{
return node_root->empty();
}
- //make use of iterator iterator.push();
+ ///finds the key in the trie
+ /**
+ \returns iterator to the found key. If not found returns end().
+ \param key is the key for which iterator is to be found
+ */
iterator find(const key_type &key)
{
return find< iterator, cursor, type* > (this,key);
}
+ ///finds the key in the trie
+ /**
+ \returns const_iterator to the found key. If not found returns end().
+ \param key is the key for which const iterator is to be found
+ */
const_iterator find(const key_type &key) const
{
return const_cast<type *>(this)->find(key);
//return find< const_iterator, const_cursor, const type* > (this,key);
}
-
+ ///finds the upper bound of a particular
+ /**
+ \returns iterator to the upper bound. If not found returns end().
+ \param key is the key for which upper bound is to be found
+ */
const_iterator upper_bound(const key_type &key) const
{
return const_cast<type *>(this)->upper_bound(key);
//return upper_bound<const_iterator,const_cursor,const type*>(this,key);
}
-
+ ///finds the upper bound of a particular
+ /**
+ \returns const_iterator to the upper bound. If not found returns end().
+ \param key is the key for which upper bound is to be found
+ */
iterator upper_bound(const key_type &key)
{
return upper_bound<iterator,cursor,type*>(this,key);
}
+ ///finds the lower bound of a particular
+ /**
+ \returns iterator to the lower bound. If not found returns end().
+ \param key is the key for which lower bound is to be found
+ */
iterator lower_bound(const key_type &key)
{
return lower_bound<iterator,cursor,type*>(this,key);
}
+ ///finds the lower bound of a particular
+ /**
+ \returns const_iterator to the lower bound. If not found returns end().
+ \param key is the key for which lower bound is to be found
+ */
const_iterator lower_bound(const key_type &key) const
{
//return lower_bound<const_iterator,const_cursor,const type*>(this,key);
@@ -141,28 +220,43 @@
}
//not very clean but works
- Key get_key(const const_iterator &cit) const
+ ///find the key corresonding the iterator
+ /**
+ \returns key_type corresponding to the iterator.
+ \param cit const_iterator
+ */
+ key_type get_key(const const_iterator &cit) const
{
typedef typename std::vector<const_cursor>::const_iterator cur_const_iterator;
std::vector<typename Key_traits::element_type> e_vector;
Key ret_key;
+ ///iterate through all elements in the vector and then collect the elements
for(cur_const_iterator it=++cit.cur_st.begin();it!=cit.cur_st.end();it++)
e_vector.push_back((*it).get_element());
return Key_traits::get_key(e_vector.begin(),e_vector.end());
}
+ //not very clean but works
+ ///find the key corresonding the reverse iterator
+ /**
+ \returns key_type corresponding to the const_reverse_iterator.
+ \param crit const_reverse_iterator
+ */
Key get_key(const const_reverse_iterator &crit) const
{
return get_key(crit.get_iterator());
}
+ ///erase the key from the trie
+ /**
+ \param key to be erase.
+ */
void erase(const key_type &key)
{
iterator it;
it=find(key);
if(it!=end())
erase(it);
-
/* typename Key_traits::const_iterator it=Key_traits::begin(key),
end_it=Key_traits::end(key),temp_it=it;
typename node_type::iterator fit;
@@ -224,11 +318,22 @@
node_allocator.deallocate(cur,1);*/
}
+ ///range of iterators with patricular prefix
+ /**
+ \returns iterator range as (const_iterator,const_iterator)
+ \param key specifes the prefix.
+ */
std::pair<const_iterator,const_iterator> prefix_range(const key_type &key) const
{
return const_cast<type *>(this)->prefix_range(key);
//return prefix_range<const_iterator,const_cursor,const type*>(this,key);
}
+
+ ///range of iterators with patricular prefix
+ /**
+ \returns iterator range as (const_iterator,const_iterator)
+ \param key specifes the prefix.
+ */
std::pair<iterator,iterator> prefix_range(const key_type &key)
{
prefix_range<iterator,cursor,type*>(this,key);
@@ -254,6 +359,7 @@
return std::make_pair(ret_it,++right);
}
+ ///clears the trie.
void clear()
{
typedef typename node_type::iterator node_it;
@@ -283,8 +389,11 @@
new(node_root) node_type();
}
- //linear iteration to find where the pointer is grr...
- //otherwise i will need to add one more function to the node
+ /**
+ \param it is the iterator to be erased
+ \note linear iteration to find where the pointer is grr...
+ otherwise i will need to add one more function to the node
+ */
void erase(const iterator &it)
{
iterator iter=it;
@@ -346,66 +455,109 @@
iter.top().get_node()->erase(node_it);
}
-
+ ///swaps two tries
+ /**
+ \param other is the other trie to be swapped with
+ */
void swap(type &other)
{
std::swap(other.node_root,node_root);
}
+ ///Returns an iterator pointing to the beginning of the trie.
+ /**
+ \returns an iterator pointing to the beginning of the trie.
+ */
iterator begin()
{
return iterator(root(),false);
}
-
+
+ ///Returns a const iterator pointing to the beginning of the trie.
+ /**
+ \returns an const_iterator pointing to the beginning of the trie.
+ */
const_iterator begin() const
{
return const_cast<type *>(this)->begin();
//return const_iterator(root(),false);
}
-
+ ///Returns an iterator pointing to the end of the hash_multiset.
+ /**
+ \returns an iterator pointing to the beginning of the trie.
+ */
iterator end()
{
return iterator(root(),true);
}
+ ///Returns an const iterator pointing to the end of the hash_multiset.
+ /**
+ \returns a const_iterator pointing to the beginning of the trie.
+ */
const_iterator end() const
{
return const_cast<type *>(this)->end();
//return const_iterator(root(),true);
}
+ /// Returns a reverse iterator pointing to the beginning of the reversed trie
+ /**
+ \returns a reverse_iterator pointing to the beginning of the reversed trie
+ */
reverse_iterator rbegin()
{
return reverse_iterator(begin(),end(),true);
}
+ /// Returns a const reverse iterator pointing to the beginning of the reversed trie
+ /**
+ \returns a const_reverse_iterator pointing to the beginning of the reversed trie
+ */
const_reverse_iterator rbegin() const
{
return const_cast<type *>(this)->end();
//return const_reverse_iterator(begin(),end(),true);
}
+ /// Returns a reverse iterator pointing to the end of the reversed trie
+ /**
+ \returns a reverse_iterator pointing to the end of the reversed trie
+ */
reverse_iterator rend()
{
return reverse_iterator(begin(),end(),false);
}
+ /// Returns a const reverse iterator pointing to the end of the reversed trie
+ /**
+ \returns a const_reverse_iterator pointing to the end of the reversed trie
+ */
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin(),end(),false);
}
+ ///Returns a cursor pointing to the root.
+ /**
+ \returns cursor pointing to the root.
+ */
cursor root()
{
return cursor(node_root);
}
+ ///Returns a const cursor pointing to the root.
+ /**
+ \returns const_cursor pointing to the root.
+ */
const_cursor root() const
{
return const_cursor(node_root);
}
+ ///destructor
~trie()
{
//std::cout<<"trie class destructor"<<std::endl;
@@ -413,8 +565,24 @@
node_allocator.deallocate(node_root,1);
}
- private:
- //get reference to the leaf node of the key
+ private:
+ ///determines the size of the trie
+ /**
+ \returns the size of the trie.
+ */
+ inline std::size_t size_()
+ {
+ int num=0;
+ iterator it,end_it=this->end();
+ for(it=this->begin();it!=end_it;it++,num++);
+ return num;
+ }
+
+ ///get reference to the leaf node of the key
+ /**
+ \returns pointer to the leaf node of the key
+ \param key is the whose leaf is suppose to be found
+ */
node_type *insert_(const key_type &key)
{
typename Key_traits::const_iterator it=Key_traits::begin(key),
@@ -446,6 +614,12 @@
return cur;
}
+ ///checks whether a key exists or not
+ /**
+ \returns true if it exists other wise false
+ \param key is the key whose existance in the trie us supposed to be
+ determined
+ */
bool exist(const key_type &key) const //make this iterator instead of bool;
{
typename Key_traits::const_iterator it=Key_traits::begin(key),
@@ -465,7 +639,10 @@
}
return false;
}
-
+ ///copy the trie preserving the internal structure of the node
+ /**
+ \param other_root is the root node of the other trie to be copied.
+ */
inline void copy_trie_preserve(node_type*other_root)
{
node_type *prev,*temp_node;
@@ -509,6 +686,13 @@
}
}
+ ///find the key in the trie
+ /**
+ \brief *was* used to avid writing two functions one for const find
+ and other non const find.
+ \param key is the key to be found
+ \param this_ptr is the pointer to this trie
+ */
template<class It_type,class Cur_type,class Trie_ptr>
static inline It_type find(Trie_ptr this_ptr,const key_type &key)
{
@@ -534,7 +718,11 @@
return this_ptr->end();
}
-
+ ///find the lower bound of an element in the node
+ /**
+ \param node to be searched
+ \param ele is the element whose lower bound is to be found
+ */
static inline typename node_type::iterator lower_bound(node_type *const &node,const typename Key_traits::element_type & ele)
{
typename node_type::iterator it=node->begin(),eit=node->end();
@@ -548,7 +736,14 @@
}
return ret_it;
}
-
+
+ ///find the upper bound of the key
+ /**
+ \brief *was* used to avid writing two functions for upperbound
+ and other non const find.
+ \param key is the key to be found
+ \param this_ptr is the pointer to this trie
+ */
template<class It_type,class Cur_type,class Trie_ptr>
static inline It_type upper_bound(Trie_ptr this_ptr,const key_type &key)
{
@@ -602,6 +797,13 @@
return ret_it;
}
+ ///find the lower bound of the key
+ /**
+ \brief *was* used to avoid writing two functions for lower bound
+ and other non const find.
+ \param key is the key to be found
+ \param this_ptr is the pointer to this trie
+ */
template<class It_type,class Cur_type,class Trie_ptr>
static inline It_type lower_bound(Trie_ptr this_ptr,const key_type &key)
{
@@ -665,6 +867,13 @@
return ret_it;
}
+ ///find the prefix_range of the key
+ /**
+ \brief *was* used to avoid writing two functions for lower bound
+ and other non const find.
+ \param key is the key to be found
+ \param this_ptr is the pointer to this trie
+ */
template<class Iter_type,class Cur_type,class Trie_t>
static inline std::pair<Iter_type,Iter_type> prefix_range(Trie_t this_ptr,const key_type &key)
{
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk