Struct PMap 

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

A persistent ordered map. Cloning is O(1) and shares everything.

Implementations

impl<K: Ord + Clone, V: Clone> PMap<K, V>

pub fn new() -> PMap<K, V>

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

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

pub fn contains_key(&self, key: &K) -> bool

pub fn same_root(&self, other: &PMap<K, V>) -> bool

Whether two maps are the same tree, not merely equal ones.

O(1), and the answer the incremental engine needs when deciding whether an event moved a map at all: structural equality would be O(n) per event, which is the cost the engine exists to avoid. A false here means “it may have changed”, never “it did”.

pub fn insert(&self, key: K, value: V) -> PMap<K, V>

Insert, returning a new map. Shares every subtree the new key did not pass through.

pub fn remove(&self, key: &K) -> PMap<K, V>

Remove, returning a new map.

pub fn iter(&self) -> Iter<'_, K, V>

Entries in key order.

pub fn keys(&self) -> impl Iterator<Item = &K>

pub fn values(&self) -> impl Iterator<Item = &V>

impl<K: Ord + Clone, V: Clone + PartialEq> PMap<K, V>

pub fn diff(&self, next: &PMap<K, V>) -> Vec<Change<K, V>>

The entries that differ between two versions, in key order.

Why this is O(δ log n) rather than O(n)

This is the operation the whole incremental view engine rests on (docs/24-incremental-views-report.md): a fold produces a whole new accumulator per event, and a dataflow plan consumes deltas, so something has to turn one into the other. Comparing entry by entry would be O(n) per event, which is the recount §3.8 exists to abolish — the plan downstream would be incremental and the thing feeding it would not.

insert rebuilds only the path to the key and shares every subtree that path did not pass through, by Arc. So two versions of a map that differ by one insert share n - O(log n) nodes by pointer, and a diff that can recognise a shared subtree can skip all of its entries at once.

The traversal is an ordered merge of the two trees, with one extra rule: when the heads of the two remaining sequences are the same subtree by pointer, both are dropped. That is sound for a reason worth stating, because it is the correctness of the engine: pointer-identical subtrees hold identical entries, so the two remaining sorted sequences share that prefix exactly, and a merge over sorted sequences reports nothing for a shared prefix. It holds whatever rebalancing did to the position of that subtree in either tree.

Trait Implementations

impl<K, V> Clone for PMap<K, V>

fn clone(&self) -> Self

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 PMap<K, V>

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

impl<K: Ord + Clone, V: Clone> FromIterator<(K, V)> for PMap<K, V>

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<K: Ord + Clone, V: Clone + Ord> Ord for PMap<K, V>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<K: Ord + Clone + PartialEq, V: Clone + PartialEq> PartialEq for PMap<K, V>

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: Ord + Clone, V: Clone + Ord> PartialOrd for PMap<K, V>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K: Ord + Clone, V: Clone + Eq> Eq for PMap<K, V>