Boost logo

Boost :

Subject: Re: [boost] [Boost-users] [boost-users][ICL] ICL Compilation errors. Ticket #5207
From: John Reid (j.reid_at_[hidden])
Date: 2011-02-24 08:14:25


On 24/02/11 11:42, Joachim Faulhaber wrote:
> (2) Generalization of "find" in the Set view and the STL/iterator view.
>
> 2011/2/23 John Reid<j.reid_at_[hidden]>:
>> On 22/02/11 20:03, Joachim Faulhaber wrote:
>>>
>>> 2011/2/22 John Reid<j.reid_at_[hidden]>
>>>>
>>>
>>> interval_map::find is a pretty late addition to ITL/ICL, because using
>>> find in the STL way makes little sense on interval containers most of
>>> the time. We can not "find" an large interval in an icl::interval_set
>>> of small intervals.
>>>
>>> {[0,2),[5,7)}.find([0,9))

Now I'm a bit confused, I thought when you said 'We can not "find" an
large interval' you meant the following isn't supported:

        namespace icl = ::boost::icl;
        typedef float type_;
        icl::interval_set< type_ > set;
        set.add( icl::interval< type_ >::type( 0, 2 ) );
        set.add( icl::interval< type_ >::type( 5, 7 ) );
        set.find( icl::interval< type_ >::type( 0, 9 ) );

but it does compile just fine.

>>
>> If we cannot find the large interval, isn't the end() iterator a suitable
>> return value to suggest it was not in the set/map?
>
> This is a question of design decisions of course. On the one hand I
> view intervals as Sets and also interval_set implements Set. (Capital
> S for concept Set). In this view, it is unusual to ask whether a set
> is found in a set, because one is not intended to be the element of
> the other. I this view (the Set view) we can achieve everything we
> need using predicates
>
> contains, intersects
>
> and functions
>
> add_intersection,&= and& (intersection)
> http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/boost_icl/function_reference/intersection.html
>
> On the other hand, but with a lower priority in my design, I am
> supporting functions using iterators that are common to STL containers
> and that will be expected by users.
>
> 'find' is only defined on element_types, because only element can be
> "found" in sets. All functionality related to a "generalized find" in
> the STL/iterator related view can be provided by the member functions
> lower_bound, upper_bound and equal_range that are common to STL
> interfaces of associative containers:
> http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/boost_icl/function_reference/iterator_related.html
>
> Here is some code for clarification:
>
> BOOST_AUTO_TEST_CASE(generalized_find)
> {
> typedef icl::interval_set<int>::iterator int_set_iterator;
> icl::interval_set<int> int_set;
>
> icl::interval<int>::type to_be_found(1,5);
> int_set += icl::interval<int>::type(0,2);
> int_set += icl::interval<int>::type(4,7);
> int_set += icl::interval<int>::type(8,9);
>
> int_set_iterator found;
> found = int_set.lower_bound(to_be_found);
> cout<< *found<< endl; // [0,2)
> found = int_set.upper_bound(to_be_found);
> cout<< *found<< endl; // [8,9)
> std::pair<int_set_iterator,int_set_iterator> exterior;
> exterior = int_set.equal_range(to_be_found);
> cout<< "["<< *exterior.first
> << ","<< *exterior.second<< ")"<< endl;
> // [[0,2),[8,9))
> }
>
> It's good you brought up this question, so I could clarify the design
> decisions here.
>

Now are you saying I should use something like the generalized find
above or that the example I gave above should work?

Thanks for taking the time to answer this and my other questions.

Regards,
John.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk