hw-fingertree-strict-0.1.0.2: 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

Segment maps 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 map. 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 SegmentMap k a Source #

Constructors

 SegmentMap (OrderedMap (Max k) (Segment k, a))

Instances

 Source # Methodsfmap :: (a -> b) -> SegmentMap k a -> SegmentMap k b #(<$) :: a -> SegmentMap k b -> SegmentMap k a # (Show a, Show k) => Show (SegmentMap k a) Source # MethodsshowsPrec :: Int -> SegmentMap k a -> ShowS #show :: SegmentMap k a -> String #showList :: [SegmentMap k a] -> 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, Eq a, Show k, Show a) => Segment k -> SegmentMap k a -> SegmentMap k a Source #

empty :: (Ord k, Bounded k) => SegmentMap k a Source #

O(1). The empty segment map.

fromList :: (Ord v, Enum v, Eq a, Bounded v, Show v, Show a) => [(Segment v, a)] -> SegmentMap v a Source #

insert :: forall k a. (Bounded k, Ord k, Enum k, Eq a, Show k, Show a) => Segment k -> a -> SegmentMap k a -> SegmentMap k a Source #

singleton :: (Bounded k, Ord k) => Segment k -> a -> SegmentMap k a Source #

O(1). Segment map with a single entry.

update :: forall k a. (Ord k, Enum k, Bounded k, Eq a, Show k, Show a) => Segment k -> Maybe a -> SegmentMap k a -> SegmentMap k a Source #

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, a)) -> (FingerTree (Max k) (Item (Max k) (Segment k, a)), FingerTree (Max k) (Item (Max k) (Segment k, a))) Source #

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