From: chintanraoh_at_[hidden]
Date: 2008-05-31 10:11:22
Author: chintanraoh
Date: 2008-05-31 10:11:22 EDT (Sat, 31 May 2008)
New Revision: 45973
URL: http://svn.boost.org/trac/boost/changeset/45973
Log:
contains a half done trie class and a simple test case file
Added:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/key_traits.hpp (contents, props changed)
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/node_cursor.hpp (contents, props changed)
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp (contents, props changed)
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_array_node.hpp (contents, props changed)
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/key_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/key_traits.hpp 2008-05-31 10:11:22 EDT (Sat, 31 May 2008)
@@ -0,0 +1,76 @@
+#ifndef BOOST_DSEARCH_KEY_TRAITS_HPP
+#define BOOST_DSEARCH_KEY_TRAITS_HPP
+
+#include<string>
+#include<vector>
+
+namespace boost{
+namespace dsearch{
+
+struct key_trait_compare_tag {};
+struct key_trait_value_tag {};
+struct key_trait_compare_value_tag: public key_trait_compare_tag,public key_trait_value_tag{};
+
+template<class Key>
+class default_iterator_traits{
+ public:
+ typedef typename Key::const_iterator const_iterator;
+ typedef Key key_type;
+ static inline const_iterator begin(const Key &key)
+ {
+ return key.begin();
+ }
+
+ static inline const_iterator end(const Key &key)
+ {
+ return key.end();
+ }
+};
+
+
+//possibly make this string value traits;
+//the user can specify how to store the value.. ie a pointer or as the value itself
+//this will lessen the burden for trie_node. Also define default_value_trait
+class string_traits: public default_iterator_traits<std::string>{
+ public:
+ typedef key_trait_compare_value_tag container_category;
+ typedef std::string::const_iterator const_iterator;
+ typedef std::string key_type;
+ typedef char element_type;
+
+ struct lt_element
+ {
+ bool operator()(element_type e1, element_type e2) const
+ {
+ return e1 < e2;
+ }
+ };
+
+ typedef lt_element key_compare;
+
+ enum {
+ max=255
+ };
+
+ static std::size_t get_value(element_type e1)
+ {
+ return static_cast<unsigned char>(e1);
+ }
+
+ template<typename value_it>
+ static key_type get_key(const value_it &beg,const value_it &end)
+ {
+ key_type str;
+ value_it it=beg;
+ while(it!=end)
+ {
+ str.push_back((char)*it);
+ it++;
+ }
+ return str;
+ }
+};
+}
+}
+#endif // BOOST_DSEARCH_KEY_TRAITS_HPP
+
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/node_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/node_cursor.hpp 2008-05-31 10:11:22 EDT (Sat, 31 May 2008)
@@ -0,0 +1,114 @@
+#ifndef BOOST_DSEARCH_NODE_CURSOR_HPP
+#define BOOST_DSEARCH_NODE_CURSOR_HPP
+
+#include "from_tree/cursor_helpers.hpp" //namespace boost::tree
+#include<assert.h>
+
+
+namespace boost {
+namespace dsearch {
+ using boost::tree::cursor_facade;
+ template<class Node>
+ class trie_cursor:public cursor_facade<trie_cursor<Node>,Node,
+ forward_traversal_tag,
+ bidirectional_traversal_tag>
+
+ {
+ private:
+ typedef trie_cursor<Node> cursor;
+
+ friend class boost::iterator_core_access;
+ friend class boost::tree::cursor_core_access;
+ unsigned char only_root;
+ bool top;
+
+ Node *cur;
+ typedef typename Node::iterator node_iterator;
+ node_iterator pos;
+
+ public:
+ trie_cursor(bool t=false):top(t)
+ {
+ }
+
+ trie_cursor(Node * const n_ptr): only_root(1) , top(false)
+ {
+ cur=n_ptr;
+ }
+
+ trie_cursor(const Node * n_ptr,const node_iterator it): only_root(0), top(false)
+ {
+ cur=const_cast<Node *>(n_ptr);
+ pos=it;
+ }
+
+ private:
+ bool equal(cursor const& other) const
+ {
+ if(top==other.top)
+ {
+ if(top) return true;
+ }
+ else
+ return false;
+ if(only_root==other.onlyroot)
+ {
+ if (only_root==1 || only_root==2)
+ return true;
+ assert(only_root==0);
+ }
+ else
+ return false;
+ if(cur==other.cur && pos=other.pos) return true;
+ return false;
+ }
+
+ cursor left() const
+ {
+ if(only_root)
+ return cursor(cur,cur->begin());
+ return cursor(*pos,(*pos)->begin());
+ }
+
+ cursor right() const
+ {
+ if(only_root)
+ return cursor(cur,cur->end());
+ return cursor(*pos,(*pos)->end());
+ }
+
+ void increment()
+ {
+ if(only_root)
+ only_root++;
+ else
+ pos++;
+ }
+
+ void decrement()
+ {
+ if(only_root)
+ only_root--;
+ else
+ pos--;
+ }
+
+ bool empty_() const
+ {
+ if(only_root)
+ return cur->empty();
+ return (*pos)->empty();
+ }
+
+ Node &dereference() const
+ {
+ if(only_root)
+ return *cur;
+ return **pos;
+ }
+ };
+}
+}
+
+#endif //BOOST_DSEARCH_NODE_CURSOR_HPP
+
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp 2008-05-31 10:11:22 EDT (Sat, 31 May 2008)
@@ -0,0 +1,234 @@
+#ifndef BOOST_DSEARCH_TRIE_HPP
+#define BOOST_DSEARCH_TRIE_HPP
+
+#include<limits>
+#include<memory>
+#include<stack>
+#include<algorithm>
+#include<assert.h>
+#include "node_cursor.hpp"
+
+namespace boost{
+namespace dsearch{
+
+template<class Key,class Mapped,
+template<class K,class M,class K_t,class A > class trie_node, //wonder allocator<char> is correct
+class Key_traits,
+class Alloc=std::allocator<char> >
+class trie
+{
+ private:
+ typedef trie_node<Key,Mapped,Key_traits,Alloc> node_type;
+ friend class trie_node<Key,Mapped,Key_traits,Alloc>;
+ typedef typename Alloc::template rebind<node_type>::other node_allocator_type;
+ node_allocator_type node_allocator;
+ node_type *node_root;
+ public:
+ typedef Key key_type;
+ typedef Mapped data_type;
+ typedef std::pair<Key,Mapped> value_type;
+ typedef trie<Key,Mapped,trie_node,Key_traits,Alloc> type;
+
+ //need to define an iterator before that will need to define cursor for trie_node
+ //TODO iterator, const_iterator, reverse_iterator, const_reverse_iterator, begin(), end()
+ //rbegin(),size(),trie(trie &), overload =, lots of other things
+
+ typedef typename Alloc::template rebind<value_type>::other allocator_type;
+ typedef typename allocator_type::pointer pointer;
+ typedef typename allocator_type::const_pointer const_pointer;
+ typedef typename allocator_type::reference reference;
+ typedef typename allocator_type::const_reference const_reference;
+ typedef typename allocator_type::size_type size_type;//should actually depend on iterator(.|?)
+ typedef typename allocator_type::difference_type difference_type; //should actually depend on iterator(.|?)
+
+ typedef trie_cursor<node_type> cursor;
+
+ trie()
+ {
+ node_root=node_allocator.allocate(1);
+ new(node_root) node_type();
+ }
+
+ data_type &operator [] (const key_type &k)
+ {
+ return insert_(k)->get_value_ref();
+ }
+
+ void insert(const value_type &v)
+ {
+ this->operator[](v.first)=v.second;
+ }
+
+ std::size_t size()
+ {
+ return 0; //for now
+ }
+
+ std::size_t max_size()
+ {
+ return std::numeric_limits<std::size_t>::max();
+ //return (std::size_t)(-1);//does this work everywhere?
+ }
+
+ bool empty()
+ {
+ return node_root->empty();
+ }
+
+ void erase(const key_type &key)
+ {
+ typename Key_traits::const_iterator it=Key_traits::begin(key),
+ end_it=Key_traits::end(key),temp_it=it;
+ typename node_type::iterator fit;
+
+ node_type* cur=node_root,*par=node_root,*temp_cur=node_root;
+
+ if(it==end_it) return;
+ fit=cur->find(*it);
+ if(fit==cur->end())
+ return;
+ cur=*fit;
+
+ it++;
+ while(!(it==end_it))
+ {
+
+ fit=cur->find(*it);
+ if(fit==cur->end())
+ {
+ return;
+ }
+ if(cur->size()!=1 || cur->has_value()) //should we delete things backwards?
+ {
+ temp_cur=cur;
+ temp_it=it;
+ }
+ cur=*fit;
+ it++;
+ }
+
+ cur->erase_value();
+ if(!cur->empty()) return;
+
+ fit=temp_cur->find(*temp_it);
+ cur=*fit;
+ std::cout<<"deleting:"<<*temp_it<<std::endl;
+ temp_cur->erase(fit);
+
+ it=temp_it+1;
+
+ while(it!=end_it)
+ {
+ std::cout<<"deleting:"<<*it<<std::endl;
+ par=cur;
+ cur=*cur->find(*it);
+ node_allocator.deallocate(par,1);
+ it++;
+ }
+ node_allocator.deallocate(cur,1);
+ }
+
+ bool find(const key_type &key) const //make this iterator instead of bool;
+ {
+ typename Key_traits::const_iterator it=Key_traits::begin(key),
+ end_it=Key_traits::end(key);
+ typename node_type::iterator fit;
+ node_type *cur=node_root;
+ while(!(it==end_it))
+ {
+ fit=cur->find(*it);
+ if(fit == cur->end() ) return false;
+ cur=*fit;
+ it++;
+ }
+ if(cur->has_value())
+ {
+ return true;
+ }
+ return false;
+ }
+
+ void swap(const type &other)
+ {
+ std::swap(other.node_root,node_root);
+ }
+
+ void clear()
+ {
+ typedef typename node_type::iterator node_it;
+ std::stack< std::pair<node_type*,node_it> > node_stack;
+ int size=1;
+ node_stack.push(std::make_pair(node_root,node_root->begin()));
+ while(1)
+ {
+ if(node_stack.top().first->end()==node_stack.top().second)
+ {
+ if(size==1) break;
+ node_allocator.destroy(node_stack.top().first);
+ node_allocator.deallocate(node_stack.top().first,1);
+ node_stack.pop();
+ size--;
+ node_stack.top().second++;
+ continue;
+ }
+ node_stack.push( std::make_pair(*(node_stack.top().second)
+ ,(*(node_stack.top().second))->begin()) );
+ size++;
+ }
+ node_stack.pop();
+ node_allocator.destroy(node_root);
+ node_allocator.deallocate(node_root,1);
+ node_root=node_allocator.allocate(1);
+ new(node_root) node_type();
+ }
+
+ cursor root()
+ {
+ return cursor(node_root);
+ }
+
+ ~trie()
+ {
+ std::cout<<"trie class destructor"<<std::endl;
+ this->clear();
+ node_allocator.deallocate(node_root,1);
+ }
+ private:
+
+ //get reference to the leaf node of the key
+ node_type *insert_(const key_type &key)
+ {
+ typename Key_traits::const_iterator it=Key_traits::begin(key),
+ end_it=Key_traits::end(key);
+ node_type *cur=node_root,*next;
+ typename node_type::iterator fit;
+ int i=0;
+ while(it!=end_it)
+ {
+ fit=cur->find(*it);
+ if(fit==cur->end())
+ break;
+ cur=*fit;
+ it++;
+ assert(i!=10);
+ }
+ i=0;
+ while(it!=end_it)
+ {
+ i++;
+ next=node_allocator.allocate(1);
+ std::cout<<"Allocating:"<<*it<<std::endl;
+ new(next) node_type();
+ cur->insert(*it,next);
+ cur=next;
+ assert(i!=10);
+ it++;
+ }
+ return cur;
+ }
+};
+
+}
+}
+#endif //BOOST_DSEARCH_TRIE_HPP
+
Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_array_node.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie_array_node.hpp 2008-05-31 10:11:22 EDT (Sat, 31 May 2008)
@@ -0,0 +1,176 @@
+#ifndef BOOST_DSEARCH_TRIE_ARRAY_NODE_HPP
+#define BOOST_DSEARCH_TRIE_ARRAY_NODE_HPP
+
+#include<iostream>
+#include<string.h>
+#include<boost/iterator/iterator_facade.hpp>
+#include<memory>
+
+namespace boost{
+namespace dsearch{
+
+
+//template<class Key,class Mapped,class Key_traits,class Allocator=std::allocator<char> >
+//class trie_array_node;
+
+template <typename trie_type>
+class trie_array_node_iterator
+:public iterator_facade<trie_array_node_iterator<trie_type>,trie_type *,boost::forward_traversal_tag>
+{
+ private:
+ trie_type** child_ptr;
+ std::size_t pos;
+ template<class K,class M,class Ke,class Allocator> friend class trie_array_node;
+
+ public:
+ typedef trie_array_node_iterator<trie_type> type;
+ trie_array_node_iterator()
+ :child_ptr(0), pos(0){}
+
+ trie_array_node_iterator(trie_type*node)
+ {
+ child_ptr=(trie_type**)node->child_ptr;
+ int i=0;
+ for(i=0;i<trie_type::max;i++)
+ if(child_ptr[i]!=0) break;
+ pos=i;
+ }
+
+ trie_array_node_iterator(trie_type *node,int p):pos(p)
+ {
+ child_ptr=(trie_type**)node->child_ptr;
+ }
+
+ bool equal( const type &other ) const
+ {
+ if(other.child_ptr==child_ptr && other.pos==pos)
+ return true;
+ return false;
+ }
+
+ void increment()
+ {
+ for(pos++; pos<trie_type::max; pos++)
+ if(child_ptr[pos]!=0) break;
+ }
+
+ void decrement()
+ {
+ for(pos--; pos>0; pos--)
+ if(child_ptr[pos]!=0) break;
+ }
+
+ trie_type *&dereference() const
+ {
+ return child_ptr[pos];
+ }
+};
+
+//TODO:write a copy constructor for good
+template<class Key,class Mapped,class Key_traits,class Alloc=std::allocator<char> >
+class trie_array_node
+{
+ public:
+ typedef trie_array_node<Key,Mapped,Key_traits,Alloc> type;
+ friend class trie_array_node_iterator<type>;
+
+ private:
+ typedef typename Key_traits::element_type element_type;
+ type* child_ptr[Key_traits::max+1];
+
+ public:
+ typedef trie_array_node_iterator<type> iterator;
+ typedef element_type key_type;
+ typedef type* value_type;
+ bool value_indicator;
+ Mapped value; //should it be mapped *? depending on sizeof(mapped)
+
+ enum{
+ max=Key_traits::max
+ };
+
+
+ trie_array_node()
+ {
+ std::cout<<"here"<<std::endl;
+ value_indicator=false;
+ memset(child_ptr,0,sizeof(child_ptr));
+ }
+
+ void insert(const element_type &key,type * const &child_cursor)
+ {
+ child_ptr[Key_traits::get_value(key)]=child_cursor;
+ }
+
+
+ //*iterator should give reference to the value Mapped to by key;
+ iterator find(const element_type &key)
+ {
+ if(child_ptr[Key_traits::get_value(key)]==0)
+ return end();
+ else
+ return iterator(this,Key_traits::get_value(key));
+ }
+
+ void erase(const iterator&it)
+ {
+ child_ptr[it.pos]=0;
+ }
+
+ iterator begin()
+ {
+ return iterator(this);
+ }
+
+ iterator end()
+ {
+ return iterator(this,max);
+ }
+
+ /*void insert_value(const Mapped &v)
+ {
+ value=v;
+ }*/
+
+ Mapped &get_value_ref() //get pointer to value of [] operator of trie class
+ {
+ value_indicator=true;
+ return value;
+ }
+
+ void erase_value()
+ {
+ value_indicator=false;
+ }
+
+ bool has_value()
+ {
+ return value_indicator;
+ }
+
+ std::size_t size()
+ {
+ int t_size=0;
+ for(int i=0;i<max;i++)
+ if(child_ptr[i]!=0)
+ t_size++;
+ return t_size;
+ }
+
+ bool empty()
+ {
+ for(int i=0;i<max;i++)
+ if(child_ptr[i]!=0)
+ return false;
+ return true;
+ }
+
+ ~trie_array_node()
+ {
+ }
+};
+
+}
+}
+#endif //BOOST_DSEARCH_TRIE_ARRAY_NODE_HPP
+