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