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

From: chintanraoh_at_[hidden]
Date: 2008-08-28 23:02:19

Author: chintanraoh
Date: 2008-08-28 23:02:18 EDT (Thu, 28 Aug 2008)
New Revision: 48435
URL: http://svn.boost.org/trac/boost/changeset/48435

Log:
detail folder
Added:
   sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/
   sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/pat_key_traits.hpp   (contents, props changed)
   sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_details.hpp   (contents, props changed)
   sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_iterator.hpp   (contents, props changed)

Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/pat_key_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/pat_key_traits.hpp	2008-08-28 23:02:18 EDT (Thu, 28 Aug 2008)
@@ -0,0 +1,119 @@
+#ifndef BOOST_DSEARCH_PAT_KEY_TRAITS_HPP
+#define BOOST_DSEARCH_PAT_KEY_TRAITS_HPP
+
+#include<string>
+#include<vector>
+
+namespace boost{
+namespace dsearch{
+
+
+///key traits describing extra traits required for patricia.
+class pat_string_traits {
+	public:
+	/// element type = unsigned type. \n
+	/// each element in string (ie char) should correspond to element_type.
+	/// ie unsigned char.
+	typedef unsigned char  element_type ; 
+	/// Const_iterator used by patricia to iterate through elements. 
+	/// It can be forward or random access.
+	typedef std::string::const_iterator const_iterator ;
+	
+	/// Returns the begin iterator of a key.
+	/**
+	 	\returns const_iterator positioned at begining of the string.
+	 	\param key whose begin is to found
+	 */
+	static inline const_iterator begin (std::string const &key)
+	{
+		return key.begin();
+	}
+	
+	/// Returns the end of a key.
+	/**
+		\returns const_iterator positioned at the end.
+		\param key whose end is to found
+	 */
+	static inline const_iterator end (std::string const &key)
+	{
+		return key.end();
+	}
+
+	/// Returns the size of the key.
+	/**
+		\returns size of the key.
+		\param key whose size is to found
+	 */
+	static inline std::size_t size(std::string const &key)
+	{
+		return key.size();
+	}
+	
+	/// Deference iterator to corresponding element_type , ie unsigned type.
+	/**
+		\returns unsigned integer of element_type corresponding to the iterator.
+		\param it: iterator corresponding to which element_type if to be found
+	 */
+	static inline element_type  get_element(const const_iterator &it) 
+	{
+		return static_cast<unsigned char>(*it);
+	}
+	
+};
+
+///vector key triats class.
+template<typename type>
+class pat_vector_traits {
+	public:
+	/// element type = unsigned type. \n
+	typedef unsigned int  element_type ; 
+	/// Const_iterator used by patricia to iterate through elements. 
+	/// It can be forward or random access.
+	typedef typename std::vector<type>::const_iterator const_iterator ;
+
+	/// Returns the begin iterator of a key.
+	/**
+	 	\returns const_iterator positioned at begining of the string.
+	 	\param key whose begin is to found
+	 */
+	static inline const_iterator begin ( std::vector<type> const &key )
+	{
+		return key.begin();
+	}
+	
+	/// Returns the end of a key.
+	/**
+		\returns const_iterator positioned at the end.
+		\param key whose end is to found
+	 */
+	static inline const_iterator end (std::vector<type> const &key)
+	{
+		return key.end();
+	}
+
+	/// Returns the size of the key.
+	/**
+		\returns size of the key.
+		\param key whose size is to found
+	 */
+	static inline std::size_t size(std::vector<type> const &key)
+	{
+		return key.size();
+	}
+	
+	/// Deference iterator to corresponding element_type , ie unsigned type.
+	/**
+		\returns unsigned integer of element_type corresponding to the iterator.
+		\param it: iterator corresponding to which element_type if to be found
+	 */
+	static inline element_type  get_element(const const_iterator &it) 
+	{
+		return static_cast<unsigned int>(*it);
+	}
+};
+
+}
+}
+
+#endif //BOOST_DSEARCH_PAT_KEY_TRAITS_HPP
+

Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_details.hpp
==============================================================================

