Struct LatticeMap 

pub struct LatticeMap<K, V> { /* private fields */ }

Pointwise map lattice over HashMap.

This is a reusable building block for CRDT states that look like “map from IDs to lattice values”.

Keys are optional; values form a join-semilattice. The induced lattice order is:

m1 ≤ m2 iff for all k, m1[k] ≤ m2[k]

Operationally, join is:

• keys: union of the key sets
• values: pointwise join on overlapping keys

Bottom is the empty map.

Key growth and deletion

Under this lattice, the set of keys grows monotonically under join (it is the union of key sets). As a result, LatticeMap does not directly support deletion semantics (there is no “remove” operation that is monotone w.r.t. this order).

Different applications want different deletion semantics and may require causal context, so LatticeMap intentionally leaves deletion policy to composition.

To model deletions, encode them in the value lattice V (tombstones), or use a dedicated set/map CRDT depending on the desired semantics. For example, one simple tombstone pattern is:

use algebra::{LatticeMap, LWW};

// Treat `None` as "deleted" at the application layer.
// Conflicts resolve via LWW; a delete can be represented by
// writing `None`.
type Tombstoned<V> = LWW<Option<V>>;
type Map<K, V> = LatticeMap<K, Tombstoned<V>>;

(If this pattern becomes common, we can add a small helper wrapper type later, but the policy is intentionally left to composition.)

Example: Watermark tracking

Track the low watermark across multiple ranks where each rank reports its progress monotonically:

use algebra::JoinSemilattice;
use algebra::LatticeMap;
use algebra::Min;

// Rank 0 reports progress: 100
let mut state1: LatticeMap<u32, Min<u64>> = LatticeMap::new();
state1.insert(0, Min(100));

// Rank 1 reports progress: 200
let mut state2: LatticeMap<u32, Min<u64>> = LatticeMap::new();
state2.insert(1, Min(200));

// Merge: union keys, pointwise min on values
let merged = state1.join(&state2);

// Low watermark is the min across all ranks
let watermark = merged.iter().map(|(_, v)| v.0).min().unwrap();
assert_eq!(watermark, 100); // min(rank0=100, rank1=200)

Commutativity and Idempotence

Unlike a simple HashMap with last-write-wins merge, LatticeMap provides true commutativity:

use algebra::JoinSemilattice;
use algebra::LatticeMap;
use algebra::Min;

let mut a: LatticeMap<u32, Min<i64>> = LatticeMap::new();
a.insert(0, Min(10));

let mut b: LatticeMap<u32, Min<i64>> = LatticeMap::new();
b.insert(0, Min(20));

// Join is commutative: a ⊔ b = b ⊔ a
assert_eq!(a.join(&b), b.join(&a));

// Join is idempotent: a ⊔ a = a
assert_eq!(a.join(&a), a);

Implementations

impl<K, V> LatticeMap<K, V>

where K: Eq + Hash,

pub fn new() -> Self

Create an empty map lattice.

pub fn insert(&mut self, k: K, v: V)

Insert or replace a value for a key.

pub fn get(&self, k: &K) -> Option<&V>

Get a reference to the value for this key, if present.

pub fn iter(&self) -> impl Iterator<Item = (&K, &V)>

Iterate over (key, value) pairs.

pub fn as_inner(&self) -> &HashMap<K, V>

Access the underlying HashMap.

pub fn into_inner(self) -> HashMap<K, V>

Consume the wrapper and return the underlying HashMap.

pub fn len(&self) -> usize

Number of entries.

pub fn is_empty(&self) -> bool

Is the map empty?

Trait Implementations

impl<K, V> BoundedJoinSemilattice for LatticeMap<K, V>

where K: Eq + Hash + Clone, V: BoundedJoinSemilattice + Clone,

fn bottom() -> Self

The bottom element of the lattice (⊥).

fn join_all_from_bottom<I>(it: I) -> Self

where I: IntoIterator<Item = Self>,

Join a finite iterator of values, starting from ⊥.

impl<K: Clone, V: Clone> Clone for LatticeMap<K, V>

fn clone(&self) -> LatticeMap<K, V>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for LatticeMap<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V> Default for LatticeMap<K, V>

where K: Eq + Hash,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, K, V> Deserialize<'de> for LatticeMap<K, V>

where K: Eq + Hash + Deserialize<'de>, V: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K, V> JoinSemilattice for LatticeMap<K, V>

where K: Eq + Hash + Clone, V: JoinSemilattice + Clone,

fn join(&self, other: &Self) -> Self

The join (least upper bound).

fn join_assign(&mut self, other: &Self)

In-place variant.

fn leq(&self, other: &Self) -> bool

where Self: PartialEq,

Derived partial order: x ≤ y iff x ⊔ y = y.

fn join_all<I>(it: I) -> Option<Self>

where I: IntoIterator<Item = Self>,

Join a finite iterator of values. Returns None for empty iterators.

impl<K, V> PartialEq for LatticeMap<K, V>

where K: Eq + Hash, V: PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, V> Serialize for LatticeMap<K, V>

where K: Eq + Hash + Serialize, V: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<K, V> Eq for LatticeMap<K, V>

where K: Eq + Hash, V: Eq,