RandomTree.Weighted

This module provides data structure that allows random picking up from a collection of data in O(log(N)) time. You can set weight of each element with WideFloat from kudzu-forest/elm-wide-float package.

Types

type Tree a

Type that represents binary tree with weighted elements for random picking up.

type alias Weighted a =

{ weight : WideFloat

, content : a

}

Type alias that represents each weighted contents in Tree.

type alias WideFloat =

WideFloat

Type that represent floating point number with wider range than Float in core package. This is introduced for preventing overflow of exponentially changing value. If you need to directly manipulate values of WideFloat, please hit elm install kudzu-forest/elm-wide-float in your terminal.

Operation around weighted datum

adjustWeight : Float -> Weighted a -> Weighted a

Returns weighted datum whose weight is multiplied with the given Float.

adjustContent : (a -> b) -> Weighted a -> Weighted b

Maps content in Element.

Creation

singleton : Weighted a -> Tree a

Returns a Tree that has only one element.

fromList : Weighted a -> List (Weighted a) -> Tree a

Returns a Tree that has all element in given list.

fromPairs : ( Float, a ) -> List ( Float, a ) -> Tree a

Creates Tree from list of tuples of a Float value corresponding to its weight as the first component, and a datum as the second component. the weighter it is, the higher probability it is chosen in.

Insertion

insert : Weighted a -> Tree a -> Tree a

Inserts a Weighted data to an already-existing Tree.

insertWithRelativeWeight : Float -> a -> Tree a -> Tree a

Inserts an element into the tree. The first parameter denotes the relative weight(1 means the whole weight of the original tree).

insertListWithRelativeWeight : List ( Float, a ) -> Tree a -> Tree a

Inserts all elements of given list into the tree of second parameter. The first components of the tuple denotes the relative weight(1 means the whole weight of the original tree).

Modification

delete : a -> Tree a -> Maybe (Tree a)

Removes any number of elements which is the same as the first parameter from the second parameter. The returned value is wrapped in Maybe.

map : (a -> b) -> Tree a -> Tree b

Maps all the content of the tree, with the weights unchanged.

filter : (WideFloat -> a -> Bool) -> Tree a -> Maybe (Tree a)

Removes any number of elements which passes the test function given as the first parameter from the second parameter. The returned value is wrapped in Maybe.

Random Pick Up

get : Tree a -> Generator a

Random generator that generates one of the elements conteined in Tree given as parameter. The time complexity is O(log(N)) where N denotes the size of the tree.

take : Tree a -> Generator ( Weighted a, Maybe (Tree a) )

Random generator that generates one of the elements conteined in Tree, paired with the rest part of the tree. If the Tree has only one element, then Nothing is returned as the second component. The time complexity is O(log(N)) where N denotes the size of the tree.

replace : Weighted a -> Tree a -> Generator ( Weighted a, Tree a )

Random generator that replaces one weighted data from the tree and generates a pair consisting of the removed data and resultant tree.

Query

count : Tree a -> Int

Returns how many elements the tree has.

totalWeight : Tree a -> WideFloat

Returns the sum of weight of all the elements in the tree.

kudzu-forest/elm-random-tree/2.0.0