From: chintanraoh_at_[hidden]
Date: 2008-06-01 13:44:51
Author: chintanraoh
Date: 2008-06-01 13:44:51 EDT (Sun, 01 Jun 2008)
New Revision: 46028
URL: http://svn.boost.org/trac/boost/changeset/46028
Log:
new file containing trie iterator
Added:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_iterator.hpp (contents, props changed)
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_iterator.hpp 2008-06-01 13:44:51 EDT (Sun, 01 Jun 2008)
@@ -0,0 +1,101 @@
+#include<iostream>
+#include<stack>
+#include<boost/iterator/iterator_facade.hpp>
+#include<assert.h>
+
+//forces the thing to be bidirectional horizontally.
+//TODO:Add specializations for ascending cursors without use of stack.
+//BUG:currently this has no indicator to say that a particular thing is pointing to a value.
+
+namespace boost{
+namespace dsearch{
+
+template<class Key,class Mapped,class Cursor>
+class trie_iterator
+:public iterator_facade< trie_iterator<Key,Mapped,Cursor>,Mapped,bidirectional_traversal_tag >
+{
+ private:
+ std::stack<Cursor> cur_st;
+ friend class iterator_core_access;
+ bool end_flag;
+ void to_right_most()
+ {
+ Cursor c=cur_st.top();
+ while(c.begin()!=c.end())
+ {
+ c=--c.end();
+ cur_st.push(c);
+ if(c.has_value()) break;
+ }
+ assert(cur_st.top().has_value());
+ }
+
+ void to_left_most()
+ {
+ Cursor c=cur_st.top();
+ if(c.has_value()) return ;
+ while(c.begin()!=c.end())
+ {
+ std::cout<<"PUSHING"<<std::endl;
+ if(c.has_value()) break;
+ c=c.begin();
+ cur_st.push(c);
+ }
+ assert(cur_st.top().has_value());
+ }
+
+ void decrement()
+ {
+ Cursor top=cur_st.top();
+ cur_st.pop();
+ while(cur_st.top().begin()==top)
+ {
+ if(top.has_value())
+ return;
+ top=cur_st.top();
+ cur_st.pop();
+ }
+ --top;
+ cur_st.push(top);
+ to_right_most();
+ }
+
+ void increment()
+ {
+ Cursor top=cur_st.top();
+ cur_st.pop();
+ while(cur_st.top().end()==top+1)
+ {
+ top=cur_st.top();
+ cur_st.pop();
+ }
+ ++top;
+ cur_st.push(top);
+ to_left_most();
+ }
+
+ Mapped &dereference() const
+ {
+ assert(cur_st.top().has_value());
+ return cur_st.top().get_value();
+ }
+
+ public:
+ trie_iterator():end_flag(0) //An end cursor
+ {}
+ trie_iterator(Cursor const &cursor_root) //returns begin cursor
+ {
+ Cursor c=cursor_root;
+/* if(c.begin()==c.end() && c.)
+ {
+ end_flag=true;
+ return;
+ }
+ end_flag=false;*/
+ cur_st.push(c);
+ to_left_most();
+ }
+};
+
+}
+}