| 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
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. https://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
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
Interval maps
data IntervalMap v a Source #
Map of closed intervals, possibly with duplicates.
Instances
| Foldable (IntervalMap v) Source # | Values in lexicographical order of intervals. | ||||
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. | ||||
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) # | |||||
| Functor (IntervalMap v) Source # | |||||
Defined in Data.IntervalMap.FingerTree Methods fmap :: (a -> b) -> IntervalMap v a -> IntervalMap v b # (<$) :: a -> IntervalMap v b -> IntervalMap v a # | |||||
| Ord v => Monoid (IntervalMap v a) Source # | |||||
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 # | |||||
| Ord v => Semigroup (IntervalMap v a) Source # | |||||
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 # | |||||
| Generic (IntervalMap v a) Source # | |||||
Defined in Data.IntervalMap.FingerTree Associated Types
Methods from :: IntervalMap v a -> Rep (IntervalMap v a) x # to :: Rep (IntervalMap v a) x -> IntervalMap v a # | |||||
| (Show v, Show a) => Show (IntervalMap v a) Source # | |||||
Defined in Data.IntervalMap.FingerTree Methods showsPrec :: Int -> IntervalMap v a -> ShowS # show :: IntervalMap v a -> String # showList :: [IntervalMap v a] -> ShowS # | |||||
| (NFData a, NFData v) => NFData (IntervalMap v a) Source # | |||||
Defined in Data.IntervalMap.FingerTree Methods rnf :: IntervalMap v a -> () # | |||||
| (Eq v, Eq a) => Eq (IntervalMap v a) Source # | |||||
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 | ||||
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 # | |||||
| type Rep (IntervalMap v a) Source # | |||||
Defined in Data.IntervalMap.FingerTree | |||||
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
leastView :: Ord v => IntervalMap v a -> Maybe ((Interval v, a), IntervalMap v a) Source #
splitAfter :: Ord v => v -> IntervalMap v a -> (IntervalMap v a, IntervalMap v a) Source #
O(log(min(i,n-i))). splitAfter k mk, and the other of those whose lower bound is greater.
Since: 0.1.3.0