Copyright	(c) Dmitry Astapov 2010
License	BSD-style
Maintainer	dastapov@gmail.com
Stability	experimental
Portability	non-portable (MPTCs, etc - see above)
Safe Haskell	Safe
Language	Haskell98

Data.SegmentTree

Description

Segment Tree implemented following section 10.3 and 10.4 of

Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars "Computational Geometry, Algorithms and Applications", Third Edition (2008) pp 231-237 "Finger trees: a simple general-purpose data structure", Journal of Functional Programming 16:2 (2006) pp 197-217. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html

Accumulation of results with monoids following "Monoids and Finger Trees", http://apfelmus.nfshost.com/articles/monoid-fingertree.html

An amortized running time is given for each operation, with n referring to the number of intervals.

Synopsis

Documentation

data R v #

Extension of the type v that includes plus and minus infinity

Constructors

MinusInf
R !v
PlusInf

Instances

Bounded (R v) #
Methods minBound :: R v # maxBound :: R v #
Eq v => Eq (R v) #
Methods (==) :: R v -> R v -> Bool # (/=) :: R v -> R v -> Bool #
Ord v => Ord (R v) #
Methods compare :: R v -> R v -> Ordering # (<) :: R v -> R v -> Bool # (<=) :: R v -> R v -> Bool # (>) :: R v -> R v -> Bool # (>=) :: R v -> R v -> Bool # max :: R v -> R v -> R v # min :: R v -> R v -> R v #
Show v => Show (R v) #
Methods showsPrec :: Int -> R v -> ShowS # show :: R v -> String # showList :: [R v] -> ShowS #

data Interval v #

Constructors

Interval
Fields ltype :: !Boundary low :: !(R v) high :: !(R v) htype :: !Boundary

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 #

data Boundary #

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

Constructors

Open
Closed

Instances

Eq Boundary #
Methods (==) :: Boundary -> Boundary -> Bool # (/=) :: Boundary -> Boundary -> Bool #
Ord Boundary #
Methods compare :: Boundary -> Boundary -> Ordering # (<) :: Boundary -> Boundary -> Bool # (<=) :: Boundary -> Boundary -> Bool # (>) :: Boundary -> Boundary -> Bool # (>=) :: Boundary -> Boundary -> Bool # max :: Boundary -> Boundary -> Boundary # min :: Boundary -> Boundary -> Boundary #

data STree t a #

Segment Tree is a binary tree that stores Interval in each leaf or branch. By construction (see leaf and branch) intervals in branches should be union of the intervals from left and right subtrees.

Additionally, each node carries a "tag" of type "t" (which should be monoid). By supplying different monoids, segment tree could be made to support different types of stabbing queries: Sum or Integer monoid will give tree that counts hits, and list or Set monoids will give a tree that returns actual intervals containing point.

Constructors

Leaf !t !(Interval a)
Branch !t !(Interval a) !(STree t a) !(STree t a)

Instances

(Show t, Show a) => Show (STree t a) #
Methods showsPrec :: Int -> STree t a -> ShowS # show :: STree t a -> String # showList :: [STree t a] -> ShowS #

fromList :: (Monoid t, Measured (Interval a) t, Ord a) => [(a, a)] -> STree t a #

Build the SegmentTree for the given list of pair of points. Time: O(n*log n) Segment tree is built as follows: * Supplied list of point pairs define so-called "atomic intervals" * They are used to build "skeleton" binary tree * Each supplied interval is then "inserted" into this tree, updating tag values in tree branches and leaves

insert :: (Ord a, Measured (Interval a) t) => STree t a -> Interval a -> STree t a #

Insert interval i into segment tree, updating tag values as necessary. Semantics of tags depends on the monoid used (see fromList)

queryTree :: (Monoid t, Measured (Interval a) t, Ord a) => STree t a -> a -> t #

Query the segment tree for the specified point. Time: O(log n)

countingQuery :: (Measured (Interval a) (Sum b), Ord a) => STree (Sum b) a -> a -> b #

Convenience wrapper around queryTree. Returns count of intervals covering the point

stabbingQuery :: (Measured (Interval a) [Interval a], Ord a) => STree [Interval a] a -> a -> [Interval a] #

Convenience wrapper around queryTree to perform stabbing query. Returns list of intevals coverting the point