From: chintanraoh_at_[hidden]
Date: 2008-06-06 02:29:58
Author: chintanraoh
Date: 2008-06-06 02:29:58 EDT (Fri, 06 Jun 2008)
New Revision: 46186
URL: http://svn.boost.org/trac/boost/changeset/46186
Log:
void erase(iterator) added to trie class.
Text files modified:
sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/trie.hpp | 66 ++++++++++++++++++++++++++++++++++++---
1 files changed, 60 insertions(+), 6 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-06 02:29:58 EDT (Fri, 06 Jun 2008)
@@ -45,7 +45,6 @@
typedef trie_cursor<key_type,data_type,node_type> cursor;
typedef trie_iterator<key_type,data_type,cursor> iterator;
-// typedef trie_cursor<key_type,data_type,node_type> cursor;
typedef trie_iterator<key_type,const data_type,cursor> const_iterator;
trie()
@@ -314,11 +313,6 @@
return std::make_pair(ret_it,++right);
}
- void swap(type &other)
- {
- std::swap(other.node_root,node_root);
- }
-
void clear()
{
typedef typename node_type::iterator node_it;
@@ -347,6 +341,65 @@
node_root=node_allocator.allocate(1);
new(node_root) node_type();
}
+
+ //linear iteration to find where the pointer is grr...
+ //otherwise i will need to add one more function to the node
+ void erase(const iterator &it)
+ {
+ iterator iter=it;
+ node_type *n_t;
+ cursor cur_it;
+ typename node_type::iterator node_it;
+ if ( iter.top().begin()==iter.top().end() )
+ {
+ node_allocator.destroy( n_t = iter.top().get_node() );
+ node_allocator.deallocate( iter.top().get_node() , 1 );
+ iter.pop();
+ }
+ else
+ {
+ iter.top().get_node()->erase_value();
+ return;
+ }
+ if ( iter.empty() )
+ if( iter.empty() ) //deallocated the root node so reallocate it.
+ {
+ node_root=node_allocator.allocate(1);
+ new(node_root) node_type();
+ return;
+ }
+
+ cur_it=iter.top().begin();
+ while((++cur_it)==iter.top().end())
+ {
+ node_allocator.destroy ( n_t = iter.top().get_node() );
+ node_allocator.deallocate ( iter.top().get_node() , 1 );
+ iter.pop();
+ if( iter.empty() ) //deallocated the root node so reallocate it.
+ {
+ node_root=node_allocator.allocate(1);
+ new(node_root) node_type();
+ return;
+ }
+ if(iter.top().has_value())
+ break;
+ cur_it=iter.top().begin();
+ }
+ node_it=iter.top().get_node()->begin();
+
+ //here is the linear iteration
+ while( (*node_it)!=n_t )
+ {
+ ++node_it;
+ assert(iter.top().get_node()->end()!=node_it);
+ }
+ iter.top().get_node()->erase(node_it);
+ }
+
+ void swap(type &other)
+ {
+ std::swap(other.node_root,node_root);
+ }
iterator begin() const
{
@@ -402,6 +455,7 @@
}
return cur;
}
+
bool exist(const key_type &key) const //make this iterator instead of bool;
{
typename Key_traits::const_iterator it=Key_traits::begin(key),