From: chintanraoh_at_[hidden]
Date: 2008-08-30 11:34:35
Author: chintanraoh
Date: 2008-08-30 11:34:34 EDT (Sat, 30 Aug 2008)
New Revision: 48472
URL: http://svn.boost.org/trac/boost/changeset/48472
Log:
removed functions from patricia_details.hpp to forward and sequence files
Added:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_forward_sequence.hpp (contents, props changed)
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_random_sequence.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_details.hpp | 703 ++++++++++++++++++++++++++++++++++++++++
1 files changed, 703 insertions(+), 0 deletions(-)
Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_details.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_details.hpp (original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_details.hpp 2008-08-30 11:34:34 EDT (Sat, 30 Aug 2008)
@@ -0,0 +1,703 @@
+
+///Has a pair of node pointers. usually has firt element as node found
+///and second element as the node from which the upward edge goes.
+typedef std::pair<patricia_node*,patricia_node*> node_pair_type;
+
+///find element points to point at which the bits become uncommon between two keys
+///and second element as uncommon bit.
+///second element=2 if two strings are equal.
+typedef std::pair<std::size_t,int> common_type;
+
+
+#include "patricia_random_sequence.hpp"
+#include "patricia_forward_sequence.hpp"
+
+///Insert new node
+/**
+ \returns reference to data_type in the new node.
+ \param key is key to be inserted.
+ */
+template<class T>
+inline data_type &insert_new_node(const key_type &key,T)
+{
+ key_iterator it,end_it;
+ patricia_node *cur=root,*next=root,*temp_node,*old_root=0;
+ std::pair< std::pair<patricia_node*,patricia_node*>,
+std::pair<std::size_t,int> > insert_pair;
+
+ //std::cout<<"in random access"<<std::endl;
+
+ std::pair<std::size_t,int> common;
+
+ //std::cout<<"\nInserting \""<<key<<"\""<<std::endl;
+
+ it=Key_traits::begin(key);
+ end_it=Key_traits::end(key);
+
+ //*do some jugglery to ensure that inserting "" first as root wont cause any problems
+ //*move root to the right position while inserting the second
+ //*that will take care of the assert(next) in find
+ old_root=0;
+ if(root!=0 && root->left==root)
+ {
+ if(it==end_it) return root->value.second; //if one adds "" twice
+ old_root=root;
+ root=0;
+ }
+
+ if(root==0)
+ {
+ root=node_allocator.allocate(1);
+ if(it!=end_it)
+ {
+ new(root) patricia_node( key, 0, old_root, root, 0 );
+ if(old_root)
+ {
+ //*reassign the old root the position.
+ old_root->par=root;
+ }
+ }
+ else
+ new(root) patricia_node( key, 0, root, 0, 0 );
+ return root->value.second;
+ }
+
+ if(it==end_it)
+ {
+ //*"" inserted
+
+ if(root->left==0)
+ {
+ root->left = node_allocator.allocate(1);
+ new(root->left) patricia_node(key,0,root->left,0,root);
+ }
+ return root->left->value.second;
+ }
+
+ //*get the insert pair. the pair in between which the things should be inserted
+ insert_pair=get_insert_pair(key,T());
+
+ common=insert_pair.second;
+ next=insert_pair.first.first;
+ cur=insert_pair.first.second;
+ //*if the key already exists return
+ if(common.second==2)
+ {
+ #ifdef PAT_DEBUG
+ std::cout<<"The key \""<<key<<"\" already exists"<<std::endl;
+ #endif
+ return next->value.second;
+ }
+
+ //*allocate new node
+ temp_node=node_allocator.allocate(1);
+
+ //*rewire the cur to temp_node
+ if(cur->left==next)
+ cur->left=temp_node;
+ else
+ if(cur->right==next)
+ cur->right=temp_node;
+ else
+ assert(false);
+
+
+ if(common.second)
+ //*temp_node should point to inself at 1 ie right
+ new (temp_node) patricia_node(key,common.first,next,temp_node,cur);
+ else
+ //*temp_node should point to inself at 0 ie right
+ new (temp_node) patricia_node(key,common.first,temp_node,next,cur);
+
+
+ assert(root->par==0);
+
+ //*if its not an upward link adjust the next->par
+ if(cur->index < next->index) next->par=temp_node;
+
+ assert(root->par==0);
+ return temp_node->value.second;
+}
+
+///get nth element nth bit in the element
+/** \returns nth bit
+ \param element whose nth bit is to be found
+ \param n is the bit to be got
+ */
+inline bool get_nth_bit(const key_element_type &element,const int &n) const
+{
+ return n==0? 1 : ( ( element&(1<<(bit_width - n )) ) !=0 );
+}
+
+///get the position upto which the bits are equal.
+/**
+ \returns inclusive of end bit after each pos and the not(un) common bit in k1;
+ \returns and the not common bit as two if both keys are equal.
+ \param k1 is the first key
+ \param k2 is the second key
+ */
+inline std::pair<std::size_t,int> get_common_bits(const key_type &k1,const key_type &k2) const
+{
+ key_iterator k1_it,k2_it,k1_end,k2_end;
+ //std::cout<<"comparing "<<k1<<" and "<<k2<<std::endl;
+ int uncommon_bit;
+ key_element_type t1,t2;
+ bool unequal=false;
+ std::size_t pos=0;
+
+ k1_it=k1.begin();
+ k2_it=k2.begin();
+ k1_end=k1.end();
+ k2_end=k2.end();
+
+ //*check until the chars are unequal and increment pos accordingly
+ while(k1_it!=k1_end && k2_it!=k2_end )
+ {
+ if ( Key_traits::get_element(k1_it) != Key_traits::get_element(k2_it) )
+ {
+ unequal=true;
+ break;
+ }
+ pos+=bit_width+1;
+ ++k1_it;
+ ++k2_it;
+ }
+
+ if(unequal)
+ {
+ //*find the unequal bit
+ std::size_t bit_pos=0;
+ t1=Key_traits::get_element(k1_it);
+ t2=Key_traits::get_element(k2_it);
+ key_element_type x=t1;
+ while((t1)!=( t2))//possibly make this ( t1 & x) != ( t1 & x )
+ {
+ t1>>=1;
+ t2>>=1;
+ ++bit_pos;
+ }
+ uncommon_bit= ( ( x & (key_element_type(1)<<(bit_pos-1)) ) !=0);
+ pos+=bit_width-bit_pos+1;
+ //increment pos accordingly
+ }
+ else
+ {
+ //*assign uncommon_bit==2 if ( k1_it==k1_end && k2_it==k2_end )
+ //*if k1_it==k1_end && k2_it!=k2_end assing 0
+ //*otherwise 1
+ uncommon_bit=(k1_it==k1_end)?((k2_it==k2_end)?2:0):1;
+ }
+
+ return std::make_pair<std::size_t,int>(pos,uncommon_bit);
+}
+
+
+
+ ///erases the found node.
+/**
+ \returns void
+ \param found is the node to be erase.
+ \param prev is the node with the uplink.
+ */
+void erase(patricia_node*found,patricia_node *prev)
+{
+ if(root==0 || found==0) return;
+ #ifdef PAT_DEBUG
+ std::cout<<"in erase: found "<<found->value.first<<" and prev "<<prev->value.first<<std::endl;
+ #endif
+ if ( found-> par == 0 ) {
+ //*==> found=root node
+ #ifdef PAT_DEBUG
+ std::cout<<"par"<<std::endl;
+ #endif
+ assert(root==found);
+
+ if( (found->right==0 || found->left==0) && found==prev){
+ //*only root or only ""
+ deallocate_node(found);
+ root=0;
+ return;
+ }
+ //std::cout<<"wrong place"<<std::endl;
+
+ if(prev==found){
+ //*also takes care of taking to "" to the root
+ root=(found->right==found)?found->left:found->right;
+ if(root) root->par=0;
+ deallocate_node(found);
+ return;
+ }
+ }
+ else
+ if ( found->right==0 || found->left==0 )
+ prev=found;
+ //* now prev contains the node from which found is wired with an uplink
+ #ifdef PAT_DEBUG
+ std::cout<<"here"<<std::endl;
+ #endif
+ //*if a node is looping to itself
+ //*deleting the leaf node.
+ //*this case for root node is handled before
+ if ( prev == found ) {
+
+
+ //*check how its liked to the par
+ //*and found->par!=0 as root node has been handled before.
+ if ( found->par->right == found )
+ {
+ //*rewire the parent.
+ found->par->right = (found->right==found)?found->left:found->right;
+ //*also take care rewiring the new childs parent
+ if( found->par->right && found==found->par->right->par ) found->par->right->par=found->par;
+ }
+ else
+ if ( found->par->left == found )
+ {
+ //*rewire the parent.
+ found->par->left = (found->right==found)?found->left:found->right;
+ //*also take care rewiring the new childs parent
+ if( found->par->left && found==found->par->left->par ) found->par->left->par=found->par;
+ }
+ else
+ assert(false);
+ //std::cout<<"prev==found with key="<<key<<std::endl;
+ if ( found->right==0 || found->left==0 )
+ {
+ //*Probably erasing "" for lets be extra careful
+ //*check whether the par is as expected proper.
+ assert(found->par==root);
+ #ifdef PAT_DEBUG
+ std::cout<<"\"\" node to be erased"<<std::endl;
+ #endif
+ }
+ deallocate_node(found);
+ return;
+ }
+
+ //*since we are moving prev to where found is we need to rewire the prev parents
+ //*check how the prev->par is attached to prev
+ if(prev->par->right==prev) {
+ //*rewrite the prev->parent to the prev's other child
+ prev->par->right=(prev->right==found)?prev->left:prev->right;
+ //*if prev->right == prev or prev->left == prev there is a self loop so we need to take for it too.
+ //*and not re-adjust par.
+ if( prev->right!=prev && prev->left!=prev && prev->par->right ) prev->par->right->par=prev->par;
+ }
+ else {
+ //std::cout<<"far away here"<<std::endl;
+ //*rewrite the prev->parent to the prev's other child
+ prev->par->left=(prev->right==found)?prev->left:prev->right;
+ //*if prev->right == prev or prev->left == prev there is a self loop so we need to take for it too.
+ //*and not re-adjust par.
+ if( prev->right!=prev && prev->left!=prev && prev->par->left) prev->par->left->par=prev->par;
+ }
+
+ //*if we are deallocating the root
+ if(found->par==0)
+ root=prev;
+ //*finally copy the pointers and index of found to prev node
+ copy_node_ptr(prev,found);
+ deallocate_node(found);
+}
+
+/// erase the node having key
+/**
+ \returns void
+ \param key is the key to be erase.
+ */
+template<class T>
+void erase(const key_type& key,T)
+{
+ patricia_node *cur,*found;
+ std::pair<patricia_node*,patricia_node*> temp_pair,check_pair;
+
+ if(root==0) return;
+
+ assert(root->par==0);
+
+ #ifdef PAT_DEBUG
+ std::cout<< ((root->left!=0)?" \"\" exists":"\"\" does not exists")<<std::endl;
+ #endif
+
+ assert( (root->left!=0 && root->left!=root)? root->left->par==root: 1 );
+
+ temp_pair=find_node_prev(root,key,T());
+ found=temp_pair.first;
+ cur=temp_pair.second;
+ if(found==0) return;
+
+ //check_pair=find_node_prev(root,key,rand_tag());
+ //assert(check_pair==temp_pair);
+
+ erase(found,cur);
+}
+
+///deallocate a particular node. Used by erase.
+/**
+ \returns void
+ \param found is the pointer to the node to be erased
+ */
+void inline deallocate_node(patricia_node *&found)
+{
+ node_allocator.destroy(found);
+ node_allocator.deallocate(found,1);
+}
+
+
+/// used by erase(key);
+///copies pointers of two nodes. replacing the "found" node by "to" node.
+/**
+ \returns void
+ \param to is the node to replaced by.
+ \param found is the node to replace.
+ */
+void inline copy_node_ptr(patricia_node* to, patricia_node* found)
+{
+ if(found->par!=0) {
+ //*rewire found->par
+ if(found->par->right==found)
+ found->par->right=to;
+ else
+ found->par->left=to;
+ }
+ to->par=found->par;
+
+ if(found->right!=found)
+ //*if found is not connected to itself
+ to->right=found->right;
+ else
+ to->right=to;
+
+ if(found->left!=found)
+ //*if found is not connected to itself
+ to->left=found->left;
+ else
+ to->left=to;
+
+ //*rewire the parents of left and right
+ if ( found->left && found->left->par==found ) found->left->par=to;
+ if ( found->right && found->right->par==found ) found->right->par=to;
+
+ to->index=found->index;
+}
+
+///finds the lower bound corresponding to the key.
+/**
+ \returns the iterator pointing to the lower bound.
+ if there is no lower bound return end()
+ \param key is the key whose upper bound is to be found
+ */
+template<class T>
+inline iterator lower_bound(const key_type &key,T)
+{
+ typedef std::pair<patricia_node*,patricia_node*> node_pair_type;
+ typedef std::pair<std::size_t, int> common_type;
+
+ std::pair<node_pair_type,common_type> node_pair;
+ common_type common;
+ patricia_node* next,*cur;
+ iterator it;
+
+
+ if(root==0) return end();
+ if ( Key_traits::begin(key)==Key_traits::end(key) )
+ {
+ //* Special case for ""
+ if(root->left==0) return end();
+ else
+ return begin();
+ }
+
+ /// Check whether there keys other that "" at all.
+ if(root->right==0)
+ {
+ //* Lowerbound has to be ""
+ return begin();
+ }
+
+ /// Get pair where one needs to insert the node corresponding to the key
+ /// this we "simulate" the insertion and check the element lesser that it.
+ node_pair = get_insert_pair(key,T());
+ next = node_pair.first.first;
+ cur = node_pair.first.second;
+ common = node_pair.second;
+
+ switch(common.second)
+ {
+ case 2:
+ //*case where key is found.
+ return iterator(next,cur);
+ case 0:
+ //*case where next->value.key > key. this ensures that all the nodes in the
+ //*subtree also greater
+ return --iterator(next,cur);
+ case 1:
+ //*case where the lower bound is in the subtree of next.
+ it=iterator(next,cur);
+ //*we just move to the highest value in the subtree.
+ it.to_right_most();
+ return it;
+ }
+ assert(false);
+}
+
+///finds the upper bound corresponding to the key.
+/**
+ \returns the iterator pointing to the upperbound.
+ if there is no upper bound return end()
+ \param key is the key whose upper bound is to be found
+ */
+template<class T>
+inline iterator upper_bound(const key_type &key,T)
+{
+ typedef std::pair<patricia_node*,patricia_node*> node_pair_type;
+ typedef std::pair<std::size_t, int> common_type;
+
+ std::pair<node_pair_type,common_type> node_pair;
+ common_type common;
+ patricia_node* next,* cur;
+ iterator it;
+
+ if ( root==0 ) return end();
+ if ( Key_traits::begin(key)==Key_traits::end(key) )
+ return begin();
+
+ //* Check whether there keys other that "" at all.
+ if ( root->right==0 )
+ {
+ //*explicitly find the upper bound
+ if(Key_traits::begin(key)!=Key_traits::end(key) )
+ return end();
+ else
+ return begin();
+ }
+
+ node_pair=get_insert_pair(key,T());
+ next=node_pair.first.first;
+ cur =node_pair.first.second;
+ common=node_pair.second;
+ #ifdef PAT_DEBUG
+ std::cout<<"Upper Bound:SECOND: "<<common.second<<std::endl;
+ #endif
+ switch ( common.second )
+ {
+ case 2:
+ //*key aleardy exists
+ return iterator(next,cur);
+ case 1:
+ //*upper bound is not in the subtree of next.its just greater than the subtree
+ return ++iterator(next,cur);
+ case 0:
+ //*it is in the subtree
+ it=iterator(next,cur);
+ #ifdef PAT_DEBUG
+ std::cout<<next->value.first<<"<-"<<cur->value.first<<std::endl;
+ #endif
+ //*go to the least element in the subtree.
+ it.to_left_most();
+ return it;
+ }
+ assert(false);
+}
+
+///used by copy_patricia
+///find the ancestor node in this patricia corresponding to parent node in other patricia
+/**
+ \returns pointer to the ancestor patricia which has corresponding incoming upward link
+ \param this_cur is the node pointer whose upward link is to be found
+ \param other_cur is the node pointer, of the other patricia, which has the upward link.
+ \param par is the node in the other patricia which is the upward link.
+ */
+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;
+}
+
+///copy other patricia on to this patricia.
+/**
+ \return void
+ \param other_root is the pointer to the root of other patricia to be copied.
+ */
+void copy_patricia(const patricia_node *other_root)
+{
+ const patricia_node *const*other_cur,*other_temp,*other_prev;
+
+ //*cur is the pointer to the edge.
+ //*ie, most of the times, cur=&node->left or cur=&node->right
+ patricia_node **cur,*prev;
+
+ if(other_root==0)
+ {
+ this->root=0;
+ return;
+ }
+
+ cur=&root;
+ other_cur=&other_root;
+ other_prev=0;
+ prev=0;
+ while(true)
+ {
+ //assert(prev!=other_root);
+ //*if the current edge in other patricia does not point to
+ //*null and is not the upward edge.
+ if( (*other_cur) && (*other_cur)->par==other_prev)
+ {
+ //*allocate a node in the current of edge of this node.
+ (*cur)=node_allocator.allocate(1);
+
+ //*copy index, data_type and key_type.
+ new(*cur) patricia_node(**other_cur);
+ (*cur)->par = prev;
+
+ //*get in to the next node and and move to the left edge.
+ other_prev=*other_cur;
+ other_cur=&(other_prev->left);
+
+ //*do the same for the this patricia too.
+ prev=*cur;
+ cur=&(prev->left);
+ //std::cout<<"copy:here1"<<std::endl;
+ continue;
+ }
+ std::cout<<"copy:here2"<<std::endl;
+
+ //*when we come here we know that the edge is iether null or point upwards
+ //*copy_patricia_find_par returns null is edge points to null.
+ //*otherwise it returns the corresponding parent
+ (*cur)=copy_patricia_find_par(prev,other_prev,*other_cur);
+
+ //*some random assert to check the pointers dont get interchaged by mistake
+ assert((*cur)!=other_root);
+
+ //*if the edge is the left is the left edge
+ if((*other_cur)==other_prev->left)
+ {
+ //*move towards the right egde
+ other_cur=&(other_prev->right);
+ //assert(other_prev!=prev);
+ cur=&(prev->right);
+ }
+ else
+ {
+ //*if already on the right edge one needs to move upward to traverse further.
+ other_temp=other_prev->right;
+ //*check whether we are on the right edge.
+ while(other_temp==other_prev->right)
+ {
+ other_temp=other_prev;
+ //*if right keep moving up
+ other_prev=other_prev->par;
+
+ //*do the same in other patricia too.
+ prev=prev->par;
+ if(other_prev==0)
+ {
+ //*Finished scanning through the entire patricia.
+ //*now return.
+ return;
+ }
+ }
+
+ //*finally its not right any more. :)
+ //*so adjust both edges towards the right
+ other_cur=&other_prev->right;
+ cur=&prev->right;
+ }
+ }
+}
+
+void pat_clear()
+{
+ patricia_node *cur,*next;
+ if(root==0) return;
+ cur=root;
+ root=0;
+ while(true)
+ {
+ //*try going left if cur->left==0 try going right
+ next=cur->left?cur->left:cur->right;
+
+ if(next==0)
+ {
+ //*if cur->right is also 0 ==> next is 0.
+ //*deallocate the node
+ next=cur->par;
+ deallocate_node(cur);
+ if(next==0) return;
+ //*adjust the parent pointer ->left or pp-> right to 0
+ if(next->left==cur)
+ next->left=0;
+ else
+ next->right=0;
+ cur=next;
+ }
+ else
+ if( next->par!=cur )
+ {
+ //*entered an uplink. so mark the thing as zero.
+ if(cur->left==next)
+ cur->left=0;
+ else
+ cur->right=0;
+ }
+ else
+ {
+ //*move forward to next
+ cur=next;
+ }
+ }
+}
+
+std::size_t pat_size() const
+{
+ patricia_node *cur,*prev;
+ std::size_t ret_size=0;
+
+ prev=cur=root;
+ while(cur)
+ {
+ if(cur->left==prev && cur->left->par==cur)
+ {
+ //*coming up from the left.
+ prev=cur;
+ //*try go right other wise got to the parent
+ cur=(cur->right && cur->right->par==cur)?cur->right:cur->par;
+ }
+ else
+ if(cur->right==prev && cur->right->par==cur)
+ {
+ //*coming up from the right
+ //*goto the parent
+ prev=cur;
+ cur=cur->par;
+ }
+ else
+ {
+ //*going into a new node so increment size
+ ret_size++;
+ #ifdef PAT_DEBUG
+ std::cout<<cur->value.first<<std::endl;
+ #endif
+ prev=cur;
+
+ //*goto left otherwise goto right other go up.
+ cur=(cur->left && cur->left->par==cur)? cur->left
+ : ( (cur->right && cur->right->par==cur)? cur->right
+ : cur->par );
+ }
+ //std::cout<<((prev->left==cur)?"GOING LEFT":(prev->right==cur)?
+ //"GOING RIGHT":"GOING UP")<<std::endl;
+ assert(ret_size!=10);
+ }
+ return ret_size;
+}
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_forward_sequence.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_forward_sequence.hpp 2008-08-30 11:34:34 EDT (Sat, 30 Aug 2008)
@@ -0,0 +1,291 @@
+
+///gets node pair b/w which a key is to inserted also returns a pair of index and bit value of the key at that index
+///to get the pair of node between which a a node is to inserted
+///This uses forward iteration only
+/**
+\returns std::pair< node_pair, common_type>. node_pair, ie pair of node between which the new node is to be inserted
+node_pair::second is the expected child of new node
+node_pair::first is the current parent of expected child.
+\param key is key to be inserted.
+*/
+template<class T>
+inline std::pair< node_pair_type, common_type>
+get_insert_pair (const key_type &key,T) const
+{
+ key_iterator it,end_it;
+ key_element_type temp_element;
+ patricia_node *cur=root,*next=root;
+ std::size_t pos=0;
+ node_pair_type node_pair;
+ common_type common;
+
+ it=Key_traits::begin(key);
+ end_it=Key_traits::end(key);
+
+ //*get the node pair between which the key is supposed to be inserted
+ node_pair=find_node_prev(root,key,T());
+ next=node_pair.first;
+ cur =node_pair.second;
+ common=get_common_bits(key,next->value.first);
+
+ //*key already exists
+ if(common.second==2)
+ return std::make_pair(std::make_pair(next,cur),common);
+
+
+ //*find the correct parent and child in between which this node needs to be added.
+ //*find until the index
+ //*note: parent can be equal to child
+ //*cur=parent, next=child
+ it=Key_traits::begin(key);
+ cur=root;
+ while(it!=end_it)
+ {
+ if ( (cur->index)%(bit_width+1)==0 )
+ {
+ //*simply got the right because. left not has a lesser length than the key.
+ next=cur->right;
+ }
+ else
+ {
+ //*goto left or right appropriately
+ temp_element=Key_traits::get_element(it);
+ next=get_nth_bit(temp_element,(cur->index)%(bit_width+1))?
+ cur->right:cur->left;
+ }
+
+ //*fortunately in this case; this should happen only when it==end_it occures.
+ assert(next);
+ if ( next->index+1 > common.first ) break; //insert at cur using next->value->first
+ if ( next->index <= cur->index ) break;
+
+ //*increment pos and it until the required pos matching index is reached
+ while( pos < (next->index)/(bit_width+1) && it!=end_it )
+ {
+ ++pos;
+ ++it;
+ }
+ cur=next;
+ }
+
+ return std::make_pair(std::make_pair(next,cur),common);
+}
+
+
+///find a node for the key.
+/**
+ \returns the pointer to the "found" node
+ \warning does not check whether the keys are actually equal.
+ Will be needed to be done outside.
+ \param cur is the node from which the search need to be made.
+ \param key is the key to be searched
+ */
+template<class T>
+inline patricia_node* find_node(const patricia_node* cur,const key_type &key,T) const
+{
+ patricia_node *next;
+ std::size_t pos=0;
+ key_iterator it,end_it;
+ key_element_type temp_element;
+
+ it=Key_traits::begin(key);
+ end_it=Key_traits::end(key);
+
+ if(root==0) return 0;
+ if(it==end_it)
+ return root->left;
+ //*adjust pos to the appropriate value
+ while ( pos < (cur->index)/(bit_width+1) && it!=end_it )
+ {
+ ++pos;
+ ++it;
+ }
+
+ while(it!=end_it) {
+ if ( (cur->index)%(bit_width+1)==0 )
+ {
+ //*always go right as length of the key on right is lesser.
+ next=cur->right;
+ }
+ else {
+ //*go left or right appropriately.
+ temp_element=Key_traits::get_element(it);
+ //std::cout<<"getting "<<(cur->index)%(bit_width+1)<<"th bit of "<<temp_element<<std::endl;
+ next=get_nth_bit ( temp_element , (cur->index)%(bit_width+1) ) ?
+ cur->right : cur->left;
+ }
+ if(next==0) return next;
+ //std::cout<<(cur->left==next?"going left":"going right")<<std::endl;
+ //std::cout<<"next: "<<next->value.first<<std::endl;
+
+ //*if we are heading toward the parent stop
+ if ( next->index <= cur->index ) break;
+
+ while ( pos < (next->index)/(bit_width+1) && it!=end_it ) {
+ ++pos;
+ ++it;
+ }
+ cur=next;
+ }
+
+ if ( it == end_it && pos==(cur->index)/(bit_width+1) ) {
+ //*just make the required connection
+ next=cur->left;
+ }
+ return next;
+}
+
+
+
+///find a node for the key and prev node also
+/**
+ \returns the pointer to the "found" node and node with upward link to found node
+ as a pair.
+ \warning does not check whether the keys are actually equal.
+ Will be needed to be done outside.
+ \param cur is the node from which the search need to be made.
+ \param key is the key to be searche
+ */
+template<class T>
+inline std::pair<patricia_node*,patricia_node*>
+find_node_prev(patricia_node *cur, const key_type &key, T ,std::size_t=std::size_t()) const
+{
+ patricia_node *next;
+ std::size_t pos=0;
+ key_iterator it,end_it;
+ key_element_type temp_element;
+
+ it=Key_traits::begin(key);
+ end_it=Key_traits::end(key);
+
+ if(cur==0) return std::make_pair(cur,cur);
+ if(it==end_it)
+ {
+ //*special cases for ""
+ if ( cur==root || cur==root->left )
+ return std::make_pair(root->left,root);
+ else
+ return std::make_pair(static_cast<patricia_node*>(0),static_cast<patricia_node*>(0));
+ }
+
+ //*adjust pos to match with cur->index
+ while ( pos < (cur->index)/(bit_width+1) && it!=end_it ) {
+ ++pos;
+ ++it;
+ }
+
+ //*ref find :)
+ while(it!=end_it) {
+ if ( (cur->index)%(bit_width+1)==0 )
+ {
+ next=cur->right;
+ }
+ else {
+ temp_element=Key_traits::get_element(it);
+ std::cout<<temp_element<<std::endl;
+ next=get_nth_bit ( temp_element , (cur->index)%(bit_width+1) ) ?
+ cur->right : cur->left;
+ }
+ if(next==0) return std::make_pair(next,next);
+
+ //std::cout<<next->value.first<<"<--"<<cur->value.first<<std::endl;
+ if ( next->index <= cur->index ) { break;}
+
+ while ( pos < (next->index)/(bit_width+1) && it!=end_it ) {
+ ++pos;
+ ++it;
+ }
+ cur=next;
+ }
+
+ if ( it == end_it && pos==(cur->index)/(bit_width+1) ) {
+ next=cur->left;
+ }
+ return std::make_pair(next,cur);
+}
+
+
+
+
+///finds the iterator range corresponding to the prefix (overloaded for random access)
+/**
+ \returns iterator range
+ \param key is the key whose prefix range is to be found
+ */
+template<class T>
+std::pair<iterator,iterator> prefix_range(const key_type &key,T)
+{
+ key_iterator it,end_it;
+ key_element_type temp_element;
+ patricia_node *cur=root,*next=root;
+ std::size_t pos=0;
+ std::pair<patricia_node*,patricia_node*> node_pair;
+ std::pair<std::size_t,int> common;
+ bool no_check=false;
+
+ it=Key_traits::begin(key);
+ end_it=Key_traits::end(key);
+
+ //*if its "" then entire patricia is needed
+ if(root==0) return std::make_pair(end(),end());
+ if(Key_traits::begin(key)==Key_traits::end(key))
+ return std::make_pair(begin(),end());
+
+ //*if we did not find a key with entire string as prefix. then then
+ //*then we will need to ditch the procedure here.
+ if(root->right==0) return std::make_pair(end(),end());
+
+ node_pair=find_node_prev(root,key,T());
+
+ next=node_pair.first;
+ assert(find_node_prev(root,key,iterator_cat()).first==next);
+ cur =node_pair.second;
+ assert(find_node_prev(root,key,iterator_cat()).second==cur);
+ common=get_common_bits(key,next->value.first);
+
+ if(common.second==2)
+ {
+ common.second=0;
+ //*no_check will indicate whether or not to check for next->index+1 > common.first
+ no_check=true;
+ }
+ if ( common.second!=0 || common.first % ( bit_width + 1 ) != 0)
+ return std::make_pair(end(),end());
+
+ //*we start searching for the until we get a key with index>common.first
+ it=Key_traits::begin(key);
+ cur=root;
+ while(it!=end_it)
+ {
+ if ( (cur->index)%(bit_width+1)==0 )
+ next=cur->right;
+ else
+ {
+ temp_element=Key_traits::get_element(it);
+ next=get_nth_bit(temp_element,(cur->index)%(bit_width+1))?
+ cur->right:cur->left;
+ }
+
+ //*fortunately in this case; this should happen only when it==end_it occures.
+ assert(next);
+ if ( no_check || next->index+1 > common.first ) break; //insert at cur using next->value->first
+ if ( next->index <= cur->index ) break;
+
+ while( pos < (next->index)/(bit_width+1) && it!=end_it )
+ {
+ ++pos;
+ ++it;
+ }
+ cur=next;
+ }
+ iterator right=iterator(next,cur);
+ iterator left =iterator(next,cur);
+
+ //*find the smallest in the subtree of next
+ left.to_left_most();
+
+ //*find one greater than greatest in the subtree of next.
+ ++right;
+ return std::make_pair(left,right);
+}
+
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_random_sequence.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_random_sequence.hpp 2008-08-30 11:34:34 EDT (Sat, 30 Aug 2008)
@@ -0,0 +1,222 @@
+
+
+///gets node pair b/w which a key is to inserted also returns a pair of index and bit value of the key at that index
+///to get the pair of node between which a a node is to inserted
+///this is for random access iterator.
+/**
+ \returns std::pair< node_pair, common_type>. node_pair, ie pair of node between which the new node is to be inserted
+ node_pair::second is the expected child of new node
+ node_pair::first is the current parent of expected child.
+ \param key is key to be inserted.
+ */
+
+inline std::pair< node_pair_type, common_type>
+ get_insert_pair(const key_type &key,rand_tag) const
+{
+ patricia_node *cur=root,*next=root;
+ std::size_t pos=0;
+ common_type common;
+ node_pair_type node_pair;
+ const std::size_t key_size=Key_traits::size(key);
+ key_iterator it=Key_traits::begin(key);
+
+ //*get the insert pair for the key.
+ node_pair=find_node_prev(root,key,iterator_cat(),key_size);
+
+ next=node_pair.first;
+ common=get_common_bits(key,next->value.first );
+
+ //*if everything is common return the data type
+ if ( common.second==2 )
+ return std::make_pair(node_pair, common);
+
+ //*else search for the key again
+ next=cur=root;
+ while (next->index < common.first) {
+ cur=next;
+ pos= cur->index / (bit_width + 1);
+ //if ( pos >= key_size ) break;
+ next=get_nth_bit ( Key_traits::get_element(it + pos), cur->index % (bit_width + 1) )?
+ cur->right: cur->left;
+ //*is its an upward link break.
+ if(cur->index >= next->index) break;
+ }
+
+ //*return the node pair along with common pair.
+ return std::make_pair(std::make_pair(next,cur), common);
+}
+
+
+///find a node for the key (over loaded for random access)
+/**
+ \returns the pointer to the "found" node
+ \warning does not check whether the keys are actually equal.
+ Will be needed to be done outside.
+ \param cur is the node from which the search need to be made.
+ \param key is the key to be searched.
+ \param key_size if the size of the key.
+ */
+inline patricia_node* find_node(const patricia_node *cur, const key_type &key,rand_tag,std::size_t key_size=0) const
+{
+ patricia_node *next=0;
+ key_iterator it, end_it;
+ it=Key_traits::begin(key);
+ std::size_t pos=0;
+ if(key_size==0)
+ key_size=Key_traits::size(key);
+
+ if ( root==0 ) return 0;
+
+ while (true )
+ {
+ pos= cur->index / (bit_width + 1);
+ //*make sure the key length is always lesser
+ if ( pos >= key_size ) break;
+ std::cout<<"getting "<<cur->index<<"th bit of "<<key<<std::endl;
+ next=get_nth_bit ( Key_traits::get_element(it + pos), cur->index % (bit_width + 1) )?
+ cur->right: cur->left;
+ if(next==0) return 0;
+ //*if we are heading toward the parent stop
+ if(cur->index >= next->index) break;
+ cur=next;
+ }
+
+ if (pos == key_size )
+ {
+ //*make the required correction if the add the last bit 0 to the node.
+ next=cur->left;
+ }
+
+ return next;
+}
+
+
+///finds the iterator range corresponding to the prefix (overloaded for random access)
+/**
+ \returns iterator range
+ \param key is the key whose prefix range is to be found
+ */
+std::pair<iterator,iterator> prefix_range(const key_type &key,rand_tag)
+{
+ std::size_t pos=0;
+ std::pair<patricia_node*,patricia_node*> node_pair;
+ std::pair<std::size_t,int> common;
+ const std::size_t key_size=Key_traits::size(key);
+ patricia_node *cur=root,*next=root;
+ key_iterator it=Key_traits::begin(key);
+
+ if(root==0) return std::make_pair(end(),end());
+
+ //*if its "" then entire patricia is needed
+ if(Key_traits::begin(key)==Key_traits::end(key))
+ return std::make_pair(begin(),end());
+
+
+ //*now key!="" and there is no other key in the patricia
+ //*so only option is end(),end()
+ if(root->right==0) return std::make_pair(end(),end());
+
+ //*find node in between which the node was supposed to be inserted
+ node_pair=find_node_prev(root,key,iterator_cat(),key_size);
+
+ next=node_pair.first;
+ common=get_common_bits(key,next->value.first );
+ if ( common.second==2 ) {
+ common.second=0;
+ //*if key is already found we will need to re adjust this thing
+ //*the bit index to be searched for
+ common.first=key_size*( bit_width + 1 );
+ #ifdef PAT_DEBUG
+ std::cout<<"FOUND"<<std::endl;
+ #endif
+ }
+
+ //*if we did not find a key with entire string as prefix. then then
+ //*then we will need to ditch the procedure here.
+ if ( common.second!=0 || common.first % ( bit_width + 1 ) != 0)
+ return std::make_pair(end(),end());
+ #ifdef PAT_DEBUG
+ std::cout<<"HERE with KEY="<<key<<std::endl;
+ #endif
+
+ //*we start searching for the until we get a key with index>common.first
+ next=cur=root;
+ while (next->index < common.first) {
+ cur=next;
+ pos= cur->index / (bit_width + 1);
+ //if ( pos >= key_size ) break;
+ next=get_nth_bit ( Key_traits::get_element(it + pos), cur->index % (bit_width + 1) )?
+ cur->right: cur->left;
+ if(cur->index >= next->index) break;
+ }
+
+
+ iterator right=iterator(next,cur);
+ iterator left =iterator(next,cur);
+
+ //*find the smallest in the subtree of next
+ left.to_left_most();
+
+ //*find one greater than greatest in the subtree of next.
+ ++right;
+ return std::make_pair(left,right);
+}
+
+
+
+///find a node for the key and prev node also (over loaded for random access)
+/**
+ \returns the pointer to the "found" node and node with upward link to found node
+ as a pair.
+ \warning does not check whether the keys are actually equal.
+ Will be needed to be done outside.
+ \param cur is the node from which the search need to be made.
+ \param key is the key to be searched
+ \param key_size is the size of key
+ */
+inline node_pair_type
+find_node_prev(patricia_node *cur, const key_type &key, rand_tag,std::size_t key_size=0) const
+{
+ patricia_node *next=0;
+ key_iterator it, end_it;
+ it=Key_traits::begin(key);
+ std::size_t pos=0;
+
+ if(key_size==0)
+ key_size=Key_traits::size(key);
+
+ if(cur==0) return std::make_pair<patricia_node*,patricia_node*>(0,0);
+
+
+ if(it==end_it)
+ {
+ //*special cases for ""
+ if ( cur==root || cur==root->left )
+ return std::make_pair(root->left,root);
+ else
+ return std::make_pair(static_cast<patricia_node*>(0),static_cast<patricia_node*>(0));
+ }
+
+
+ //*refer find()
+ while (true ) {
+ pos= cur->index / (bit_width + 1);
+ if ( pos >= key_size ) break;
+ //std::cout<<Key_traits::get_element(it + pos)<<std::endl;
+ next=get_nth_bit ( Key_traits::get_element(it + pos), cur->index % (bit_width + 1) )?
+ cur->right: cur->left;
+ //std::cout<<"In find: cur="<<cur->value.first
+ //<<" going to next \""<<next->value.first<<"\""<<std::endl;
+ if(next==0) return std::make_pair<patricia_node*,patricia_node*>(0,0);
+ if(cur->index >= next->index) break;
+ cur=next;
+ }
+
+ if(pos == key_size ) {
+ next=cur->left;
+ }
+
+ return std::make_pair<patricia_node*,patricia_node*>(next,cur);
+}
+
+