From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2008-05-16 22:16:35
2008/5/16, vicente.botet <vicente.botet_at_[hidden]>:
> Hello,
>
> I'm mainly interested in an implementation of set<T> using set<interval<T>
> and on how it comapres to the stl::set in space and time, when the set are
> dense or scattered.
>
> I have just take a look to the documentation and the implementation, and I
> have some questions?
Thank you for looking at my code. I am quite thrilled to get so many
good responses.
Let me note, before answering your questions, that I followed the
boost advice from the web page to post suggestions *before* investing
work on adjusting or producing library code to conform the boost
standards and requirements, in order to avoid unnecessary work.
I know the library might not conform some boost requirements yet, but
I am of course happy to adjust the code and design if there is
significant interest in my work.
To keep the text simple I will talk mostly of sets and interval_sets,
when I want to say things about sets/maps and
interval_sets/interval_maps because most statements apply to both.
> * Why not follow the STL set and map interfaces as far as possible?
I intended to follow the STL and there is a large set of functions and
operators common to std::set/map and itl::interval_sets/maps. But
there are differences
also.
(1) One very interesting point is that interval_sets in the design presented
do have a twofold character. An interval_set is intended to implement
set. Yet at the same time it is a set of intervals. So the question
how a function like e.g.
find should be implemented has no obvious answer.
(2) In my design I am exploiting concepts (Inplace)Addable and
(Inplace)Subtractable in many ways. That is I do rely on the existence
of a += operator for almost all and -= for many datatypes in my
library. So I have added +=, -= and also *= (intersection) to
interval_set/map. A propagation of += and -= through container
operations is a core element of my design and a base of the useful
'aggregate on overlap' (aggrovering;) mechanics of interval_maps.
(see examples party and history from http://sourceforge.net/projects/itl.)
I have defined o= operators as memberfunctions because this seemed
natural to me. But I think the whole library can be easily refactored,
making them global function templates.
> * Why do you use virtual functions? Are the classes sets, and
> interval_base_set public? I think this can and should be avoided.
The original design was classical OO-design, defining an interface
class that allows different implementations being used uniformly by a
weak polymophic interfacepointer. Furthermore there is a body of
baseclass functions that are common to interval_set and
split_interval_set. They only vary in the handling of interval
borders. This has been expressed by basecalss interval_base_set,
interitence and a virtual function 'handle_neighbours'.
All those virtual functions can be devirtualized without problems. The
interface class templates can be omitted and handle_neighbours might
be expressed via a policy template parameter.
> * Does it works with boost::interval?
>
Unfortunately not. Interval containers rely on the notion of open
interval bounds. This was necessary to express operations for
flotingpoint numbers:
interval_set<double> is;
is.insert([1,pi)); is.insert([pi,4]); // is=={[1,4]} merging INTENDED
is.insert([1,pi)); is.insert((pi,4]); // is=={[1,pi), (pi,4]} must not merge
As I've read in the archives an extension for open interval bounds
have been suggested for boost::interval in the past.
> > The benefits of interval sets and maps are
> > 1. The implementation of sets/maps via interval_set/map is very
> > space and also time efficient.
>
> Have you done some messures, in space and time? In the worst case {1, 11,
> 21...}?
>
Not yet. Space can be reckoned easily. Wost case is that every
interval inserted has exactly one value element x per interval [x,x].
In this case you have double data content and one byte extra for
borderinformation so roughly 2 times the space of stl::set.
The 'nice' case is that you can represent a set of uncountable values like
{[0.0, pi)} quite compact ;)
>
> Do you plan to boostify your code?
>
I would very much like to boostify the code. I admit thou that I am
not yet familiar with all of the boostification ;) I hope guidance
will be provided.
> I'm no sure interval_set is a model of Unique Associative Container.
>
> Given the following :
> interval_set<int> is; //not quite: interval_set<interval<int>> is;
> is.insert([1,3));
> is.insert([3,5));
>
> What is the result of
> assert(find([1,3))!= end);
> And of
> assert(find([1,5))== end);
>
I thought about find more than twice and decided not to provide it.
You can say
interval_set<int> found;
is.intersect(found, rightopen_interval([1,5]); // Intersect to find contents
As interval_set<T> implements set<T> if find is implemented it should
deliver an iterator pointing to a value, but such iterators are not
available. The closest one can provide is an iterator that points to
the interval containing the value or end(), if such interval does not
exist.
> I'm no sure interval_set is a model of Unique Associative Container.
No, I'm afraid it is not.
> Which operator would you use for set_symmetric_difference? This is a detail
> but it will be better to provided the function version of this operators as
> well.
don't know, probably function name. Are there boost suggestions for that?
>
> > split_interval_map:
> > A split_interval_map implements a map as a map of intervals
> > and associated values. For dealing with the insertion
> > of overlapping intervals the principle of "aggregation on
> > overlap" has proved to be very useful: It is shown by example:
> >
> > typedef set<string> guests;
> > split_interval_map<time, guests> party;
> > guests mary; mary.insert("Mary");
> > guests harry; harry.insert("Harry");
> > party.insert(make_pair(rightopen_interval(20:00, 22:00), mary));
> > party.insert(make_pair(rightopen_interval(21:00, 23:00), harry));
> > // party now contains
> > [20:00, 21:00)->{"Mary"}
> > [21:00, 22:00)->{"Harry","Mary"} //guest sets aggregated on overlap
> > [22:00, 23:00)->{"Harry"}
> >
> > As can be seen from the example a split_interval_map has both
> > a decompositional behavior (on the time dimension) as well as
> > a accumulative one (on the associated values).
>
> Quite interesting!
>
> > Quality, validation, portability:
> >
> > The library code of the itl has been validated with a law based
> > test automaton (LaBatea;) which is included in
> > the current release. It includes a testcase generator and law tester
> > that checks laws like e.g. commutativity<interval_set<double>, +=>:
> > the commutativity of interval_set<double> w.r.t. the operation +=.
> >
> > The code has been compiled and tested with three compilers
> > (gcc 3.4.4, conceptgcc-boostcon, msvc 8.0 sp1) and with three
> > implementations of the stl (linux/gnu, stlport, msvc8) under
> > suse linux 10.1. and ms-windows xp.
>
> > I'd be happy if you found interval conainers as presented in this
> > post an interesting contribution to look at.
>
> I'm sure that this library will be a good candidate to boost.
>
> > If so, I am looking forward to an inspiring discussion.
>
> Best regards
>
> Vicente Botet
>
Thank you for your good questions and valuable feedback on my work.
Best regards
Joachim Faulhaber