From: chintanraoh_at_[hidden]
Date: 2008-06-16 14:12:46
Author: chintanraoh
Date: 2008-06-16 14:12:45 EDT (Mon, 16 Jun 2008)
New Revision: 46433
URL: http://svn.boost.org/trac/boost/changeset/46433
Log:
fixed bugs; erase for forward access keys; begin() and end();
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp | 550 ++++++++++++++++++++++++++++++++++-----
1 files changed, 472 insertions(+), 78 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-16 14:12:45 EDT (Mon, 16 Jun 2008)
@@ -1,3 +1,5 @@
+//CONTAINS REWRITE OF PATRICIA.HPP
+
#ifndef BOOST_DSEARCH_PATRICIA_HPP
#define BOOST_DSEARCH_PATRICIA_HPP
@@ -5,6 +7,13 @@
#include<memory>
#include<iostream>
#include<assert.h>
+#include<vector>
+#include<iterator>
+#include<boost/iterator/iterator_traits.hpp>
+#include<boost/dsearch/patricia_iterator.hpp>
+
+//replace all key assignement operations with key_copy
+//replace all key.size() with key_traits::size();
namespace boost{
namespace dsearch{
@@ -15,80 +24,135 @@
typedef typename Key_traits::element_type key_element_type;
enum{
- bit_width=sizeof(typename Key_traits::element_type)*8
+ bit_width=8*sizeof(typename Key_traits::element_type)
};
public:
typedef Key key_type;
typedef Mapped data_type;
- typedef std::pair<key_type,data_type> value_type;
+ typedef std::pair<const key_type,data_type> value_type;
private:
- //template<class Key,class Mapped>
+ typedef typename std::iterator_traits<typename Key_traits::const_iterator>::iterator_category iterator_cat;
+ typedef typename std::random_access_iterator_tag rand_tag;
+
+
class patricia_node {
typedef patricia_node self;
public:
- //typedef Key key_type;
- //typedef Mapped data_type;
- typedef std::pair<key_type,data_type> value_type;
self *par; //avoids the usage of a stack to traverse
value_type value;
std::size_t index;
self *left,*right;//left for zero.. right for one.
- patricia_node(): par(0), left(0), right(0), index(0)
+ patricia_node(): par(0), index(0), left(0), right(0)
{
}
+ 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;*/
+ }
};
typedef typename Alloc::template rebind<patricia_node>::other node_allocator_type;
node_allocator_type node_allocator;
-
patricia_node *root;
public:
+ typedef patricia_iterator<value_type, patricia_node, Alloc> iterator;
+ typedef patricia_iterator<const value_type, const patricia_node, Alloc> const_iterator;
patricia(): root(0)
{
}
-
+
+ data_type &operator [](const key_type &k)
+ {
+ #ifndef FORWARD
+ return insert_new_node(k,iterator_cat());
+ #else
+ return insert_new_node(k,0);
+ #endif
+ }
+
void insert(const value_type &v)
{
- insert_new_node(v.first)=v.second;
+ this->operator [](v.first)=v.second;
}
-
+
+ iterator begin()
+ {
+ return iterator ( root, true );
+ }
+
+ iterator end()
+ {
+ return iterator ( root, false );
+ }
+
bool find(const key_type &k)
{
std::pair<std::size_t,int> common;
patricia_node *node;
- node=find_node(k);
+ #ifndef FORWARD
+ node=find_node(root,k,iterator_cat());
+ #else
+ node=find_node(root,k,0);
+ #endif
if(node==0) return 0;
common=get_common_bits(node->value.first,k);
return (common.second==2);
return true;
}
+ void erase(const key_type &k)
+ {
+ #ifndef FORWARD
+ erase(k,iterator_cat());
+ #else
+ erase(k,0);
+ #endif
+ }
+
+ bool empty() const
+ {
+ //if(root)
+ // std::cout<<"NOT EMPTY "<<root->value.first<<std::endl;
+ return root==0;
+ }
+
private:
- inline data_type &insert_new_node(const key_type&key)
+ //function for Random Access Iterator
+ inline data_type &insert_new_node(const key_type &key,rand_tag)
{
key_iterator it,end_it;
patricia_node *cur=root,*next=root,*temp_node,*old_root=0;
- key_element_type temp_element;
std::size_t pos=0;
+
+ //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);
+
+ const std::size_t key_size=Key_traits::size(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->right==root)
+ if(root!=0 && root->left==root)
{
- if(it==end_it) return root->value.second;
+ if(it==end_it) return root->value.second; //if one adds "" twice
old_root=root;
root=0;
}
@@ -96,37 +160,132 @@
if(root==0)
{
root=node_allocator.allocate(1);
- new(root) patricia_node();
- root->index=0; //(root->index)%(bit_width+1)==0
- root->value.first=key;
-
if(it!=end_it)
{
- root->left=root;
- root->right=old_root;
+ new(root) patricia_node( key, 0, old_root, root, 0 );
+ if(old_root)
+ {
+ std::cout<<"assigning OLD ROOT"<<std::endl;
+ old_root->par=root;
+ }
}
else
- root->right=root; //add to right if the first node added is "";
+ new(root) patricia_node( key, 0, root, 0, 0 );
+
+ return root->value.second;
+ }
+
+ if(it==end_it) //"" inserted
+ {
+ if(root->left!=0)
+ next=root->left;
+ else
+ {
+ root->left = node_allocator.allocate(1);
+ new(root->left) patricia_node(key,0,root->left,0,root);
+ return root->left->value.second;
+ }
+ }
+
+ next=find_node(root,key,iterator_cat(),key_size);
+
+ common=get_common_bits(key,next->value.first );
+ if ( common.second==2 )
+ {
+ std::cout<<"The key \""<<key<<"\" already exists"<<std::endl;
+ return next->value.second;
+ }
+
+ 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;
+ }
+ temp_node=node_allocator.allocate(1);
+ if(cur->left==next) cur->left=temp_node;
+ else
+ if(cur->right==next)
+ cur->right=temp_node;
+ else
+ assert(false);
+
+ assert(common.second!=2);
+
+ 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
+ new (temp_node) patricia_node(key,common.first,temp_node,next,cur);
+
+ assert(root->par==0);
+ if(cur->index < next->index) next->par=temp_node;
+
+ assert(root->par==0);
+ return temp_node->value.second;
+ }
+
+ template<class T>
+ inline data_type &insert_new_node(const key_type&key,T)
+ {
+ key_iterator it,end_it;
+ key_element_type temp_element;
+ patricia_node *cur=root,*next=root,*temp_node,*old_root=0;
+ std::size_t pos=0;
+
+ //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)
+ {
+ std::cout<<"assigning OLD ROOT"<<std::endl;
+ 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->right!=0)
- next=root->right;
+ if(root->left!=0)
+ next=root->left;
else
{
- root->right = node_allocator.allocate(1);
- new(root->right) patricia_node();
- root->right->par=root;
- root->right->index=0;
- root->right->right=root->right;
- root->right->value.first=key;
- return root->right->value.second;
+ root->left = node_allocator.allocate(1);
+ new(root->left) patricia_node(key,0,root->left,0,root);
+ return root->left->value.second;
}
}
- next=find_node(key);
+ next=find_node(root,key,T());
//find the largerst prefix matching the key and the found key
//std::cout<<"After find"<<std::endl;
@@ -135,7 +294,7 @@
//key already exists
if(common.second==2)
{
- //std::cout<<"The key \""<<key<<"\" already exists"<<std::endl;
+ std::cout<<"The key \""<<key<<"\" already exists"<<std::endl;
return next->value.second;
}
@@ -149,7 +308,7 @@
while(it!=end_it)
{
if ( (cur->index)%(bit_width+1)==0 )
- next=cur->left;
+ next=cur->right;
else
{
temp_element=Key_traits::get_element(it);
@@ -171,44 +330,33 @@
}
temp_node=node_allocator.allocate(1);
- new (temp_node) patricia_node();
- temp_node->value.first=key;
- //recalculate common;
- //std::cout<<"After second find"<<std::endl;
- common=get_common_bits ( temp_node->value.first, next->value.first );
-
- //find where next was and insert the new node there
if(cur->left==next) cur->left=temp_node;
else
- if(cur->right==next) cur->right=temp_node;
+ if(cur->right==next)
+ cur->right=temp_node;
else
assert(false);
assert(common.second!=2);
- //std::cout<<"common: "<<common.first<<" uncommon "<<common.second<<std::endl;
- temp_node->index=common.first;
- temp_node->par=cur;
if(common.second) //temp_node should point to inself at 1 ie right
- {
- temp_node->right=temp_node;
- temp_node->left=next;
- }
+ new (temp_node) patricia_node(key,common.first,next,temp_node,cur);
else
- {
- temp_node->right=next;
- temp_node->left=temp_node;
- }
+ new (temp_node) patricia_node(key,common.first,temp_node,next,cur);
+ assert(root->par==0);
+ if(cur->index < next->index) next->par=temp_node;
+
+ assert(root->par==0);
return temp_node->value.second;
}
inline std::size_t get_nth_bit(const key_element_type &element,const int &n) const
{
- return n==0? 0 : ( element & (1<<(n-1)) );
+ return n==0? 1 : ( element & (1<<(n-1)) );
}
-
+
//returns inclusive of end bit after each pos and the not(un) common bit in k1;
//returns not common bit as two if both keys are equal.
inline std::pair<std::size_t,int> get_common_bits(const key_type &k1,const key_type &k2) const
@@ -241,27 +389,26 @@
{
t1=Key_traits::get_element(k1_it);
t2=Key_traits::get_element(k2_it);
- while(t1%2==t2%2)
+ while((t1 & 0x1)==( t2 & 0x1))
{
- t1/=2;
- t2/=2;
+ t1>>=1;
+ t2>>=1;
++pos;
}
uncommon_bit=t1%2;
++pos;
}
else
- uncommon_bit=(k1_it==k1_end)?((k2_it==k2_end)?2:1):0;
+ uncommon_bit=(k1_it==k1_end)?((k2_it==k2_end)?2:0):1;
- //we dont know anything yet about the last bit. ie len+1 th bit
- //if(pos%(bit_width+1)!=0) pos++;
return std::make_pair<std::size_t,int>(pos,uncommon_bit);
}
- patricia_node* find_node(const key_type &key)
+ template<class T>
+ patricia_node* find_node(const patricia_node* cur,const key_type &key,T)
{
- patricia_node *cur=root,*next;
+ patricia_node *next;
std::size_t pos=0;
key_iterator it,end_it;
key_element_type temp_element;
@@ -271,14 +418,12 @@
if(root==0) return 0;
if(it==end_it)
- return root->right;
+ return root->left;
- while(it!=end_it)
- {
+ while(it!=end_it) {
if ( (cur->index)%(bit_width+1)==0 )
- next=cur->left;
- else
- {
+ next=cur->right;
+ else {
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) ) ?
@@ -290,25 +435,274 @@
if ( next->index <= cur->index ) break;
- while ( pos < (next->index)/(bit_width+1) && it!=end_it )
- {
+ while ( pos < (next->index)/(bit_width+1) && it!=end_it ) {
++pos;
++it;
}
cur=next;
}
- if ( it == end_it && pos==(cur->index)/(bit_width+1) )
- {
-// cur=next;
- next=cur->right;
+
+ if ( it == end_it && pos==(cur->index)/(bit_width+1) ) {
+ next=cur->left;
}
return next;
}
-};
+ patricia_node* find_node(const patricia_node *cur, const key_type &key,rand_tag,std::size_t key_size=0)
+ {
+ 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.size();
+
+ if(root==0) return 0;
+
+ while ( pos < (cur->index)/(bit_width+1) && it!=end_it ) {
+ ++pos;
+ ++it;
+ }
+ while (true ) {
+ 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;
+ //std::cout<<"In find: cur="<<cur->value.first
+ //<<" going to next \""<<next->value.first<<"\""<<std::endl;
+ if(next==0) return 0;
+ if(cur->index >= next->index) break;
+ cur=next;
+ }
+
+ if(pos == key_size ) {
+ next=cur->left;
+ }
+
+ return next;
+ }
+
+ std::pair<patricia_node*,patricia_node*>
+ find_node_prev(patricia_node *root, const key_type &key, rand_tag,std::size_t key_size=0)
+ {
+ patricia_node *cur,*next=0;
+ key_iterator it, end_it;
+ it=Key_traits::begin(key);
+ std::size_t pos=0;
+ if(key_size==0)
+ key_size=key.size();
+
+ if(root==0) return std::make_pair<patricia_node*,patricia_node*>(0,0);
+
+ cur=root;
+
+ 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;
+ }
+ if(key_size==0) cur=next;
+ return std::make_pair<patricia_node*,patricia_node*>(next,cur);
+ }
+
+ template<class T>
+ std::pair<patricia_node*,patricia_node*>
+ find_node_prev(patricia_node *root, const key_type &key, T ,std::size_t)
+ {
+ patricia_node *cur=root,*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 std::make_pair(root,root);
+ if(it==end_it)
+ return std::make_pair(root->left,root->left);
+ while ( pos < (cur->index)/(bit_width+1) && it!=end_it ) {
+ ++pos;
+ ++it;
+ }
+
+ 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);
+ }
+
+ template<class T>
+ void erase(const key_type& key,T)
+ {
+ if(root==0) return;
+ patricia_node *cur,*next=0,*found;
+ key_iterator it, end_it;
+ it=Key_traits::begin(key);
+
+ std::size_t key_size=key.size();
+ std::pair<patricia_node*,patricia_node*> temp_pair,check_pair;
+
+ if(root==0) return;
+ assert(root->par==0);
+ std::cout<< ((root->left!=0)?" \"\" exists":"\"\" does not exists")<<std::endl;
+
+ assert( (root->left!=0 && root->left!=root)? root->left->par==root: 1 );
+
+ std::cout<<(root->par==0)<<" root key:"<<root->value.first<<std::endl;
+ cur=root;
+ next=root;
+
+
+ temp_pair=find_node_prev(root,key,T(),key_size);
+ found=next=temp_pair.first;
+ cur=temp_pair.second;
+ if(found==0) return;
+ check_pair=find_node_prev(root,key,rand_tag(),key_size);
+ std::cout<<"KEY=="<<key<<";Next key=="<<temp_pair.first->value.first
+ <<";Cur key=="<<temp_pair.second->value.first<<std::endl;
+
+ assert(check_pair==temp_pair);
+
+ std::cout<<"in erase: found "<<found->value.first<<" and prev "<<cur->value.first<<std::endl;
+
+ if ( found-> par == 0 ) { //root node
+ std::cout<<"par"<<std::endl;
+ assert(root==found);
+
+ if( (found->right==0 || found->left==0) && found==cur){ //only root or only ""
+ deallocate_node(found);
+ root=0;
+ return;
+ }
+ std::cout<<"wrong place"<<std::endl;
+ if(cur==found){ //also takes care of "" at 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 )
+ cur=found;
+
+ std::cout<<"here"<<std::endl;
+ if ( cur == found ) { //deleting the leaf node. //this case for root node is handled before
+ if ( found->par->right == found )
+ found->par->right = (found->right==found)?found->left:found->right;
+ else
+ if ( found->par->left == found )
+ found->par->left = (found->right==found)?found->left:found->right;
+ else
+ assert(false);
+ std::cout<<"cur==found with key="<<key<<std::endl;
+ if ( found->right==0 || found->left==0 )
+ {
+ assert(found->par==root);
+ std::cout<<"\"\" node to be erased"<<std::endl;
+ }
+ deallocate_node(found);
+ return;
+ }
+
+ temp_pair=find_node_prev(cur,cur->value.first,T(),cur->value.first.size());
+ /*check_pair=find_node_prev(cur,cur->value.first,rand_tag(),cur->value.first.size());
+
+ std::cout<<"KEY=="<<cur->value.first<<";Next key=="<<temp_pair.first->value.first
+ <<";Cur key=="<<temp_pair.second->value.first<<std::endl;
+ std::cout<<"KEY=="<<cur->value.first<<";Next key=="<<check_pair.first->value.first
+ <<";Cur key=="<<check_pair.second->value.first<<std::endl;
+ assert(check_pair==temp_pair);*/
+
+ next=temp_pair.first;
+ cur=temp_pair.second;
+ assert(next->par);
+
+ if(next->par->right==next) {
+ next->par->right=(next->right==found)?next->left:next->right;
+ if( next->right!=next && next->left!=next && next->par->right ) next->par->right->par=next->par;
+ }
+ else {
+ std::cout<<"far away here"<<std::endl;
+ next->par->left=(next->right==found)?next->left:next->right;
+ if( next->right!=next && next->left!=next && next->par->left) next->par->left->par=next->par;
+ }
+
+ if(found->par==0)
+ root=next;
+ copy_node_ptr(next,found);
+ deallocate_node(found);
+ }
+
+ void inline deallocate_node(patricia_node *&found)
+ {
+ node_allocator.destroy(found);
+ node_allocator.deallocate(found,1);
+ }
+
+ //used by erase(key);
+ void inline copy_node_ptr(patricia_node* to, patricia_node* found)
+ {
+ if(found->par!=0) {
+ 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;
+ 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;
+ }
+
+};
}//namespace dsearch
}//namespace boost
#endif //BOOST_DSEARCH_PATRICIA_HPP
+