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

From: abir basak (abirbasak_at_[hidden])
Date: 2007-02-19 01:38:52

shunsuke wrote:
> abir basak wrote:
>> Hi,
>>    I am having a few containers whose some portion I want to refer to 
>> another class (sometime I need to refer to a continuous portion, while 
>> sometime need a non-continuous portion) .
>>    At present I have written all of these myself. But wondering if a few 
>> portion can be substituted by some boost library.
>>
>> Just to make the concept clear, I am elaborating the structure and why 
>> it is done in that way.
>> In the program it takes the user handwriting (as entered using digital 
>> pen etc) and analysis them.
>> as user writes, I register points (x,y coord) and put them in an deque 
>> (in actual case I am using boost::circular_buffer_space_optimized ).
>>
>> Now, a second deque (or other container) stores another structure Trace, 
>> which has 2 index pointing start & end of that continuous writing until 
>> pen up occurs. These have to be 2 index rather than iterator, as 
>> iterator may get (and usually gets ) invalidated while more points are 
>> added in the point deque.  Thus Trace refers deque<Point>
>> Now from the trace structure I return the points for the trace 
>> (boost::sub_range ) using the 2 index and the deque (i.e from 
>> deque<Point> get iterator, add index as offset , make sub_range and 
>> return).
>> Now these are the continues portions , referred by 2 index.
>> Next, some such things can be even not continuous. In that case I store 
>> all index to which it points (in a vector ) and return a sub_range kind 
>> of structure (named index_range ) which takes these index and a 
>> container, and iterates over it jumping by those specific offsets.
>>
>> Example can be a Character class which refers some of those traces , not 
>> necessarily continuous (like user writes a dot much later than the i , 
>> thus Character i contains index of the vertical stroke of the i & dot )
>>
>> Similarly more hierarchy are constructed, like Trace => Page, and 
>> Character => Word => Line => Paragraph => Page etc.
>>
>> Most of them contains 2 index and with the help of the container returns 
>>   a boost sub_range , while some contains a vector of index (size_t) and 
>> returns index_range (created by me) .
>>
>> So far I found it is the ONLY way to create a level of hierarchy/ view 
>> from different set of dynamic data. (The other can be storing everything 
>>   as a pointer in the container, and creating by new, in that case no 
>> problem arises as the objects are not movable, but in C++ it is quite 
>> bad solution)
>>
>> A Graphical representation is like,
>> =============== deque<Point> =====================
>> <=remove old data             => add new data
>> |  1 |  2   | 3    | 4   | 5   | 6   | 7  | 8   |
>> =============== deque<Trace> ====================
>> |    1                    |          2          |
>> =============== deque<Page> =====================
>>
>> These are for continuous data (i.e 2 index struct & boost::sub_range )
>>
>> ================ deque<Trace> ====================
>> |1,3,4|  2 | 5,6 | 7,9 | 8 | ...
>> ================== deque<Character> ===============
>> | 1,2,4, 5 | 3 | ....
>> ================== deque<Word> =====================
>> | 1 | 2 | 3 | .... (assuming past a line user doesn't correct word, they 
>> can be made a pair of index ! )
>> ================== deque<Line> =====================
>> ....
>> ================== deque<Paragraph> ================ etc...
>>
>>   My question ,
>> 1) had anyone faced these kind of design , where a class referrers a 
>> portion of STL container ? and multiple view from same set of data 
>> exists (otherwise I could had Trace contains the points , instead of 
>> having index of the portion, if Trace is the only view for the points )
>>
>> 2) Any boost library / other library is there to help these kind of 
>> design ?
>>
>> I had posted a same kind of topic in C++ newsgroup also, but it seems 
>> their people are more concerned with answering C++ standard based 
>> question . I think, boost may be the better news group to ask this 
>> question, as boosters work in a broader area.
>>
>> Thanks to all, esp to those who share their thought on it ...
>> abir
>>
> 
> Though I can't understand exactly what you mean because of my poor english,
> I guess the solution is polymorphic range, which is the 'iterator_range'
> of 'any_iterator'?
> 
> Assume 'make_xxx' returns 'iterator_range' of 'xxx_iterator'.
> 
>      deque<any_range> traces;
>      traces.push_back(make_counting(1, 5)); // continuous (light-weight)
>      traces.push_back(an_index_range); // non-continuous (needs its own
> storage)
> 
>      Draw( make_permutation(points, traces[0]) );
>      Draw( make_permutation(points, traces[1]) );
> 
> If my guess is right, I'll specify urls of 'any_iterator' implementations.
> 
> Regards,
> 
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 ?
2) a library like index_range, which hops over a container (random 
access preferably ) adding an user specified offset to the iterator 
position
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 ....

and sorry for being late, I was out of station for last 2 days ...

any help or suggestion is appreciated ...

-- 
Abir Basak, Member IEEE
B. Tech, IIT Kharagpur
email: abir_at_[hidden]
homepage: www.abirbasak.com