|
|
Boost-Commit : |
From: chintanraoh_at_[hidden]
Date: 2008-07-05 02:38:52
Author: chintanraoh
Date: 2008-07-05 02:38:50 EDT (Sat, 05 Jul 2008)
New Revision: 47088
URL: http://svn.boost.org/trac/boost/changeset/47088
Log:
finished documentation for trie and patricia
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/node_cursor.hpp | 96 +++++++++++++++++++++-
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp | 2
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia_iterator.hpp | 2
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp | 165 +++++++++++++++++++++++++++++++++------
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_array_node.hpp | 111 +++++++++++++++++++++++---
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_iterator.hpp | 125 ++++++++++++++++++++++++++---
6 files changed, 435 insertions(+), 66 deletions(-)
Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/node_cursor.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/node_cursor.hpp (original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/node_cursor.hpp 2008-07-05 02:38:50 EDT (Sat, 05 Jul 2008)
@@ -9,14 +9,23 @@
namespace boost {
namespace dsearch {
using boost::tree::cursor_facade;
- template<class Key,class Mapped,class Node>
- class trie_cursor:public cursor_facade<trie_cursor<Key,Mapped,Node>,Node,
+
+///cursor poiting to the node.
+/**
+ \param Key is trie::key_type
+ \param Mapped is trie::data_type
+ \param Node is the type of node to be used.
+ */
+template<class Key,class Mapped,class Node>
+class trie_cursor:public cursor_facade<trie_cursor<Key,Mapped,Node>,Node,
forward_traversal_tag,
bidirectional_traversal_tag>
{
private:
+ /// cursor
typedef trie_cursor<Key,Mapped,Node> cursor;
+ /// element_type as spefied in the key_traits
typedef typename Node::element_type element_type;
friend class boost::iterator_core_access;
@@ -24,22 +33,37 @@
template<class K,class M,template<class K1,class M1,class K_t1,class A1 > class t_n,class K_t,class A >
friend class trie;
template<class K,class M,class N> friend class trie_cursor;
+
+ /// helps in avoiding conversion of const_cursor to cursor.
struct enabler {};
+
+ ///if Node is const the node_iterator is const_iterator otherwise its
+ ///just iterator.
typedef typename mpl::eval_if<is_const<Node>, typename Node::const_iterator,
- typename Node::iterator>::type node_iterator;
+ typename Node::iterator>::type node_iterator;
+ /// if the cursor points to root. then only root is set.
unsigned char only_root;
+ /// for specifying the imaginary node above root
bool top;
+ /// position of the child in cur. (cur,pos) specfies the child node
+ /// ie the node which cursor points to.
node_iterator pos;
+ /// usually the parent of the node which cursor points to.
Node *cur;
public:
+ /// Default constructor.
trie_cursor():only_root(0),top(0),cur(0)
{
}
+ /// copy constructer
+ /**
+ \param other is the cursor to be copied
+ */
template<class K,class M,class N>
trie_cursor( trie_cursor<K,M,N> const& other,
typename enable_if< is_convertible<N*,Node*>,
@@ -52,11 +76,20 @@
this->cur=other.cur;
}
+ ///specific the cursor using the root.
+ /**
+ \param n_ptr is the pointer to the root.
+ */
trie_cursor(Node * const &n_ptr): only_root(1) , top(false)
{
cur=n_ptr;
}
+ ///construct the node usin node pointer and iterator.
+ /**
+ \param n_ptr pointer to the node.
+ \param it: is the node iterator in the child.
+ */
trie_cursor(Node* const &n_ptr,const node_iterator &it): only_root(0), top(false)
{
cur=(n_ptr);
@@ -65,6 +98,7 @@
private:
+ ///for cursor::begin()
cursor left() const
{
if(top)
@@ -76,6 +110,7 @@
return cursor(*pos,(*pos)->begin());
}
+ ///for cursor::end()
cursor right() const
{
if(top)
@@ -85,6 +120,7 @@
return cursor(*pos,(*pos)->end());
}
+ /// decrement the cursor.
void decrement()
{
if(only_root)
@@ -93,16 +129,25 @@
pos--;
}
+ /// check whether the particular node is leaf node or not.
bool empty_() const
{
return get_node()->empty();
}
+ /// dereference the node
+ /**
+ \returns reference to the Node
+ */
Node &dereference() const
{
return *get_node();
}
+ /// get the current node.
+ /**
+ \returns the pointer to current node.
+ */
Node *get_node() const
{
if(only_root)
@@ -110,6 +155,10 @@
return *pos;
}
+ /// get the current node.
+ /**
+ \returns the pointer to current node.
+ */
Node *get_node()
{
if(only_root)
@@ -117,14 +166,18 @@
return *pos;
}
- //returns const_iterator for const_cursor :(
- //used by trie erase function
+ ///get the iterator pointing to the node.
+ /**
+ \warning returns const_iterator for const_cursor
+ \note used by trie erase function
+ */
node_iterator get_iterator() const
{
assert(!only_root);
return pos;
}
+ ///increment the cursor.
void increment()
{
if(only_root)
@@ -133,6 +186,13 @@
pos++;
}
+ /// used to check whether two cursors are equal.
+ /**
+ \returns true if the are equyal false otherwise
+ \param other is other cursor whose equality with cursor needs to be
+ checked
+
+ */
template<class K,class M,class N>
bool equal(trie_cursor<K,M,N> const& other) const
{
@@ -156,24 +216,44 @@
}
public:
+
+ /// check whether node has a value. ie end of an insert key.
+ /**
+ \returns true is it the end of an inserted key.
+ */
bool has_value() const
{
return get_node()->has_value();
}
- //const because dereference is const
+
+ /// get value at the particular node. Should have a value.
+ /**
+ \returns reference to the value.
+ \note const because dereference is const.
+ \warning should not be called when has_value is false.
+ */
Mapped &get_value() const
{
return get_node()->get_value_ref();
}
+ /// get element of the edge which points to the node.
+ /**
+ \returns the element.
+ */
element_type get_element() const
{
assert(!only_root && !top);
return cur->get_element(pos);
}
-
- //const_cast here? trouble is only with const_cursor as get_node()=*pos = const Node *:(.
+
+ ///find the cursor corresponding to the element
+ /**
+ \returns cursor pointed to be edge specified by e
+ \param e is the egde for which cursor is to be found
+ \note const_cast here? trouble is only with const_cursor as get_node()=*pos = const Node *:(.
+ */
cursor find(const element_type &e) const
{
return cursor(this->get_node(),get_node()->find(e));
Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp (original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp 2008-07-05 02:38:50 EDT (Sat, 05 Jul 2008)
@@ -22,7 +22,7 @@
namespace boost{
namespace dsearch{
-/// The pactrica class
+/// The patricia class
/** \ingroup group_nothing
\param Key key currently accepts a string only.
\param Mapped can be any datatype which is supposed to be indexed using string
Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia_iterator.hpp (original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia_iterator.hpp 2008-07-05 02:38:50 EDT (Sat, 05 Jul 2008)
@@ -20,7 +20,7 @@
{
template<class K,class M,class K_t,class A > friend class patricia;
protected:
- ///empty struct used for conversion from const_iterator to iterator
+ ///empty struct used for avoiding conversion from const_iterator to iterator
struct enabler {};
friend class boost::iterator_core_access;
///Pointer to prev node . usually cur->left or cur->right ==next
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-05 02:38:50 EDT (Sat, 05 Jul 2008)
@@ -325,7 +325,7 @@
*/
std::pair<const_iterator,const_iterator> prefix_range(const key_type &key) const
{
- return const_cast<type *>(this)->prefix_range(key);
+ return const_cast<type *>(this)->prefix_range(key);
//return prefix_range<const_iterator,const_cursor,const type*>(this,key);
}
@@ -336,13 +336,15 @@
*/
std::pair<iterator,iterator> prefix_range(const key_type &key)
{
- prefix_range<iterator,cursor,type*>(this,key);
+ return prefix_range<iterator,cursor,type*>(this,key);
+#if 0
typename Key_traits::const_iterator it=Key_traits::begin(key),
end_it=Key_traits::end(key);
iterator ret_it,right;
cursor cur,next;
cur=root();
ret_it.push(cur);
+ //* find where the leaf is.
while(it!=end_it)
{
if(cur.empty()) return std::make_pair(end(),end());
@@ -353,39 +355,59 @@
ret_it.push(cur);
it++;
}
+
right=ret_it;
+ //* and left most from the leaf.
ret_it.to_left_most();
+ //* move right most from the leaf.
right.to_right_most();
+ //* since we want right range not to be closed we increment right
+ //* before returning.
return std::make_pair(ret_it,++right);
+#endif
+
}
///clears the trie.
void clear()
{
typedef typename node_type::iterator node_it;
+ //* store the node and node iterator in a stack.
std::stack< std::pair<node_type*,node_it> > node_stack;
int size=1;
+
+ //* push root and its begin()
node_stack.push(std::make_pair(node_root,node_root->begin()));
while(1)
- {
+ {
+ //* if the iterator has reached the end we will need to pop
+ //* and goto to the next sub tree.
if(node_stack.top().first->end()==node_stack.top().second)
{
+ //* if size of 1 we have done every thing :)
if(size==1) break;
node_allocator.destroy(node_stack.top().first);
node_allocator.deallocate(node_stack.top().first,1);
+ //* pop the current sub tree.
node_stack.pop();
size--;
+ //* move to the next subtree.
node_stack.top().second++;
continue;
}
+ //* arrange for a new node.
node_stack.push( std::make_pair(*(node_stack.top().second)
,(*(node_stack.top().second))->begin()) );
size++;
}
node_stack.pop();
+ //* we have not yet deallocated root.
+ //* clean up root.
node_allocator.destroy(node_root);
node_allocator.deallocate(node_root,1);
node_root=node_allocator.allocate(1);
+
+ //* and allocate a new one.
new(node_root) node_type();
}
@@ -397,25 +419,30 @@
void erase(const iterator &it)
{
iterator iter=it;
- node_type *n_t;
cursor cur_it;
typename node_type::iterator node_it;
+
+ //* check whether the iterator points to a leaf node
if ( iter.top().begin()==iter.top().end() )
{
+ //* iter.size() refers to size of the iterator's stack.
+ //* since there is no parent for the root node it does not
+ //* have a corresponding iterator.
if(iter.size()!=1)
node_it=iter.top().get_iterator();
- node_allocator.destroy( n_t = iter.top().get_node() );
+
+ node_allocator.destroy( iter.top().get_node() );
node_allocator.deallocate( iter.top().get_node() , 1 );
iter.pop();
}
else
{
+ //*if it does not point to a leaf node just erase the data and return
iter.top().get_node()->erase_value();
return;
}
- if ( iter.empty() )
- if( iter.empty() ) //deallocated the root node so reallocate it.
+ if ( iter.empty() )//*deallocated the root node so reallocate it.
{
node_root=node_allocator.allocate(1);
new(node_root) node_type();
@@ -423,22 +450,28 @@
}
cur_it=iter.top().begin();
+ //*if (++cur_it)==iter.top().end() then its only child has been erased.
while( (++cur_it)==iter.top().end() )
{
+ //* iter.size() refers to size of the iterator's stack.
+ //* since there is no parent for the root node it does not
+ //* have a corresponding iterator.
if(iter.size()!=1)
node_it=iter.top().get_iterator();
- node_allocator.destroy ( n_t = iter.top().get_node() );
+ //* deallocate the node.
+ node_allocator.destroy ( iter.top().get_node() );
node_allocator.deallocate ( iter.top().get_node() , 1 );
iter.pop();
- if( iter.empty() ) //deallocated the root node so reallocate it.
+ //* deallocated the root node so reallocate it.
+ if( iter.empty() )
{
node_root=node_allocator.allocate(1);
new(node_root) node_type();
return;
}
-
+ //* if a particular node has value then break then and there.
if(iter.top().has_value())
break;
cur_it=iter.top().begin();
@@ -574,7 +607,9 @@
{
int num=0;
iterator it,end_it=this->end();
+ //* just iterate and find out no of elements.
for(it=this->begin();it!=end_it;it++,num++);
+
return num;
}
@@ -587,30 +622,35 @@
{
typename Key_traits::const_iterator it=Key_traits::begin(key),
end_it=Key_traits::end(key);
- node_type *cur=node_root,*next;
+ node_type *cur=node_root, *next;
typename node_type::iterator fit;
- int i=0;
- while(it!=end_it)
+
+ //*go as far as one can.
+ while ( it!=end_it )
{
- fit=cur->find(*it);
- if(fit==cur->end())
+ //*find the current char in the node.
+ fit=cur->find( *it );
+ //*if not found go out of the loop.
+ if ( fit == cur->end() )
break;
+ //*change cur to pointer of the new node.
cur=*fit;
it++;
- assert(i!=10);
+
}
- i=0;
+
+ //*allocate nodes untill the end of the string.
while(it!=end_it)
{
- i++;
next=node_allocator.allocate(1);
//std::cout<<"Allocating:"<<*it<<std::endl;
new(next) node_type();
+ //*insert the char in to new node along with pointer to next node.
cur->insert(*it,next);
cur=next;
- assert(i!=10);
it++;
}
+ //*return the pointer to the leaf node.
return cur;
}
@@ -620,23 +660,26 @@
\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;
+ bool exist(const key_type &key) const
{
typename Key_traits::const_iterator it=Key_traits::begin(key),
end_it=Key_traits::end(key);
typename node_type::iterator fit;
node_type *cur=node_root;
+
+ //* for each element in the key find the corresponding node pointer
+ //* and move the the node.
while(!(it==end_it))
{
fit=cur->find(*it);
- if(fit == cur->end() ) return false;
+ if ( fit == cur->end() ) return false;
cur=*fit;
it++;
}
+ //* if the "leaf" has the a value return true.
if(cur->has_value())
- {
return true;
- }
+ //* else
return false;
}
///copy the trie preserving the internal structure of the node
@@ -647,15 +690,22 @@
{
node_type *prev,*temp_node;
typedef typename node_type::iterator node_iterator;
+ //* stack to maintain the list of iterators for the other root.
std::stack<node_iterator> st;
+ //* stack to maintain the list of iterators.
std::stack<node_iterator> this_st;
+ //* maintain iterators for other root.
node_iterator cur_it=other_root->begin();
+ //* allocate the root node
node_root=node_allocator.allocate(1);
node_allocator.construct(node_root,*other_root);
+ //* if the other root is empty return
if ( other_root->end() == other_root->begin() )
return;
+
+ //* push root on to the stack
this_st.push(node_root->begin());
while(true)
@@ -668,20 +718,34 @@
if( cur_it == prev->end() )
{
if(st.empty()) return;
+
+ //* change cur_it
cur_it=++st.top();
+ //* pop to change top.
st.pop();
+
+ //* do the same (nearly) to other stack too.
this_st.pop();
++this_st.top();
continue;
}
+ //* assign new node.
temp_node=node_allocator.allocate(1);
+
+ //* call the copy constructor of the new node.
+ //* this helps in preserving the internal node structure.
node_allocator.construct( temp_node , **cur_it );
+
+ //* put the pointer of new node on the parent outward edge
*(this_st.top())=temp_node;
+ //* push the begin of new node on to the stack.
this_st.push(temp_node->begin());
+
+ //* push the cur_it on to the stack and move move one to new it.
st.push(cur_it);
-
+
cur_it=(*cur_it)->begin();
}
}
@@ -698,19 +762,27 @@
{
typename Key_traits::const_iterator it=Key_traits::begin(key),
end_it=Key_traits::end(key);
+
+ //* iterator is a stack of cursors
It_type ret_it;
Cur_type cur,next;
cur=this_ptr->root();
+ //* goto the leaf of the key.
while(!(it==end_it))
{
+ //* push the current iterator on to the stack.
ret_it.push(cur);
+ //* find the particular charecter in the node.
next=cur.find(*it);
+ //* if not found return null.
if ( next == cur.end() )
return this_ptr->end();
cur=next;
it++;
}
+
ret_it.push(cur);
+ //* if leaf has value return ret_it.
if(cur.has_value())
{
return ret_it;
@@ -727,6 +799,8 @@
{
typename node_type::iterator it=node->begin(),eit=node->end();
typename node_type::iterator ret_it=eit;
+
+ //* linear iteration to find where the lower bound is.
while(it!=eit)
{
if( node->get_element(it) > ele)
@@ -755,13 +829,18 @@
cur=r;
ret_it.push(cur);
//std::cout<<"CONST UPPER BOUND"<<std::endl;
+
+ //go as far as possible with the key.
while(it!=end_it)
{
if(cur.empty())
{
+ //* if the cur is empty then prefix of the key is there in the trie
+ //* so goto the iterator adjacent to prefix
ret_it++;
return ret_it;
}
+ //* the usual find procedure.
next=cur.find(*it);
if ( next == cur.end() )
{
@@ -773,15 +852,28 @@
ret_it.push(cur);
it++;
}
+
+ //* if the entire key is not found
if( not_found )
{
+ //* if find the lower bound in the last node we could atmost reach.
next=Cur_type(cur.get_node(),lower_bound(cur.get_node(),*it));
//next=Cur_type(cur.get_node(),const_cast<node_type *>(cur.get_node())->lower_bound(*it));
if(next==ret_it.top().end())
+ {
+ //* if there is no lower bound we position the cursor at begin.
next=Cur_type ( cur.get_node(), cur.get_node()->begin());
+ }
else
+ {
+ //* if else we just need increment the cursor.
+ //* because the upper bound is adjacent to the lower bound.
next++;
+ }
+
+ //* next++ could have positoned the cursor at the end.
+ //* so pop untill next++ does not position at the end.
while(next==ret_it.top().end())
{
//std::cout<<"popping "<<std::endl;
@@ -793,7 +885,9 @@
}
ret_it.push(next);
}
- ret_it.to_left_most(); //if ret_it.top().hash_value() then this does nothing
+ //* move the iterator to the left most from the current position.
+ //* if ret_it.top().has_value() then this does nothing
+ ret_it.to_left_most();
return ret_it;
}
@@ -816,11 +910,13 @@
cur=r;
ret_it.push(cur);
//std::cout<<"LOWER BOUND"<<std::endl;
+ //* try to find the key in the trie
while(it!=end_it)
{
if(cur.empty())
break;
//std::cout<<"finding "<<*it<<std::endl;
+ //* find the next cursor
next=cur.find(*it);
if ( next == cur.end() )
{
@@ -833,13 +929,20 @@
it++;
}
+ //* if the entire key is not found
if(not_found)
{
+ //* then find the lower bound of the element which is not found the node.
+ //* then make cursor out of it.
next=Cur_type(cur.get_node(),lower_bound(cur.get_node(),*it));
//next=Cur_type(cur.get_node(),const_cast<node_type *>(cur.get_node())->lower_bound(*it));
+
+ //* if lower bound is found we have no problems :).
if(next!=cur.end())
{
ret_it.push(next);
+ //* move the right most in the subtree.
+ //* ie the greatest element/
ret_it.to_right_most();
return ret_it;
}
@@ -847,6 +950,7 @@
do
{
+ //* else pop until --next!= end() or next has value
next=ret_it.top();
ret_it.pop();
if(next.has_value())
@@ -863,9 +967,11 @@
next--;
ret_it.push(next);
+ //* move to highest key in the subtree.
ret_it.to_right_most();
return ret_it;
}
+
///find the prefix_range of the key
/**
@@ -883,23 +989,26 @@
Cur_type cur,next;
cur=this_ptr->root();
ret_it.push(cur);
+ //* as usual try to find the prefix in the trie.
while(it!=end_it)
{
if(cur.empty()) return std::make_pair(this_ptr->end(),this_ptr->end());
next=cur.find(*it);
+
+ //* if not found return end() pairs
if(cur.end()==next)
return std::make_pair(this_ptr->end(),this_ptr->end());
- //std::cout<<"LOOK AT ME:"<<*it<<std::endl;
+
cur=next;
ret_it.push(cur);
it++;
}
right=ret_it;
- //std::cout<<"To LEFT MOST"<<std::endl;
+ //* if prefix is found move to left most and right most.
ret_it.to_left_most();
//std::cout<<"To RIGHT MOST"<<std::endl;
right.to_right_most();
- //std::cout<<"pair range "<<*right<<std::endl;
+ //std::cout<<"pair range "<<*right<<std::endl;
return std::make_pair(ret_it,++right);
}
Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_array_node.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_array_node.hpp (original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_array_node.hpp 2008-07-05 02:38:50 EDT (Sat, 05 Jul 2008)
@@ -16,6 +16,10 @@
namespace boost{
namespace dsearch{
+/// iterator for trie array node.
+/**
+ \param trie_type is the type of trie node used.
+ */
template <typename trie_type>
class trie_array_node_iterator
:public iterator_facade<trie_array_node_iterator<trie_type>,trie_type *,boost::bidirectional_traversal_tag>
@@ -23,33 +27,43 @@
private:
friend class boost::iterator_core_access;
template<class Trie_t> friend class trie_array_node_iterator;
-
template<class K,class M,class Ke,class Allocator> friend class trie_array_node;
+ /// helps in avoiding conversion of const_iterator to iterator.
struct enabler {};
+ /// pointer to the child array.
trie_type** child_ptr;
+ /// pos is the position in the child array.
std::size_t pos;
public:
+ ///Self
typedef trie_array_node_iterator<trie_type> type;
+
+ /// Default constructor
trie_array_node_iterator()
:child_ptr(0), pos(0){}
+ /// Intialize a iterator from the node. ie begin().
trie_array_node_iterator(trie_type*node)
{
child_ptr=(trie_type**)(node->child_ptr);
int i=0;
+ //* find the first non zero position in the node.
for(i=0;i<trie_type::max;i++)
if(child_ptr[i]!=0) break;
pos=i;
}
+ /// Intialize the iterator to a particular position.
trie_array_node_iterator(trie_type *node,int p):pos(p)
{
child_ptr=(trie_type**)node->child_ptr;
}
private:
+
+ /// Used to check whether two iterators are equal.
template<class Trie_t>
bool equal( trie_array_node_iterator<Trie_t> const &other ) const
{
@@ -58,60 +72,90 @@
return false;
}
+ /// increment the iterator.
void increment()
{
+ //* check for the next non zero entry.
for(pos++; pos<trie_type::max; pos++)
if(child_ptr[pos]!=0) break;
}
+ /// decrement the iterator.
void decrement()
{
for(pos--; pos>0; pos--)
if(child_ptr[pos]!=0) break;
}
+ /// dereference the iterator
trie_type *&dereference() const
{
return child_ptr[pos];
}
public:
+ ///copy constructor
+ /**
+ \param other is the iterator to be copied
+ */
template<class Trie_t>
trie_array_node_iterator(const trie_array_node_iterator<Trie_t> &other,
typename enable_if< is_convertible<Trie_t*,trie_type*>,
enabler >::type = enabler()
)
{
- child_ptr=(trie_type **)(other.child_ptr);//converting from x* to const x*
+ //* converting from x* to const x*
+ child_ptr=(trie_type **)(other.child_ptr);
pos=other.pos;
}
};
-//TODO:const_cast (if safe) at other places to avoid duplication. Remove const functions here.
+/// This makes the trie class use an array for index children in every node.
+/**
+ \param Key is trie::key_type.
+ \param Mapped is trie::data_type.
+ \param Alloc is the allocator used.
+ */
template<class Key,class Mapped,class Key_traits,class Alloc=std::allocator<char> >
class trie_array_node
{
public:
+ ///Self
typedef trie_array_node<Key,Mapped,Key_traits,Alloc> type;
template<class T> friend class trie_array_node_iterator;
private:
+ /// An array of children indexed by the element_type.
type* child_ptr[Key_traits::max+1];
//typedef typename Alloc::template rebind<node_type>::other node_allocator_type;
public:
+ /// Element_type is type of each element in the key.
typedef typename Key_traits::element_type element_type;
+
+ /// iterator for the array node. Should iterate in increasing order or
+ /// decreasing order of elements.
typedef trie_array_node_iterator<type> iterator;
+
+ /// iterator for the array node. Should iterate in increasing order or
+ /// decreasing order of elements.
typedef trie_array_node_iterator<const type> const_iterator;
+
+ /// element_type is the key_type of trie_array node
typedef element_type key_type;
+
+ /// type* is the value type.
typedef type* value_type;
+ /// stored the value of the array in a pointer
Mapped *value_ptr;
+ /// maximum value of element_type
enum{
max=Key_traits::max
};
+ /// Default constructor
trie_array_node()
{
// std::cout<<"here"<<std::endl;
@@ -119,6 +163,7 @@
value_ptr=0;
}
+ /// Copy constructor
trie_array_node(const type &other)
{
if(other.value_ptr!=0)
@@ -131,13 +176,23 @@
assert( memcpy(child_ptr, other.child_ptr, sizeof(child_ptr) ) == child_ptr);
}
- void insert(const element_type &key,type * const &child_cursor)
+ /// insert a new child corresponding to the key.
+ /**
+ \param key element_type specifying the edge to the child.
+ \param child is the pointer to the child.
+ */
+ void insert(const element_type &key,type * const &child)
{
- child_ptr[Key_traits::get_value(key)]=child_cursor;
+ child_ptr[Key_traits::get_value(key)]=child;
}
- //*iterator should give reference to the value Mapped to by key;
+
+ // *iterator should give reference to the value Mapped to by key;
+ /// find a particular key in trie_array_node
+ /**
+ \param key for which the iterator is to be found.
+ */
iterator find(const element_type &key)
{
if(child_ptr[Key_traits::get_value(key)]==0)
@@ -155,11 +210,16 @@
return const_iterator(this,Key_traits::get_value(key));
}*/
+ /// erase value correspoding the iterator.
void erase(const iterator&it)
{
child_ptr[it.pos]=0;
}
+ /// returns an iterator which shows the elements in sorted order.
+ /**
+ \returns iterator pointing to the least element.
+ */
iterator begin()
{
return iterator(this);
@@ -170,6 +230,10 @@
return const_iterator(this);
}*/
+ /// returns an iterator which shows the elements in sorted order.
+ /**
+ \returns iterator pointing to the greatest element.
+ */
iterator end()
{
return iterator(this,max);
@@ -180,7 +244,14 @@
return const_iterator(this,max);
}*/
- //called only from insert function and trie::iterator
+ /// get reference to value stored
+ /**
+ \brief if has_value is false, assign default to value and return reference
+ to value.
+ Called only by insert and operator []
+ \note This function should be const
+ */
+
Mapped &get_value_ref()
{
if(value_ptr==0)
@@ -188,18 +259,28 @@
return *value_ptr;
}
- //called to get const reference fron const_* iterators and cursors
+ /// get reference to value stored
+ /**
+ \note This function should be const.
+ */
Mapped &get_value_ref() const
{
return *value_ptr;
}
+ ///erase value from trie_array_node
+ /**
+ */
void erase_value()
{
delete value_ptr;
value_ptr=0;
}
+ /// check whether this node has value or not.
+ /**
+ \returns true if node has a value stored. false otherwise.
+ */
bool has_value() const
{
return value_ptr!=0;
@@ -214,11 +295,6 @@
return t_size;
}*/
- element_type get_element(const iterator &it)
- {
- return Key_traits::get_element(it.pos);
- }
-
/* iterator lower_bound(const element_type &e)
{
int k=Key_traits::get_value(e);
@@ -228,6 +304,10 @@
return iterator(this,k);
}*/
+ /// check whether the node is empty or not.
+ /**
+ \returns true if node is empty false otherwise.
+ */
bool empty() const
{
for(int i=0;i<max;i++)
@@ -236,11 +316,16 @@
return true;
}
+ /// get element at a particular position specified by the iterator.
+ /**
+ \param it is the iterator whose element is to be got.
+ */
element_type get_element(const_iterator it) const
{
return Key_traits::get_element(it.pos);
}
+ /// Class destructor
~trie_array_node()
{
if(value_ptr!=0)
Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_iterator.hpp (original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_iterator.hpp 2008-07-05 02:38:50 EDT (Sat, 05 Jul 2008)
@@ -8,11 +8,18 @@
#include<boost/type_traits/is_convertible.hpp>
#include<boost/utility/enable_if.hpp>
-//TODO:Add specializations for ascending cursors without use of stack.
namespace boost{
namespace dsearch{
+/// iterator class for trie
+/**
+ \brief iterator is implemented using a stack of cursor.
+ \param Key is patricia::key_type
+ \param Mapped is patricia::data_type
+ \param Cursor is the type of cursor to be used iterate through the node.
+ \todo add specialization when the node has a parent pointer
+ */
template<class Key,class Mapped,class Cursor>
class trie_iterator
:public iterator_facade< trie_iterator<Key,Mapped,Cursor>,Mapped,bidirectional_traversal_tag >
@@ -23,47 +30,62 @@
friend class trie;
template<class K,class M,class C> friend class trie_iterator;
+ /// helps in avoiding conversion of const_iterator to iterator.
struct enabler {};
+ /// Self.
typedef trie_iterator<Key,Mapped,Cursor> self;
+ /// "stack" of cursors.
std::vector<Cursor> cur_st;
+ /// size of the stack.
int cur_size;
+ /// flag is true if the iterator is end()
bool end_flag;
+ /// push cursor into the stack
+ /**
+ \param c is the cursor to be pushed.
+ */
void push ( const Cursor &c )
{
++cur_size;
cur_st.push_back(c);
}
+ /// pop the cursor from the stack.
void pop()
{
--cur_size;
cur_st.pop_back();
}
+ /// get reference to top of the stack
Cursor &top()
{
assert(!(this->empty()));
return cur_st[cur_size-1];
}
+ /// returns the size of the stack
std::size_t size()
{
return cur_size;
}
+ /// get the top of the stack
Cursor get_top() const
{
assert(!(this->empty()));
return cur_st[cur_size-1];
}
+ ///checks whether the stack is empty.
bool empty() const
{
return cur_st.empty();
}
+ ///go to the right most leaf from the current top.
void to_right_most()
{
Cursor c=this->top();
@@ -77,6 +99,10 @@
assert(this->top().has_value());
}
+ ///check whether two iterators are equal.
+ /**
+ \param other is the other iterator. It can be const or non const.
+ */
template<class K,class M,class C>
bool equal(trie_iterator<K,M,C> const& other) const
{
@@ -85,6 +111,7 @@
return false;
}
+ ///go to the left most leaf from the current top.
void to_left_most()
{
Cursor c=this->top();
@@ -104,6 +131,7 @@
assert(this->top().has_value());
}
+ ///decrement the iterator.
void decrement()
{
bool first_loop=true;
@@ -124,16 +152,25 @@
end_flag=true;
return;
}
+
+ //* if we one the left edge of a node.
while(top==this->top().begin())
{
+ //* If top has value then we need to stop.
if(top.has_value() && !first_loop)
{
- this->push(top); //to make sure to_right_most still works
+ //* to make sure to_right_most still works
+ this->push(top);
return;
}
+
first_loop=false;
top=this->top();
this->pop();
+
+ //* we have reached the and empty stack? then we have reached
+ //* then we can go up no more.Also is top has value then
+ //* root has value.
if(this->empty())
{
this->push(top);
@@ -142,19 +179,26 @@
return;
}
}
+
+ //finally we found an edge which we can shift to the right
--top;
this->push(top);
+
+ //* move to the right most.
to_right_most();
}
+ ///increment the iterator.
void increment()
{
- assert(end_flag==false && NULL!="incrementing at end");//just for debugging
+ assert(end_flag==false && NULL!="incrementing at end");
assert(!this->empty() && NULL!="incrementing before begin");
Cursor top=this->top().begin();
+ //*if if it is the leaf node || we reached the edge a node.
while(this->top().end()==top)
{
+ //* pop in search of a new top.
top=this->top();
this->pop();
if(this->empty())
@@ -166,15 +210,18 @@
++top;
}
this->push (top);
+ //* go to left most.
to_left_most();
}
+ ///return a reference to the node the the is pointing to.
Mapped &dereference() const
{
assert ( (cur_st[cur_size-1]).has_value() );
return ( (cur_st[cur_size-1]).get_value() );
}
+ /*
bool equal( const self &other ) const
{
assert(!this->empty());
@@ -182,14 +229,19 @@
if(other.cur_st[other.cur_size-1]==cur_st[cur_size-1])
return true;
return false;
- }
+ }*/
public:
- trie_iterator():end_flag(false) //to be pushed later.. thats why
- {
- cur_size=0;
+ ///default constructor
+ trie_iterator():cur_size(0), end_flag(false)
+ {
}
+ ///constructor for begin() or end()
+ /**
+ \param cursor_root is patricia::node_root
+ \param end_flag specifies whether its begin cursor or end cursor.
+ */
trie_iterator( Cursor const &cursor_root,bool end_flag=false ) //returns begin cursor
{
cur_size=0;
@@ -199,20 +251,24 @@
this->push(cursor_root);
return;
}
-
- if( cursor_root.empty() && !cursor_root.has_value() ) //special case of only empty root
+ //*special case of only empty root
+ if( cursor_root.empty() && !cursor_root.has_value() )
{
-// std::cout<<"IN"<<std::endl;
this->end_flag=true;
this->push(cursor_root);
return;
}
-// std::cout<<"OUT"<<std::endl
+
this->push(cursor_root);
+ //goto the begin();
to_left_most();
}
public:
+ ///copy constructor
+ /**
+ \param other is the iterator to be copied
+ */
template<class K,class M,class C>
trie_iterator( trie_iterator<K,M,C> const& other,
typename enable_if< is_convertible<M*,Mapped*>,
@@ -222,6 +278,7 @@
end_flag=other.end_flag;
cur_size=0;
+ //* copy stack elements one by one.
typename std::vector<C>::const_iterator it=other.cur_st.begin();
while ( it!=other.cur_st.end() )
{
@@ -231,6 +288,16 @@
}
};
+
+/// reverse iterator class for trie
+/**
+ \brief reverse iterator class is implemented using an iterator.
+ \param Key is patricia::key_type
+ \param Mapped is patricia::data_type
+ \param Cursor is the type of cursor to be used iterate through the node.
+ \todo add specialization when the node has a parent pointer
+ */
+
template<class Key,class Mapped,class Cursor>
class trie_reverse_iterator
:public iterator_facade< trie_reverse_iterator<Key,Mapped,Cursor>,Mapped,bidirectional_traversal_tag >
@@ -239,15 +306,23 @@
friend class boost::iterator_core_access;
template<class K,class M,template<class K1,class M1,class K_t1,class A1 > class t_n,class K_t,class A >
friend class trie;
-
- struct enabler {};
template<class K,class M,class C> friend class trie_reverse_iterator;
+
+ /// helps in avoiding conversion of const_iterator to iterator.
+ struct enabler {};
+ /// Self
typedef trie_reverse_iterator<Key,Mapped,Cursor> self;
+ /// type of iterator corresponding to reverse_iterator.
typedef trie_iterator<Key,Mapped,Cursor> iterator;
- iterator correspond_it,beg_it;
+ /// use the corresponding iterator to iterate.
+ iterator correspond_it;
+ /// one must know when one hits rend :). thats this exists
+ iterator beg_it;
+ /// end_flag=true ==> we have reached rend
bool end_flag;
+ ///increments the reverse iterator.
void increment()
{
assert(!end_flag);
@@ -257,11 +332,13 @@
--correspond_it;
}
+ /// gets the corresponding iterator.
const iterator &get_iterator() const
{
return correspond_it;
}
+ /// decrements the reverse iterator.
void decrement()
{
if(end_flag)
@@ -275,6 +352,10 @@
return ( this->correspond_it==other.correspond_it && this->end_flag==other.end_flag);
}
*/
+ /// checks whether two reverse iterator.
+ /**
+ \param other is the other reverse iterator.
+ */
template<class K,class M,class C>
bool equal(trie_reverse_iterator<K,M,C> const& other) const
{
@@ -282,7 +363,8 @@
return true;
return false;
}
-
+
+ /// dereferences iterator.
Mapped &dereference() const
{
assert(!end_flag);
@@ -290,9 +372,18 @@
}
public:
+
+ /// default constructor
trie_reverse_iterator(): end_flag(0)
{
}
+
+ /// constructor of instilaizing to rbegin and rend
+ /**
+ \param beg_it is trie::begin()
+ \param end_it is trie::end()
+ \param is_beg_flag is true if its rbegin() otherwise false if its rend()
+ */
trie_reverse_iterator(const iterator &beg_it,const iterator &end_it,bool is_beg_flag)//should be intialized with end iterator
{
if(is_beg_flag)
@@ -309,6 +400,10 @@
}
}
+ ///copy constructor
+ /**
+ \param other is the reverse_iterator to be copied
+ */
template<class K,class M,class C>
trie_reverse_iterator( trie_reverse_iterator<K,M,C> const& other,
typename enable_if< is_convertible<M*,Mapped*>,
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