Re: [Boost-users] [boost][boost-users][ICL] ICL Compilation errors. Ticket #5207

Subject: Re: [Boost-users] [boost][boost-users][ICL] ICL Compilation errors. Ticket #5207
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2011-02-24 06:42:41

(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))
>
> 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.

Thanks,
Joachim

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de