Data.Set.Diet

Discrete Interval Encoding Tree described by Martin Erwig in Diets for Fat Sets, January 1993.

Documentation

data Interval a

An interval with discrete values between.

Instances

Eq a => Eq (Interval a)

(Eq (Interval a), Ord a) => Ord (Interval a)

(Eq a, Show a) => Show (Interval a)

point :: a -> Interval a

An interval with the same minimum and maximum.

interval :: Ord a => a -> a -> Interval a

Construct an interval ensuring that the minimum is less than or equal to maximum.

intervalMin :: Interval a -> a

The minimum of the interval.

intervalMax :: Interval a -> a

The maximum of the interval.

mergeI :: (Ord a, Enum a) => Interval a -> Interval a -> Maybe (Interval a)

Merge two intervals if they are overlapping or adjacent.

isPointed :: Eq a => Interval a -> Bool

Returns whether or not the interval has the same minimum and maximum.

mapI :: Ord b => (a -> b) -> Interval a -> Interval b

Map a function across the minimum and maximum of the interval.

data Diet a

A Discrete Interval Encoding Tree.

Instances

Eq a => Eq (Diet a)

(Eq (Diet a), Ord a) => Ord (Diet a)

(Eq a, Show a) => Show (Diet a)

member :: Ix a => a -> Diet a -> Bool

Test for membership in the interval tree.

notMember :: Ix a => a -> Diet a -> Bool

Test for non-membership in the interval tree.

insert :: (Ord a, Enum a) => a -> Diet a -> Diet a

Insert an element into the interval tree.

delete :: (Ord a, Enum a) => a -> Diet a -> Diet a

Delete an element from the interval tree.

empty :: Diet a

Construct an interval tree with no elements.

single :: a -> Diet a

Construct an interval tree with a single element.

singleI :: Interval a -> Diet a

Construct an interval tree with a single interval.

size :: Ix a => Diet a -> Int

Return the number of elements in the interval tree.

diet :: (b -> Interval a -> b -> b) -> b -> Diet a -> b

Fold on the interval tree.

toList :: Ix a => Diet a -> [a]

Return all elements of the interval tree as a list.

fromList :: (Foldable t, Ord a, Enum a) => t a -> Diet a

Construct an interval tree with the elements of the list.

mapD :: Ord b => (a -> b) -> Diet a -> Diet b

Map a function across the interval tree.