Copyright	(c) Ross Paterson 2008
License	BSD-style
Maintainer	R.Paterson@city.ac.uk
Stability	experimental
Portability	non-portable (MPTCs and functional dependencies)
Safe Haskell	Safe
Language	Haskell2010

Data.IntervalMap.FingerTree

Contents

Intervals
Interval maps
Searching
Extraction

Description

Interval 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 Programming 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 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

data Interval v = Interval v v
low :: Interval v -> v
high :: Interval v -> v
point :: v -> Interval v
data IntervalMap v a
empty :: Ord v => IntervalMap v a
singleton :: Ord v => Interval v -> a -> IntervalMap v a
insert :: Ord v => Interval v -> a -> IntervalMap v a -> IntervalMap v a
union :: Ord v => IntervalMap v a -> IntervalMap v a -> IntervalMap v a
search :: Ord v => v -> IntervalMap v a -> [(Interval v, a)]
intersections :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]
dominators :: Ord v => Interval v -> IntervalMap v a -> [(Interval v, a)]
bounds :: Ord v => IntervalMap v a -> Maybe (Interval v)
leastView :: Ord v => IntervalMap v a -> Maybe ((Interval v, a), IntervalMap v a)
splitAfter :: Ord v => v -> IntervalMap v a -> (IntervalMap v a, IntervalMap v a)

Intervals

data Interval v Source #

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

Constructors

Interval v v

Lower and upper bounds of the interval.

Instances

Instances details

Eq v => Eq (Interval v) Source #
Instance details Defined in Data.IntervalMap.FingerTree Methods (==) :: Interval v -> Interval v -> Bool # (/=) :: Interval v -> Interval v -> Bool #
Ord v => Ord (Interval v) Source #
Instance details Defined in 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 #
Read v => Read (Interval v) Source #
Instance details Defined in Data.IntervalMap.FingerTree Methods readsPrec :: Int -> ReadS (Interval v) # readList :: ReadS [Interval v] # readPrec :: ReadPrec (Interval v) # readListPrec :: ReadPrec [Interval v] #
Show v => Show (Interval v) Source #
Instance details Defined in 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 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 #
type Rep (Interval v) Source #
Instance details Defined in Data.IntervalMap.FingerTree type Rep (Interval v) = D1 ('MetaData "Interval" "Data.IntervalMap.FingerTree" "fingertree-0.1.5.0-5BqMGuylRI2119MyOz6mqp" 'False) (C1 ('MetaCons "Interval" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 v) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 v)))

low :: Interval v -> v Source #

Lower bound of the interval

high :: Interval v -> v Source #

Upper bound of the interval

point :: v -> Interval v Source #

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

Interval maps

data IntervalMap v a Source #

Map of closed intervals, possibly with duplicates.

Instances

Instances details

Functor (IntervalMap v) Source #
Instance details Defined in Data.IntervalMap.FingerTree Methods fmap :: (a -> b) -> IntervalMap v a -> IntervalMap v b # (<$) :: a -> IntervalMap v b -> IntervalMap v a #
Foldable (IntervalMap v) Source #	Values in lexicographical order of intervals.
Instance details Defined in Data.IntervalMap.FingerTree Methods fold :: Monoid m => IntervalMap v m -> m # foldMap :: Monoid m => (a -> m) -> IntervalMap v a -> 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 #	Traverse the intervals in lexicographical order.
Instance details Defined in 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) #
(Eq v, Eq a) => Eq (IntervalMap v a) Source #
Instance details Defined in Data.IntervalMap.FingerTree Methods (==) :: IntervalMap v a -> IntervalMap v a -> Bool # (/=) :: IntervalMap v a -> IntervalMap v a -> Bool #
(Ord v, Ord a) => Ord (IntervalMap v a) Source #	Lexicographical ordering
Instance details Defined in Data.IntervalMap.FingerTree Methods compare :: IntervalMap v a -> IntervalMap v a -> Ordering # (<) :: IntervalMap v a -> IntervalMap v a -> Bool # (<=) :: IntervalMap v a -> IntervalMap v a -> Bool # (>) :: IntervalMap v a -> IntervalMap v a -> Bool # (>=) :: IntervalMap v a -> IntervalMap v a -> Bool # max :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a # min :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a #
(Show v, Show a) => Show (IntervalMap v a) Source #
Instance details Defined in Data.IntervalMap.FingerTree Methods showsPrec :: Int -> IntervalMap v a -> ShowS # show :: IntervalMap v a -> String # showList :: [IntervalMap v a] -> ShowS #
Generic (IntervalMap v a) Source #
Instance details Defined in 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 #	`union`.
Instance details Defined in 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 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 #
type Rep (IntervalMap v a) Source #
Instance details Defined in 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 and associated value 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.

Extraction

bounds :: Ord v => IntervalMap v a -> Maybe (Interval v) Source #

O(1). bounds m returns Nothing if m is empty, and otherwise Just i, where i is the smallest interval containing all the intervals in the map.

Since: 0.1.3.0

leastView :: Ord v => IntervalMap v a -> Maybe ((Interval v, a), IntervalMap v a) Source #

O(1). leastView m returns Nothing if m is empty, and otherwise Just ((i, x), m'), where i is the least interval, x is the associated value, and m' is the rest of the map.

Since: 0.1.3.0

splitAfter :: Ord v => v -> IntervalMap v a -> (IntervalMap v a, IntervalMap v a) Source #

O(log(min(i,n-i))). splitAfter k m returns a pair of submaps, one consisting of intervals whose lower bound is less than or equal to k, and the other of those whose lower bound is greater.

Since: 0.1.3.0