Hello Joachim, ----- Original Message ----- From: "Joachim Faulhaber" <afojgo@googlemail.com> To: <boost@lists.boost.org> Sent: Saturday, May 17, 2008 4:16 AM Subject: Re: [boost] proposal: interval containers
2008/5/16, vicente.botet <vicente.botet@wanadoo.fr>:
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.
You are welcome and thanks for all your explanations. I would like to use a set implemented with interval_set. This was on my todo list for a locally unique identifier library.
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.
No problem.
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.
Could you be exhaustive with the functions not implemented? In addition there are the template parameters for comparator and allocator that don't mach.
(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.
As the base classes are not public you have the choice between not implementing them, use policies, or even better use mixins, which will give you the impresion of virtual functions.
(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.)
OK, I understand.
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.
Yes, this should be possible.
* 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.
Do you need this polymorphism now?
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.
Please consider the possibility to use mixins.
* 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
This is not a reason your library should not work for boost::intervals. If interval_set works for any kind of intervals, why should not work for closed intervals?
As I've read in the archives an extension for open interval bounds have been suggested for boost::interval in the past.
It will be a good thing to see how to extend the interval library to manage with open boundaries and continuous semanstics. Why not make a separated proposal for intervals?
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 ;)
You are right. This is the nice feature.
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.
If I can give you a first guide, follow the directory structure boost/itl for the public files boost/itl/detail for non public files libs/itl/src for the implementation libs/itl/example libs/itl/test This will help a lot on how to read your code.
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
This was a sage decision. I'm not sure which could be consequences to give to the find function a intersection semantic. I need to think more on that.
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.
First of all I think that interval_set<interval<T>> must not provide the interface of set<T>. I can be used to implement the interface of set<T>.
The closest one can provide is an iterator that points to the interval containing the value or end(), if such interval does not exist.
You can use a use the same technique used by bitset. The iterator is a proxy that contains the iterator to the interval and the current value. Evidently this not work for continuous types.
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?
Maybe ^= could b an option. As is the case for stl::bitset and boost::dynamic_bitset a|b union a&b intersection a^b difference a^b symetric difference ~a not a|=b inplace union a&=b inplace intersection a-=b inplace difference a^=b inplace symetric difference Otherwise you can use /,and /= for symetric difference
split_interval_set: split_interval_set works like interval_set but borders of the inserted intervals are preserved, so it can be used as time grid. Using itl::split_interval_set you can partition other interval containers using the *= operator to perform intersections.
Please could you clarify me. Which are the difference between split_interval_set <interval<T> > and set<interval<T> >? Best regards Vicente Botet