range-set-list-0.1.3: Memory efficient sets with ranges of elements.

Copyright(c) Oleg Grenrus 2014
LicenseMIT
Maintaineroleg.grenrus@iki.fi
Stabilityexperimental
Portabilitynon-portable (tested with GHC only)
Safe HaskellSafe
LanguageHaskell2010

Data.RangeSet.List

Contents

Description

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.

Synopsis

Range set type

data RSet a Source #

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

Instances

Eq a => Eq (RSet a) Source # 

Methods

(==) :: RSet a -> RSet a -> Bool #

(/=) :: RSet a -> RSet a -> Bool #

Ord a => Ord (RSet a) Source # 

Methods

compare :: RSet a -> RSet a -> Ordering #

(<) :: RSet a -> RSet a -> Bool #

(<=) :: RSet a -> RSet a -> Bool #

(>) :: RSet a -> RSet a -> Bool #

(>=) :: RSet a -> RSet a -> Bool #

max :: RSet a -> RSet a -> RSet a #

min :: RSet a -> RSet a -> RSet a #

Show a => Show (RSet a) Source # 

Methods

showsPrec :: Int -> RSet a -> ShowS #

show :: RSet a -> String #

showList :: [RSet a] -> ShowS #

(Ord a, Enum a) => Semigroup (RSet a) Source # 

Methods

(<>) :: RSet a -> RSet a -> RSet a #

sconcat :: NonEmpty (RSet a) -> RSet a #

stimes :: Integral b => b -> RSet a -> RSet a #

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

Methods

mempty :: RSet a #

mappend :: RSet a -> RSet a -> RSet a #

mconcat :: [RSet a] -> RSet a #

NFData a => NFData (RSet a) Source # 

Methods

rnf :: RSet a -> () #

Hashable a => Hashable (RSet a) Source # 

Methods

hashWithSalt :: Int -> RSet a -> Int #

hash :: RSet a -> Int #

Operators

(\\) :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a infixl 9 Source #

O(n+m). See difference.

Query

null :: RSet a -> Bool Source #

O(1). Is this the empty set?

isFull :: (Eq a, Bounded a) => RSet a -> Bool Source #

O(1). Is this the full set?

size :: Enum a => RSet a -> Int Source #

O(n). The number of the elements in the set.

member :: Ord a => a -> RSet a -> Bool Source #

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

notMember :: Ord a => a -> RSet a -> Bool Source #

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

lookupLT :: (Ord a, Enum a) => a -> RSet a -> Maybe a Source #

O(n). Find largest element smaller than the given one.

lookupGT :: (Ord a, Enum a) => a -> RSet a -> Maybe a Source #

O(n). Find smallest element greater than the given one.

lookupLE :: Ord a => a -> RSet a -> Maybe a Source #

O(n). Find largest element smaller or equal to than the given one.

lookupGE :: Ord a => a -> RSet a -> Maybe a Source #

O(n). Find smallest element greater or equal to than the given one.

containsRange :: Ord a => (a, a) -> RSet a -> Bool Source #

O(n). Is the entire range contained within the set?

isSubsetOf :: Ord a => RSet a -> RSet a -> Bool Source #

O(n+m). Is this a subset? (s1 isSubsetOf s2) tells whether s1 is a subset of s2.

valid :: (Ord a, Enum a, Bounded a) => RSet a -> Bool Source #

O(n). Ensure that a set is valid. All functions should return valid sets except those with unchecked preconditions: fromAscList, fromNormalizedRangeList

Construction

empty :: RSet a Source #

O(1). The empty set.

full :: Bounded a => RSet a Source #

O(1). The full set.

singleton :: a -> RSet a Source #

O(1). Create a singleton set.

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

O(1). Create a continuos range set.

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

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

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

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

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

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

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

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

Combine

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

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

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

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

intersection :: Ord a => RSet a -> RSet a -> RSet a Source #

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

Filter

split :: (Ord a, Enum a) => a -> RSet a -> (RSet a, RSet a) Source #

O(n). The expression (split x set) is a pair (set1,set2) where set1 comprises the elements of set less than x and set2 comprises the elements of set greater than x.

splitMember :: (Ord a, Enum a) => a -> RSet a -> (RSet a, Bool, RSet a) Source #

O(n). Performs a split but also returns whether the pivot element was found in the original set.

Min/Max

findMin :: RSet a -> a Source #

O(1). The minimal element of a set.

findMax :: RSet a -> a Source #

O(n). The maximal element of a set.

Complement

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

O(n). Complement of the set.

Conversion

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

O(n*r). An alias of toAscList. The elements of a set in ascending order. r is the size of longest range.

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

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 Source #

O(n*log n). Create a set from a list of elements.

fromAscList :: (Ord a, Enum a) => [a] -> RSet a Source #

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

The precondition is not checked. You may use valid to check the result.

toAscList :: Enum a => RSet a -> [a] Source #

O(n*r). Convert the set to an ascending list of elements.

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

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

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

O(n*log n). Create a set from a list of range pairs.

fromNormalizedRangeList :: [(a, a)] -> RSet a Source #

O(1). Convert a normalized, non-adjacent, ascending list of ranges to a set.

The precondition is not checked. In general you should only use this function on the result of toRangeList or ensure valid on the result.

toSet :: Enum a => RSet a -> Set a Source #

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