|
|
Boost-Commit : |
From: chintanraoh_at_[hidden]
Date: 2008-06-22 11:14:08
Author: chintanraoh
Date: 2008-06-22 11:14:08 EDT (Sun, 22 Jun 2008)
New Revision: 46612
URL: http://svn.boost.org/trac/boost/changeset/46612
Log:
prefix_range()
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp | 127 +++++++++++++++++++++++++++++++++------
1 files changed, 105 insertions(+), 22 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-22 11:14:08 EDT (Sun, 22 Jun 2008)
@@ -169,6 +169,8 @@
node_pair=find_node_prev(root,k,0);
#endif
if ( node_pair.first==0) return end();
+ if(get_common_bits(node_pair.first->value.first,k).second!=2)
+ return end();
return iterator(node_pair.first,node_pair.second);
}
@@ -200,6 +202,15 @@
#endif
}
+ std::pair<iterator,iterator> prefix_range(const key_type &k)
+ {
+ #ifndef FORWARD
+ return prefix_range(k,iterator_cat());
+ #else
+ return prefix_range(k,0);
+ #endif
+ }
+
void erase(const key_type &k)
{
#ifndef FORWARD
@@ -304,7 +315,7 @@
*/
inline std::pair< std::pair<patricia_node*,patricia_node*>,
std::pair<std::size_t,int> >
- get_insert_pair(const key_type &key,rand_tag)
+ get_insert_pair(const key_type &key,rand_tag) const
{
patricia_node *cur=root,*next=root;
std::size_t pos=0;
@@ -336,7 +347,7 @@
template<class T>
inline std::pair< std::pair<patricia_node*,patricia_node*>,
std::pair<std::size_t,int> >
- get_insert_pair (const key_type &key,T)
+ get_insert_pair (const key_type &key,T) const
{
key_iterator it,end_it;
key_element_type temp_element;
@@ -508,7 +519,7 @@
while(k1_it!=k1_end && k2_it!=k2_end )
{
- if( Key_traits::get_element(k1_it) != Key_traits::get_element(k2_it) )
+ if ( Key_traits::get_element(k1_it) != Key_traits::get_element(k2_it) )
{
unequal=true;
break;
@@ -523,16 +534,17 @@
std::size_t bit_pos=0;
t1=Key_traits::get_element(k1_it);
t2=Key_traits::get_element(k2_it);
- key_element_type x=key_element_type(-1)-1;
+ key_element_type x=t1;
//TODO:optimize this part!!!
//key_element_type x= (key_element_type(1)<<(bit_width-1));
- while((t1 & x)!=( t2 & x))//possibly make this ( t1 & x) != ( t1 & x )
+ while((t1)!=( t2))//possibly make this ( t1 & x) != ( t1 & x )
{
- x<<=1;
+ t1>>=1;
+ t2>>=1;
++bit_pos;
}
- uncommon_bit= ( (t1 & (key_element_type(1)<<bit_pos)) !=0);
- pos+=bit_width-bit_pos;
+ uncommon_bit= ( ( x & (key_element_type(1)<<(bit_pos-1)) ) !=0);
+ pos+=bit_width-bit_pos+1;
}
else
uncommon_bit=(k1_it==k1_end)?((k2_it==k2_end)?2:0):1;
@@ -541,7 +553,7 @@
}
template<class T>
- inline patricia_node* find_node(const patricia_node* cur,const key_type &key,T)
+ inline patricia_node* find_node(const patricia_node* cur,const key_type &key,T) const
{
patricia_node *next;
std::size_t pos=0;
@@ -583,7 +595,7 @@
return next;
}
- inline patricia_node* find_node(const patricia_node *cur, const key_type &key,rand_tag,std::size_t key_size=0)
+ 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;
@@ -623,7 +635,7 @@
}
inline std::pair<patricia_node*,patricia_node*>
- find_node_prev(patricia_node *root, const key_type &key, rand_tag,std::size_t key_size=0)
+ find_node_prev(patricia_node *root, const key_type &key, rand_tag,std::size_t key_size=0) const
{
patricia_node *cur,*next=0;
key_iterator it, end_it;
@@ -670,7 +682,7 @@
if(root==0) return std::make_pair(root,root);
if(it==end_it)
- return std::make_pair(root->left,root->left);
+ return std::make_pair(root->left,root);
while ( pos < (cur->index)/(bit_width+1) && it!=end_it ) {
++pos;
++it;
@@ -923,7 +935,7 @@
assert(false);
}
-
+ /*
std::size_t get_mask_bits(const key_element_type &mask)
{
std::size_t no;
@@ -932,24 +944,21 @@
while(m>>=1) no++;
return no;
}
-
- template<class T>
- std::pair<iterator,iterator> prefix_range(const key_type &key,T)
+ */
+ 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;
- std::size_t bit_mask;
key_iterator it=Key_traits::begin(key);
-
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;
+ if(root->right==0) return std::make_pair(begin(),end());
node_pair=find_node_prev(root,key,iterator_cat(),key_size);
@@ -957,11 +966,14 @@
common=get_common_bits(key,next->value.first );
if ( common.second==2 )
{
- //not_handled
+ common.second=0;
+ common.first=key_size*( bit_width + 1 );
+ std::cout<<"FOUND"<<std::endl;
}
+
if ( common.second!=0 || common.first % ( bit_width + 1 ) != 0)
return std::make_pair(end(),end());
-
+ std::cout<<"HERE with KEY="<<key<<std::endl;
next=cur=root;
while (next->index < common.first) {
@@ -976,7 +988,78 @@
iterator right=iterator(next,cur);
iterator left =iterator(next,cur);
left.to_left_most();
- right.to_right_most();
+ ++right;
+ return std::make_pair(left,right);
+ }
+
+ 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(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());
+
+ 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);
+ //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=true;
+ }
+ if ( common.second!=0 || common.first % ( bit_width + 1 ) != 0)
+ return std::make_pair(end(),end());
+
+ 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);
+ left.to_left_most();
+ //right.to_right_most();
+ ++right;
return std::make_pair(left,right);
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk