Boost logo

Boost-Commit :

From: chintanraoh_at_[hidden]
Date: 2008-06-06 13:46:13


Author: chintanraoh
Date: 2008-06-06 13:46:13 EDT (Fri, 06 Jun 2008)
New Revision: 46198
URL: http://svn.boost.org/trac/boost/changeset/46198

Log:
added reverse iterator
Text files modified:
   sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_iterator.hpp | 120 +++++++++++++++++++++++++++++++++++++--
   1 files changed, 112 insertions(+), 8 deletions(-)

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-06-06 13:46:13 EDT (Fri, 06 Jun 2008)
@@ -4,6 +4,8 @@
 #include<stack>
 #include<boost/iterator/iterator_facade.hpp>
 #include<assert.h>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/utility/enable_if.hpp>
 
 //forces the thing to be bidirectional horizontally.
 //TODO:Add specializations for ascending cursors without use of stack.
@@ -17,14 +19,17 @@
 :public iterator_facade< trie_iterator<Key,Mapped,Cursor>,Mapped,bidirectional_traversal_tag >
 {
         private:
- std::stack<Cursor> cur_st;
+ struct enabler {};
         typedef trie_iterator<Key,Mapped,Cursor> self;
         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;
+ std::stack<Cursor> cur_st;
         bool end_flag;
+ template<class K,class M,class C> friend class trie_iterator;
+
 
- void push(const Cursor &c)
+ void push( const Cursor &c )
         {
                 cur_st.push(c);
         }
@@ -58,6 +63,13 @@
                 assert(this->top().has_value());
         }
 
+ template<class K,class M,class C>
+ bool equal(trie_iterator<K,M,C> const& other) const
+ {
+ if( this->end_flag == other.end_flag && this->cur_st.top() == other.cur_st.top() )
+ return true;
+ return false;
+ }
         void to_left_most()
         {
                 Cursor c=this->top();
@@ -87,9 +99,8 @@
                         end_flag=false;
                         return;
                 }
-
                 assert(!this->empty());
- //pop();
+
                 top=this->top();
                 this->pop();
                 if(this->empty())
@@ -150,7 +161,7 @@
                 return ((cur_st.top()).get_value());
         }
         
- bool equal(const self &other) const
+ bool equal( const self &other ) const
         {
                 assert(!this->empty());
                 if(end_flag!=other.end_flag) return false;
@@ -160,11 +171,11 @@
         }
 
         public:
- trie_iterator():end_flag(false)
+ trie_iterator():end_flag(false) //to be pushed later.. thats why
         {
         }
 
- trie_iterator(Cursor const &cursor_root,bool end_flag=false) //returns begin cursor
+ trie_iterator( Cursor const &cursor_root,bool end_flag=false ) //returns begin cursor
         {
                 this->end_flag=end_flag;
                 if(this->end_flag)
@@ -173,7 +184,7 @@
                         return;
                 }
 
- if(cursor_root.empty() && !cursor_root.has_value()) //special case of only empty root
+ if( cursor_root.empty() && !cursor_root.has_value() ) //special case of only empty root
                 {
                         end_flag=true;
                         this->push(cursor_root);
@@ -182,6 +193,99 @@
                 this->push(cursor_root);
                 to_left_most();
         }
+
+ //TODO:use enable_if and is_convertible correctly
+ template<class K,class M,class C>
+ trie_iterator( trie_iterator<K,M,C> const& other,
+ typename enable_if< is_convertible<M*,Mapped*>,
+ enabler >::type = enabler()
+ )
+ {
+ end_flag=other.end_flag;
+ cur_st=other.cur_st;
+ }
+
+};
+
+template<class Key,class Mapped,class Cursor>
+class trie_reverse_iterator
+:public iterator_facade< trie_reverse_iterator<Key,Mapped,Cursor>,Mapped,bidirectional_traversal_tag >
+{
+ private:
+ struct enabler {};
+ friend class boost::iterator_core_access;
+ template<class K,class M,class C> friend class trie_reverse_iterator;
+ typedef trie_reverse_iterator<Key,Mapped,Cursor> self;
+ typedef trie_iterator<Key,Mapped,Cursor> iterator;
+
+ iterator correspond_it,beg_it;
+ bool end_flag;
+
+ void increment()
+ {
+ assert(!end_flag);
+ if(beg_it==correspond_it)
+ end_flag=true;
+ else
+ --correspond_it;
+ }
+
+ void decrement()
+ {
+ if(end_flag)
+ end_flag=false;
+ else
+ ++correspond_it;
+ }
+
+ bool equal(const self &other) const
+ {
+ return ( this->correspond_it==other.correspond_it && this->end_flag==other.end_flag);
+ }
+
+ template<class K,class M,class C>
+ bool equal(trie_iterator<K,M,C> const& other) const
+ {
+ if( this->end_flag == other.end_flag && this->correspond_it=other.correspond_it )
+ return true;
+ return false;
+ }
+
+ Mapped &dereference()
+ {
+ assert(!end_flag);
+ return *correspond_it;
+ }
+
+
+ public:
+ 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)
+ {
+ this->beg_it=beg_it;
+ correspond_it=end_it;
+ --correspond_it;
+ end_flag=false;
+ }
+ else
+ {
+ this->beg_it=correspond_it=beg_it;
+ end_flag=true;
+ }
+ }
+
+ 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*>,
+ enabler >::type = enabler()
+ )
+ {
+ this->end_flag=other.end_flag;
+ this->correspond_it=other.correspond_it;
+ this->beg_it=other.beg_it;
+ }
+
 };
 
 }


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