diet-0.1.0.0: Discrete Interval Encoding Trees

Safe Haskell None Haskell2010

Data.Diet.Set.Lifted

Contents

Synopsis

# Documentation

data Set a Source #

Instances

 (Ord a, Enum a) => IsList (Set a) Source # Associated Typestype Item (Set a) :: * # MethodsfromList :: [Item (Set a)] -> Set a #fromListN :: Int -> [Item (Set a)] -> Set a #toList :: Set a -> [Item (Set a)] # Eq a => Eq (Set a) Source # Methods(==) :: Set a -> Set a -> Bool #(/=) :: Set a -> Set a -> Bool # Ord a => Ord (Set a) Source # Methodscompare :: Set a -> Set a -> Ordering #(<) :: Set a -> Set a -> Bool #(<=) :: Set a -> Set a -> Bool #(>) :: Set a -> Set a -> Bool #(>=) :: Set a -> Set a -> Bool #max :: Set a -> Set a -> Set a #min :: Set a -> Set a -> Set a # Show a => Show (Set a) Source # MethodsshowsPrec :: Int -> Set a -> ShowS #show :: Set a -> String #showList :: [Set a] -> ShowS # (Ord a, Enum a) => Semigroup (Set a) Source # Methods(<>) :: Set a -> Set a -> Set a #sconcat :: NonEmpty (Set a) -> Set a #stimes :: Integral b => b -> Set a -> Set a # (Ord a, Enum a) => Monoid (Set a) Source # Methodsmempty :: Set a #mappend :: Set a -> Set a -> Set a #mconcat :: [Set a] -> Set a # type Item (Set a) Source # type Item (Set a) = (a, a)

Arguments

 :: Ord a => a inclusive lower bound -> a inclusive upper bound -> Set a

O(1) Create a diet set with a single element.

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

O(log n) Lookup the value at a key in the map.

Arguments

 :: (Ord a, Enum a) => Set a minuend -> Set a subtrahend -> Set a

O(n + m*log n) Subtract the subtrahend of size m from the minuend of size n. It should be possible to improve the improve the performance of this to O(n + m). Anyone interested in doing this should open a PR.

# Split

Arguments

 :: Ord a => a inclusive lower bound -> Set a -> Set a

O(n) The subset where all elements are greater than or equal to the given value.

Arguments

 :: Ord a => a inclusive upper bound -> Set a -> Set a

O(n) The subset where all elements are less than or equal to the given value.

Arguments

 :: Ord a => a inclusive lower bound -> a inclusive upper bound -> Set a -> Set a

O(n) The subset where all elements are greater than or equal to the lower bound and less than or equal to the upper bound.

# Folds

foldr :: (a -> a -> b -> b) -> b -> Set a -> b Source #

# List Conversion

fromList :: (Ord a, Enum a) => [(a, a)] -> Set a Source #

Arguments

 :: (Ord a, Enum a) => Int expected size of resulting diet Set -> [(a, a)] key-value pairs -> Set a