From: chintanraoh_at_[hidden]
Date: 2008-07-03 14:02:35
Author: chintanraoh
Date: 2008-07-03 14:02:34 EDT (Thu, 03 Jul 2008)
New Revision: 47048
URL: http://svn.boost.org/trac/boost/changeset/47048
Log:
documented patricia class
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp | 319 ++++++++++++++++++++++-----------------
1 files changed, 183 insertions(+), 136 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-07-03 14:02:34 EDT (Thu, 03 Jul 2008)
@@ -10,8 +10,12 @@
#include<boost/iterator/iterator_traits.hpp>
#include<boost/dsearch/patricia_iterator.hpp>
+
+//note //* has been used where there is an inline comment documenting the code.
+
+
#if 0
-/// when FORWARD is defined, the class uses sequetial access for the key.
+//* when FORWARD is defined, the class uses sequential access for the key.
#define FORWARD
#endif
@@ -24,8 +28,8 @@
\param Mapped can be any datatype which is supposed to be indexed using string
\warning Test waring
\todo
- replace all key assignement operations with key_copy.
- replace all key.size() with key_traits::size().
+ replace all key assignement operations with key_copy.\n
+ replace all key.size() with key_traits::size().\n
remove key.size() calculation where not needed.
*/
@@ -138,15 +142,15 @@
copy_patricia(other.root);
}
- ///
+ /// operator [ ] works similar to std::map
/** \returns returns a reference to the object that is associated with a particular key.
If the map does not already contain such an object, operator[] inserts the default object data_type()
\param k corresponding to the data_type's reference to retrieved.
*/
- data_type &operator [] (const key_type &k)
+ data_type &operator [ ] (const key_type &k)
{
#ifndef FORWARD
- ///call insert node with insert node category
+ //call insert node with insert node category
return insert_new_node(k,iterator_cat());
#else
return insert_new_node(k,0);
@@ -249,16 +253,16 @@
std::pair<std::size_t,int> common;
patricia_node *node;
#ifndef FORWARD
- ///call find_node with iterator_cat()
+ //*call find_node with iterator_cat()
node=find_node(root,k,iterator_cat());
#else
node=find_node(root,k,0);
#endif
if(node==0) return 0;
- ///get the common bits . equivalent to key compare.
+ //*get the common bits . equivalent to key compare.
common=get_common_bits(node->value.first,k);
- ///return true is the keys are equal.
+ //*return true is the keys are equal.
return (common.second==2);
}
@@ -270,17 +274,17 @@
{
std::pair<patricia_node*,patricia_node*> node_pair;
#ifndef FORWARD
- ///call find_node_prev with iterator_cat()
+ //*call find_node_prev with iterator_cat()
node_pair=find_node_prev(root,k,iterator_cat());
#else
node_pair=find_node_prev(root,k,0);
#endif
if ( node_pair.first==0) return end();
- ///return end() if the found keys are not equal.
+ //*return end() if the found keys are not equal.
if(get_common_bits(node_pair.first->value.first,k).second!=2)
return end();
- ///construct the iterator and then return it.
+ //*construct the iterator and then return it.
return iterator(node_pair.first,node_pair.second);
}
@@ -299,7 +303,7 @@
iterator upper_bound(const key_type &k)
{
#ifndef FORWARD
- ///call upper bound with iterator category.
+ //*call upper bound with iterator category.
return upper_bound(k,iterator_cat());
#else
return upper_bound(k,0);
@@ -320,7 +324,7 @@
iterator lower_bound(const key_type &k)
{
#ifndef FORWARD
- ///call upper bound with iterator_cat();
+ //*call upper bound with iterator_cat();
return lower_bound(k,iterator_cat());
#else
return lower_bound(k,0);
@@ -343,7 +347,7 @@
std::pair<iterator,iterator> prefix_range(const key_type &k)
{
#ifndef FORWARD
- ///call prefix_range with iterator category
+ //*call prefix_range with iterator category
return prefix_range(k,iterator_cat());
#else
return prefix_range(k,0);
@@ -400,17 +404,17 @@
root=0;
while(true)
{
- ///try going left if cur->left==0 try going right
+ //*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
+ //*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
+ //*adjust the parent pointer ->left or pp-> right to 0
if(next->left==cur)
next->left=0;
else
@@ -420,7 +424,7 @@
else
if( next->par!=cur )
{
- ///entered an uplink. so mark the thing as zero.
+ //*entered an uplink. so mark the thing as zero.
if(cur->left==next)
cur->left=0;
else
@@ -428,7 +432,7 @@
}
else
{
- ///move forward to next
+ //*move forward to next
cur=next;
}
}
@@ -447,27 +451,27 @@
{
if(cur->left==prev && cur->left->par==cur)
{
- ///coming up from the left.
+ //*coming up from the left.
prev=cur;
- ///try go right other wise got to the parent
+ //*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
+ //*coming up from the right
+ //*goto the parent
prev=cur;
cur=cur->par;
}
else
{
- ///going into a new node so increment size
+ //*going into a new node so increment size
ret_size++;
std::cout<<cur->value.first<<std::endl;
prev=cur;
- ///goto left otherwise goto right other go up.
+ //*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 );
@@ -515,17 +519,17 @@
const std::size_t key_size=Key_traits::size(key);
key_iterator it=Key_traits::begin(key);
- ///get the insert pair for the 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 everything is common return the data type
if ( common.second==2 )
return std::make_pair(node_pair, common);
- ///else search for the key again
+ //*else search for the key again
next=cur=root;
while (next->index < common.first) {
cur=next;
@@ -533,11 +537,11 @@
//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.
+ //*is its an upward link break.
if(cur->index >= next->index) break;
}
- ///return the node pair along with common pair.
+ //*return the node pair along with common pair.
return std::make_pair(std::make_pair(next,cur), common);
}
@@ -564,44 +568,44 @@
it=Key_traits::begin(key);
end_it=Key_traits::end(key);
- ///get the node pair between which the key is supposed to be inserted
+ //*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
+ //*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
+ //*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.
+ //*simply got the right because. left not has a lesser length than the key.
next=cur->right;
}
else
{
- ///goto left or right appropriately
+ //*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.
+ //*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
+ //*increment pos and it until the required pos matching index is reached
while( pos < (next->index)/(bit_width+1) && it!=end_it )
{
++pos;
@@ -635,9 +639,9 @@
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
+ //*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)
{
@@ -654,7 +658,7 @@
new(root) patricia_node( key, 0, old_root, root, 0 );
if(old_root)
{
- ///reassign the old root the position.
+ //*reassign the old root the position.
old_root->par=root;
}
}
@@ -665,7 +669,7 @@
if(it==end_it)
{
- ///"" inserted
+ //*"" inserted
if(root->left==0)
{
@@ -675,23 +679,23 @@
return root->left->value.second;
}
- ///get the insert pair. the pair in between which the things should be inserted
+ //*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 the key already exists return
if(common.second==2)
{
std::cout<<"The key \""<<key<<"\" already exists"<<std::endl;
return next->value.second;
}
- ///allocate new node
+ //*allocate new node
temp_node=node_allocator.allocate(1);
- ///rewire the cur to temp_node
+ //*rewire the cur to temp_node
if(cur->left==next)
cur->left=temp_node;
else
@@ -702,16 +706,16 @@
if(common.second)
- ///temp_node should point to inself at 1 ie right
+ //*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
+ //*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 its not an upward link adjust the next->par
if(cur->index < next->index) next->par=temp_node;
assert(root->par==0);
@@ -749,7 +753,7 @@
k1_end=k1.end();
k2_end=k2.end();
- ///check until the chars are unequal and increment pos accordingly
+ //*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) )
@@ -764,7 +768,7 @@
if(unequal)
{
- ///find the unequal bit
+ //*find the unequal bit
std::size_t bit_pos=0;
t1=Key_traits::get_element(k1_it);
t2=Key_traits::get_element(k2_it);
@@ -781,9 +785,9 @@
}
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
+ //*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;
}
@@ -812,7 +816,7 @@
if(root==0) return 0;
if(it==end_it)
return root->left;
- ///adjust pos to the appropriate value
+ //*adjust pos to the appropriate value
while ( pos < (cur->index)/(bit_width+1) && it!=end_it )
{
++pos;
@@ -822,11 +826,11 @@
while(it!=end_it) {
if ( (cur->index)%(bit_width+1)==0 )
{
- ///always go right as length of the key on right is lesser.
+ //*always go right as length of the key on right is lesser.
next=cur->right;
}
else {
- ///go left or right appropriately.
+ //*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) ) ?
@@ -836,7 +840,7 @@
//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 we are heading toward the parent stop
if ( next->index <= cur->index ) break;
while ( pos < (next->index)/(bit_width+1) && it!=end_it ) {
@@ -847,7 +851,7 @@
}
if ( it == end_it && pos==(cur->index)/(bit_width+1) ) {
- ///just make the required connection
+ //*just make the required connection
next=cur->left;
}
return next;
@@ -876,22 +880,20 @@
while (true )
{
pos= cur->index / (bit_width + 1);
- ///make sure the key length is always lesser
+ //*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;
- //std::cout<<"In find of "<<key<<": cur="<<cur->value.first
- //<<" going to next \""<<next->value.first<<"\""<<std::endl;
- ///if we are heading toward the parent stop
+ //*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.
+ //*make the required correction if the add the last bit 0 to the node.
next=cur->left;
}
@@ -924,7 +926,7 @@
if(it==end_it)
{
- ///special cases for ""
+ //*special cases for ""
if ( cur==root || cur==root->left )
return std::make_pair(root->left,root);
else
@@ -932,7 +934,7 @@
}
- ///refer find()
+ //*refer find()
while (true ) {
pos= cur->index / (bit_width + 1);
if ( pos >= key_size ) break;
@@ -977,20 +979,20 @@
if(cur==0) return std::make_pair(cur,cur);
if(it==end_it)
{
- ///special cases for ""
+ //*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
+ //*adjust pos to match with cur->index
while ( pos < (cur->index)/(bit_width+1) && it!=end_it ) {
++pos;
++it;
}
- ///ref find :)
+ //*ref find :)
while(it!=end_it) {
if ( (cur->index)%(bit_width+1)==0 )
{
@@ -1033,13 +1035,13 @@
std::cout<<"in erase: found "<<found->value.first<<" and prev "<<prev->value.first<<std::endl;
if ( found-> par == 0 ) {
- ///==> found=root node
+ //*==> found=root node
std::cout<<"par"<<std::endl;
assert(root==found);
if( (found->right==0 || found->left==0) && found==prev){
- ///only root or only ""
+ //*only root or only ""
deallocate_node(found);
root=0;
return;
@@ -1047,7 +1049,7 @@
//std::cout<<"wrong place"<<std::endl;
if(prev==found){
- ///also takes care of taking to "" to the root
+ //*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);
@@ -1057,30 +1059,30 @@
else
if ( found->right==0 || found->left==0 )
prev=found;
- /// now prev contains the node from which found is wired with an uplink
+ //* now prev contains the node from which found is wired with an uplink
std::cout<<"here"<<std::endl;
- ///if a node is looping to itself
- ///deleting the leaf node.
- ///this case for root node is handled before
+ //*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.
+ //*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.
+ //*rewire the parent.
found->par->right = (found->right==found)?found->left:found->right;
- ///also take care rewiring the new childs parent
+ //*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.
+ //*rewire the parent.
found->par->left = (found->right==found)?found->left:found->right;
- ///also take care rewiring the new childs parent
+ //*also take care rewiring the new childs parent
if( found->par->left && found==found->par->left->par ) found->par->left->par=found->par;
}
else
@@ -1088,8 +1090,8 @@
//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.
+ //*Probably erasing "" for lets be extra careful
+ //*check whether the par is as expected proper.
assert(found->par==root);
std::cout<<"\"\" node to be erased"<<std::endl;
}
@@ -1097,28 +1099,28 @@
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
+ //*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
+ //*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 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
+ //*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 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 we are deallocating the root
if(found->par==0)
root=prev;
- ///finally copy the pointers and index of found to prev node
+ //*finally copy the pointers and index of found to prev node
copy_node_ptr(prev,found);
deallocate_node(found);
}
@@ -1175,7 +1177,7 @@
void inline copy_node_ptr(patricia_node* to, patricia_node* found)
{
if(found->par!=0) {
- ///rewire found->par
+ //*rewire found->par
if(found->par->right==found)
found->par->right=to;
else
@@ -1184,18 +1186,18 @@
to->par=found->par;
if(found->right!=found)
- ///if found is not connected to itself
+ //*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
+ //*if found is not connected to itself
to->left=found->left;
else
to->left=to;
- ///rewire the parents of left and right
+ //*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;
@@ -1223,7 +1225,7 @@
if(root==0) return end();
if ( Key_traits::begin(key)==Key_traits::end(key) )
{
- /// Special case for ""
+ //* Special case for ""
if(root->left==0) return end();
else
return begin();
@@ -1232,7 +1234,7 @@
/// Check whether there keys other that "" at all.
if(root->right==0)
{
- /// Lowerbound has to be ""
+ //* Lowerbound has to be ""
return begin();
}
@@ -1246,16 +1248,16 @@
switch(common.second)
{
case 2:
- ///case where key is found.
+ //*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
+ //*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.
+ //*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.
+ //*we just move to the highest value in the subtree.
it.to_right_most();
return it;
}
@@ -1283,10 +1285,10 @@
if ( Key_traits::begin(key)==Key_traits::end(key) )
return begin();
- /// Check whether there keys other that "" at all.
+ //* Check whether there keys other that "" at all.
if ( root->right==0 )
{
- ///explicitly find the upper bound
+ //*explicitly find the upper bound
if(Key_traits::begin(key)!=Key_traits::end(key) )
return end();
else
@@ -1301,16 +1303,16 @@
switch ( common.second )
{
case 2:
- ///key aleardy exists
+ //*key aleardy exists
return iterator(next,cur);
case 1:
- ///upper bound is not in the subtree of next.its just greater than the subtree
+ //*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 is in the subtree
it=iterator(next,cur);
std::cout<<next->value.first<<"<-"<<cur->value.first<<std::endl;
- ///go to the least element in the subtree.
+ //*go to the least element in the subtree.
it.to_left_most();
return it;
}
@@ -1333,25 +1335,35 @@
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());
- if(root->right==0) 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 )
- {
+ 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 );
std::cout<<"FOUND"<<std::endl;
}
+ //*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());
std::cout<<"HERE with KEY="<<key<<std::endl;
+ //*we start searching for the until we get a key with index>common.first
next=cur=root;
while (next->index < common.first) {
cur=next;
@@ -1361,10 +1373,15 @@
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);
}
@@ -1388,10 +1405,14 @@
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(root->right==0) 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());
@@ -1399,19 +1420,18 @@
assert(find_node_prev(root,key,iterator_cat()).first==next);
cur =node_pair.second;
assert(find_node_prev(root,key,iterator_cat()).second==cur);
- //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);
- //key already exists
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)
@@ -1425,7 +1445,7 @@
cur->right:cur->left;
}
- //fortunately in this case; this should happen only when it==end_it occures.
+ //*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;
@@ -1439,8 +1459,11 @@
}
iterator right=iterator(next,cur);
iterator left =iterator(next,cur);
+
+ //*find the smallest in the subtree of next
left.to_left_most();
- //right.to_right_most();
+
+ //*find one greater than greatest in the subtree of next.
++right;
return std::make_pair(left,right);
}
@@ -1475,7 +1498,11 @@
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;
@@ -1483,57 +1510,74 @@
}
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 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);
- //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;
+
+ //*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);
- //leaf node!!
+
+ //*if the edge is the left is the left edge
if((*other_cur)==other_prev->left)
{
- //assert(*cur!=other_root);
+ //*move towards the right egde
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
{
+ //*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)
{
- //std::cout<<"ROOT:"<<root<<std::endl;
+ //*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;
}
@@ -1546,6 +1590,7 @@
\returns true is equal false otherwise
\param p1 is the first patricia node
\param p2 is the second patricia node
+ \todo check whether are actually better ways.
*/
template<class Key,class Mapped,class Key_traits,class Alloc >
@@ -1558,6 +1603,8 @@
it_1=p1.begin();
it_2=p2.begin();
+ //* simply check whether all keys and values are equal when enumerated
+ //* in ascending order
while ( it_1 != p1.end() && it_2 != p2.end()
&& (*it_1).first == (*it_2).first && (*it_1).second == (*it_2).second )
{