[Boost-commit] svn:boost r46186 - sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch

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),