API / Belt / MutableSet

MutableSet

A mutable sorted set module which allows customize compare behavior. The implementation uses balanced binary trees, and therefore searching and insertion take time logarithmic in the size of the map.

It also has three specialized inner modules Belt.MutableSet.Int and Belt.MutableSet.String - This module separates data from function which is more verbose but slightly more efficient

RES
module PairComparator = Belt.Id.MakeComparable({
  type t = (int, int)
  let cmp = ((a0, a1), (b0, b1)) =>
    switch Pervasives.compare(a0, b0) {
    | 0 => Pervasives.compare(a1, b1)
    | c => c
    }
})

let mySet = Belt.MutableSet.make(~id=module(PairComparator))
mySet->Belt.MutableSet.add((1, 2))

t

RES
type t<'value, 'id>

'value is the element type

'id the identity of the collection

id

RES
type id<'value, 'id> = Belt_Id.comparable<'value, 'id>

The identity needed for making a set from scratch

make

let make: (~id: id<'value, 'id>) => t<'value, 'id>

Creates a new set by taking in the comparator

fromArray

let fromArray: (array<'value>, ~id: id<'value, 'id>) => t<'value, 'id>

Creates new set from array of elements.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([1, 3, 2, 4], ~id=module(IntCmp))

s0->Belt.MutableSet.toArray /* [1, 2, 3, 4] */

fromSortedArrayUnsafe

let fromSortedArrayUnsafe: (array<'value>, ~id: id<'value, 'id>) => t<'value, 'id>

The same as [fromArray][#fromarray] except it is after assuming the input array is already sorted.

copy

let copy: t<'value, 'id> => t<'value, 'id>

Returns copy of a set.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([1, 3, 2, 4], ~id=module(IntCmp))

let copied = s0->Belt.MutableSet.copy
copied->Belt.MutableSet.toArray /* [1, 2, 3, 4] */

isEmpty

let isEmpty: t<'a, 'b> => bool

Checks if set is empty.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let empty = Belt.MutableSet.fromArray([], ~id=module(IntCmp))
let notEmpty = Belt.MutableSet.fromArray([1], ~id=module(IntCmp))

Belt.MutableSet.isEmpty(empty) /* true */
Belt.MutableSet.isEmpty(notEmpty) /* false */

has

let has: (t<'value, 'a>, 'value) => bool

Checks if element exists in set.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let set = Belt.MutableSet.fromArray([1, 4, 2, 5], ~id=module(IntCmp))

set->Belt.MutableSet.has(3) /* false */
set->Belt.MutableSet.has(1) /* true */

add

let add: (t<'value, 'id>, 'value) => unit

Adds element to set. If element existed in set, value is unchanged.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.make(~id=module(IntCmp))
s0->Belt.MutableSet.add(1)
s0->Belt.MutableSet.add(2)
s0->Belt.MutableSet.add(2)

s0->Belt.MutableSet.toArray /* [1, 2] */

addCheck

let addCheck: (t<'value, 'id>, 'value) => bool

mergeMany

let mergeMany: (t<'value, 'id>, array<'value>) => unit

Adds each element of array to set.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let set = Belt.MutableSet.make(~id=module(IntCmp))

set->Belt.MutableSet.mergeMany([5, 4, 3, 2, 1])
set->Belt.MutableSet.toArray /* [1, 2, 3, 4, 5] */

remove

let remove: (t<'value, 'id>, 'value) => unit

Removes element from set. If element wasn't existed in set, value is unchanged.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([2, 3, 1, 4, 5], ~id=module(IntCmp))
s0->Belt.MutableSet.remove(1)
s0->Belt.MutableSet.remove(3)
s0->Belt.MutableSet.remove(3)

s0->Belt.MutableSet.toArray /* [2,4,5] */

removeCheck

let removeCheck: (t<'value, 'id>, 'value) => bool

removeMany

let removeMany: (t<'value, 'id>, array<'value>) => unit

Removes each element of array from set.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let set = Belt.MutableSet.fromArray([1, 2, 3, 4], ~id=module(IntCmp))

set->Belt.MutableSet.removeMany([5, 4, 3, 2, 1])
set->Belt.MutableSet.toArray /* [] */

union

let union: (t<'value, 'id>, t<'value, 'id>) => t<'value, 'id>

Returns union of two sets.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([5, 2, 3, 5, 6], ~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([5, 2, 3, 1, 5, 4], ~id=module(IntCmp))
let union = Belt.MutableSet.union(s0, s1)
union->Belt.MutableSet.toArray /* [1,2,3,4,5,6] */

intersect

let intersect: (t<'value, 'id>, t<'value, 'id>) => t<'value, 'id>

Returns intersection of two sets.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([5, 2, 3, 5, 6], ~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([5, 2, 3, 1, 5, 4], ~id=module(IntCmp))
let intersect = Belt.MutableSet.intersect(s0, s1)
intersect->Belt.MutableSet.toArray /* [2,3,5] */

diff

let diff: (t<'value, 'id>, t<'value, 'id>) => t<'value, 'id>

Returns elements from first set, not existing in second set.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([5, 2, 3, 5, 6], ~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([5, 2, 3, 1, 5, 4], ~id=module(IntCmp))
Belt.MutableSet.toArray(Belt.MutableSet.diff(s0, s1)) /* [6] */
Belt.MutableSet.toArray(Belt.MutableSet.diff(s1, s0)) /* [1,4] */

subset

let subset: (t<'value, 'id>, t<'value, 'id>) => bool

Checks if second set is subset of first set.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([5, 2, 3, 5, 6], ~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([5, 2, 3, 1, 5, 4], ~id=module(IntCmp))
let s2 = Belt.MutableSet.intersect(s0, s1)
Belt.MutableSet.subset(s2, s0) /* true */
Belt.MutableSet.subset(s2, s1) /* true */
Belt.MutableSet.subset(s1, s0) /* false */

cmp

let cmp: (t<'value, 'id>, t<'value, 'id>) => int

Total ordering between sets. Can be used as the ordering function for doing sets of sets. It compares size first and then iterates over each element following the order of elements.

eq

let eq: (t<'value, 'id>, t<'value, 'id>) => bool

Checks if two sets are equal.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([5, 2, 3], ~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([3, 2, 5], ~id=module(IntCmp))

Belt.MutableSet.eq(s0, s1) /* true */

forEachU

let forEachU: (t<'value, 'id>, (. 'value) => unit) => unit

Same as forEach but takes uncurried functon.

forEach

let forEach: (t<'value, 'id>, 'value => unit) => unit

Applies function f in turn to all elements of set in increasing order.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([5, 2, 3, 5, 6], ~id=module(IntCmp))
let acc = ref(list{})
s0->Belt.MutableSet.forEach(x => acc := Belt.List.add(acc.contents, x))
acc /* [6,5,3,2] */

reduceU

let reduceU: (t<'value, 'id>, 'a, (. 'a, 'value) => 'a) => 'a

reduce

let reduce: (t<'value, 'id>, 'a, ('a, 'value) => 'a) => 'a

Applies function f to each element of set in increasing order. Function f has two parameters: the item from the set and an “accumulator”, which starts with a value of initialValue. reduce returns the final value of the accumulator.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([5, 2, 3, 5, 6], ~id=module(IntCmp))
s0->Belt.MutableSet.reduce(list{}, (acc, element) => acc->Belt.List.add(element)) /* [6,5,3,2] */

everyU

let everyU: (t<'value, 'id>, (. 'value) => bool) => bool

every

let every: (t<'value, 'id>, 'value => bool) => bool

Checks if all elements of the set satisfy the predicate. Order unspecified.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let isEven = x => mod(x, 2) == 0

let s0 = Belt.MutableSet.fromArray([2, 4, 6, 8], ~id=module(IntCmp))
s0->Belt.MutableSet.every(isEven) /* true */

someU

let someU: (t<'value, 'id>, (. 'value) => bool) => bool

some

let some: (t<'value, 'id>, 'value => bool) => bool

Checks if at least one element of the set satisfies the predicate.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let isOdd = x => mod(x, 2) != 0

let s0 = Belt.MutableSet.fromArray([1, 2, 4, 6, 8], ~id=module(IntCmp))
s0->Belt.MutableSet.some(isOdd) /* true */

keepU

let keepU: (t<'value, 'id>, (. 'value) => bool) => t<'value, 'id>

keep

let keep: (t<'value, 'id>, 'value => bool) => t<'value, 'id>

Returns the set of all elements that satisfy the predicate.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let isEven = x => mod(x, 2) == 0

let s0 = Belt.MutableSet.fromArray([1, 2, 3, 4, 5], ~id=module(IntCmp))
let s1 = s0->Belt.MutableSet.keep(isEven)

s1->Belt.MutableSet.toArray /* [2, 4] */

partitionU

let partitionU: (t<'value, 'id>, (. 'value) => bool) => (t<'value, 'id>, t<'value, 'id>)

partition

let partition: (t<'value, 'id>, 'value => bool) => (t<'value, 'id>, t<'value, 'id>)

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let isOdd = x => mod(x, 2) != 0

let s0 = Belt.MutableSet.fromArray([1, 2, 3, 4, 5], ~id=module(IntCmp))
let (s1, s2) = s0->Belt.MutableSet.partition(isOdd)

s1->Belt.MutableSet.toArray /* [1,3,5] */
s2->Belt.MutableSet.toArray /* [2,4] */

size

let size: t<'value, 'id> => int

Returns size of the set.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([1, 2, 3, 4], ~id=module(IntCmp))

s0->Belt.MutableSet.size /* 4 */

toList

let toList: t<'value, 'id> => list<'value>

Returns list of ordered set elements.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([3, 2, 1, 5], ~id=module(IntCmp))

s0->Belt.MutableSet.toList /* [1,2,3,5] */

toArray

let toArray: t<'value, 'id> => array<'value>

Returns array of ordered set elements.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([3, 2, 1, 5], ~id=module(IntCmp))

s0->Belt.MutableSet.toArray /* [1,2,3,5] */

minimum

let minimum: t<'value, 'id> => option<'value>

Returns minimum value of the collection. None if collection is empty.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.make(~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([3, 2, 1, 5], ~id=module(IntCmp))

s0->Belt.MutableSet.minimum /* None */
s1->Belt.MutableSet.minimum /* Some(1) */

minUndefined

let minUndefined: t<'value, 'id> => Js.undefined<'value>

Returns minimum value of the collection. undefined if collection is empty.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.make(~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([3, 2, 1, 5], ~id=module(IntCmp))

s0->Belt.MutableSet.minUndefined /* undefined */
s1->Belt.MutableSet.minUndefined /* 1 */

maximum

let maximum: t<'value, 'id> => option<'value>

Returns maximum value of the collection. None if collection is empty.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.make(~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([3, 2, 1, 5], ~id=module(IntCmp))

s0->Belt.MutableSet.maximum /* None */
s1->Belt.MutableSet.maximum /* Some(5) */

maxUndefined

let maxUndefined: t<'value, 'id> => Js.undefined<'value>

Returns maximum value of the collection. undefined if collection is empty.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.make(~id=module(IntCmp))
let s1 = Belt.MutableSet.fromArray([3, 2, 1, 5], ~id=module(IntCmp))

s0->Belt.MutableSet.maxUndefined /* undefined */
s1->Belt.MutableSet.maxUndefined /* 5 */

get

let get: (t<'value, 'id>, 'value) => option<'value>

Returns the reference of the value which is equivalent to value using the comparator specifiecd by this collection. Returns None if element does not exist.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([1, 2, 3, 4, 5], ~id=module(IntCmp))

s0->Belt.MutableSet.get(3) /* Some(3) */
s0->Belt.MutableSet.get(20) /* None */

getUndefined

let getUndefined: (t<'value, 'id>, 'value) => Js.undefined<'value>

Same as get but returns undefined when element does not exist.

getExn

let getExn: (t<'value, 'id>, 'value) => 'value

Same as get but raise when element does not exist.

split

let split: (t<'value, 'id>, 'value) => ((t<'value, 'id>, t<'value, 'id>), bool)

Returns a tuple ((smaller, larger), present), present is true when element exist in set.

RES
module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = Pervasives.compare
})

let s0 = Belt.MutableSet.fromArray([1, 2, 3, 4, 5], ~id=module(IntCmp))

let ((smaller, larger), present) = s0->Belt.MutableSet.split(3)

present /* true */
smaller->Belt.MutableSet.toArray /* [1,2] */
larger->Belt.MutableSet.toArray /* [4,5] */

checkInvariantInternal

let checkInvariantInternal: t<'a, 'b> => unit

raise when invariant is not held