Boost logo

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