-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Memory efficient sets with ranges of elements. -- -- Memory efficient sets with continuous ranges of discrete, bounded -- elements. List- and map-based implementations. Interface mimics -- Data.Set where possible. @package range-set-list @version 0.1.4 -- | Most functions in this module deal with normalized (closed, fst <= -- snd, non-overlapping, non-adjacent, ordered) ranges, but do not check -- this assumption. Most users should use a higher-level interface. module Data.RangeSet.Internal -- | Determine the number of items in an Enum range as a Sum rangeSize :: Enum a => a -> a -> Sum Int -- | Determine if [x,y] is a subset of the list, returning the -- list right of y if so. rangeIsSubsetList :: Ord a => a -> a -> [(a, a)] -> Maybe [(a, a)] -- | Determine if the first list is a subset of the second. isSubsetRangeList :: Ord a => [(a, a)] -> [(a, a)] -> Bool -- | Add [x,y]. -- -- There are three possibilities we consider, when inserting into -- non-empty set: -- -- insertRangeList :: (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)] -- | Remove a range from a range list. -- -- There are 6 possibilities we consider, when deleting from non-empty -- set: -- -- deleteRangeList :: (Ord a, Enum a) => a -> a -> [(a, a)] -> [(a, a)] -- | Union two range lists. unionRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)] -- | Compute the set difference, removing each range in the second list -- from the first. differenceRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)] -> [(a, a)] -- | Compute the intersection. intersectRangeList :: Ord a => [(a, a)] -> [(a, a)] -> [(a, a)] -- | Compute the complement. complementRangeList :: (Ord a, Enum a, Bounded a) => [(a, a)] -> [(a, a)] -- | Normalize a sorted list of elements to a range list. fromAscElemList :: (Eq a, Enum a) => [a] -> [(a, a)] -- | Normalize an arbitrary list of elements to a range list. fromElemList :: (Ord a, Enum a) => [a] -> [(a, a)] -- | Normalize an arbitrary list of ranges. normalizeRangeList :: (Ord a, Enum a) => [(a, a)] -> [(a, a)] -- | Check if a list is normalized. validRangeList :: (Ord a, Enum a, Bounded a) => [(a, a)] -> Bool -- | 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. module Data.RangeSet.List -- | Internally set is represented as sorted list of distinct inclusive -- ranges. data RSet a -- | O(n+m). See difference. (\\) :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a infixl 9 \\ -- | O(1). Is this the empty set? null :: RSet a -> Bool -- | O(1). Is this the full set? isFull :: (Eq a, Bounded a) => RSet a -> Bool -- | O(n). The number of the elements in the set. size :: Enum a => RSet a -> Int -- | O(n). Is the element in the set? member :: Ord a => a -> RSet a -> Bool -- | O(n). Is the element not in the set? notMember :: Ord a => a -> RSet a -> Bool -- | O(n). Find largest element smaller than the given one. lookupLT :: (Ord a, Enum a) => a -> RSet a -> Maybe a -- | O(n). Find smallest element greater than the given one. lookupGT :: (Ord a, Enum a) => a -> RSet a -> Maybe a -- | O(n). Find largest element smaller or equal to than the given -- one. lookupLE :: Ord a => a -> RSet a -> Maybe a -- | O(n). Find smallest element greater or equal to than the given -- one. lookupGE :: Ord a => a -> RSet a -> Maybe a -- | O(n). Is the entire range contained within the set? containsRange :: Ord a => (a, a) -> RSet a -> Bool -- | O(n+m). Is this a subset? (s1 isSubsetOf s2) -- tells whether s1 is a subset of s2. isSubsetOf :: Ord a => RSet a -> RSet a -> Bool -- | O(n). Ensure that a set is valid. All functions should return -- valid sets except those with unchecked preconditions: -- fromAscList, fromNormalizedRangeList valid :: (Ord a, Enum a, Bounded a) => RSet a -> Bool -- | O(1). The empty set. empty :: RSet a -- | O(1). The full set. full :: Bounded a => RSet a -- | O(1). Create a singleton set. singleton :: a -> RSet a -- | O(1). Create a continuos range set. singletonRange :: Ord a => (a, a) -> RSet a -- | O(n). Insert an element in a set. insert :: (Ord a, Enum a) => a -> RSet a -> RSet a -- | O(n). Insert a continuos range in a set. insertRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a -- | /O(n). Delete an element from a set. delete :: (Ord a, Enum a) => a -> RSet a -> RSet a -- | /O(n). Delete a continuos range from a set. deleteRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a -- | O(n+m). The union of two sets. union :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a -- | O(n+m). Difference of two sets. difference :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a -- | O(n+m). The intersection of two sets. intersection :: Ord a => RSet a -> RSet a -> RSet a -- | 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. split :: (Ord a, Enum a) => a -> RSet a -> (RSet a, RSet a) -- | O(n). Performs a split but also returns whether the -- pivot element was found in the original set. splitMember :: (Ord a, Enum a) => a -> RSet a -> (RSet a, Bool, RSet a) -- | O(1). The minimal element of a set. findMin :: RSet a -> a -- | O(n). The maximal element of a set. findMax :: RSet a -> a -- | O(n). Complement of the set. complement :: (Ord a, Enum a, Bounded a) => RSet a -> RSet a -- | O(n*r). An alias of toAscList. The elements of a set in -- ascending order. r is the size of longest range. 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*log n). Create a set from a list of elements. fromList :: (Ord a, Enum a) => [a] -> RSet a -- | O(n). Create a set from a list of ascending elements. -- -- The precondition is not checked. You may use valid to -- check the result. fromAscList :: (Ord a, Enum a) => [a] -> RSet a -- | O(n*r). Convert the set to an ascending list of elements. toAscList :: Enum a => RSet a -> [a] -- | O(1). Convert the set to a list of range pairs. toRangeList :: RSet a -> [(a, a)] -- | O(n*log n). Create a set from a list of range pairs. fromRangeList :: (Ord a, Enum a) => [(a, a)] -> RSet a -- | 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. fromNormalizedRangeList :: [(a, a)] -> RSet a -- | O(n*r). Convert the set to a Set of elements. r -- is the size of longest range. toSet :: Enum a => RSet a -> Set a instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.RangeSet.List.RSet a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.RangeSet.List.RSet a) instance GHC.Show.Show a => GHC.Show.Show (Data.RangeSet.List.RSet a) instance (GHC.Classes.Ord a, GHC.Enum.Enum a) => GHC.Base.Semigroup (Data.RangeSet.List.RSet a) instance (GHC.Classes.Ord a, GHC.Enum.Enum a) => GHC.Base.Monoid (Data.RangeSet.List.RSet a) instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Data.RangeSet.List.RSet a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.RangeSet.List.RSet a) -- | This is simply a specialization of Data.RangeSet.Map to -- Int. -- -- The implementation of RIntSet is based on -- Data.IntMap.Strict. module Data.RangeSet.IntMap -- | Internally set is represented as sorted list of distinct inclusive -- ranges. data RIntSet -- | O(n+m). See difference. (\\) :: RIntSet -> RIntSet -> RIntSet infixl 9 \\ -- | O(1). Is this the empty set? null :: RIntSet -> Bool -- | O(1). Is this the empty set? isFull :: RIntSet -> Bool -- | O(n). The number of the elements in the set. size :: RIntSet -> Int -- | O(log n). Is the element in the set? member :: Int -> RIntSet -> Bool -- | O(log n). Is the element not in the set? notMember :: Int -> RIntSet -> Bool -- | O(log n). Find largest element smaller than the given one. lookupLT :: Int -> RIntSet -> Maybe Int -- | O(log n). Find smallest element greater than the given one. lookupGT :: Int -> RIntSet -> Maybe Int -- | O(log n). Find largest element smaller or equal to than the -- given one. lookupLE :: Int -> RIntSet -> Maybe Int -- | O(log n). Find smallest element greater or equal to than the -- given one. lookupGE :: Int -> RIntSet -> Maybe Int -- | O(log n). Is the entire range contained within the set? containsRange :: (Int, Int) -> RIntSet -> Bool -- | O(n+m). Is this a subset? (s1 isSubsetOf s2) -- tells whether s1 is a subset of s2. isSubsetOf :: RIntSet -> RIntSet -> Bool -- | O(n). Ensure that a set is valid. All functions should return -- valid sets except those with unchecked preconditions: -- fromAscList, fromNormalizedRangeList valid :: RIntSet -> Bool -- | O(1). The empty set. empty :: RIntSet -- | O(1). The full set. full :: RIntSet -- | O(1). Create a singleton set. singleton :: Int -> RIntSet -- | O(1). Create a continuos range set. singletonRange :: (Int, Int) -> RIntSet -- | O(n). Insert an element in a set. insert :: Int -> RIntSet -> RIntSet -- | O(n). Insert a continuos range in a set. insertRange :: (Int, Int) -> RIntSet -> RIntSet -- | /O(n). Delete an element from a set. delete :: Int -> RIntSet -> RIntSet -- | /O(n). Delete a continuos range from a set. deleteRange :: (Int, Int) -> RIntSet -> RIntSet -- | O(n*m). The union of two sets. union :: RIntSet -> RIntSet -> RIntSet -- | O(n*m). Difference of two sets. difference :: RIntSet -> RIntSet -> RIntSet -- | O(n*m). The intersection of two sets. intersection :: RIntSet -> RIntSet -> RIntSet -- | O(log 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. split :: Int -> RIntSet -> (RIntSet, RIntSet) -- | O(log n). Performs a split but also returns whether the -- pivot element was found in the original set. splitMember :: Int -> RIntSet -> (RIntSet, Bool, RIntSet) -- | O(log n). The minimal element of a set. findMin :: RIntSet -> Int -- | O(log n). The maximal element of a set. findMax :: RIntSet -> Int -- | O(n). Complement of the set. complement :: RIntSet -> RIntSet -- | O(n*r). An alias of toAscList. The elements of a set in -- ascending order. r is the size of longest range. elems :: RIntSet -> [Int] -- | O(n*r). Convert the set to a list of elements (in arbitrary -- order). r is the size of longest range. toList :: RIntSet -> [Int] -- | O(n*log n). Create a set from a list of elements. -- -- Note that unlike Data.Set and other binary trees, this always -- requires a full sort and traversal to create distinct, disjoint ranges -- before constructing the tree. fromList :: [Int] -> RIntSet -- | O(n). Create a set from a list of ascending elements. -- -- The precondition is not checked. You may use valid to -- check the result. Note that unlike Data.Set and other binary -- trees, this always requires a full traversal to create distinct, -- disjoint ranges before constructing the tree. fromAscList :: [Int] -> RIntSet -- | O(n*r). Convert the set to an ascending list of elements. toAscList :: RIntSet -> [Int] -- | O(n). Convert the set to a list of range pairs. toRangeList :: RIntSet -> [(Int, Int)] -- | O(n*log n). Create a set from a list of range pairs. -- -- Note that unlike Data.Set and other binary trees, this always -- requires a full sort and traversal to create distinct, disjoint ranges -- before constructing the tree. fromRangeList :: [(Int, Int)] -> RIntSet -- | O(n). Convert a list-based RSet to a map-based -- RIntSet. fromRList :: RSet Int -> RIntSet -- | O(n). Convert a map-based RIntSet to a list-based -- RSet. toRList :: RIntSet -> RSet Int -- | O(n). 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. fromNormalizedRangeList :: [(Int, Int)] -> RIntSet instance GHC.Classes.Ord Data.RangeSet.IntMap.RIntSet instance GHC.Classes.Eq Data.RangeSet.IntMap.RIntSet instance GHC.Show.Show Data.RangeSet.IntMap.RIntSet instance GHC.Base.Semigroup Data.RangeSet.IntMap.RIntSet instance GHC.Base.Monoid Data.RangeSet.IntMap.RIntSet instance Control.DeepSeq.NFData Data.RangeSet.IntMap.RIntSet -- | A slightly less trivial implementation of range sets. -- -- This is nearly identical to Data.RangeSet.List except for some -- important performance differences: -- -- -- -- If you're mainly calling member, you should consider using this -- module, but if you're calling union, deleteRange, and -- other range manipulation functions as often as querying, you might -- stick with the list implementation. -- -- This module is intended to be imported qualified, to avoid name -- clashes with Prelude functions, e.g. -- -- 
--   import Data.RangeSet.Map (RSet)
--   import qualified Data.RangeSet.Map as RSet
--
-- -- The implementation of RSet is based on Data.Map.Strict. module Data.RangeSet.Map -- | Internally set is represented as sorted list of distinct inclusive -- ranges. data RSet a -- | O(n+m). See difference. (\\) :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a infixl 9 \\ -- | O(1). Is this the empty set? null :: RSet a -> Bool -- | O(1). Is this the empty set? isFull :: (Eq a, Bounded a) => RSet a -> Bool -- | O(n). The number of the elements in the set. size :: Enum a => RSet a -> Int -- | O(log n). Is the element in the set? member :: Ord a => a -> RSet a -> Bool -- | O(log n). Is the element not in the set? notMember :: Ord a => a -> RSet a -> Bool -- | O(log n). Find largest element smaller than the given one. lookupLT :: (Ord a, Enum a) => a -> RSet a -> Maybe a -- | O(log n). Find smallest element greater than the given one. lookupGT :: (Ord a, Enum a) => a -> RSet a -> Maybe a -- | O(log n). Find largest element smaller or equal to than the -- given one. lookupLE :: Ord a => a -> RSet a -> Maybe a -- | O(log n). Find smallest element greater or equal to than the -- given one. lookupGE :: Ord a => a -> RSet a -> Maybe a -- | O(log n). Is the entire range contained within the set? containsRange :: Ord a => (a, a) -> RSet a -> Bool -- | O(n+m). Is this a subset? (s1 isSubsetOf s2) -- tells whether s1 is a subset of s2. isSubsetOf :: Ord a => RSet a -> RSet a -> Bool -- | O(n). Ensure that a set is valid. All functions should return -- valid sets except those with unchecked preconditions: -- fromAscList, fromNormalizedRangeList valid :: (Ord a, Enum a, Bounded a) => RSet a -> Bool -- | O(1). The empty set. empty :: RSet a -- | O(1). The full set. full :: Bounded a => RSet a -- | O(1). Create a singleton set. singleton :: a -> RSet a -- | O(1). Create a continuos range set. singletonRange :: Ord a => (a, a) -> RSet a -- | O(n). Insert an element in a set. insert :: (Ord a, Enum a) => a -> RSet a -> RSet a -- | O(n). Insert a continuos range in a set. insertRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a -- | /O(n). Delete an element from a set. delete :: (Ord a, Enum a) => a -> RSet a -> RSet a -- | /O(n). Delete a continuos range from a set. deleteRange :: (Ord a, Enum a) => (a, a) -> RSet a -> RSet a -- | O(n*m). The union of two sets. union :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a -- | O(n*m). Difference of two sets. difference :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a -- | O(n*m). The intersection of two sets. intersection :: (Ord a, Enum a) => RSet a -> RSet a -> RSet a -- | O(log 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. split :: (Ord a, Enum a) => a -> RSet a -> (RSet a, RSet a) -- | O(log n). Performs a split but also returns whether the -- pivot element was found in the original set. splitMember :: (Ord a, Enum a) => a -> RSet a -> (RSet a, Bool, RSet a) -- | O(log n). The minimal element of a set. findMin :: RSet a -> a -- | O(log n). The maximal element of a set. findMax :: RSet a -> a -- | O(n). Complement of the set. complement :: (Ord a, Enum a, Bounded a) => RSet a -> RSet a -- | O(n*r). An alias of toAscList. The elements of a set in -- ascending order. r is the size of longest range. elems :: Enum a => RSet a -> [a] -- | O(n*r). Convert the set to a list of elements (in arbitrary -- order). r is the size of longest range. toList :: Enum a => RSet a -> [a] -- | O(n*log n). Create a set from a list of elements. Note that -- unlike Data.Set and other binary trees, this always requires a -- full sort and traversal to create distinct, disjoint ranges before -- constructing the tree. fromList :: (Ord a, Enum a) => [a] -> RSet a -- | O(n). Create a set from a list of ascending elements. The -- precondition is not checked. You may use valid to check the -- result. Note that unlike Data.Set and other binary trees, this -- always requires a full traversal to create distinct, disjoint ranges -- before constructing the tree. fromAscList :: (Ord a, Enum a) => [a] -> RSet a -- | O(n*r). Convert the set to an ascending list of elements. toAscList :: Enum a => RSet a -> [a] -- | O(n). Convert the set to a list of range pairs. toRangeList :: RSet a -> [(a, a)] -- | O(n*log n). Create a set from a list of range pairs. Note that -- unlike Data.Set and other binary trees, this always requires a -- full sort and traversal to create distinct, disjoint ranges before -- constructing the tree. fromRangeList :: (Ord a, Enum a) => [(a, a)] -> RSet a -- | O(n). Convert a list-based RSet to a map-based -- RSet. fromRList :: RSet a -> RSet a -- | O(n). Convert a map-based RSet to a list-based -- RSet. toRList :: RSet a -> RSet a -- | O(n). 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. fromNormalizedRangeList :: [(a, a)] -> RSet a instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.RangeSet.Map.RSet a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.RangeSet.Map.RSet a) instance GHC.Show.Show a => GHC.Show.Show (Data.RangeSet.Map.RSet a) instance (GHC.Classes.Ord a, GHC.Enum.Enum a) => GHC.Base.Semigroup (Data.RangeSet.Map.RSet a) instance (GHC.Classes.Ord a, GHC.Enum.Enum a) => GHC.Base.Monoid (Data.RangeSet.Map.RSet a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.RangeSet.Map.RSet a)