Copyright | (c) Sam T. 2013 |
---|---|

License | BSD3 |

Maintainer | pxqr.sta@gmail.com |

Stability | experimental |

Portability | portable |

Safe Haskell | None |

Language | Haskell98 |

An efficient implementation of dense integer sets based on Big-Endian PATRICIA trees with buddy suffix compression.

References:

- Fast Mergeable Integer Maps (1998) by Chris Okasaki, Andrew Gill http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452

This implementation performs espessially well then set contains
long integer invervals like `[0..2047]`

that are just merged into
one interval description. This allow to perform many operations
in constant time and space. However if set contain sparse
integers like `[1,12,7908,234,897]`

the same operations will take
*O(min(W, n))* which is good enough in most cases.

Conventions in complexity notation:

n — number of elements in a set;

- W — number bits in a
`Key`

. This is 32 or 64 at 32 and 64 bit platforms respectively; - O(n) or O(k) — means this operation have complexity O(n) in worst case (e.g. sparse set) or O(k) in best case (e.g. one single interval).

- W — number bits in a

Note that some operations will take centuries to compute. For
exsample `map id universe`

will never end as well as `filter`

applied to `universe`

, `naturals`

, `positives`

or `negatives`

.

Also note that some operations like `union`

, `intersection`

and
`difference`

have overriden from default fixity, so use these
operations with infix syntax carefully.

- data IntSet
- type Key = Int
- null :: IntSet -> Bool
- size :: IntSet -> Int
- member :: Key -> IntSet -> Bool
- notMember :: Key -> IntSet -> Bool
- isSubsetOf :: IntSet -> IntSet -> Bool
- isSupersetOf :: IntSet -> IntSet -> Bool
- empty :: IntSet
- singleton :: Key -> IntSet
- interval :: Key -> Key -> IntSet
- insert :: Key -> IntSet -> IntSet
- delete :: Key -> IntSet -> IntSet
- map :: (Key -> Key) -> IntSet -> IntSet
- foldr :: (Key -> a -> a) -> a -> IntSet -> a
- filter :: (Key -> Bool) -> IntSet -> IntSet
- split :: Key -> IntSet -> (IntSet, IntSet)
- splitGT :: Key -> IntSet -> IntSet
- splitLT :: Key -> IntSet -> IntSet
- partition :: (Key -> Bool) -> IntSet -> (IntSet, IntSet)
- findMin :: IntSet -> Key
- findMax :: IntSet -> Key
- union :: IntSet -> IntSet -> IntSet
- unions :: [IntSet] -> IntSet
- intersection :: IntSet -> IntSet -> IntSet
- intersections :: [IntSet] -> IntSet
- difference :: IntSet -> IntSet -> IntSet
- symDiff :: IntSet -> IntSet -> IntSet
- data Union
- data Intersection
- data Difference
- elems :: IntSet -> [Key]
- toList :: IntSet -> [Key]
- fromList :: [Key] -> IntSet
- toAscList :: IntSet -> [Key]
- toDescList :: IntSet -> [Key]
- fromAscList :: [Key] -> IntSet

# Types

Integer set.

Bin !Prefix !Mask !IntSet !IntSet | Layout: prefix up to branching bit, mask for branching bit, left subtree and right subtree. IntSet = Bin: contains elements of left and right subtrees thus just merge to subtrees. All elements of left subtree is less that from right subtree. Except non-negative numbers, they are in left subtree of root bin, if any. |

Tip !Prefix !BitMap | Layout: Prefix up to IntSet = Tip: contains elements |

Fin !Prefix !Mask | Layout: Prefix up to IntSet = Fin: contains all elements from prefix to (prefix - mask - 1) |

Nil | Empty set. Contains nothing. |

# Query

## Cardinality

## Membership

member :: Key -> IntSet -> Bool Source

*O(min(W, n))* or *O(1)*.
Test if the value is element of the set.

notMember :: Key -> IntSet -> Bool Source

