Definition
An instance S of the parameterized data type interval_set<I> is a
collection of items (
is
item). Every item in S contains a closed
interval of the double numbers as key and an information from data type I,
called the information type of S. The number of items in S is called
the size of S. An interval set of size zero is said to be empty. We use
< x, y, i > to denote the item with interval [x, y] and information i;
x (y) is called the left (right) boundary of the item. For each
interval [x, y] there is at most one item
< x, y, i >
S.
#include < LEDA/geo/interval_set.h >
Creation
Operations
Implementation
Interval sets are implemented by two-dimensional range trees [90,57]. Operations insert, lookup, del_item and del take time O(log2n), intersection takes time O(k + log2n), where k is the size of the returned list. Operations left, right, inf, empty, and size take time O(1), and clear O(n log n). Here n is always the current size of the interval set. The space requirement is O(n log n).