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

HaskellWorks.Data.SegmentMap.Strict

Contents

Segments
Segment maps

Description

Segment maps implemented using the FingerTree type, following section 4.8 of

Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", Journal of Functional Programmaxg 16:2 (2006) pp 197-217. http://staff.city.ac.uk/~ross/papers/FingerTree.html

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 low :: !k high :: !k

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 #
Generic (Segment k) Source #
Associated Types type Rep (Segment k) :: * -> * # Methods from :: Segment k -> Rep (Segment k) x # to :: Rep (Segment k) x -> Segment k #
NFData k => NFData (Segment k) Source #
Methods rnf :: Segment k -> () #
type Rep (Segment k) Source #
type Rep (Segment k) = D1 * (MetaData "Segment" "HaskellWorks.Data.Segment.Strict" "hw-fingertree-strict-0.1.1.0-BC7rHFKaflB3QI1ck3u9LV" False) (C1 * (MetaCons "Segment" PrefixI True) ((::) (S1 * (MetaSel (Just Symbol "low") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 * k)) (S1 * (MetaSel (Just Symbol "high") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 * k))))

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 #
Generic (SegmentMap k a) Source #
Associated Types type Rep (SegmentMap k a) :: * -> * # Methods from :: SegmentMap k a -> Rep (SegmentMap k a) x # to :: Rep (SegmentMap k a) x -> SegmentMap k a #
(NFData a, NFData k) => NFData (SegmentMap k a) Source #
Methods rnf :: SegmentMap k a -> () #
type Rep (SegmentMap k a) Source #
type Rep (SegmentMap k a) = D1 * (MetaData "SegmentMap" "HaskellWorks.Data.SegmentMap.Strict" "hw-fingertree-strict-0.1.1.0-BC7rHFKaflB3QI1ck3u9LV" True) (C1 * (MetaCons "SegmentMap" PrefixI False) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * (OrderedMap (Max k) (Segment k, a)))))

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 #
Generic (OrderedMap k a) Source #
Associated Types type Rep (OrderedMap k a) :: * -> * # Methods from :: OrderedMap k a -> Rep (OrderedMap k a) x # to :: Rep (OrderedMap k a) x -> OrderedMap k a #
(NFData a, NFData k) => NFData (OrderedMap k a) Source #
Methods rnf :: OrderedMap k a -> () #
type Rep (OrderedMap k a) Source #
type Rep (OrderedMap k a) = D1 * (MetaData "OrderedMap" "HaskellWorks.Data.SegmentMap.Strict" "hw-fingertree-strict-0.1.1.0-BC7rHFKaflB3QI1ck3u9LV" True) (C1 * (MetaCons "OrderedMap" PrefixI False) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * (FingerTree k (Item k a)))))

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 #

segmentMapToList :: SegmentMap k a -> [(Segment 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 #
Generic (Item k a) Source #
Associated Types type Rep (Item k a) :: * -> * # Methods from :: Item k a -> Rep (Item k a) x # to :: Rep (Item k a) x -> Item k a #
(NFData a, NFData k) => NFData (Item k a) Source #
Methods rnf :: Item k a -> () #
type Rep (Item k a) Source #
type Rep (Item k a) = D1 * (MetaData "Item" "HaskellWorks.Data.Item.Strict" "hw-fingertree-strict-0.1.1.0-BC7rHFKaflB3QI1ck3u9LV" False) (C1 * (MetaCons "Item" PrefixI False) ((::) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 * k)) (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 * a))))

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 #