*O(min(W, n))* or *O(1)*.
Test if the value is not an element of the set.

## Inclusion

isSubsetOf :: IntSet -> IntSet -> Bool Source

*O(n + m)* or *O(1)*. Test if the second set contain each element
of the first.

isSupersetOf :: IntSet -> IntSet -> Bool Source

*O(n + m)* or *O(1)*. Test if the second set is subset of the
first.

# Construction

interval :: Key -> Key -> IntSet Source

*O(n)*. Set containing elements from the specified range.

interval a b = fromList [a..b]

# Modification

# Map Fold Filter

map :: (Key -> Key) -> IntSet -> IntSet Source

*O(n * min(W, n))*.
Apply the function to each element of the set.

Do not use this operation with the `universe`

, `naturals`

or
`negatives`

sets.

foldr :: (Key -> a -> a) -> a -> IntSet -> a Source

*O(n)*. Fold the element using the given right associative
binary operator.

filter :: (Key -> Bool) -> IntSet -> IntSet Source

*O(n)*. Filter all elements that satisfy the predicate.

Do not use this operation with the `universe`

, `naturals`

or
`negatives`

sets.

# Splits

split :: Key -> IntSet -> (IntSet, IntSet) Source

*O(min(W, n)*. Split the set such that the left projection of the
resulting pair contains elements less than the key and right
element contains greater than the key. The exact key is excluded
from result:

split 5 (fromList [0..10]) == (fromList [0..4], fromList [6..10])

Performance note: if need only lesser or greater keys, use splitLT or splitGT respectively.

splitGT :: Key -> IntSet -> IntSet Source

*O(min(W, n)*. Takes subset such that each element is greater
than the specified key. The exact key is excluded from result.

splitLT :: Key -> IntSet -> IntSet Source

*O(min(W, n)*. Takes subset such that each element is less
than the specified key. The exact key is excluded from result.

partition :: (Key -> Bool) -> IntSet -> (IntSet, IntSet) Source

*O(n)*. Split a set using given predicate.

forall f. fst . partition f = filter f forall f. snd . partition f = filter (not . f)

# Min/Max

findMin :: IntSet -> Key Source

*O(min(W, n))* or *O(1)*. Find minimal element of the set.
If set is empty then min is undefined.

findMax :: IntSet -> Key Source

*O(min(W, n))* or *O(1)*. Find maximal element of the set.
Is set is empty then max is undefined.

# Combine

union :: IntSet -> IntSet -> IntSet infixl 6 Source

*O(n + m)* or *O(1)*. Find set which contains elements of both
right and left sets.

intersection :: IntSet -> IntSet -> IntSet infixl 7 Source

*O(n + m)* or *O(1)*. Find maximal common subset of the two given
sets.

intersections :: [IntSet] -> IntSet Source

*O(max(n) * spine)* or *O(spine)*.
Find out common subset of the list of sets.

difference :: IntSet -> IntSet -> IntSet infixl 6 Source

*O(n + m)* or *O(1)*. Find difference of the two sets.

symDiff :: IntSet -> IntSet -> IntSet Source

*O(n + m)* or *O(1)*. Find symmetric difference of the two sets:
resulting set containts elements that either in first or second
set, but not in both simultaneous.

## Monoids

data Intersection Source

Monoid under `intersection`

.

data Difference Source

Monoid under `symDiff`

.

Don't mix up `symDiff`

with `difference`

.

# Conversion

### Arbitary

fromList :: [Key] -> IntSet Source

*O(n * min(W, n))* or *O(n)*.
Create a set from a list of its elements.

### Ordered

toAscList :: IntSet -> [Key] Source

*O(n)*.
Convert the set to a list of its element in ascending order.

toDescList :: IntSet -> [Key] Source

*O(n)*.
Convert the set to a list of its element in descending order.

fromAscList :: [Key] -> IntSet Source

Build a set from an ascending list of elements.