hw-fingertree-strict-0.1.0.1: Generic strict finger-tree structure

Copyright (c) Arbor Networks 2017 BSD-style mayhem@arbor.net experimental non-portable (MPTCs and functional dependencies) Safe Haskell2010

Contents

Description

SegmentSet provides an efficient implementation of a set of segments (a.k.a intervals). Segments in the set are non-overlapping. Adjacent segments are merged (i.e. (a .. b), (b + 1 .. c) -> (a .. c)).

Segment sets are implemented using the FingerTree type, following section 4.8 of

An amortized running time is given for each operation, with n referring to the size of the set. These bounds hold even in a persistent (shared) setting.

Note: Many of these operations have the same names as similar operations on lists in the Prelude. The ambiguity may be resolved using either qualification or the hiding clause.

Synopsis

# Segments

data Segment k Source #

A closed segment. The lower bound should be less than or equal to the higher bound.

Constructors

 Segment Fieldslow :: !k high :: !k

Instances

 Monoid k => Measured k (Segment k) Source # Methodsmeasure :: Segment k -> k Source # Eq k => Eq (Segment k) Source # Methods(==) :: Segment k -> Segment k -> Bool #(/=) :: Segment k -> Segment k -> Bool # Ord k => Ord (Segment k) Source # Methodscompare :: Segment k -> Segment k -> Ordering #(<) :: Segment k -> Segment k -> Bool #(<=) :: Segment k -> Segment k -> Bool #(>) :: Segment k -> Segment k -> Bool #(>=) :: Segment k -> Segment k -> Bool #max :: Segment k -> Segment k -> Segment k #min :: Segment k -> Segment k -> Segment k # Show k => Show (Segment k) Source # MethodsshowsPrec :: Int -> Segment k -> ShowS #show :: Segment k -> String #showList :: [Segment k] -> ShowS #

point :: k -> Segment k Source #

A segment in which the lower and upper bounds are equal.

# Segment maps

newtype SegmentSet k Source #

Constructors

 SegmentSet (OrderedMap (Max k) (Segment k))

Instances

 Show k => Show (SegmentSet k) Source # MethodsshowsPrec :: Int -> SegmentSet k -> ShowS #show :: SegmentSet k -> String #showList :: [SegmentSet k] -> ShowS #

newtype OrderedMap k a Source #

Map of closed segments, possibly with duplicates. The Foldable and Traversable instances process the segments in lexicographical order.

Constructors

 OrderedMap (FingerTree k (Item k a))

Instances

 Source # Methodsfmap :: (a -> b) -> OrderedMap k a -> OrderedMap k b #(<$) :: a -> OrderedMap k b -> OrderedMap k a # Source # Methodsfold :: Monoid m => OrderedMap k m -> m #foldMap :: Monoid m => (a -> m) -> OrderedMap k a -> m #foldr :: (a -> b -> b) -> b -> OrderedMap k a -> b #foldr' :: (a -> b -> b) -> b -> OrderedMap k a -> b #foldl :: (b -> a -> b) -> b -> OrderedMap k a -> b #foldl' :: (b -> a -> b) -> b -> OrderedMap k a -> b #foldr1 :: (a -> a -> a) -> OrderedMap k a -> a #foldl1 :: (a -> a -> a) -> OrderedMap k a -> a #toList :: OrderedMap k a -> [a] #null :: OrderedMap k a -> Bool #length :: OrderedMap k a -> Int #elem :: Eq a => a -> OrderedMap k a -> Bool #maximum :: Ord a => OrderedMap k a -> a #minimum :: Ord a => OrderedMap k a -> a #sum :: Num a => OrderedMap k a -> a #product :: Num a => OrderedMap k a -> a # Source # Methodstraverse :: Applicative f => (a -> f b) -> OrderedMap k a -> f (OrderedMap k b) #sequenceA :: Applicative f => OrderedMap k (f a) -> f (OrderedMap k a) #mapM :: Monad m => (a -> m b) -> OrderedMap k a -> m (OrderedMap k b) #sequence :: Monad m => OrderedMap k (m a) -> m (OrderedMap k a) # (Show a, Show k) => Show (OrderedMap k a) Source # MethodsshowsPrec :: Int -> OrderedMap k a -> ShowS #show :: OrderedMap k a -> String #showList :: [OrderedMap k a] -> ShowS # delete :: forall k a. (Bounded k, Ord k, Enum k, Show k) => Segment k -> SegmentSet k -> SegmentSet k Source # O(log(n)). Remove a segment from the set. Alias of update. empty :: (Ord k, Bounded k) => SegmentSet k Source # O(1). The empty segment set. fromList :: (Ord v, Enum v, Bounded v, Show v) => [Segment v] -> SegmentSet v Source # insert :: forall k a. (Bounded k, Ord k, Enum k, Show k) => Segment k -> SegmentSet k -> SegmentSet k Source # O(log(n)). Insert a segment into the set. Alias of update. singleton :: (Bounded k, Ord k) => Segment k -> SegmentSet k Source # O(1). Segment set with a single entry. update :: forall k a. (Ord k, Enum k, Bounded k, Show k) => Segment k -> Bool -> SegmentSet k -> SegmentSet k Source # Update a segment set. Prefer insert or delete in most cases. data Item k a Source # Constructors  Item !k !a Instances  Monoid k => Measured k (Item k a) Source # Methodsmeasure :: Item k a -> k Source # Functor (Item k) Source # Methodsfmap :: (a -> b) -> Item k a -> Item k b #(<$) :: a -> Item k b -> Item k a # Foldable (Item k) Source # Methodsfold :: Monoid m => Item k m -> m #foldMap :: Monoid m => (a -> m) -> Item k a -> m #foldr :: (a -> b -> b) -> b -> Item k a -> b #foldr' :: (a -> b -> b) -> b -> Item k a -> b #foldl :: (b -> a -> b) -> b -> Item k a -> b #foldl' :: (b -> a -> b) -> b -> Item k a -> b #foldr1 :: (a -> a -> a) -> Item k a -> a #foldl1 :: (a -> a -> a) -> Item k a -> a #toList :: Item k a -> [a] #null :: Item k a -> Bool #length :: Item k a -> Int #elem :: Eq a => a -> Item k a -> Bool #maximum :: Ord a => Item k a -> a #minimum :: Ord a => Item k a -> a #sum :: Num a => Item k a -> a #product :: Num a => Item k a -> a # Source # Methodstraverse :: Applicative f => (a -> f b) -> Item k a -> f (Item k b) #sequenceA :: Applicative f => Item k (f a) -> f (Item k a) #mapM :: Monad m => (a -> m b) -> Item k a -> m (Item k b) #sequence :: Monad m => Item k (m a) -> m (Item k a) # (Eq a, Eq k) => Eq (Item k a) Source # Methods(==) :: Item k a -> Item k a -> Bool #(/=) :: Item k a -> Item k a -> Bool # (Show a, Show k) => Show (Item k a) Source # MethodsshowsPrec :: Int -> Item k a -> ShowS #show :: Item k a -> String #showList :: [Item k a] -> ShowS #

cappedL :: (Enum k, Ord k, Bounded k, Show k) => k -> FingerTree (Max k) (Item (Max k) (Segment k)) -> (FingerTree (Max k) (Item (Max k) (Segment k)), FingerTree (Max k) (Item (Max k) (Segment k))) Source #

cappedM :: (Enum k, Ord k, Bounded k, Show k) => k -> FingerTree (Max k) (Item (Max k) (Segment k)) -> FingerTree (Max k) (Item (Max k) (Segment k)) Source #