-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Data structure for querying the set (or count) of intervals covering given point
--   
--   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
@package SegmentTree
@version 0.3


-- | Segment Tree implemented following section 10.3 and 10.4 of
--   
--   <ul>
--   <li>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", <i>Journal of Functional Programming</i> 16:2 (2006) pp
--   197-217.
--   <a>http://www.soi.city.ac.uk/~ross/papers/FingerTree.html</a></li>
--   </ul>
--   
--   Accumulation of results with monoids following "Monoids and Finger
--   Trees",
--   <a>http://apfelmus.nfshost.com/articles/monoid-fingertree.html</a>
--   
--   An amortized running time is given for each operation, with <i>n</i>
--   referring to the number of intervals.
module Data.SegmentTree

-- | Extension of the type <tt>v</tt> that includes plus and minus infinity
data R v
MinusInf :: R v
R :: !v -> R v
PlusInf :: R v
data Interval v
Interval :: !Boundary -> !(R v) -> !(R v) -> !Boundary -> Interval v
[ltype] :: Interval v -> !Boundary
[low] :: Interval v -> !(R v)
[high] :: Interval v -> !(R v)
[htype] :: Interval v -> !Boundary

-- | An interval. The lower bound should be less than or equal to the
--   higher bound.
data Boundary
Open :: Boundary
Closed :: Boundary

-- | Segment Tree is a binary tree that stores Interval in each leaf or
--   branch. By construction (see <a>leaf</a> and <a>branch</a>) 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.
data STree t a
Leaf :: !t -> !(Interval a) -> STree t a
Branch :: !t -> !(Interval a) -> !(STree t a) -> !(STree t a) -> STree t a

-- | Build the <tt>SegmentTree</tt> 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
fromList :: (Monoid t, Measured (Interval a) t, Ord a) => [(a, a)] -> STree t a

-- | Insert interval <tt>i</tt> into segment tree, updating tag values as
--   necessary. Semantics of tags depends on the monoid used (see
--   <a>fromList</a>)
insert :: (Ord a, Measured (Interval a) t) => STree t a -> Interval a -> STree t a

-- | Query the segment tree for the specified point. Time: O(log n)
queryTree :: (Monoid t, Measured (Interval a) t, Ord a) => STree t a -> a -> t

-- | Convenience wrapper around <a>queryTree</a>. Returns count of
--   intervals covering the <tt>point</tt>
countingQuery :: (Measured (Interval a) (Sum b), Ord a) => STree (Sum b) a -> a -> b

-- | Convenience wrapper around <a>queryTree</a> to perform stabbing query.
--   Returns list of intevals coverting the point
stabbingQuery :: (Measured (Interval a) [Interval a], Ord a) => STree [Interval a] a -> a -> [Interval a]
instance (GHC.Show.Show t, GHC.Show.Show a) => GHC.Show.Show (Data.SegmentTree.STree t a)
instance Data.SegmentTree.Measured.Measured (Data.SegmentTree.Interval.Interval a) [Data.SegmentTree.Interval.Interval a]
instance (GHC.Num.Num a, GHC.Num.Num b) => Data.SegmentTree.Measured.Measured (Data.SegmentTree.Interval.Interval a) (Data.Monoid.Sum b)
