Data.RangeSet.List

A trivial implementation of range sets.

This module is intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

  import Data.RangeSet.List (RSet)
  import qualified Data.RangeSet.List as RSet

The implementation of RSet is based on list.

Compared to Set, this module imposes also Enum restriction for many functions. We must be able to identify consecutive elements to be able to glue and split ranges properly.

The implementation assumes that

 x < succ x
 pred x < x

and there aren't elements in between (not true for Float and Double). Also succ and pred are never called for largest or smallest value respectively.

Range set type

data RSet a

Internally set is represented as sorted list of distinct inclusive ranges.

Instances

Eq a => Eq (RSet a)

Ord a => Ord (RSet a)

Show a => Show (RSet a)

(Ord a, Enum a) => Monoid (RSet a)

Operators

(\\) :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a

O(n+m). See difference.

Query

null :: RSet a -> Bool

O(1). Is this the empty set?

member :: (Ord a, Enum a) => a -> RSet a -> Bool

O(n). Is the element in the set?

notMember :: (Ord a, Enum a) => a -> RSet a -> Bool

O(n). Is the element not in the set?

Construction

empty :: RSet a

O(1). The empty set.

full :: Bounded a => RSet a

O(1). The full set.

singleton :: a -> RSet a

O(1). Create a singleton set.

singletonRange :: Ord a => (a, a) -> RSet a

O(1). Create a continuos range set.

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

O(n). Insert an element in a set.

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

O(n). Insert a continuos range in a set.

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

/O(n). Delete an element from a set.

deleteRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a

/O(n). Delete a continuos range from a set.

Combine

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

O(n*m). The union of two sets.

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

O(n*m). Difference of two sets.

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

O(n*m). The intersection of two sets.

Complement

complement :: (Ord a, Enum a, Bounded a) => RSet a -> RSet a

O(n). Complement of the set.

Conversion

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

O(n*r). Convert the set to a list of elements. r is the size of longest range.

toList :: Enum a => RSet a -> [a]

O(n*r). Convert the set to a list of elements. r is the size of longest range.

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

O(n^2). Create a set from a list of elements.

toRangeList :: RSet a -> [(a, a)]

O(1). Convert the set to a list of range pairs.

fromRangeList :: (Ord a, Enum a) => [(a, a)] -> RSet a

O(n^2). Create a set from a list of range pairs.