fingertree-0.1.4.1: Generic finger-tree structure, with example instances

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

Data.IntervalMap.FingerTree

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 upper bound.

Constructors

 Interval v v Lower and upper bounds of the interval.

Instances

 Eq v => Eq (Interval v) Source # Methods(==) :: Interval v -> Interval v -> Bool #(/=) :: Interval v -> Interval v -> Bool # Ord v => Ord (Interval v) Source # Methodscompare :: 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 # MethodsreadsPrec :: Int -> ReadS (Interval v) # Show v => Show (Interval v) Source # MethodsshowsPrec :: Int -> Interval v -> ShowS #show :: Interval v -> String #showList :: [Interval v] -> ShowS # Source # Associated Typestype Rep (Interval v) :: * -> * # Methodsfrom :: Interval v -> Rep (Interval v) x #to :: Rep (Interval v) x -> Interval v # type Rep (Interval v) Source # type Rep (Interval v) = D1 * (MetaData "Interval" "Data.IntervalMap.FingerTree" "fingertree-0.1.4.1-GNuCBfIfWR5LF1bN45m0JD" False) (C1 * (MetaCons "Interval" PrefixI False) ((:*:) * (S1 * (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 * v)) (S1 * (MetaSel (Nothing 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

 Source # Methodsfmap :: (a -> b) -> IntervalMap v a -> IntervalMap v b #(<\$) :: a -> IntervalMap v b -> IntervalMap v a # Source # Values in lexicographical order of intervals. Methodsfold :: 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 # Source # Traverse the intervals in lexicographical order. Methodstraverse :: 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 # 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 Methodscompare :: 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 # MethodsshowsPrec :: Int -> IntervalMap v a -> ShowS #show :: IntervalMap v a -> String #showList :: [IntervalMap v a] -> ShowS # Generic (IntervalMap v a) Source # Associated Typestype Rep (IntervalMap v a) :: * -> * # Methodsfrom :: 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. 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. Methodsmempty :: 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 # 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