-- 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 <a>Computational
--   Geometry, Algorithms and Applications</a>, 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
--   <a>Computational Geometry, Algorithms and Applications</a>, 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 <a>Monoids and Finger
--   Trees</a>,
--   http:<i></i>apfelmus.nfshost.com<i>articles</i>monoid-fingertree.html
--   
--   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 <a>tag</a> of type <a>t</a> (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 <a>atomic intervals</a> * They are used
--   to build <a>skeleton</a> binary tree * Each supplied interval is then
--   <a>inserted</a> 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 (Num a, Num b) => Measured (Interval a) (Sum b)
instance Measured (Interval a) [Interval a]
instance (Show t, Show a) => Show (STree t a)