Safe Haskell	Safe
Language	Haskell98

Data.Tree.Fenwick

Synopsis

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) #
Methods showsPrec :: Int -> FTree a -> ShowS # show :: FTree a -> String # showList :: [FTree a] -> ShowS #

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.