Copyright | (c) Christoph Breitkopf 2015 |
---|---|

License | BSD-style |

Maintainer | chbreitkopf@gmail.com |

Stability | experimental |

Portability | non-portable (MPTC with FD) |

Safe Haskell | Safe |

Language | Haskell98 |

An implementation of sets of intervals. The intervals may overlap, and the implementation contains efficient search functions for all intervals containing a point or overlapping a given interval. Closed, open, and half-open intervals can be contained in the same set.

It is an error to insert an empty interval into a set. This precondition is not checked by the various construction functions.

Since many function names (but not the type name) clash with
*Prelude* names, this module is usually imported `qualified`

, e.g.

import Data.IntervalSet.Strict (IntervalSet) import qualified Data.IntervalSet.Strict as IS

It offers most of the same functions as `Set`

, but the member type must be an
instance of `Interval`

. The `findMin`

and `findMax`

functions deviate from their
set counterparts in being total and returning a `Maybe`

value.
Some functions differ in asymptotic performance (for example `size`

) or have not
been tuned for efficiency as much as their equivalents in `Set`

.

In addition, there are functions specific to sets of intervals, for example to search for all intervals containing a given point or contained in a given interval.

The implementation is a red-black tree augmented with the maximum upper bound of all keys.

Parts of this implementation are based on code from the `Map`

implementation,
(c) Daan Leijen 2002, (c) Andriy Palamarchuk 2008.
The red-black tree deletion is based on code from llrbtree by Kazu Yamamoto.
Of course, any errors are mine.

- class Ord e => Interval i e | i -> e where
- data IntervalSet k
- = Nil
- | Node !Color !k !k !(IntervalSet k) !(IntervalSet k)

- (\\) :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k
- null :: IntervalSet k -> Bool
- size :: IntervalSet k -> Int
- member :: Ord k => k -> IntervalSet k -> Bool
- notMember :: Ord k => k -> IntervalSet k -> Bool
- containing :: Interval k e => IntervalSet k -> e -> IntervalSet k
- intersecting :: Interval k e => IntervalSet k -> k -> IntervalSet k
- within :: Interval k e => IntervalSet k -> k -> IntervalSet k
- empty :: IntervalSet k
- singleton :: k -> IntervalSet k
- insert :: (Interval k e, Ord k) => k -> IntervalSet k -> IntervalSet k
- delete :: (Interval k e, Ord k) => k -> IntervalSet k -> IntervalSet k
- union :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k
- unions :: (Interval k e, Ord k) => [IntervalSet k] -> IntervalSet k
- difference :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k
- intersection :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k
- map :: (Interval a e1, Interval b e2, Ord b) => (a -> b) -> IntervalSet a -> IntervalSet b
- mapMonotonic :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalSet k1 -> IntervalSet k2
- foldr :: (k -> b -> b) -> b -> IntervalSet k -> b
- foldl :: (b -> k -> b) -> b -> IntervalSet k -> b
- foldl' :: (b -> k -> b) -> b -> IntervalSet k -> b
- foldr' :: (k -> b -> b) -> b -> IntervalSet k -> b
- elems :: IntervalSet k -> [k]
- toList :: IntervalSet k -> [k]
- fromList :: (Interval k e, Ord k) => [k] -> IntervalSet k
- toAscList :: IntervalSet k -> [k]
- toDescList :: IntervalSet k -> [k]
- fromAscList :: (Interval k e, Eq k) => [k] -> IntervalSet k
- fromDistinctAscList :: Interval k e => [k] -> IntervalSet k
- filter :: Interval k e => (k -> Bool) -> IntervalSet k -> IntervalSet k
- partition :: Interval k e => (k -> Bool) -> IntervalSet k -> (IntervalSet k, IntervalSet k)
- split :: (Interval i k, Ord i) => i -> IntervalSet i -> (IntervalSet i, IntervalSet i)
- splitMember :: (Interval i k, Ord i) => i -> IntervalSet i -> (IntervalSet i, Bool, IntervalSet i)
- isSubsetOf :: Ord k => IntervalSet k -> IntervalSet k -> Bool
- isProperSubsetOf :: Ord k => IntervalSet k -> IntervalSet k -> Bool
- findMin :: IntervalSet k -> Maybe k
- findMax :: IntervalSet k -> Maybe k
- findLast :: Interval k e => IntervalSet k -> Maybe k
- deleteMin :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k
- deleteMax :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k
- deleteFindMin :: (Interval k e, Ord k) => IntervalSet k -> (k, IntervalSet k)
- deleteFindMax :: (Interval k e, Ord k) => IntervalSet k -> (k, IntervalSet k)
- minView :: (Interval k e, Ord k) => IntervalSet k -> Maybe (k, IntervalSet k)
- maxView :: (Interval k e, Ord k) => IntervalSet k -> Maybe (k, IntervalSet k)
- valid :: (Interval i k, Ord i) => IntervalSet i -> Bool

