<alex.fishman@gmail.comwrote:
Quote:
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<Interval MyIntervals;
// Add elements to list:
MyIntervals.push_back(Interval(1,3));
MyIntervals.push_back(Interval(7,32));
MyIntervals.push_back(Interval(13, -74));
// Remove all instances of (7,32) from list:
MyIntervals.remove(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.sort()
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<Interval 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::multiset" 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/ 
