From: chintanraoh_at_[hidden]
Date: 2008-06-05 14:23:48
Author: chintanraoh
Date: 2008-06-05 14:23:47 EDT (Thu, 05 Jun 2008)
New Revision: 46174
URL: http://svn.boost.org/trac/boost/changeset/46174
Log:
added a copy constructor and over loaded "=" operator
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp | 132 ++++++++++++++++++++++++++++++++++++++-
1 files changed, 127 insertions(+), 5 deletions(-)
Modified: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp
==============================================================================
--- sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp (original)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp 2008-06-05 14:23:47 EDT (Thu, 05 Jun 2008)
@@ -14,9 +14,9 @@
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
+template<class K,class M,class K_t,class A > class trie_node,
class Key_traits,
-class Alloc=std::allocator<char> >
+class Alloc=std::allocator<char> > //wonder allocator<char> is correct
class trie
{
private:
@@ -54,6 +54,23 @@
new(node_root) node_type();
}
+ trie(const type &other)
+ {
+ std::cout<<"in copy constructor"<<std::endl;
+
+ copy_trie_preserve(const_cast<node_type *>(other.node_root) );
+ }
+
+ type &operator = ( const type other )
+ {
+ if(node_root==other.node_root) return *this;
+ clear();
+ node_allocator.destroy(node_root);
+ node_allocator.deallocate(node_root,1);
+ copy_trie(other.node_root);
+ return *this;
+ }
+
data_type &operator [] (const key_type &k)
{
return insert_(k)->get_value_ref();
@@ -72,7 +89,6 @@
std::size_t max_size()
{
return std::numeric_limits<std::size_t>::max();
- //return (std::size_t)(-1);//does this work everywhere?
}
bool empty()
@@ -88,7 +104,12 @@
node_type* cur=node_root,*par=node_root,*temp_cur=node_root;
- if(it==end_it) return;
+ if(it==end_it)
+ {
+ if(node_root->has_value())
+ node_root->erase_value();
+ return;
+ }
fit=cur->find(*it);
if(fit==cur->end())
return;
@@ -190,7 +211,11 @@
//ret_it.push(cur);
if( not_found )
{
- next=++cursor(cur.get_node(),cur.get_node()->lower_bound(*it));
+ next=cursor(cur.get_node(),cur.get_node()->lower_bound(*it));
+ if(next==ret_it.top().end())
+ next=cursor ( cur.get_node(), cur.get_node()->begin());
+ else
+ next++;
while(next==ret_it.top().end())
{
std::cout<<"popping "<<std::endl;
@@ -396,6 +421,103 @@
}
return false;
}
+
+ void copy_trie_preserve(node_type*other_root)
+ {
+ node_type *prev,*temp_node;
+ typedef typename node_type::iterator node_iterator;
+ std::stack<node_iterator> st;
+ std::stack<node_iterator> this_st;
+ node_iterator cur_it=other_root->begin();
+
+ node_root=node_allocator.allocate(1);
+ node_allocator.construct(node_root,*other_root);
+
+ if ( other_root->end() == other_root->begin() )
+ return;
+ this_st.push(node_root->begin());
+
+ while(true)
+ {
+ if(st.empty())
+ prev=other_root;
+ else
+ prev=*st.top();
+
+ if( cur_it == prev->end() )
+ {
+ if(st.empty()) return;
+ cur_it=++st.top();
+ st.pop();
+ this_st.pop();
+ ++this_st.top();
+ continue;
+ }
+
+ temp_node=node_allocator.allocate(1);
+ node_allocator.construct( temp_node , **cur_it );
+ *(this_st.top())=temp_node;
+
+ /*if((*cur_it)->has_value())
+ temp_node->get_value_ref()=(*cur_it)->get_value_ref();*/
+ this_st.push(temp_node->begin());
+ st.push(cur_it);
+
+ cur_it=(*cur_it)->begin();
+ }
+ }
+
+ //this does not preserve the stucture of tst.
+ void copy_trie(node_type*other_root)
+ {
+ node_type *prev,*this_prev,*temp_node;
+ typedef typename node_type::iterator node_iterator;
+ std::stack<node_iterator> st;
+ std::stack<node_type *> this_st;
+
+ node_iterator cur_it=other_root->begin();
+
+ node_root=node_allocator.allocate(1);
+ new(node_root) node_type;
+ if(other_root->has_value())
+ node_root->get_value_ref()=other_root->get_value_ref();
+
+ while(true)
+ {
+ if(st.empty())
+ {
+ prev=other_root;
+ this_prev=node_root;
+ }
+ else
+ {
+ prev=*st.top();
+ this_prev=this_st.top();
+ }
+
+ if(cur_it==prev->end())
+ {
+ std::cout<<"reached end"<<std::endl;
+ if(st.empty()) return;
+ this_st.pop();
+ cur_it=++st.top();
+ st.pop();
+ continue;
+ }
+ else
+ std::cout<<"going to:"<<prev->get_element(cur_it)<<std::endl;
+
+ temp_node=node_allocator.allocate(1);
+ new(temp_node) node_type();
+ this_prev->insert(prev->get_element(cur_it),temp_node);
+
+ if((*cur_it)->has_value())
+ temp_node->get_value_ref()=(*cur_it)->get_value_ref();
+ this_st.push(temp_node);
+ st.push(cur_it);
+ cur_it=(*cur_it)->begin();
+ }
+ }
};
}