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

From: chintanraoh_at_[hidden]
Date: 2008-06-03 16:37:21

Author: chintanraoh
Date: 2008-06-03 16:37:21 EDT (Tue, 03 Jun 2008)
New Revision: 46091
URL: http://svn.boost.org/trac/boost/changeset/46091

Log:
added upper_bound, lower_bound and prefix_range
Text files modified: 
   sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp |   142 ++++++++++++++++++++++++++++++++++++++- 
   1 files changed, 136 insertions(+), 6 deletions(-)

Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp	(original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp	2008-06-03 16:37:21 EDT (Tue, 03 Jun 2008)
@@ -133,32 +133,162 @@
                 node_allocator.deallocate(cur,1);		
         }
 
+	//make use of iterator iterator.push();
         iterator find(const key_type &key) const //make this iterator instead of bool;
         {
                 typename Key_traits::const_iterator it=Key_traits::begin(key),
                                         end_it=Key_traits::end(key);
-		std::vector<cursor> cur_st;
+		iterator ret_it;
                 cursor cur,next;
                 cur=root();
                 while(!(it==end_it))
                 {
-			cur_st.push_back(cur);
+			ret_it.push(cur);
                         next=cur.find(*it);
-			if( next == cur.end() ) return end();
+			if ( next == cur.end() ) return end();
                         cur=next;
                         it++;
                 }
-		cur_st.push_back(cur);
+		ret_it.push(cur);
                 if(cur->has_value())
                 {
-			return iterator(cur_st.begin(),cur_st.end());
+			return ret_it;
                 }
                 return end();
         }
 
+	iterator upper_bound(const key_type &key)
+	{
+		typename Key_traits::const_iterator it=Key_traits::begin(key),
+					end_it=Key_traits::end(key);
+		iterator ret_it;
+		bool not_found=false;
+		cursor cur,next,r=root();
+		cur=r;
+		ret_it.push(cur);
+		std::cout<<"UPPER BOUND"<<std::endl;
+		while(it!=end_it)
+		{
+			if(cur.empty())
+			{
+				ret_it++;
+				return ret_it;
+			}
+			std::cout<<"finding "<<*it<<std::endl;
+			next=cur.find(*it);
+			if ( next == cur.end() )
+			{
+				not_found=true;
+				break;
+			}
+			std::cout<<"found "<<*it<<std::endl;
+			cur=next;
+			ret_it.push(cur);
+			it++;
+		}
+		//ret_it.push(cur);
+		if( not_found )
+		{
+			next=++cursor(cur.get_node(),cur.get_node()->lower_bound(*it));
+			while(next==ret_it.top().end())
+			{
+				std::cout<<"popping "<<std::endl;
+				next=ret_it.top();
+				if(next==r)
+					return end();
+				ret_it.pop();
+				next++;
+			}
+			ret_it.push(next);
+		}
+		ret_it.to_left_most(); //if ret_it.top().hash_value() then this does nothing
+		return ret_it;
+	}
+
+	iterator lower_bound(const key_type &key)
+	{
+		typename Key_traits::const_iterator it=Key_traits::begin(key),
+				end_it=Key_traits::end(key);
+		iterator ret_it;
+		bool not_found=false;
+		cursor cur,next,r=root();
+		cur=r;
+		ret_it.push(cur);
+		std::cout<<"LOWER BOUND"<<std::endl;
+		while(it!=end_it)
+		{
+			if(cur.empty())
+				break;
+			std::cout<<"finding "<<*it<<std::endl;
+			next=cur.find(*it);
+			if ( next == cur.end() )
+			{
+				not_found=true;
+				break;
+			}
+			std::cout<<"found "<<*it<<std::endl;
+			cur=next;
+			ret_it.push(cur);
+			it++;
+		}
+
+		if(not_found)
+		{
+			next=cursor(cur.get_node(),cur.get_node()->lower_bound(*it));
+			if(next!=cur.end()) 
+			{
+				ret_it.push(next);
+				ret_it.to_right_most();
+				return ret_it;
+			}
+		}
+
+		do
+		{
+			next=ret_it.top();
+			ret_it.pop();
+			if(next.has_value())
+			{
+				ret_it.push(next);
+				return ret_it;
+			}
+			if(next==r)
+			{
+				return end();
+			}
+		}
+		while(next==ret_it.top().begin());
+
+		next--;
+		ret_it.push(next);
+		ret_it.to_right_most();
+		return ret_it;
+	}
 
+	std::pair<iterator,iterator> prefix_range(const key_type &key)
+	{
+		typename Key_traits::const_iterator it=Key_traits::begin(key),
+				end_it=Key_traits::end(key);
+		iterator ret_it,right;
+		cursor cur,next;
+		cur=root();
+		ret_it.push(cur);
+		while(it!=end_it)
+		{
+			if(cur.empty()) return std::make_pair(end(),end());
+			next=cur.find(*it);
+			if(cur.end()==next)
+				return std::make_pair(end(),end());
+			cur=next;
+			ret_it.push(cur);
+		}
+		right=ret_it;
+		ret_it.to_left_most();
+		right.to_right_most();
+		return std::make_pair(ret_it,right);
+	}
 
-	void swap(const type &other)
+	void swap(type &other)
         {
                 std::swap(other.node_root,node_root);
         }