Function diff

pub fn diff<'p, 'a: 'p, T, U, K>(local: T, peer: U) -> Vec<DiffRange<'p, K>>
where
    T: IntoIterator<Item = PageRange<'a, K>>,
    U: IntoIterator<Item = PageRange<'p, K>>,
    K: PartialOrd + Ord + Debug + 'p + 'a,

Compute the difference between local and peer, returning the set of DiffRange covering the inconsistent key ranges found in peer.

use merkle_search_tree::{MerkleSearchTree, diff::diff};

// Initialise a "peer" tree.
let mut node_a = MerkleSearchTree::default();
node_a.upsert("bananas", &42);
node_a.upsert("plátanos", &42);

// Initialise the "local" tree with differing keys
let mut node_b = MerkleSearchTree::default();
node_b.upsert("donkey", &42);

// Generate the tree hashes before serialising the page ranges
node_a.root_hash();
node_b.root_hash();

// Generate the tree page bounds & hashes, and feed into the diff function
let diff_range = diff(
    node_b.serialise_page_ranges().unwrap().into_iter(),
    node_a.serialise_page_ranges().unwrap().into_iter(),
);

// The diff_range contains all the inclusive key intervals the "local" tree
// should fetch from the "peer" tree to converge.
assert_matches::assert_matches!(diff_range.as_slice(), [range] => {
    assert_eq!(range.start(), &"bananas");
    assert_eq!(range.end(), &"plátanos");
});

State Convergence

To converge the state of the two trees, the key ranges in the returned DiffRange instances should be requested from peer and used to update the state of local.

If local is a superset of peer (contains all the keys in peer and the values are consistent), or the two trees are identical, no DiffRange intervals are returned.

Termination

A single invocation to diff() always terminates, and completes in O(n) time and space. Inconsistent page ranges (if any) are minimised in O(n_consistent * n_inconsistent) time and O(n) space.

In the absence of further external updates to either tree, this algorithm terminates (leaving local and peer fully converged) and no diff is returned within a finite number of sync rounds between the two trees.

If a one-way sync is performed (pulling inconsistent keys from peer and updating local, but never syncing the other way around) this algorithm MAY NOT terminate.