Added: sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/digital_searching/dsearch/boost/dsearch/details/patricia_iterator.hpp	2008-08-28 23:02:18 EDT (Thu, 28 Aug 2008)
@@ -0,0 +1,304 @@
+#ifndef BOOST_DSEARCH_PATRICIA_ITERATOR_HPP
+#define BOOST_DSEARCH_PATRICIA_ITERATOR_HPP
+#include<boost/iterator/iterator_facade.hpp>
+#include<boost/utility/enable_if.hpp>
+#include<boost/type_traits/is_convertible.hpp>
+
+namespace boost{
+namespace dsearch{
+
+///iterator for patricia
+/**
+ \param Value_type is patricia::value_type 
+ \param Node_type is patricia::patricia_node
+ \param Alloc is the allocator
+ */
+template<class Value_type, class Node_type, class Alloc>
+class patricia_iterator
+:public iterator_facade< patricia_iterator<Value_type,Node_type, Alloc>, 
+Value_type, bidirectional_traversal_tag >
+{
+	template<class K,class M,class K_t,class A > friend class patricia;
+	protected:
+	///empty struct used for avoiding conversion from const_iterator to iterator
+	struct enabler {};
+	friend class boost::iterator_core_access;
+	///Pointer to prev node . usually cur->left or cur->right ==next
+	/// if cur ! = NULL.  if cur==NULL then next==root.
+	Node_type *cur;
+	///Node to which the iterator points to. 
+	Node_type *next;
+	
+	///increments the iterator.
+	virtual void increment()
+	{
+		if (cur)
+		{
+			//*move up if cur->right===next
+			while ( cur && ( cur->right==next || cur->right==0) )
+			{
+				next=cur;
+				cur=cur->par;
+			}
+			if ( cur == 0) return; //* reached end()
+			next=cur->right; //* also cur->right!=0
+		}
+		else
+		{
+			//* next == root and now we are moving to the begin()
+			cur=next;
+			next=(cur->left)?cur->left:cur->right;
+		}
+
+		//* go down the least element in the edge
+		while ( next && next->index > cur->index )
+		{
+			cur=next;
+			next=cur->left?cur->left:cur->right;
+		}
+	}
+	
+	///decrements the iterator.
+	virtual void decrement()
+	{
+		if(cur)
+		{
+			//*move up if cur->left===next
+			while(cur && ( cur->left==next || cur->left==0 ) )
+			{
+				next=cur;
+				cur=cur->par;
+			}
+			if(cur==0)
+				//* reached before begin()
+				return;
+			//* also cur->left!=0
+			next=cur->left;
+		}
+		else
+		{
+			//* next == root and now we are moving to the end() - 1
+			cur=next;
+			next=(cur->right==0)?cur->left:cur->right;
+		}
+
+		//* go down the greatest element in the edge
+		while ( next && next->index > cur->index )
+		{
+			cur=next;
+			next=cur->right?cur->right:next=cur->left;
+		}
+	}
+	
+	///dereferences the iterator.
+	Value_type &dereference() const
+	{
+		assert(cur); //dont reference null;
+		return next->value;
+	}
+	
+	///check whether two iterator are equal.
+	/**
+	 	\returns true if the iterator are equal otherwise false.
+	 	\param other is other iterator which is supposed to compared to this.
+	 */
+	template<class V,class N,class A>
+	bool equal(patricia_iterator<V,N,A> const &other) const
+	{
+	#ifdef PAT_DEBUG
+		std::cout<<cur << " " << other.cur << " " << next  << 
+		" "<< other.next << std::endl;
+	#endif
+		if ( cur == other.cur && next == other.next )
+			return true;
+		return false;
+	}
+
+	private:
+	///move to the right most node of the edge cur<-->next
+	void to_right_most()
+	{
+		assert(cur);
+		while(next->par==cur)
+		{
+			cur=next;
+			next=cur->right?cur->right:cur->left;
+		}
+	}
+	
+	private:
+	///move to the left most node of the edge cur<-->next
+	void to_left_most()
+	{
+		assert(cur);
+		while(next->par==cur)
+		{
+			cur=next;
+			next=cur->left?cur->left:cur->right;
+			//std::cout<<"To left most"<<cur->value.first<<"<-"<<next->value.first<<std::endl;
+		}
+	#ifdef PAT_DEBUG
+		std::cout<<"To left most"<<cur->value.first<<"<-"<<next->value.first<<std::endl;
+	#endif
+	}
+
+	public:
+	///default constructor
+	patricia_iterator() : cur(0),next(0)
+	{
+	}
+
+	///use to intialize begin or end.
+	/**
+	 	\param root is the patricia's root node
+	 	\param start specifies start or end
+	 */
+	patricia_iterator(Node_type *root, bool start)
+	{
+		if(start)
+		{
+			if(root==0) 
+			{
+				std::cout<<"root is zero"<<std::endl;
+				cur=0;
+				next=0;
+				return;
+			}
+			//*move to the left most wrt root.
+			cur=root;
+			next= (cur->left)?cur->left:cur->right;
+			assert(next!=0);
+			while ( cur->index < next->index )
+			{
+				cur=next;
+				next=cur->left?cur->left:cur->right;
+			}
+		}
+		else
+		{
+			next=root;
+			cur=0;
+		}
+		return;
+	}
+
+	///copy constructor for the iterator
+	/**
+	 \brief is_covertible ensures that const_iterator cannot be converted 
+	 to iterator
+	 \param other is the iterator to be copied
+	 */
+	template<class V,class N,class A>
+	patricia_iterator ( patricia_iterator<V,N,A> const& other,
+				typename enable_if< is_convertible<V*,Value_type*>, 
+				enabler >::type = enabler()
+		    		) : cur(other.cur),next(other.next)
+	{
+	}
+	
+	///initialize the iterator by specifying the edge using found and prev.
+	/**
+	 \param found is the node whihc the iterator points to
+	 \param prev  is node such that prev->left==found or prev->right==found
+	 */ 
+	patricia_iterator (Node_type* found,Node_type *prev):
+	cur(prev),next(found)
+	{
+	}
+};
+
+///reverse iterator for the patricia node
+/**
+ \param Value_type is patricia::value_type 
+ \param Node_type is patricia::patricia_node
+ \param Alloc is the allocator
+ */
+template<class Value_type, class Node_type, class Alloc >
+class patricia_reverse_iterator:
+public patricia_iterator<Value_type, Node_type, Alloc>
+{
+	friend class patricia_iterator<Value_type, Node_type, Alloc>;
+	///the patricia_iterator super class
+	typedef patricia_iterator<Value_type, Node_type, Alloc> forward_type;
+	private:
+	///empty struct used for conversion from const_iterator to iterator
+	struct enabler {};
+	
+	///decrements to reverse_iterator
+	void decrement()
+	{
+		forward_type::increment();
+	}
+	
+	///increments the reverse_iterator
+	void increment()
+	{
+		forward_type::decrement();
+	}
+
+	///check whether two reverse iterator are equal.
+	/**
+	 	\returns true if the reverse iterator are equal otherwise false.
+	 	\param other is other reverse iterator which is supposed to compared to this.
+	 */
+	template<class V,class N,class A>
+	bool equal(patricia_reverse_iterator<V,N,A> const &other) const
+	{
+		if ( forward_type::cur == other.cur && forward_type::next == other.next )
+			return true;
+		
+		return false;
+	}
+	
+	///dereferences the iterator
+	Value_type &dereference() const
+	{
+		return forward_type::dereference();
+	}
+
+	public:
+	///default constructor
+	patricia_reverse_iterator(): forward_type()
+	{
+	}
+
+	///initialize the iterator by specifying the edge using found and prev.
+	/**
+	 \param found is the node whihc the iterator points to
+	 \param prev  is node such that prev->left==found or prev->right==found
+	 */ 
+	patricia_reverse_iterator(Node_type *found,Node_type*prev)
+	:forward_type(found,prev)
+	{
+	}
+
+	///use to intialize begin or end.
+	/**
+	 	\param root is the patricia's root node
+	 	\param start specifies start or end
+	 */
+	patricia_reverse_iterator(Node_type *root,bool start) : forward_type(root,false)
+	{
+		if(start && root!=0)
+			forward_type::decrement();
+	}
+	///copy constructor for reverse the iterator
+	/**
+	 \brief is_covertible ensures that const_reverse_iterator cannot be converted 
+	 to reverse_iterator
+	 \param other is the iterator to be copied
+	 */
+	template<class V,class N,class A>
+	patricia_reverse_iterator ( patricia_reverse_iterator<V,N,A> const& other,
+				typename enable_if< is_convertible<V*,Value_type*>, 
+				enabler >::type = enabler()
+		    		)
+	: forward_type(other.next,other.cur)
+	{
+	}
+
+};
+
+}
+}
+#endif //BOOST_DSEARCH_PATRICIA_ITERATOR_HPP