HaskellWorks.Data.IntervalMap.Strict

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

Intervals

data Interval v

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

Constructors

Interval

Fields

• low :: !v
• high :: !v

Instances

Eq v => Eq (Interval v)

Methods

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

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

Ord v => Ord (Interval v)

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)

Methods

showsPrec :: Int -> Interval v -> ShowS

show :: Interval v -> String

showList :: [Interval v] -> ShowS

Generic (Interval v)

Associated Types

type Rep (Interval v) :: * -> *

Methods

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

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

NFData v => NFData (Interval v)

Methods

rnf :: Interval v -> ()

type Rep (Interval v)

type Rep (Interval v) = D1 * (MetaData "Interval" "HaskellWorks.Data.IntervalMap.Strict" "hw-fingertree-strict-0.1.1.1-1UsuYkohZPGJ8bjSrBSs55" False) (C1 * (MetaCons "Interval" PrefixI True) ((:*:) * (S1 * (MetaSel (Just Symbol "low") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 * v)) (S1 * (MetaSel (Just Symbol "high") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 * v))))

point :: v -> Interval v

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

Interval maps

newtype IntervalMap v a

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)

Methods

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

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

Foldable (IntervalMap v)

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)

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)

Methods

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

(/=) :: IntervalMap v a -> IntervalMap v a -> Bool

(Show a, Show v) => Show (IntervalMap v a)

Methods

showsPrec :: Int -> IntervalMap v a -> ShowS

show :: IntervalMap v a -> String

showList :: [IntervalMap v a] -> ShowS

Generic (IntervalMap v a)

Associated Types

type Rep (IntervalMap v a) :: * -> *

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)

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)

empty and union.

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)

Methods

rnf :: IntervalMap v a -> ()

type Rep (IntervalMap v a)

type Rep (IntervalMap v a)

empty :: IntervalMap v a

O(1). The empty interval map.

singleton :: Interval v -> a -> IntervalMap v a

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

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

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

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)]

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)]

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)]

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