# re-export

class Ord e => Interval i e | i -> e where Source

Intervals with endpoints of type `e`

.
A minimal instance declaration for a closed interval needs only
to define `lowerBound`

and `upperBound`

.

lowerBound :: i -> e Source

lower bound

upperBound :: i -> e Source

upper bound

leftClosed :: i -> Bool Source

Does the interval include its lower bound? Default is True for all values, i.e. closed intervals.

rightClosed :: i -> Bool Source

Does the interval include its upper bound bound? Default is True for all values, i.e. closed intervals.

before :: i -> i -> Bool Source

Interval strictly before another? True if the upper bound of the first interval is below the lower bound of the second.

after :: i -> i -> Bool Source

Interval strictly after another? Same as 'flip before'.

subsumes :: i -> i -> Bool Source

Does the first interval completely contain the second?

overlaps :: i -> i -> Bool Source

Do the two intervals overlap?

below :: e -> i -> Bool Source

Is a point strictly less than lower bound?

above :: e -> i -> Bool Source

Is a point strictly greater than upper bound?

inside :: e -> i -> Bool Source

Does the interval contain a given point?

Is the interval empty?

# Set type

data IntervalSet k Source

A set of intervals of type `k`

.

Nil | |

Node !Color !k !k !(IntervalSet k) !(IntervalSet k) |

Foldable IntervalSet Source | |

Eq k => Eq (IntervalSet k) Source | |

Ord k => Ord (IntervalSet k) Source | |

(Ord k, Read k, Interval i k, Ord i, Read i) => Read (IntervalSet i) Source | |

Show k => Show (IntervalSet k) Source | |

(Interval i k, Ord i) => Monoid (IntervalSet i) Source | |

NFData k => NFData (IntervalSet k) Source |

# Operators

(\\) :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k infixl 9 Source

Same as `difference`

.

# Query

null :: IntervalSet k -> Bool Source

*O(1)*. Is the set empty?

size :: IntervalSet k -> Int Source

*O(n)*. Number of keys in the set.

Caution: unlike `size`

, this takes linear time!

member :: Ord k => k -> IntervalSet k -> Bool Source

*O(log n)*. Does the set contain the given value? See also `notMember`

.

notMember :: Ord k => k -> IntervalSet k -> Bool Source

*O(log n)*. Does the set not contain the given value? See also `member`

.

## Interval query

containing :: Interval k e => IntervalSet k -> e -> IntervalSet k Source

Return the set of all intervals containing the given point.

*O(n)*, since potentially all intervals could contain the point.
*O(log n)* average case. This is also the worst case for sets containing no overlapping intervals.

intersecting :: Interval k e => IntervalSet k -> k -> IntervalSet k Source

Return the set of all intervals overlapping (intersecting) the given interval.

*O(n)*, since potentially all values could intersect the interval.
*O(log n)* average case, if few values intersect the interval.

within :: Interval k e => IntervalSet k -> k -> IntervalSet k Source

Return the set of all intervals which are completely inside the given interval.

*O(n)*, since potentially all values could be inside the interval.
*O(log n)* average case, if few keys are inside the interval.

# Construction

empty :: IntervalSet k Source

*O(1)*. The empty set.

singleton :: k -> IntervalSet k Source

*O(1)*. A set with one entry.

## Insertion

insert :: (Interval k e, Ord k) => k -> IntervalSet k -> IntervalSet k Source

*O(log n)*. Insert a new value. If the set already contains an element equal to the value,
it is replaced by the new value.

## Delete/Update

delete :: (Interval k e, Ord k) => k -> IntervalSet k -> IntervalSet k Source

*O(log n)*. Delete an element from the set. If the set does not contain the value,
it is returned unchanged.

# Combine

union :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k Source

*O(n+m)*. The expression (

) takes the left-biased union of `union`

t1 t2`t1`

and `t2`

.
It prefers `t1`

when duplicate elements are encountered.

unions :: (Interval k e, Ord k) => [IntervalSet k] -> IntervalSet k Source

difference :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k Source

*O(n+m)*. Difference of two sets.
Return elements of the first set not existing in the second set.

intersection :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k -> IntervalSet k Source

*O(n+m)*. Intersection of two sets.
Return elements in the first set also existing in the second set.

# Traversal

## Map

map :: (Interval a e1, Interval b e2, Ord b) => (a -> b) -> IntervalSet a -> IntervalSet b Source

*O(n log n)*. Map a function over all values in the set.

The size of the result may be smaller if `f`

maps two or more distinct
elements to the same value.

