From: chintanraoh_at_[hidden]
Date: 2008-06-11 14:35:16
Author: chintanraoh
Date: 2008-06-11 14:35:15 EDT (Wed, 11 Jun 2008)
New Revision: 46334
URL: http://svn.boost.org/trac/boost/changeset/46334
Log:
Intial patricia trie work. untested
Added:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/pat_key_traits.hpp (contents, props changed)
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp (contents, props changed)
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/pat_key_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/pat_key_traits.hpp 2008-06-11 14:35:15 EDT (Wed, 11 Jun 2008)
@@ -0,0 +1,36 @@
+#ifndef BOOST_DSEARCH_PAT_KEY_TRAITS_HPP
+#define BOOST_DSEARCH_PAT_KEY_TRAITS_HPP
+
+#include<string>
+
+namespace boost{
+namespace dsearch{
+
+
+//because we require an unsigned type from each element
+class pat_key_traits{
+ public:
+ typedef unsigned char element_type; //element type = unsigned type with size 2^(8*2^n) upto n=3. ie "unsigned long long";
+ typedef std::string::const_iterator const_iterator ;
+ static const_iterator &begin (std:string &key)
+ {
+ return key.begin();
+ }
+
+ static inline const_iterator &end (std::string &key)
+ {
+ return key.end();
+ }
+
+ static inline element_type get_element(const const_iterator &it)
+ {
+ return static_cast<unsigned char>(*it);
+ }
+ //no get_key as the keys are stored as it is.
+};
+
+}
+}
+
+#endif //BOOST_DSEARCH_PAT_KEY_TRAITS_HPP
+
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/patricia.hpp 2008-06-11 14:35:15 EDT (Wed, 11 Jun 2008)
@@ -0,0 +1,224 @@
+#ifndef BOOST_DSEARCH_PATRICIA_HPP
+#define BOOST_DSEARCH_PATRICIA_HPP
+
+#include<algorithm>
+#include<memory>
+#include<assert.h>
+
+namespace boost{
+namespace dsearch{
+template<class Key,class Mapped,class Key_traits,class Alloc=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
+ };
+ template<class Key,class Mapped>
+ class patricia_node {
+ typedef typename patricia_node<Key,Mapped> 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);
+ {
+ }
+ };
+ 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;
+
+ patricia(): root(0)
+ {
+ }
+
+ void insert(const value_type &v)
+ {
+ }
+
+ private:
+ inline data_type &insert_new_node(const key_type&key)
+ {
+ key_iterator it,end_it;
+ pat_node *cur=root,*next=root,*temp_node;
+ key_element_type temp_element;
+ int pos=0;
+ std::pair<std::size_t,bool> common;
+
+ it=Key_traits::begin(key);
+ end_it=Key_traits::end(key);
+
+ 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;
+ else
+ root->right=root; //add to right if the first node added is "";
+ 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((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))?
+ cur->right:cur->left;
+ }
+
+ //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;
+ }
+ common=get_common_bits(key,next->value.first);
+ if(common.second==2) //key already exists
+ return next->value.second;
+
+ assert(common.first);
+ it=Key_traits::begin(key);
+ cur=root;
+ while(it!=end_it)
+ {
+ 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))?
+ 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 <= cur->index ) break;
+
+ if( pos < (next->index)/(bit_width+1) )
+ {
+ ++pos;
+ ++it;
+ }
+ cur=next;
+ }
+
+ temp_node=node_allocator.allocate(1);
+ new (temp_node) patricia_node();
+ temp->value.first=key;
+
+ //recalculate common;
+ common=get_common_bits ( temp->value.first, next->key );
+
+ 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;
+ 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;
+ }
+ else
+ {
+ temp_node->right=next;
+ temp_node->left=temp_node;
+ }
+
+ return temp_node->value.second;
+ }
+
+ inline std::size_t get_nth_bit(const key_element_type &element,const int &n) const
+ {
+ return 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
+ {
+ key_iterator k1_it,k2_it,k1_end,k2_end;
+ //std::pair<std::size_t,bool> ret_type;
+ 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();
+
+ if(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)
+ {
+ t1=Key_traits::get_element(k1_it)
+ t2=Key_traits::get_element(k2_it)
+ while(t1%2==t2%2)
+ {
+ t1/=2;
+ t2/=2;
+ ++pos;
+ }
+ uncommon_bit=t1%2;
+ }
+ else
+ uncommon_bit=(k1==k1_end)?((k2==k2_end)?2:1):0;
+
+ return make_pair(pos,uncommon_bit);
+ }
+};
+
+
+}//namespace dsearch
+}//namespace boost
+
+#endif //BOOST_DSEARCH_PATRICIA_HPP
+