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


-- | Data structure for fast query and update of cumulative sums
--   
--   Fenwick trees are a O(log N) data structure for updating cumulative
--   sums. This implementation comes with an operation to find a least
--   element for which real-valued cumulative sum reaches certain value,
--   and allows for storage of arbitrary information in the nodes.
@package FenwickTree
@version 0.1

module Data.Tree.Fenwick

-- | Mother structure holds functions that allow to get a value to be
--   summed and comparison function. Below there is a tree of
--   <a>FNode</a>s.
data FTree a

-- | Creates an empty Fenwick tree.
empty :: (a -> Double) -> (a -> a -> Ordering) -> FTree a

-- | Inserts a value into a Fenwick tree.
insert :: a -> FTree a -> FTree a

-- | Finds a cumulative sum up to a given node of a Fenwick tree. Note: if
--   the node is not found, a sum at point corresponding to this node is
--   still returned. (Convenient for finding CDF value at a given point.)
query :: a -> FTree a -> Val

-- | Finds a node corresponding to a given cumulative sum, convenient for
--   sampling quantile function of a distribution. NOTE: returns an answer
--   only up to a cumulative sum of a whole tree.
invQuery :: Val -> FTree a -> Maybe a

-- | Extract a sorted list of inserted values from the tree.
toList :: FTree a -> [a]

-- | Extract a sorted list of cumulative sums, and corresponding objects
--   from the tree.
toFreqList :: FTree a -> [(Double, a)]

-- | Creates a tree from a list and helper functions: compare, and value.
fromList :: (a -> a -> Ordering) -> (a -> Val) -> [a] -> FTree a

-- | Returns number of elements in a tree.
size :: FTree a -> Int

-- | Returns a maximum depth of a tree.
depth :: FTree a -> Int
instance Show a => Show (FNode a)
instance Show a => Show (FTree a)