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


-- | Data structure for O(log n) mconcats on list intervals
--   
--   The <a>SegmentTree</a> data structure allows for logarithmic time
--   accumulations on preprocessed lists of <a>Monoid</a>s.
@package SegmentTree
@version 0.1


-- | This module contains the <a>SegmentTree</a> data structure, its
--   constructor and the query function.
--   
--   Example Usage:
--   
--   <pre>
--   import Data.Monoid
--   import Data.SegmentTree
--   ...
--   st = mkTree $ map Sum [0..10]
--   ...
--   queryTree st (0, 10) == Sum 55
--   queryTree st (5, 10) == Sum 45
--   queryTree st (0, 4)  == Sum 10
--   </pre>
module Data.SegmentTree

-- | A <a>SegmentTree</a> is a binary tree and the bounds of its
--   corresponding interval.
data (Monoid a) => SegmentTree a
SegmentTree :: (Tree a) -> (Int, Int) -> SegmentTree a

-- | Build the <a>SegmentTree</a> for the given list. Time: O(n*log n)
mkTree :: (Monoid a) => [a] -> SegmentTree a

-- | Query the <a>SegmentTree</a> for the specified closed interval. Time:
--   O(log n)
queryTree :: (Monoid a) => SegmentTree a -> (Int, Int) -> a
instance (Monoid a) => Show (SegmentTree a)


-- | Example uses of <a>SegmentTree</a>s.
module Data.SegmentTree.Examples

-- | Find the sum of the elements in the interval [l, u].
intervalSum :: SegmentTree (Sum Int) -> (Int, Int) -> Int

-- | Find out if any of the elements are True in the interval [l, u].
intervalAny :: SegmentTree Any -> (Int, Int) -> Bool
newtype (Integral a) => GCD a
GCD :: a -> GCD a
getGCD :: GCD a -> a

-- | Find the greatest common divisor of the elements in the interval [l,
--   u].
intervalGCD :: SegmentTree (GCD Int) -> (Int, Int) -> Int

-- | Concatenate the strings in the interval [l, u].
intervalConcat :: SegmentTree String -> (Int, Int) -> String
newtype Unwords
Unwords :: String -> Unwords
getUnwords :: Unwords -> String

-- | Unwords the words in the interval [l, u].
intervalUnwords :: SegmentTree Unwords -> (Int, Int) -> String
instance Monoid Unwords
instance (Integral a) => Monoid (GCD a)