[Boost-commit] svn:boost r46198 - sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch

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;
+	}
+
 };
 
 }