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

From: chintanraoh_at_[hidden]
Date: 2008-06-18 14:25:10

Author: chintanraoh
Date: 2008-06-18 14:25:09 EDT (Wed, 18 Jun 2008)
New Revision: 46487
URL: http://svn.boost.org/trac/boost/changeset/46487

Log:
clear and copy
Text files modified: 
   sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp |   151 ++++++++++++++++++++++++++++++++++++++- 
   1 files changed, 144 insertions(+), 7 deletions(-)

Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp	(original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp	2008-06-18 14:25:09 EDT (Wed, 18 Jun 2008)
@@ -20,6 +20,7 @@
 template<class Key,class Mapped,class Key_traits,class Alloc=std::allocator<char> >
 class patricia{
         private: 
+	typedef patricia<Key,Mapped,Key_traits,Alloc> self;
         typedef typename Key_traits::const_iterator key_iterator;
         typedef typename Key_traits::element_type key_element_type;
 
@@ -52,12 +53,11 @@
                 patricia_node(const key_type& key_,const std::size_t &index_,patricia_node *left_
                 ,patricia_node *right_,patricia_node *par_) 
                 :par(par_),value(make_pair(key_,0)),index(index_),left(left_),right(right_)
-		{	
-			/*this->index=index;
-			this->left=left;
-			this->right=right;
-			this->par=par;
-			this->value.first=key;*/
+		{
+		}
+		patricia_node(const patricia_node &other)
+		:par(0),value(other.value),index(other.index),left(0),right(0)
+		{
                 }
         };
         typedef typename Alloc::template rebind<patricia_node>::other node_allocator_type;
@@ -71,6 +71,11 @@
         patricia(): root(0)
         {
         }
+	
+	patricia(const self &other)
+	{
+		copy_patricia(other.root);
+	}
 
         data_type &operator [](const key_type &k)
         {
@@ -127,6 +132,45 @@
                 return root==0;
         }
 
+	void clear()
+	{
+		patricia_node *cur,*next;
+		if(root==0) return;
+		cur=root;
+		root=0;
+		while(true)
+		{
+			next=cur->left?cur->left:cur->right;
+			if(next==0)
+			{
+				next=cur->par;
+				delete cur;
+				if(next==0) return; 
+				if(next->left==cur)
+					next->left=0;
+				else
+					next->right=0;
+				cur=next;
+			}
+			else
+			if( next->par!=cur ) 
+			{
+				//entered up link. so mark the thing as zero.
+				if(cur->left==next)
+					cur->left=0;
+				else
+					cur->right=0;
+			}
+			else
+			cur=next;
+		}
+	}
+	
+	~patricia()
+	{
+		this->clear();
+	}
+
         private:
         //function for Random Access Iterator
         inline data_type &insert_new_node(const key_type &key,rand_tag)
@@ -402,7 +446,6 @@
                 else
                         uncommon_bit=(k1_it==k1_end)?((k2_it==k2_end)?2:0):1;
 
-
                 return std::make_pair<std::size_t,int>(pos,uncommon_bit);
         }
 
@@ -449,6 +492,18 @@
                 return next;
         }
 
+	/*key_iterator move_iterator(const key_iterator it,const iterator end_it,const std::size_t &cur_pos,const std::size_t &dest_pos)
+	{
+		std::size_t i=dest_pos-cur_pos;
+		key_iterator ret_it=it;
+		while(i){
+			if ( ret_it==end_it ) return end_it;
+			++ret_it;
+			--i;
+		}
+		return ret_it;
+	}*/
+
         patricia_node* find_node(const patricia_node *cur, const key_type &key,rand_tag,std::size_t key_size=0)
         {
                 patricia_node  *next=0;
@@ -699,6 +754,88 @@
                 to->index=found->index;
         }
 
+	//used by copy_patricia
+	patricia_node *copy_patricia_find_par(patricia_node* const &this_cur,
+	const patricia_node* const &other_cur,const patricia_node * const &par)
+	{
+		patricia_node *cur=this_cur;
+		const patricia_node* o_cur=other_cur;
+		if(other_cur==0) return 0;
+		while(o_cur!=par)
+		{
+			cur=cur->par;
+			o_cur=o_cur->par;
+		}
+		return cur;
+	}
+
+	void copy_patricia(const patricia_node *other_root)
+	{
+		const patricia_node *const*other_cur,*other_temp,*other_prev;
+		patricia_node **cur,*prev;
+		if(other_root==0)
+		{
+			this->root=0;
+			return;
+		}
+
+		cur=&root;
+		std::cout<<"OTHER ROOT:"<<other_root<<std::endl;
+		other_cur=&other_root;
+		other_prev=0;
+		prev=0;
+		while(true)
+		{
+			assert(prev!=other_root);
+			if( (*other_cur) && (*other_cur)->par==other_prev)
+			{
+				(*cur)=node_allocator.allocate(1);
+				new(*cur) patricia_node(**other_cur);
+				assert((*cur)!=other_root);
+				assert(other_root);
+				assert((*cur)->right!=other_root);
+				(*cur)->par = prev;
+				std::cout<<(**cur).value.first<<" "<<(prev==0?"NULL":prev->value.first)<<std::endl;
+				other_prev=*other_cur;
+				other_cur=&(other_prev->left);
+				prev=*cur;
+				cur=&(prev->left);
+				std::cout<<"copy:here1"<<std::endl;
+				continue;
+			}
+			std::cout<<"copy:here2"<<std::endl;
+			(*cur)=copy_patricia_find_par(prev,other_prev,*other_cur);
+			assert((*cur)!=other_root);
+			//leaf node!!
+			if((*other_cur)==other_prev->left)
+			{
+				//assert(*cur!=other_root);
+				other_cur=&(other_prev->right);
+				//assert(other_prev!=prev);
+				cur=&(prev->right);
+				std::cout<<prev->value.first<<std::endl;
+				std::cout<<( (*other_cur)?(*other_cur)->value.first:"HOW NULL" )<<std::endl;
+				assert((*cur)!=other_root);
+			}
+			else
+			{
+				other_temp=other_prev->right;
+				while(other_temp==other_prev->right)
+				{
+					other_temp=other_prev;
+					other_prev=other_prev->par;
+					prev=prev->par;
+					if(other_prev==0) 
+					{
+						std::cout<<"ROOT:"<<root<<std::endl;
+						return;
+					}
+				}
+				other_cur=&other_prev->right;
+				cur=&prev->right;
+			}
+		}
+	}
 };
 
 }//namespace dsearch