One join key's worth of elements or tokens: an ordered multiset.
Internal. Everything above it sees a list in arrival order, which to_list/1
produces. Adding and removing one occurrence are both O(1) amortised, however large the
bucket grows — a plain list cannot do both. Buckets are routinely large: a
Rete.Network.Node.RootJoin has nothing to join on, so it stores every matching fact
under one key.
:stack holds every item ever pushed, newest first. :counts holds live occurrences
per value, and :dead holds retracted ones still in the stack. Removal tombstones an
occurrence, instead of rebuilding the stack. to_list/1 then skips the first
dead[value] occurrences of each value, in arrival order — so the oldest occurrence
is the one that went. Tombstones are compacted once they outnumber the living
occurrences. See docs/design/engine.md §7.
iex> alias Rete.Memory.Bucket
iex> {:ok, bucket} = Bucket.new([:a, :b, :a]) |> Bucket.take(:a)
iex> Bucket.to_list(bucket)
[:b, :a]
iex> Bucket.take(bucket, :never_stored)
:errorSummary
Functions
Whether anything live is left.
A bucket holding items, in arrival order.
Adds items behind the ones already there. O(1) per item.
Removes the oldest live occurrence of target, or :error if there is none.
The live items, in arrival order.
Types
@type t() :: %Rete.Memory.Bucket{ counts: %{required(term()) => pos_integer()}, dead: %{required(term()) => pos_integer()}, dead_total: non_neg_integer(), live: non_neg_integer(), stack: [term()] }
Functions
Whether anything live is left.
A bucket holding items, in arrival order.
Adds items behind the ones already there. O(1) per item.
Removes the oldest live occurrence of target, or :error if there is none.
This returns :error, instead of silently doing nothing. A caller that propagated a
retraction of something the bucket never held would corrupt every count below it.
The live items, in arrival order.