diet-0.0.1: Discrete Interval Encoding Tree

Data.Set.Diet

Description

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

Synopsis

# Documentation

data Interval a Source

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 aSource

An interval with the same minimum and maximum.

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

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

intervalMin :: Interval a -> aSource

The minimum of the interval.

intervalMax :: Interval a -> aSource

The maximum of the interval.

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

Merge two intervals if they are overlapping or adjacent.

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

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

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

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

data Diet a Source

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 -> BoolSource

Test for membership in the interval tree.

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

Test for non-membership in the interval tree.

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

Insert an element into the interval tree.

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

Delete an element from the interval tree.

Construct an interval tree with no elements.

single :: a -> Diet aSource

Construct an interval tree with a single element.

singleI :: Interval a -> Diet aSource

Construct an interval tree with a single interval.

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

Return the number of elements in the interval tree.

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

Fold on the interval tree.

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

Return all elements of the interval tree as a list.

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

Construct an interval tree with the elements of the list.

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

Map a function across the interval tree.