Re: [Boost-users] any boost library for referring a portion of the container ?

From: shunsuke (pstade.mb_at_[hidden])
Date: 2007-02-19 04:23:24

abir basak wrote:
> It is better if I try to post some code to show what I exactly trying to do.
> ( I am trying to capture digital pen input and create a hierarchical
> structure from it )
> ///This is a range (2 point index, which can create 2 iterators with the
> ///help of the container, I am using  boost::sub_range for that )
> typedef std::pair<std::size_t,std::size_t> range_t;
> 
> ///This is a multi index range allows iterate over a few specific index
> ///on a container , used with my index_range and container. (for 
> ///simplicity now it uses vector, it can be any container )
> typedef std::vector<size_t> index_t;
> 
> ///The index range. iterates over the specific position on the container
> ///a simplified version to show the concept. It has const correctness
> ///and all other functions that sub_range has. It takes container &
> ///index vector unlike iterators in boost::sub_range.
> template<typename C>	
> class index_range{
> public:
> 	typedef C container_type;
> 	typedef typename C::iterator iterator;
> 	typedef typename C::reference reference;
> 	typedef typename C::pointer pointer;
> 	typedef typename C::size_type size_type;
> private:
>    index_t index_;
> 	C& c_;
> 	size_type pos_;
> public:	
> 	index_range(C& c,index_t index) : c_(c),index_(index) , pos_(0){}
> 	size_type size()const { return index_.size();}
> 	reference operator[](size_type pos) { return c_[ index_[pos] ] };
> 	reference front() { return c_[index_[0] ] ;}
> 	reference back() { return c_[index_[size()-1]] ; }
> 	reference operator++(){
> 		return c_[index_ [ pos_ ++] ] ;
> 	}
> };
> ///The point comes as user input through digital pen
> struct point{
> 	int x;
> 	int y;
> 	point(int _x,int _y) : x(_x),y(_y){}
> };
> typedef std::deque<point> point_buffer;
> typedef boost::sub_range<point_buffer> point_range;
> 
> ///The buffer of points.
> point_buffer points; 	
> 
> ///trace a continuous user writing, until pen up. points a portion
> ///of point_buffer
> struct trace{
> 	range_t range;
> 	point_range get_points() {
> 		return
> boost::make_iterator_range(points.begin()+range.first,points.begin()+range.second);
> 	}
> };
> 
> typedef std::deque<trace> trace_buffer;
> typedef boost::sub_range<trace_buffer> trace_range;
> typedef index_range<trace_buffer> trace_index_range;
> ///buffer for traces.
> trace_buffer traces;
> 
> ///a page contains a set of traces.
> struct page{
> 	range_t range;
> 	trace_range get_traces(){
> 		return
> boost::make_iterator_range(traces.begin()+range.first,traces.begin()+range.second);
> 	}
> };
> 
> ///a word contains a few discrete traces, may not be continuous to
> ///represent by 2 index. But 2 word may not contain same trace. i.e
> ///common way of writing, but 2 or more character may contain same trace
> //(like cursive writing)
> struct word{
> 	index_t index;
> 	trace_index_range get_traces(){
>      return index_range<trace_buffer>(traces,index);
> 	}
> };
> A few additional things do happen, like each container keeps track of 
> how many elements had been removed, to translate properly from  index to 
> iterator.
> 
> So there are 3 library I am searching,
> 1) Index -> iterator , and iterator -> index conversion
> (I know that 2 famous facts in STL that iterator doesn't know container 
> and their position, but that is only applicable for pointers . There is 
> no harm to know this facts from iterator. and thus some library can do 
> to-from conversion between iterator & index position , or better 
> sub_range & pair<index_t,index_t> any library ?

Boost has 'counting_iterator'.
http://www.boost.org/libs/iterator/doc/counting_iterator.html
You can call 'counting_iterator::base()' if you want the 'index'.

> 2) a library like index_range, which hops over a container (random 
> access preferably ) adding an user specified offset to the iterator 
> position

Boost has 'permutation_iterator'.
http://www.boost.org/libs/iterator/doc/permutation_iterator.html
Unfortunately, 'boost::permutation_iterator' cannot work with
'boost::counting_iterator', hence requires a patch something like this..
http://tinyurl.com/35qkzw

> 3) an utility which allows to refer a portion (or some portions ) of a 
> container to be stored ( i.e store by index & return by iterator ) 
> inside another class , using the above two library ....

If you take the portions represented by different types into
a single deque, Dr.Becker's 'any_iterator' is a candidate.
http://thbecker.net/free_software_utilities/type_erasure_for_cpp_iterators/start_page.html

Well, you have to make a range by using these iterators,
because Boost doesn't have the range wrappers yet.
It would be something like this.. http://tinyurl.com/38474e

Finally, I've written everything noted above. :-)
http://tinyurl.com/2o2mnv

Regards,

-- 
Shunsuke Sogame