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

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

Eq v => Eq (Interval v) Source # |
Instance details Defined in Data.IntervalMap.FingerTree Methods (==) :: Interval v -> Interval v -> Bool Source # (/=) :: Interval v -> Interval v -> Bool Source #
Ord v => Ord (Interval v) Source # |

Instance details

Defined in Data.IntervalMap.FingerTree

Methods

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

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

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

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

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

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

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

Read v => Read (Interval v) Source # |
Instance details Defined in Data.IntervalMap.FingerTree Methods readsPrec :: Int -> ReadS (Interval v) Source # readList :: ReadS [Interval v] Source # readPrec :: ReadPrec (Interval v) Source # readListPrec :: ReadPrec [Interval v] Source #
Show v => Show (Interval v) Source # |
Instance details Defined in Data.IntervalMap.FingerTree Methods showsPrec :: Int -> Interval v -> ShowS Source # show :: Interval v -> String Source # showList :: [Interval v] -> ShowS Source #
Generic (Interval v) Source # |
Instance details Defined in Data.IntervalMap.FingerTree Associated Types type Rep (Interval v) :: Type -> Type Source # Methods from :: Interval v -> Rep (Interval v) x Source # to :: Rep (Interval v) x -> Interval v Source #
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.4.2-3y9RCeoabqFEsIFOGn6xXZ" 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

Functor (IntervalMap v) Source # |
Instance details Defined in Data.IntervalMap.FingerTree Methods fmap :: (a -> b) -> IntervalMap v a -> IntervalMap v b Source # (<$) :: a -> IntervalMap v b -> IntervalMap v a Source #
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 Source #

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

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

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

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

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

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

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

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

null :: IntervalMap v a -> Bool Source #

length :: IntervalMap v a -> Int Source #

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

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

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

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

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

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) Source # sequenceA :: Applicative f => IntervalMap v (f a) -> f (IntervalMap v a) Source # mapM :: Monad m => (a -> m b) -> IntervalMap v a -> m (IntervalMap v b) Source # sequence :: Monad m => IntervalMap v (m a) -> m (IntervalMap v a) Source #
(Eq v, Eq a) => Eq (IntervalMap v a) Source # |
Instance details Defined in Data.IntervalMap.FingerTree Methods (==) :: IntervalMap v a -> IntervalMap v a -> Bool Source # (/=) :: IntervalMap v a -> IntervalMap v a -> Bool Source #
(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 Source #

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

(<=) :: IntervalMap v a -> IntervalMap v a -> Bool Source #

(>) :: IntervalMap v a -> IntervalMap v a -> Bool Source #

(>=) :: IntervalMap v a -> IntervalMap v a -> Bool Source #

max :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a Source #

min :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a Source #

(Show v, Show a) => Show (IntervalMap v a) Source # |
Instance details Defined in Data.IntervalMap.FingerTree Methods showsPrec :: Int -> IntervalMap v a -> ShowS Source # show :: IntervalMap v a -> String Source # showList :: [IntervalMap v a] -> ShowS Source #
Generic (IntervalMap v a) Source # |
Instance details Defined in Data.IntervalMap.FingerTree Associated Types type Rep (IntervalMap v a) :: Type -> Type Source # Methods from :: IntervalMap v a -> Rep (IntervalMap v a) x Source # to :: Rep (IntervalMap v a) x -> IntervalMap v a Source #
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 Source # sconcat :: NonEmpty (IntervalMap v a) -> IntervalMap v a Source # stimes :: Integral b => b -> IntervalMap v a -> IntervalMap v a Source #
Ord v => Monoid (IntervalMap v a) Source # | `empty` and `union`.
Instance details Defined in Data.IntervalMap.FingerTree Methods mempty :: IntervalMap v a Source # mappend :: IntervalMap v a -> IntervalMap v a -> IntervalMap v a Source # mconcat :: [IntervalMap v a] -> IntervalMap v a Source #
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