Library

Module

Module type

Parameter

Class

Class type

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">

On This Page

Legend:

Library

Module

Module type

Parameter

Class

Class type

Library

Module

Module type

Parameter

Class

Class type

Functor building an implementation of the urn structure given a weight type.

`module Weight : WeightType`

`type weight = Weight.t`

The type of weights.

`singleton w x`

returns the one-element urn containing `x`

with weight `w`

. Time complexity O(1).

`of_list was`

creates an urn from a list of pairs of weights and values. Time complexity O(n).

`add w a ur`

returns an urn containing the same weights and elements as `ur`

but additionally containing `a`

with weight `w`

. Time complexity O(log n).

Add the weight-value pairs in the sequence to the urn. Time complexity O(m log n), where m is the length of the sequence.

Add the weight-value pairs in the list to the urn. Time complexity O(m log n), where m is the length of the list.

`val sample : 'a t -> 'a`

`sample ur`

samples an element of the urn `ur`

and returns it. Time complexity O(log n).

`remove ur`

samples an element of the urn `ur`

and returns it along with a new urn with that element removed, or `None`

if the new urn would be empty. Time complexity O(log n).

`replace w a ur`

samples the urn `ur`

, and returns the sampled element and its weight along with a new urn with the sampled elements removed and `a`

with weight `w`

added. Time complexity O(log n).

`update f ur`

samples an element of the urn `ur`

, then takes the chosen element `a`

and its weight `w`

, and replaces it with `f w a`

, returning a triple of `(w, a), f w a, ur'`

where `ur'`

is the urn containing all the elements and weights of `ur`

but with the chosen `w, a`

replaced by `f w a`

. Time complexity O(log n).

```
val update_opt :
(weight -> 'a -> (weight * 'a) option) ->
'a t ->
(weight * 'a) * (weight * 'a) option * 'a t option
```

`update f ur`

samples an element of the urn `ur`

, then takes the chosen element `a`

and its weight `w`

, and applies `f`

to them. If `f w a`

returns `None`

then the element is removed from the urn. If `f w a`

returns `Some (w', a')`

then the chosen elements weight and value is replaced by `w'`

and `a'`

respectively. The elements of the returned triple are as in `update`

. Time complexity O(log n).

`val size : 'a t -> int`

`size ur`

returns the total number of elements in the urn `ur`

. Time complexity O(1).

On This Page