stl container for interval data type

[alex.fishman]

Hi,

I need to implement a container for integer intervals, something that
looks like (1,5), (10,20), (4,7), etc. The container has to be of the
following properties: search for an arbitratry interval for
intersection in O(log n) or O(1) if possible, insert and delete in
O(log n).
Does this sound simple? Is there any reference implementation that I
can look at?

-Alex

[Luke Meyers]

al**********@gm ail.com wrote:

I need to implement a container for integer intervals, something that
looks like (1,5), (10,20), (4,7), etc. The container has to be of the
following properties: search for an arbitratry interval for
intersection in O(log n) or O(1) if possible, insert and delete in
O(log n).
Does this sound simple? Is there any reference implementation that I
can look at?

It sounds vaguely like homework, but not necessarily, so...

....actually, would be a great interview question, too. But anyway...

....I don't think any of the standard library containers are a
particularly good fit for this problem. However, I can see
representing this quite nicely as a binary tree. I actually
implemented something very similar a few months ago. Basically think
of the tree as a bitset, where if a bit is set it means the
corresponding integer is in the interval. When a whole subtree is the
same, you don't actually need nodes for it -- just interpret null
children as being all the same as their parent. The neat part (though
a bit tricky to implement) is that you can flip a whole subtree by
toggling a single bit. The reason it's tricky is worrying about all
those possibly-flipped bits when interpreting the contents of the tree.
I've done it, it's workable, it's not the only approach but it's an
interesting one. I suspect that most practical solutions to this
problem will revolve in some way around a binary tree.

Luke

[Robbie Hatley]

<al**********@g mail.comwrote:

I need to implement a container for integer intervals, something that
looks like (1,5), (10,20), (4,7), etc. The container has to be of the
following properties: search for an arbitratry interval for
intersection in O(log n) or O(1) if possible, insert and delete in
O(log n).
Does this sound simple? Is there any reference implementation that I
can look at?

I'm not sure what you mean by "interval for intersection"; can you
elaborate?

I do have a couple of ideas for you, though:
// ======= APPROACH #1: =============== =============== =========

// Make a list of ordered pairs of integers:
typedef std::pair<int, intInterval;
std::list<Inter val MyIntervals;

// Add elements to list:
MyIntervals.pus h_back(Interval (1,3));
MyIntervals.pus h_back(Interval (7,32));
MyIntervals.pus h_back(Interval (13, -74));

// Remove all instances of (7,32) from list:
MyIntervals.rem ove(Interval(7, 32));

I can't swear as to the exact speed of this, but it's fast.
Insertions and deletions will be quite fast.

Drawbacks: it allows intervals such as (13,-74) which are mal-formed
according to usual mathematical convention. You'd have to manually
disallow adding such intervals to the container if you don't want
that. There may also be an issue trying to do MyIntervals.sor t()
if a suitable version of "<" is not available; you'd have to look
into that.

Advantages: ultra-simple; ready to go out of the box with no
modification; fast insertion, deletion.

Research "std::list" and "std::pair" for more info.
// ======= Approach #2: =============== =============== ===========

If you want to prohibit duplicate intervals,
use a std::set instead of a std::list, like so:

typedef std::pair<int, intInterval;
std::set<Interv al MyIntervals;

Advantages: Uniqueness of elements (if that's what you want);
blazing-fast lookup (uses binary trees).

Disadvantages: Might be a bit trickier to work with than lists
or other "ordinary" containers, do to the uniqueness requirement.

Research "std::set" for more info.
// ======= Approach #3: =============== =============== ==========

Same as above, but using std::multiset instead of std::set.
This allows multiple copies of an interval such as (5,7),
if you want to allow that. Research "std::multi set" for more
info.
--
Cheers,
Robbie Hatley
Tustin, CA, USA
lonewolfintj at pacbell dot net
(put "[usenet]" in subject to bypass spam filter)
http://home.pacbell.net/earnur/

[n2xssvv g02gfr12930]

al**********@gm ail.com wrote:

Hi,

I need to implement a container for integer intervals, something that
looks like (1,5), (10,20), (4,7), etc. The container has to be of the
following properties: search for an arbitratry interval for
intersection in O(log n) or O(1) if possible, insert and delete in
O(log n).
Does this sound simple? Is there any reference implementation that I
can look at?

-Alex

Most implementations of STL map use an RB, (Red Black), tree which have
an insertion and deletion operation worse case of O(log n) and a search
operation with a worse case of O(h) where h is the height of the tree.
Unless there's some other trick you can use on the data I doubt you'll
find a better solution. Hopefully you'll find this to be the best
solution, being easy with STL map and hence not requiring a lot of coding.

JB