Data.Tree.Fenwick

Documentation

data FTree a

Mother structure holds functions that allow to get a value to be summed and comparison function. Below there is a tree of FNodes.

Instances

Show a => Show (FTree a)

empty :: (a -> Double) -> (a -> a -> Ordering) -> FTree a

Creates an empty Fenwick tree.

insert :: a -> FTree a -> FTree a

Inserts a value into a Fenwick tree.

query :: a -> FTree a -> Val

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.)

invQuery :: Val -> FTree a -> Maybe a

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.

toList :: FTree a -> [a]

Extract a sorted list of inserted values from the tree.

toFreqList :: FTree a -> [(Double, a)]

Extract a sorted list of cumulative sums, and corresponding objects from the tree.

fromList :: (a -> a -> Ordering) -> (a -> Val) -> [a] -> FTree a

Creates a tree from a list and helper functions: compare, and value.

size :: FTree a -> Int

Returns number of elements in a tree.

depth :: FTree a -> Int

Returns a maximum depth of a tree.