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

Copyright(c) Arbor Networks 2017
LicenseBSD-style
Maintainermayhem@arbor.net
Stabilityexperimental
Portabilitynon-portable (MPTCs and functional dependencies)
Safe HaskellSafe
LanguageHaskell2010

HaskellWorks.Data.SegmentMap.Strict

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 

Fields

Instances

Monoid k => Measured k (Segment k) Source # 

Methods

measure :: 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 # 

Methods

compare :: 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 # 

Methods

showsPrec :: 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

Functor (SegmentMap k) Source # 

Methods

fmap :: (a -> b) -> SegmentMap k a -> SegmentMap k b #

(<$) :: a -> SegmentMap k b -> SegmentMap k a #

(Show a, Show k) => Show (SegmentMap k a) Source # 

Methods

showsPrec :: 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

Functor (OrderedMap k) Source # 

Methods

fmap :: (a -> b) -> OrderedMap k a -> OrderedMap k b #

(<$) :: a -> OrderedMap k b -> OrderedMap k a #

Foldable (OrderedMap k) Source # 

Methods

fold :: 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 #

Traversable (OrderedMap k) Source # 

Methods

traverse :: 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 # 

Methods

showsPrec :: 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 # 

Methods

measure :: Item k a -> k Source #

Functor (Item k) Source # 

Methods

fmap :: (a -> b) -> Item k a -> Item k b #

(<$) :: a -> Item k b -> Item k a #

Foldable (Item k) Source # 

Methods

fold :: 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 #

Traversable (Item k) Source # 

Methods

traverse :: 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 # 

Methods

showsPrec :: 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 #