Parsley.Internal.Common.RangeSet

This module contains the implementation of an efficient set for contiguous data. It has a much smaller memory footprint than a Set, and can result in asymptotically faster operations.

Since: 2.1.0.0

Documentation

data RangeSet a

A Set type designed for types that are Enum as well as Ord. This allows the RangeSet to compress the data when it is contiguous, reducing memory-footprint and enabling otherwise impractical operations like complement for Bounded types.

Since: 2.1.0.0

Constructors

Fork !Int !Size !a !a !(RangeSet a) !(RangeSet a)

Tip

Instances

Eq a => Eq (RangeSet a)

Defined in Parsley.Internal.Common.RangeSet

Methods

(==) :: RangeSet a -> RangeSet a -> Bool

(/=) :: RangeSet a -> RangeSet a -> Bool

Show a => Show (RangeSet a)

Defined in Parsley.Internal.Common.RangeSet

Methods

showsPrec :: Int -> RangeSet a -> ShowS

show :: RangeSet a -> String

showList :: [RangeSet a] -> ShowS

empty :: RangeSet a

The empty RangeSet.

Since: 2.1.0.0

singleton :: a -> RangeSet a

A RangeSet containing a single value.

Since: 2.1.0.0

null :: RangeSet a -> Bool

Is this set empty?

Since: 2.1.0.0

full :: (Eq a, Bounded a) => RangeSet a -> Bool

Is this set full?

Since: 2.1.0.0

isSingle :: RangeSet a -> Bool

Does this set contain a single element?

Since: 2.1.0.0

extractSingle :: Eq a => RangeSet a -> Maybe a

Possibly extract the element contained in the set if it is a singleton set.

Since: 2.1.0.0

size :: RangeSet a -> Int

Return the number of elements in the set.

Since: 2.1.0.0

sizeRanges :: RangeSet a -> Int

Return the number of contiguous ranges that populate the set.

Since: 2.1.0.0

member :: forall a. Ord a => a -> RangeSet a -> Bool

Test whether or not a given value is found within the set.

Since: 2.1.0.0

notMember :: Ord a => a -> RangeSet a -> Bool

Test whether or not a given value is not found within the set.

Since: 2.1.0.0

findMin :: RangeSet a -> Maybe a

This deletes the right-most range of the tree. It *must not* be used with an empty tree.

Find the minimum value within the set, if one exists.

Since: 2.1.0.0

findMax :: RangeSet a -> Maybe a

Find the maximum value within the set, if one exists.

Since: 2.1.0.0

insert :: forall a. (Enum a, Ord a) => a -> RangeSet a -> RangeSet a

Insert a new element into the set.

Since: 2.1.0.0

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

Remove an element from the set, if it appears.

Since: 2.1.0.0

union :: (Enum a, Ord a) => RangeSet a -> RangeSet a -> RangeSet a

Unions two sets together such that if and only if an element appears in either one of the sets, it will appear in the result set.

Since: 2.1.0.0

intersection :: (Enum a, Ord a) => RangeSet a -> RangeSet a -> RangeSet a

Intersects two sets such that an element appears in the result if and only if it is present in both of the provided sets.

Since: 2.1.0.0

difference :: (Enum a, Ord a) => RangeSet a -> RangeSet a -> RangeSet a

Removes all elements from the first set that are found in the second set.

Since: 2.1.0.0

disjoint :: (Enum a, Ord a) => RangeSet a -> RangeSet a -> Bool

Do two sets have no elements in common?

Since: 2.1.0.0

complement :: forall a. (Bounded a, Enum a, Eq a) => RangeSet a -> RangeSet a

Inverts a set: every value which was an element is no longer an element, and every value that was not an element now is. This is only possible on Bounded types.

Since: 2.1.0.0

isSubsetOf :: (Enum a, Ord a) => RangeSet a -> RangeSet a -> Bool

Tests if all the elements of the first set appear in the second.

Since: 2.1.0.0

isProperSubsetOf :: (Enum a, Ord a) => RangeSet a -> RangeSet a -> Bool

Tests if all the element of the first set appear in the second, but also that the first and second sets are not equal.

Since: 2.1.0.0

allLess :: (Enum a, Ord a) => a -> RangeSet a -> RangeSet a

Filters a set by removing all values greater than or equal to the given value.

Since: 2.1.0.0

allMore :: (Enum a, Ord a) => a -> RangeSet a -> RangeSet a

Filters a set by removing all values less than or equal to the given value.

Since: 2.1.0.0

elems :: Enum a => RangeSet a -> [a]

Returns all the elements found within the set.

Since: 2.1.0.0

unelems :: (Bounded a, Enum a, Eq a) => RangeSet a -> [a]

Returns all the values that are not found within the set.

Since: 2.1.0.0

fromRanges :: (Enum a, Ord a) => [(a, a)] -> RangeSet a

Constructs a RangeSet given a list of ranges.

Since: 2.1.0.0

insertRange :: (Enum a, Ord a) => a -> a -> RangeSet a -> RangeSet a

Inserts a range into a RangeSet.

Since: 2.1.0.0

fromList :: (Enum a, Ord a) => [a] -> RangeSet a

Builds a RangeSet from a given list of elements.

Since: 2.1.0.0

fold

Arguments

:: (a -> a -> b -> b -> b)

Function that combines the lower and upper values (inclusive) for a range with the folded left- and right-subtrees.

-> b

Value to be substituted at the leaves.

-> RangeSet a

-> b

Folds a range set.

Since: 2.1.0.0