|
|
Boost-Commit : |
From: chintanraoh_at_[hidden]
Date: 2008-07-03 14:03:03
Author: chintanraoh
Date: 2008-07-03 14:03:02 EDT (Thu, 03 Jul 2008)
New Revision: 47049
URL: http://svn.boost.org/trac/boost/changeset/47049
Log:
documented patricia iterator class
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia_iterator.hpp | 116 +++++++++++++++++++++++++++++++--------
1 files changed, 91 insertions(+), 25 deletions(-)
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-03 14:03:02 EDT (Thu, 03 Jul 2008)
@@ -6,6 +6,13 @@
namespace boost{
namespace dsearch{
+
+///iterator for patricia
+/**
+ \param Value_type is patricia::value_type
+ \param Node_type is patricia::patricia_node
+ \param Alloc is the allocator
+ */
template<class Value_type, class Node_type, class Alloc>
class patricia_iterator
:public iterator_facade< patricia_iterator<Value_type,Node_type, Alloc>,
@@ -13,59 +20,69 @@
{
template<class K,class M,class K_t,class A > friend class patricia;
protected:
+ ///empty struct used for 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
+ /// if cur ! = NULL. if cur==NULL then next==root.
Node_type *cur;
+ ///Node to which the iterator points to.
Node_type *next;
+ ///increments the iterator.
virtual void increment()
{
if (cur)
{
+ //*move up if cur->right===next
while ( cur && ( cur->right==next || cur->right==0) )
{
next=cur;
cur=cur->par;
}
- if ( cur == 0) return; //reached end()
- next=cur->right; //cur->right!=0
+ if ( cur == 0) return; //* reached end()
+ next=cur->right; //* also cur->right!=0
}
else
{
+ //* next == root and now we are moving to the begin()
cur=next;
next=(cur->left)?cur->left:cur->right;
}
+ //* go down the least element in the edge
while ( next && next->index > cur->index )
{
cur=next;
next=cur->left?cur->left:cur->right;
}
}
-
+
+ ///decrements the iterator.
virtual void decrement()
{
if(cur)
{
+ //*move up if cur->left===next
while(cur && ( cur->left==next || cur->left==0 ) )
{
next=cur;
cur=cur->par;
}
if(cur==0)
- {
- //assert(false);
- //std::cout<<"Reached before begin"<<std::endl;
+ //* reached before begin()
return;
- }
+ //* also cur->left!=0
next=cur->left;
}
else
{
+ //* next == root and now we are moving to the end() - 1
cur=next;
next=(cur->right==0)?cur->left:cur->right;
}
+ //* go down the greatest element in the edge
while ( next && next->index > cur->index )
{
cur=next;
@@ -73,28 +90,28 @@
}
}
+ ///dereferences the iterator.
Value_type &dereference() const
{
assert(cur); //dont reference null;
return next->value;
}
+ ///check whether two iterator are equal.
+ /**
+ \returns true if the iterator are equal otherwise false.
+ \param other is other iterator which is supposed to compared to this.
+ */
template<class V,class N,class A>
- bool equal(patricia_iterator<V,N,A> const &other,
- typename enable_if< is_convertible<V*,Value_type*>,
- enabler >::type = enabler()
- ) const
- {
-
+ bool equal(patricia_iterator<V,N,A> const &other) const
+ {
if ( cur == other.cur && next == other.next )
return true;
- //std::cout<<"In equal cur:"<<cur<< "!=" << other.cur<<std::endl;
- //std::cout<<"In equal next:"<<next<< "!=" << other.next<<std::endl;
- //std::cout<<"In equal"<<next->value.first << "!=" << other.next->value.first<<std::endl;
return false;
}
private:
+ ///move to the right most node of the edge cur<-->next
void to_right_most()
{
assert(cur);
@@ -106,6 +123,7 @@
}
private:
+ ///move to the left most node of the edge cur<-->next
void to_left_most()
{
assert(cur);
@@ -119,10 +137,16 @@
}
public:
+ ///default constructor
patricia_iterator() : cur(0),next(0)
{
}
+ ///use to intialize begin or end.
+ /**
+ \param root is the patricia's root node
+ \param start specifies start or end
+ */
patricia_iterator(Node_type *root, bool start)
{
if(start)
@@ -133,6 +157,7 @@
root=0;
return;
}
+ //*move to the left most wrt root.
cur=root;
next= (cur->left)?cur->left:cur->right;
assert(next!=0);
@@ -149,7 +174,13 @@
}
return;
}
-
+
+ ///copy constructor for the iterator
+ /**
+ \brief is_covertible ensures that const_iterator cannot be converted
+ to iterator
+ \param other is the iterator to be copied
+ */
template<class V,class N,class A>
patricia_iterator ( patricia_iterator<V,N,A> const& other,
typename enable_if< is_convertible<V*,Value_type*>,
@@ -158,36 +189,53 @@
{
}
+ ///initialize the iterator by specifying the edge using found and prev.
+ /**
+ \param found is the node whihc the iterator points to
+ \param prev is node such that prev->left==found or prev->right==found
+ */
patricia_iterator (Node_type* found,Node_type *prev):
cur(prev),next(found)
{
}
};
+///reverse iterator for the patricia node
+/**
+ \param Value_type is patricia::value_type
+ \param Node_type is patricia::patricia_node
+ \param Alloc is the allocator
+ */
template<class Value_type, class Node_type, class Alloc >
class patricia_reverse_iterator:
public patricia_iterator<Value_type, Node_type, Alloc>
{
friend class patricia_iterator<Value_type, Node_type, Alloc>;
+ ///the patricia_iterator super class
typedef patricia_iterator<Value_type, Node_type, Alloc> forward_type;
private:
+ ///empty struct used for conversion from const_iterator to iterator
struct enabler {};
+
+ ///decrements to reverse_iterator
void decrement()
{
forward_type::increment();
}
+ ///increments the reverse_iterator
void increment()
{
forward_type::decrement();
}
-
+ ///check whether two reverse iterator are equal.
+ /**
+ \returns true if the reverse iterator are equal otherwise false.
+ \param other is other reverse iterator which is supposed to compared to this.
+ */
template<class V,class N,class A>
- bool equal(patricia_reverse_iterator<V,N,A> const &other,
- typename enable_if< is_convertible<V*,Value_type*>,
- enabler >::type = enabler()
- ) const
+ bool equal(patricia_reverse_iterator<V,N,A> const &other) const
{
if ( forward_type::cur == other.cur && forward_type::next == other.next )
return true;
@@ -195,29 +243,47 @@
return false;
}
+ ///dereferences the iterator
Value_type &dereference() const
{
return forward_type::dereference();
}
public:
+ ///default constructor
patricia_reverse_iterator(): forward_type()
{
}
+ ///initialize the iterator by specifying the edge using found and prev.
+ /**
+ \param found is the node whihc the iterator points to
+ \param prev is node such that prev->left==found or prev->right==found
+ */
patricia_reverse_iterator(Node_type *found,Node_type*prev)
:forward_type(found,prev)
{
}
-
+
+
+ ///use to intialize begin or end.
+ /**
+ \param root is the patricia's root node
+ \param start specifies start or end
+ */
patricia_reverse_iterator(Node_type *root,bool start)
{
forward_type::cur=0;
forward_type::next=root;
if(start)
- forward_type::decrement(); //rbegin()=end()-1
+ forward_type::decrement(); ///rbegin()=end()-1
}
-
+ ///copy constructor for reverse the iterator
+ /**
+ \brief is_covertible ensures that const_reverse_iterator cannot be converted
+ to reverse_iterator
+ \param other is the iterator to be copied
+ */
template<class V,class N,class A>
patricia_reverse_iterator ( patricia_reverse_iterator<V,N,A> const& other,
typename enable_if< is_convertible<V*,Value_type*>,
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