SegmentTree-0.3: Data structure for querying the set (or count) of intervals covering given point

Copyright(c) Dmitry Astapov 2010
LicenseBSD-style
Maintainerdastapov@gmail.com
Stabilityexperimental
Portabilitynon-portable (MPTCs, etc - see above)
Safe HaskellSafe
LanguageHaskell98

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

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 

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