-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Pure, fast and memory efficient integer sets. -- -- This library provides persistent, time and space efficient integer -- sets implemented as dense big-endian patricia trees with buddy -- suffixes compaction. In randomized settings this structure expected to -- be as fast as Data.IntSet from containers, but if a sets is likely to -- have long continuous intervals it should be much faster. -- -- -- -- @package intset @version 0.1.0.1 -- | Fast conversion from or to lazy and strict bytestrings. Serialized -- IntSets are represented as single continious bitmap. -- -- This module is kept separated due safe considerations. module Data.IntervalSet.ByteString -- | Unpack IntSet from bitmap. fromByteString :: ByteString -> IntSet -- | Pack the IntSet as bitmap to the strict bytestring. -- -- NOTE: negative elements are ignored! toByteString :: IntSet -> ByteString -- | An efficient implementation of dense integer sets based on Big-Endian -- PATRICIA trees with buddy suffix compression. -- -- References: -- -- -- -- 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: -- -- -- -- 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. module Data.IntervalSet -- | Integer set. data 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. Bin :: {-# UNPACK #-} !Prefix -> {-# UNPACK #-} !Mask -> !IntSet -> !IntSet -> IntSet -- | Layout: Prefix up to mask of bitmap size, and bitmap containing -- elements starting from the prefix. -- -- IntSet = Tip: contains elements Tip :: {-# UNPACK #-} !Prefix -> {-# UNPACK #-} !BitMap -> IntSet -- | Layout: Prefix up to mask of bitmap size, and mask specifing -- how large is set. There is no branching bit at all. Tip is never full. -- -- IntSet = Fin: contains all elements from prefix to (prefix - mask - 1) Fin :: {-# UNPACK #-} !Prefix -> {-# UNPACK #-} !Mask -> IntSet -- | Empty set. Contains nothing. Nil :: IntSet -- | Type of IntSet elements. type Key = Int -- | O(1). Is this the empty set? null :: IntSet -> Bool -- | O(n) or O(1). Cardinality of a set. size :: IntSet -> Int -- | O(min(W, n)) or O(1). Test if the value is element of -- the set. member :: Key -> IntSet -> Bool -- | O(min(W, n)) or O(1). Test if the value is not an -- element of the set. notMember :: Key -> IntSet -> Bool -- | O(n + m) or O(1). Test if the second set contain each -- element of the first. isSubsetOf :: IntSet -> IntSet -> Bool -- | O(n + m) or O(1). Test if the second set is subset of -- the first. isSupersetOf :: IntSet -> IntSet -> Bool -- | O(1). The empty set. empty :: IntSet -- | O(1). A set containing one element. singleton :: Key -> IntSet -- | O(n). Set containing elements from the specified range. -- -- 
--   interval a b = fromList [a..b]
--
interval :: Key -> Key -> IntSet -- | O(min(W, n) or O(1). Add a value to the set. insert :: Key -> IntSet -> IntSet -- | O(min(n, W)). Delete a value from the set. delete :: Key -> IntSet -> IntSet -- | 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. map :: (Key -> Key) -> IntSet -> IntSet -- | O(n). Fold the element using the given right associative binary -- operator. foldr :: (Key -> a -> a) -> a -> IntSet -> a -- | O(n). Filter all elements that satisfy the predicate. -- -- Do not use this operation with the universe, naturals or -- negatives sets. filter :: (Key -> Bool) -> IntSet -> IntSet -- | 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. split :: Key -> IntSet -> (IntSet, IntSet) -- | O(min(W, n). Takes subset such that each element is greater -- than the specified key. The exact key is excluded from result. splitGT :: Key -> IntSet -> IntSet -- | O(min(W, n). Takes subset such that each element is less than -- the specified key. The exact key is excluded from result. splitLT :: Key -> IntSet -> IntSet -- | O(n). Split a set using given predicate. -- -- 
--   forall f. fst . partition f = filter f
--   forall f. snd . partition f = filter (not . f)
--
partition :: (Key -> Bool) -> IntSet -> (IntSet, IntSet) -- | O(min(W, n)) or O(1). Find minimal element of the set. -- If set is empty then min is undefined. findMin :: IntSet -> Key -- | O(min(W, n)) or O(1). Find maximal element of the set. -- Is set is empty then max is undefined. findMax :: IntSet -> Key -- | O(n + m) or O(1). Find set which contains elements of -- both right and left sets. union :: IntSet -> IntSet -> IntSet -- | O(max(n)^2 * spine) or O(spine). The union of list of -- sets. unions :: [IntSet] -> IntSet -- | O(n + m) or O(1). Find maximal common subset of the two -- given sets. intersection :: IntSet -> IntSet -> IntSet -- | O(max(n) * spine) or O(spine). Find out common subset of -- the list of sets. intersections :: [IntSet] -> IntSet -- | O(n + m) or O(1). Find difference of the two sets. difference :: IntSet -> IntSet -> IntSet -- | 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. symDiff :: IntSet -> IntSet -> IntSet -- | Monoid under union. Used by default for IntSet. -- -- You could use Sum from Monoid as well. data Union -- | Monoid under intersection. -- -- You could use Product from Monoid as well. data Intersection -- | Monoid under symDiff. -- -- Don't mix up symDiff with difference. data Difference -- | elems is alias to toList for compatibility. elems :: IntSet -> [Key] -- | O(n). Convert the set to a list of its elements. toList :: IntSet -> [Key] -- | O(n * min(W, n)) or O(n). Create a set from a list of -- its elements. fromList :: [Key] -> IntSet -- | O(n). Convert the set to a list of its element in ascending -- order. toAscList :: IntSet -> [Key] -- | O(n). Convert the set to a list of its element in descending -- order. toDescList :: IntSet -> [Key] -- | Build a set from an ascending list of elements. fromAscList :: [Key] -> IntSet