hw-fingertree-0.1.2.0: Generic finger-tree structure, with example instances

Copyright(c) Ross Paterson 2008
LicenseBSD-style
MaintainerR.Paterson@city.ac.uk
Stabilityexperimental
Portabilitynon-portable (MPTCs and functional dependencies)
Safe HaskellNone
LanguageHaskell2010

HaskellWorks.Data.IntervalMap.FingerTree

Contents

Description

Interval 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 priority queue. 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

Intervals

data Interval v Source #

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

Constructors

Interval 

Fields

Instances
Eq v => Eq (Interval v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

(==) :: Interval v -> Interval v -> Bool #

(/=) :: Interval v -> Interval v -> Bool #

Ord v => Ord (Interval v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

compare :: Interval v -> Interval v -> Ordering #

(<) :: Interval v -> Interval v -> Bool #

(<=) :: Interval v -> Interval v -> Bool #

(>) :: Interval v -> Interval v -> Bool #

(>=) :: Interval v -> Interval v -> Bool #

max :: Interval v -> Interval v -> Interval v #

min :: Interval v -> Interval v -> Interval v #

Show v => Show (Interval v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

showsPrec :: Int -> Interval v -> ShowS #

show :: Interval v -> String #

showList :: [Interval v] -> ShowS #

Generic (Interval v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Associated Types

type Rep (Interval v) :: Type -> Type #

Methods

from :: Interval v -> Rep (Interval v) x #

to :: Rep (Interval v) x -> Interval v #

NFData v => NFData (Interval v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

rnf :: Interval v -> () #

type Rep (Interval v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

type Rep (Interval v) = D1 (MetaData "Interval" "HaskellWorks.Data.IntervalMap.FingerTree" "hw-fingertree-0.1.2.0-3DwksjKuN7xALuwqw6iuem" False) (C1 (MetaCons "Interval" PrefixI True) (S1 (MetaSel (Just "low") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v) :*: S1 (MetaSel (Just "high") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v)))

point :: v -> Interval v Source #

An interval in which the lower and upper bounds are equal.

Interval maps

newtype IntervalMap v a Source #

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

Constructors

IntervalMap (FingerTree (IntInterval v) (Node v a)) 
Instances
Functor (IntervalMap v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

fmap :: (a -> b) -> IntervalMap v a -> IntervalMap v b #

(<$) :: a -> IntervalMap v b -> IntervalMap v a #

Foldable (IntervalMap v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

fold :: Monoid m => IntervalMap v m -> m #

foldMap :: Monoid m => (a -> m) -> IntervalMap v a -> m #

foldr :: (a -> b -> b) -> b -> IntervalMap v a -> b #

foldr' :: (a -> b -> b) -> b -> IntervalMap v a -> b #

foldl :: (b -> a -> b) -> b -> IntervalMap v a -> b #

foldl' :: (b -> a -> b) -> b -> IntervalMap v a -> b #

foldr1 :: (a -> a -> a) -> IntervalMap v a -> a #

foldl1 :: (a -> a -> a) -> IntervalMap v a -> a #

toList :: IntervalMap v a -> [a] #

null :: IntervalMap v a -> Bool #

length :: IntervalMap v a -> Int #

elem :: Eq a => a -> IntervalMap v a -> Bool #

maximum :: Ord a => IntervalMap v a -> a #

minimum :: Ord a => IntervalMap v a -> a #

sum :: Num a => IntervalMap v a -> a #

product :: Num a => IntervalMap v a -> a #

Traversable (IntervalMap v) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

traverse :: Applicative f => (a -> f b) -> IntervalMap v a -> f (IntervalMap v b) #

sequenceA :: Applicative f => IntervalMap v (f a) -> f (IntervalMap v a) #

mapM :: Monad m => (a -> m b) -> IntervalMap v a -> m (IntervalMap v b) #

sequence :: Monad m => IntervalMap v (m a) -> m (IntervalMap v a) #

Generic (IntervalMap v a) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Associated Types

type Rep (IntervalMap v a) :: Type -> Type #

Methods

from :: IntervalMap v a -> Rep (IntervalMap v a) x #

to :: Rep (IntervalMap v a) x -> IntervalMap v a #

Ord v => Semigroup (IntervalMap v a) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

(<>) :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a #

sconcat :: NonEmpty (IntervalMap v a) -> IntervalMap v a #

stimes :: Integral b => b -> IntervalMap v a -> IntervalMap v a #

Ord v => Monoid (IntervalMap v a) Source #

empty and union.

Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

mempty :: IntervalMap v a #

mappend :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a #

mconcat :: [IntervalMap v a] -> IntervalMap v a #

(NFData a, NFData v) => NFData (IntervalMap v a) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

Methods

rnf :: IntervalMap v a -> () #

type Rep (IntervalMap v a) Source # 
Instance details

Defined in HaskellWorks.Data.IntervalMap.FingerTree

type Rep (IntervalMap v a)

empty :: Ord v => IntervalMap v a Source #

O(1). The empty interval map.

singleton :: Ord v => Interval v -> a -> IntervalMap v a Source #

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

insert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v a Source #

O(log n). Insert an interval into a map. The map may contain duplicate intervals; the new entry will be inserted before any existing entries for the same interval.

union :: Ord v => IntervalMap v a -> IntervalMap v a -> IntervalMap v a Source #

O(m log (n/m)). Merge two interval maps. The map may contain duplicate intervals; entries with equal intervals are kept in the original order.

Searching

search :: Ord v => v -> IntervalMap v a -> [(Interval v, a)] Source #

O(k log (n/k)). All intervals that contain the given point, in lexicographical order.

intersections :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)] Source #

O(k log (n/k)). All intervals that intersect with the given interval, in lexicographical order.

dominators :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)] Source #

O(k log (n/k)). All intervals that contain the given interval, in lexicographical order.