mapMonotonic :: (Interval k2 e, Ord k2) => (k1 -> k2) -> IntervalSet k1 -> IntervalSet k2 Source

*O(n)*.

, but works only when `mapMonotonic`

f s == `map`

f s`f`

is strictly monotonic.
That is, for any values `x`

and `y`

, if `x`

< `y`

then `f x`

< `f y`

.
*The precondition is not checked.*

## Fold

foldr :: (k -> b -> b) -> b -> IntervalSet k -> b Source

foldl :: (b -> k -> b) -> b -> IntervalSet k -> b Source

foldl' :: (b -> k -> b) -> b -> IntervalSet k -> b Source

*O(n)*. A strict version of `foldl`

. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.

foldr' :: (k -> b -> b) -> b -> IntervalSet k -> b Source

*O(n)*. A strict version of `foldr`

. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.

# Conversion

elems :: IntervalSet k -> [k] Source

*O(n)*. List of all values in the set, in ascending order.

## Lists

toList :: IntervalSet k -> [k] Source

*O(n)*. The list of all values in the set, in no particular order.

fromList :: (Interval k e, Ord k) => [k] -> IntervalSet k Source

*O(n log n)*. Build a set from a list of elements. See also `fromAscList`

.
If the list contains duplicate values, the last value is retained.

## Ordered lists

toAscList :: IntervalSet k -> [k] Source

*O(n)*. The list of all values contained in the set, in ascending order.

toDescList :: IntervalSet k -> [k] Source

*O(n)*. The list of all values in the set, in descending order.

fromAscList :: (Interval k e, Eq k) => [k] -> IntervalSet k Source

*O(n)*. Build a set from an ascending list in linear time.
*The precondition (input list is ascending) is not checked.*

fromDistinctAscList :: Interval k e => [k] -> IntervalSet k Source

*O(n)*. Build a set from an ascending list of distinct elements in linear time.
*The precondition is not checked.*

# Filter

filter :: Interval k e => (k -> Bool) -> IntervalSet k -> IntervalSet k Source

*O(n)*. Filter values satisfying a predicate.

partition :: Interval k e => (k -> Bool) -> IntervalSet k -> (IntervalSet k, IntervalSet k) Source

*O(n)*. Partition the set according to a predicate. The first
set contains all elements that satisfy the predicate, the second all
elements that fail the predicate. See also `split`

.

split :: (Interval i k, Ord i) => i -> IntervalSet i -> (IntervalSet i, IntervalSet i) Source

*O(n)*. The expression (

) is a pair `split`

k set`(set1,set2)`

where
the elements in `set1`

are smaller than `k`

and the elements in `set2`

larger than `k`

.
Any key equal to `k`

is found in neither `set1`

nor `set2`

.

splitMember :: (Interval i k, Ord i) => i -> IntervalSet i -> (IntervalSet i, Bool, IntervalSet i) Source

*O(n)*. The expression (

) splits a set just
like `splitMember`

k set`split`

but also returns

.`member`

k set

# Subset

isSubsetOf :: Ord k => IntervalSet k -> IntervalSet k -> Bool Source

*O(n+m)*.

isProperSubsetOf :: Ord k => IntervalSet k -> IntervalSet k -> Bool Source

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).

# Min/Max

findMin :: IntervalSet k -> Maybe k Source

*O(log n)*. Returns the least interval in the set.

findMax :: IntervalSet k -> Maybe k Source

*O(log n)*. Returns the largest interval in the set.

findLast :: Interval k e => IntervalSet k -> Maybe k Source

Returns the interval with the largest endpoint. If there is more than one interval with that endpoint, return the rightmost.

*O(n)*, since all intervals could have the same endpoint.
*O(log n)* average case.

deleteMin :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k Source

*O(log n)*. Remove the smallest element from the set. Return the empty set if the set is empty.

deleteMax :: (Interval k e, Ord k) => IntervalSet k -> IntervalSet k Source

*O(log n)*. Remove the largest element from the set. Return the empty set if the set is empty.

deleteFindMin :: (Interval k e, Ord k) => IntervalSet k -> (k, IntervalSet k) Source

*O(log n)*. Delete and return the smallest element.

deleteFindMax :: (Interval k e, Ord k) => IntervalSet k -> (k, IntervalSet k) Source

*O(log n)*. Delete and return the largest element.

minView :: (Interval k e, Ord k) => IntervalSet k -> Maybe (k, IntervalSet k) Source

*O(log n)*. Retrieves the minimal element of the set, and
the set stripped of that element, or `Nothing`

if passed an empty set.

maxView :: (Interval k e, Ord k) => IntervalSet k -> Maybe (k, IntervalSet k) Source

*O(log n)*. Retrieves the maximal element of the set, and
the set stripped of that element, or `Nothing`

if passed an empty set.