THashSet[A: Any val, T: Comparable[T] val, B: (BiasInsert val | BiasDelete val), H: HashFunction[A] val]¶

[Source]

A mutable set with last-write-wins semantics for insertion and deletion. That is, every insertion and deletion operation includes a logical timestamp (U64 by default, though it may be any Comparable immutable type), and operations are overridden only by those with a higher logical timestamp.

This implies that the timestamps must be correct (or at least logically so) in order for the last-write-wins semantics to hold true.

This data structure is conceptually composed of two grow-only sets (GSet); one for insertions and one for deletions. Both sets include the logical timestamp for each element. An element is present in the combined logical set if it is present in only the insertion set (not in the deletion set), or if the logical timestamp of the insertion is higher than that of the deletion.

The actual implementation is a bit more memory-optimized than a literal pair of GSets - it stores the data as a map with the elements as keys and each value being a 2-tuple with the highest logical timestamp so far and a boolean indicating whether that timestamp represents an insertion or a deletion.

If the logical timestamp is equal for two compared operations, the tie will be broken by the bias type parameter. BiasInsert implies that inserts will override deletions in a tie, while BiasDelete implies the opposite. The default bias is BiasInsert.

Because the set is composed of two grow-only sets that are eventually consistent when converged, the overall result is also eventually consistent. The same bias must be used on all replicas for tie results to be consistent.

All mutator methods accept and return a convergent delta-state.

class ref THashSet[A: Any val, T: Comparable[T] val, B: (BiasInsert val | BiasDelete val), H: HashFunction[A] val] is
  Comparable[THashSet[A, T, B, H] ref] ref,
  Convergent[THashSet[A, T, B, H] ref] ref,
  Replicated ref

Implements¶

Comparable[THashSet[A, T, B, H] ref] ref
Convergent[THashSet[A, T, B, H] ref] ref
Replicated ref

Constructors¶

create¶

[Source]

new ref create()
: THashSet[A, T, B, H] ref^

Returns¶

THashSet[A, T, B, H] ref^

Public Functions¶

is_empty¶

[Source]

Return true if the data structure contains no information (bottom state).

fun box is_empty()
: Bool val

Returns¶

Bool val

size¶

[Source]

Return the number of items in the set.

fun box size()
: USize val

Returns¶

USize val

apply¶

[Source]

Return the logical timestamp if it's in the set, otherwise raise an error.

fun box apply(
  value: val->A)
: T ?

Parameters¶

value: val->A

Returns¶

T ?

contains¶

[Source]

Check whether the set contains the given value.

fun box contains(
  value: val->A)
: Bool val

Parameters¶

value: val->A

Returns¶

Bool val

clear[optional D: THashSet[A, T, B, H] ref]¶

[Source]

Remove all elements from the set. Accepts and returns a convergent delta-state.

fun ref clear[optional D: THashSet[A, T, B, H] ref](
  timestamp: T,
  delta: D = recover THashSet[A, T, B, H] end)
: D^

Parameters¶

timestamp: T
delta: D = recover THashSet[A, T, B, H] end

Returns¶

D^

set[optional D: THashSet[A, T, B, H] ref]¶

[Source]

Add a value to the set. Accepts and returns a convergent delta-state.

fun ref set[optional D: THashSet[A, T, B, H] ref](
  value: A,
  timestamp: T,
  delta: D = recover THashSet[A, T, B, H] end)
: D^

Parameters¶

value: A
timestamp: T
delta: D = recover THashSet[A, T, B, H] end

Returns¶

D^

unset[optional D: THashSet[A, T, B, H] ref]¶

[Source]

Remove a value from the set. Accepts and returns a convergent delta-state.

fun ref unset[optional D: THashSet[A, T, B, H] ref](
  value: box->A!,
  timestamp: T,
  delta: D = recover THashSet[A, T, B, H] end)
: D^

Parameters¶

