From: chintanraoh_at_[hidden]
Date: 2008-06-12 13:05:33
Author: chintanraoh
Date: 2008-06-12 13:05:32 EDT (Thu, 12 Jun 2008)
New Revision: 46357
URL: http://svn.boost.org/trac/boost/changeset/46357
Log:
debugged insert function
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp | 208 ++++++++++++++++++++++++++++-----------
1 files changed, 149 insertions(+), 59 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-12 13:05:32 EDT (Thu, 12 Jun 2008)
@@ -3,25 +3,33 @@
#include<algorithm>
#include<memory>
+#include<iostream>
#include<assert.h>
namespace boost{
namespace dsearch{
-template<class Key,class Mapped,class Key_traits,class Alloc=allocator<char>>
+template<class Key,class Mapped,class Key_traits,class Alloc=std::allocator<char> >
class patricia{
private:
typedef typename Key_traits::const_iterator key_iterator;
typedef typename Key_traits::element_type key_element_type;
enum{
- bit_width=sizeof(Key_traits::element_type)*8
+ bit_width=sizeof(typename Key_traits::element_type)*8
};
- template<class Key,class Mapped>
+
+ public:
+ typedef Key key_type;
+ typedef Mapped data_type;
+ typedef std::pair<key_type,data_type> value_type;
+
+ private:
+ //template<class Key,class Mapped>
class patricia_node {
- typedef typename patricia_node<Key,Mapped> self;
+ typedef patricia_node self;
public:
- typedef Key key_type;
- typedef Mapped data_type;
+ //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
@@ -29,104 +37,132 @@
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), left(0), right(0), index(0)
{
}
};
typedef typename Alloc::template rebind<patricia_node>::other node_allocator_type;
node_allocator_type node_allocator;
- public:
- typedef Key key_type;
- typedef Mapped data_type;
- typedef std::pair<key_type,data_type> value_type;
-
-
patricia_node *root;
+ public:
+
patricia(): root(0)
{
}
void insert(const value_type &v)
{
+ insert_new_node(v.first)=v.second;
+ }
+
+ bool find(const key_type &k)
+ {
+ std::pair<std::size_t,int> common;
+ patricia_node *node;
+ node=find_node(k);
+ if(node==0) return 0;
+ common=get_common_bits(node->value.first,k);
+ return (common.second==2);
+ return true;
}
private:
inline data_type &insert_new_node(const key_type&key)
{
key_iterator it,end_it;
- pat_node *cur=root,*next=root,*temp_node;
+ patricia_node *cur=root,*next=root,*temp_node,*old_root=0;
key_element_type temp_element;
- int pos=0;
- std::pair<std::size_t,bool> common;
+ std::size_t pos=0;
+ 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->right==root)
+ {
+ if(it==end_it) return root->value.second;
+ old_root=root;
+ root=0;
+ }
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;
+ root->index=0; //(root->index)%(bit_width+1)==0
+ root->value.first=key;
+
if(it!=end_it)
+ {
root->left=root;
+ root->right=old_root;
+ }
else
root->right=root; //add to right if the first node added is "";
- return root->value->second;
+
+ return root->value.second;
}
- //do some jugglery to ensure that inserting "" first wont cause any problems
- //perhaps move root to right position after doing the job.
- //that will take of the assert(next) in find
-
- while(it!=end_it)
+ if(it==end_it) //"" inserted
{
- if((cur->index)%(bit_width+1)==0)
- next=cur->left;
+ if(root->right!=0)
+ next=root->right;
else
{
- temp_element=Key_traits::get_element(it);
- next=get_nth_bit(temp_element,(cur->index)%(bitwidth+1))?
- cur->right:cur->left;
+ 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;
}
-
- //fortunately in this case; this should happen only when it==end_it occures.
- assert(next);
-
- if ( next->index <= cur->index ) break;
-
- if( pos < (next->index)/(bit_width+1) )
- {
- ++pos;
- ++it;
- }
- cur=next;
}
+
+ next=find_node(key);
+
+ //find the largerst prefix matching the key and the found key
+ //std::cout<<"After find"<<std::endl;
common=get_common_bits(key,next->value.first);
- if(common.second==2) //key already exists
+
+ //key already exists
+ if(common.second==2)
+ {
+ //std::cout<<"The key \""<<key<<"\" already exists"<<std::endl;
return next->value.second;
+ }
+
+ //assert(common.first);wrong assert
- assert(common.first);
+ //find the parent and child in between which this thing needs to be added.
+ //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)
+ if ( (cur->index)%(bit_width+1)==0 )
next=cur->left;
else
{
temp_element=Key_traits::get_element(it);
- next=get_nth_bit(temp_element,(cur->index)%(bitwidth+1))?
+ 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 > common.first ) break; //insert at cur using next->value->first
+ if ( next->index+1 > common.first ) break; //insert at cur using next->value->first
if ( next->index <= cur->index ) break;
- if( pos < (next->index)/(bit_width+1) )
+ while( pos < (next->index)/(bit_width+1) && it!=end_it )
{
++pos;
++it;
@@ -136,18 +172,22 @@
temp_node=node_allocator.allocate(1);
new (temp_node) patricia_node();
- temp->value.first=key;
+ temp_node->value.first=key;
//recalculate common;
- common=get_common_bits ( temp->value.first, next->key );
-
+ //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;
else
assert(false);
- temp_node->index=common.first+1;
+ 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
@@ -166,15 +206,15 @@
inline std::size_t get_nth_bit(const key_element_type &element,const int &n) const
{
- return element && ( 1<<(n-1) );
+ return n==0? 0 : ( 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 &k2) const
+ 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::pair<std::size_t,bool> ret_type;
+ //std::cout<<"comparing "<<k1<<" and "<<k2<<std::endl;
int uncommon_bit;
key_element_type t1,t2;
bool unequal=false;
@@ -185,7 +225,7 @@
k1_end=k1.end();
k2_end=k2.end();
- if(k1_it!=k1_end && k2_it!=k2_end )
+ while(k1_it!=k1_end && k2_it!=k2_end )
{
if( Key_traits::get_element(k1_it) != Key_traits::get_element(k2_it) )
{
@@ -199,8 +239,8 @@
if(unequal)
{
- t1=Key_traits::get_element(k1_it)
- t2=Key_traits::get_element(k2_it)
+ t1=Key_traits::get_element(k1_it);
+ t2=Key_traits::get_element(k2_it);
while(t1%2==t2%2)
{
t1/=2;
@@ -208,11 +248,61 @@
++pos;
}
uncommon_bit=t1%2;
+ ++pos;
}
else
- uncommon_bit=(k1==k1_end)?((k2==k2_end)?2:1):0;
+ uncommon_bit=(k1_it==k1_end)?((k2_it==k2_end)?2:1):0;
+
+ //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)
+ {
+ 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 0;
+ if(it==end_it)
+ return root->right;
+
+ while(it!=end_it)
+ {
+ if ( (cur->index)%(bit_width+1)==0 )
+ next=cur->left;
+ 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) ) ?
+ 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;
- return make_pair(pos,uncommon_bit);
+ 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) )
+ {
+// cur=next;
+ next=cur->right;
+ }
+ return next;
}
};