value: box->A!
timestamp: T
delta: D = recover THashSet[A, T, B, H] end

Returns¶

D^

union[optional D: THashSet[A, T, B, H] ref]¶

[Source]

Add everything in the given iterator to the set. Accepts and returns a convergent delta-state.

fun ref union[optional D: THashSet[A, T, B, H] ref](
  that: Iterator[(A , T)] ref,
  delta: D = recover THashSet[A, T, B, H] end)
: D^

Parameters¶

that: Iterator[(A , T)] ref
delta: D = recover THashSet[A, T, B, H] end

Returns¶

D^

converge¶

[Source]

Converge from the given TSet into this one. For this data type, the convergence is the union of both constituent sets. Returns true if the convergence added new information to the data structure.

fun ref converge(
  that: THashSet[A, T, B, H] box)
: Bool val

Parameters¶

that: THashSet[A, T, B, H] box

Returns¶

Bool val

result¶

[Source]

Return the elements of the resulting logical set as a single flat set. Information about specific deletions is discarded, so that the case of a deleted element is indistinct from that of an element never inserted.

fun box result()
: HashSet[A, H] ref

Returns¶

HashSet[A, H] ref

map¶

[Source]

Return the elements of the resulting logical set as a single flat map, with the elements as keys and logical timestamps of the insertion as timestamps. Information about specific deletions is discarded, so that the case of a deleted element is indistinct from that of an element never inserted.

fun box map()
: HashMap[A, T, H] ref

Returns¶

HashMap[A, T, H] ref

string¶

[Source]

Return a best effort at printing the set. If A is a Stringable box, use the string representation of each value; otherwise print the as question marks.

fun box string()
: String iso^

Returns¶

String iso^

eq¶

[Source]

fun box eq(
  that: THashSet[A, T, B, H] box)
: Bool val

Parameters¶

that: THashSet[A, T, B, H] box

Returns¶

Bool val

ne¶

[Source]

fun box ne(
  that: THashSet[A, T, B, H] box)
: Bool val

Parameters¶

that: THashSet[A, T, B, H] box

Returns¶

Bool val

lt¶

[Source]

fun box lt(
  that: THashSet[A, T, B, H] box)
: Bool val

Parameters¶

that: THashSet[A, T, B, H] box

Returns¶

Bool val

le¶

[Source]

fun box le(
  that: THashSet[A, T, B, H] box)
: Bool val

Parameters¶

that: THashSet[A, T, B, H] box

Returns¶

Bool val

gt¶

[Source]

fun box gt(
  that: THashSet[A, T, B, H] box)
: Bool val

Parameters¶

that: THashSet[A, T, B, H] box

Returns¶

Bool val

ge¶

[Source]

fun box ge(
  that: THashSet[A, T, B, H] box)
: Bool val

Parameters¶

that: THashSet[A, T, B, H] box

Returns¶

Bool val

values¶

[Source]

fun box values()
: Iterator[A] ref^

Returns¶

Iterator[A] ref^

timestamps¶

[Source]

fun box timestamps()
: Iterator[T] ref^

Returns¶

Iterator[T] ref^

pairs¶

[Source]

fun box pairs()
: Iterator[(A , T)] ref^

Returns¶

Iterator[(A , T)] ref^

from_tokens¶

[Source]

Deserialize an instance of this data structure from a stream of tokens.

fun ref from_tokens(
  that: TokensIterator ref)
: None val ?

Parameters¶

that: TokensIterator ref

Returns¶

None val ?

each_token¶

[Source]

Serialize the data structure, capturing each token into the given Tokens.

fun ref each_token(
  tokens: Tokens ref)
: None val

Parameters¶

tokens: Tokens ref

Returns¶

None val

compare¶

[Source]

fun box compare(
  that: THashSet[A, T, B, H] box)
: Compare

Parameters¶

that: THashSet[A, T, B, H] box

Returns¶

Compare