Struct SplittableTreap 

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

Implementations

impl<K: Ord, V> SplittableTreap<K, V>

pub fn new(seed: u64) -> Self

Examples found in repository

examples/sample_app.rs (line 250)

fn partition_ladder() {
    use subms_treap::SplittableTreap;
    println!("\n== merge-split: partition at the touch ==");
    let mut book: SplittableTreap<u32, u64> = SplittableTreap::new(SEED);
    for (px, qty) in [
        (9_996u32, 600u64),
        (9_998, 1_000),
        (9_999, 250),
        (10_000, 650),
        (10_001, 900),
        (10_002, 400),
    ] {
        book.insert(px, qty);
    }

    // Everything strictly below 10000 is the resting book; 10000 and above is
    // the band a marketable order would clear against.
    let (resting, marketable) = book.split(&10_000);
    println!(
        "  below 10000: {} levels | 10000 and up: {} levels",
        resting.len(),
        marketable.len()
    );
    assert_eq!((resting.len(), marketable.len()), (3, 3));
    assert_eq!(
        marketable.collect_in_order().first().map(|(k, _)| **k),
        Some(10_000)
    );

    let rejoined = SplittableTreap::merge(resting, marketable);
    let keys: Vec<u32> = rejoined
        .collect_in_order()
        .into_iter()
        .map(|(k, _)| *k)
        .collect();
    println!("  rejoined: {keys:?}");
    assert_eq!(keys, vec![9_996, 9_998, 9_999, 10_000, 10_001, 10_002]);
}

examples/perf_features.rs (line 165)

fn main() -> io::Result<()> {
    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
        .join("..")
        .join(".subms")
        .join("features")
        .join("rust.json");
    let existing = std::fs::read_to_string(&path).unwrap_or_default();
    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
    // Stamp the box these numbers came from. The bench runs wherever it is
    // invoked, so an unstamped manifest is indistinguishable from a fleet
    // capture; the renderer will not publish one it cannot attribute.
    let (source, instance) = SubMsP99Source::from_env();
    manifest.set_p99_source(source, instance.as_deref());

    // The baseline: a base-treap lookup at the canonical size. A feature landing
    // at or under this costs nothing on the read path.
    let base = build(CANON);
    let base_p50 = keyed(CANON, |i| _ = base.get(&key_at(i)), true);
    eprintln!("base get p50: {base_p50}ns");

    // ---------- persistent: path-copying insert, old version stays valid ----------
    #[cfg(feature = "persistent")]
    {
        use subms_treap::PersistentTreap;
        // `insert` returns a NEW treap sharing everything off the copied path,
        // so the cost is the path length - O(log n), which should read flat.
        let sw = sweep("persistent/insert", |n| {
            let mut p = PersistentTreap::new(SEED);
            for i in 0..n {
                p = p.insert(key_at(i), i as u64);
            }
            keyed(n, |i| _ = p.insert(key_at(i), i as u64), true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p = PersistentTreap::new(SEED);
        for i in 0..CANON {
            p = p.insert(key_at(i), i as u64);
        }
        let mut p99 = BTreeMap::new();
        p99.insert(
            "insert".to_string(),
            keyed(CANON, |i| _ = p.insert(key_at(i), i as u64), false),
        );
        p99.insert(
            "get".to_string(),
            keyed(CANON, |i| _ = p.get(&key_at(i)), false),
        );
        p99.insert(
            "remove".to_string(),
            keyed(CANON, |i| _ = p.remove(&key_at(i)), false),
        );
        manifest.set_feature("persistent", cat, &p99, &reason);
    }

    // ---------- merge-split: split at a pivot, merge two ordered halves ----------
    #[cfg(feature = "merge-split")]
    {
        use subms_treap::SplittableTreap;
        // Timed as a split-then-merge ROUND TRIP, because `split` consumes the
        // treap: rebuilding one per rep would put an O(n log n) build inside the
        // timed region and the figure would be the build. A round trip restores
        // the original, so the input is set up once and every rep does identical
        // work.
        //
        // The sweep classifies this structural, and the reason is in `split`
        // rather than in `split_node`: the descent is O(log n), but split then
        // calls `count()` on BOTH halves to fill in their lengths, and that is a
        // full traversal. An O(log n) op with an O(n) bookkeeping tail.
        let make = |n: usize| {
            let mut t = SplittableTreap::new(SEED);
            for i in 0..n {
                t.insert(key_at(i), i as u64);
            }
            Some(t)
        };
        let round_trip = |slot: &mut Option<SplittableTreap<u64, u64>>| {
            let t = slot.take().expect("round trip restores the treap");
            let (l, r) = t.split(&(KEY_SPACE / 2));
            *slot = Some(SplittableTreap::merge(l, r));
        };
        let sw = sweep("merge-split/split+merge", |n| {
            bulk(|| make(n), round_trip, true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p99 = BTreeMap::new();
        p99.insert(
            "split_merge".to_string(),
            bulk(|| make(CANON), round_trip, false),
        );
        manifest.set_feature("merge-split", cat, &p99, &reason);
    }

    // ---------- concurrent-reads: a flattened immutable snapshot ----------
    #[cfg(feature = "concurrent-reads")]
    {
        use subms_treap::TreapSnapshot;
        // `from_treap` flattens the tree into a sorted Vec, so it is O(n) and the
        // sweep says so. Lookups on the result are a binary search over that Vec,
        // which is the point: readers pay O(log n) with no tree pointers and no
        // coordination with the writer.
        let sw = sweep("concurrent-reads/snapshot", |n| {
            let t = build(n);
            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let t = build(CANON);
        let snap = TreapSnapshot::from_treap(&t);
        let mut p99 = BTreeMap::new();
        p99.insert(
            "snapshot".to_string(),
            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), false),
        );
        p99.insert(
            "lookup_on_snapshot".to_string(),
            keyed(CANON, |i| _ = snap.get(&key_at(i)), false),
        );
        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
    }

    std::fs::create_dir_all(path.parent().unwrap())?;
    std::fs::write(&path, manifest.to_json())?;
    io::stdout().write_all(manifest.to_json().as_bytes())?;
    Ok(())
}

pub fn len(&self) -> usize

Examples found in repository

examples/sample_app.rs (line 267)

fn partition_ladder() {
    use subms_treap::SplittableTreap;
    println!("\n== merge-split: partition at the touch ==");
    let mut book: SplittableTreap<u32, u64> = SplittableTreap::new(SEED);
    for (px, qty) in [
        (9_996u32, 600u64),
        (9_998, 1_000),
        (9_999, 250),
        (10_000, 650),
        (10_001, 900),
        (10_002, 400),
    ] {
        book.insert(px, qty);
    }

    // Everything strictly below 10000 is the resting book; 10000 and above is
    // the band a marketable order would clear against.
    let (resting, marketable) = book.split(&10_000);
    println!(
        "  below 10000: {} levels | 10000 and up: {} levels",
        resting.len(),
        marketable.len()
    );
    assert_eq!((resting.len(), marketable.len()), (3, 3));
    assert_eq!(
        marketable.collect_in_order().first().map(|(k, _)| **k),
        Some(10_000)
    );

    let rejoined = SplittableTreap::merge(resting, marketable);
    let keys: Vec<u32> = rejoined
        .collect_in_order()
        .into_iter()
        .map(|(k, _)| *k)
        .collect();
    println!("  rejoined: {keys:?}");
    assert_eq!(keys, vec![9_996, 9_998, 9_999, 10_000, 10_001, 10_002]);
}

pub fn is_empty(&self) -> bool

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

Examples found in repository

examples/sample_app.rs (line 259)

fn partition_ladder() {
    use subms_treap::SplittableTreap;
    println!("\n== merge-split: partition at the touch ==");
    let mut book: SplittableTreap<u32, u64> = SplittableTreap::new(SEED);
    for (px, qty) in [
        (9_996u32, 600u64),
        (9_998, 1_000),
        (9_999, 250),
        (10_000, 650),
        (10_001, 900),
        (10_002, 400),
    ] {
        book.insert(px, qty);
    }

    // Everything strictly below 10000 is the resting book; 10000 and above is
    // the band a marketable order would clear against.
    let (resting, marketable) = book.split(&10_000);
    println!(
        "  below 10000: {} levels | 10000 and up: {} levels",
        resting.len(),
        marketable.len()
    );
    assert_eq!((resting.len(), marketable.len()), (3, 3));
    assert_eq!(
        marketable.collect_in_order().first().map(|(k, _)| **k),
        Some(10_000)
    );

    let rejoined = SplittableTreap::merge(resting, marketable);
    let keys: Vec<u32> = rejoined
        .collect_in_order()
        .into_iter()
        .map(|(k, _)| *k)
        .collect();
    println!("  rejoined: {keys:?}");
    assert_eq!(keys, vec![9_996, 9_998, 9_999, 10_000, 10_001, 10_002]);
}

examples/perf_features.rs (line 167)

fn main() -> io::Result<()> {
    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
        .join("..")
        .join(".subms")
        .join("features")
        .join("rust.json");
    let existing = std::fs::read_to_string(&path).unwrap_or_default();
    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
    // Stamp the box these numbers came from. The bench runs wherever it is
    // invoked, so an unstamped manifest is indistinguishable from a fleet
    // capture; the renderer will not publish one it cannot attribute.
    let (source, instance) = SubMsP99Source::from_env();
    manifest.set_p99_source(source, instance.as_deref());

    // The baseline: a base-treap lookup at the canonical size. A feature landing
    // at or under this costs nothing on the read path.
    let base = build(CANON);
    let base_p50 = keyed(CANON, |i| _ = base.get(&key_at(i)), true);
    eprintln!("base get p50: {base_p50}ns");

    // ---------- persistent: path-copying insert, old version stays valid ----------
    #[cfg(feature = "persistent")]
    {
        use subms_treap::PersistentTreap;
        // `insert` returns a NEW treap sharing everything off the copied path,
        // so the cost is the path length - O(log n), which should read flat.
        let sw = sweep("persistent/insert", |n| {
            let mut p = PersistentTreap::new(SEED);
            for i in 0..n {
                p = p.insert(key_at(i), i as u64);
            }
            keyed(n, |i| _ = p.insert(key_at(i), i as u64), true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p = PersistentTreap::new(SEED);
        for i in 0..CANON {
            p = p.insert(key_at(i), i as u64);
        }
        let mut p99 = BTreeMap::new();
        p99.insert(
            "insert".to_string(),
            keyed(CANON, |i| _ = p.insert(key_at(i), i as u64), false),
        );
        p99.insert(
            "get".to_string(),
            keyed(CANON, |i| _ = p.get(&key_at(i)), false),
        );
        p99.insert(
            "remove".to_string(),
            keyed(CANON, |i| _ = p.remove(&key_at(i)), false),
        );
        manifest.set_feature("persistent", cat, &p99, &reason);
    }

    // ---------- merge-split: split at a pivot, merge two ordered halves ----------
    #[cfg(feature = "merge-split")]
    {
        use subms_treap::SplittableTreap;
        // Timed as a split-then-merge ROUND TRIP, because `split` consumes the
        // treap: rebuilding one per rep would put an O(n log n) build inside the
        // timed region and the figure would be the build. A round trip restores
        // the original, so the input is set up once and every rep does identical
        // work.
        //
        // The sweep classifies this structural, and the reason is in `split`
        // rather than in `split_node`: the descent is O(log n), but split then
        // calls `count()` on BOTH halves to fill in their lengths, and that is a
        // full traversal. An O(log n) op with an O(n) bookkeeping tail.
        let make = |n: usize| {
            let mut t = SplittableTreap::new(SEED);
            for i in 0..n {
                t.insert(key_at(i), i as u64);
            }
            Some(t)
        };
        let round_trip = |slot: &mut Option<SplittableTreap<u64, u64>>| {
            let t = slot.take().expect("round trip restores the treap");
            let (l, r) = t.split(&(KEY_SPACE / 2));
            *slot = Some(SplittableTreap::merge(l, r));
        };
        let sw = sweep("merge-split/split+merge", |n| {
            bulk(|| make(n), round_trip, true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p99 = BTreeMap::new();
        p99.insert(
            "split_merge".to_string(),
            bulk(|| make(CANON), round_trip, false),
        );
        manifest.set_feature("merge-split", cat, &p99, &reason);
    }

    // ---------- concurrent-reads: a flattened immutable snapshot ----------
    #[cfg(feature = "concurrent-reads")]
    {
        use subms_treap::TreapSnapshot;
        // `from_treap` flattens the tree into a sorted Vec, so it is O(n) and the
        // sweep says so. Lookups on the result are a binary search over that Vec,
        // which is the point: readers pay O(log n) with no tree pointers and no
        // coordination with the writer.
        let sw = sweep("concurrent-reads/snapshot", |n| {
            let t = build(n);
            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let t = build(CANON);
        let snap = TreapSnapshot::from_treap(&t);
        let mut p99 = BTreeMap::new();
        p99.insert(
            "snapshot".to_string(),
            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), false),
        );
        p99.insert(
            "lookup_on_snapshot".to_string(),
            keyed(CANON, |i| _ = snap.get(&key_at(i)), false),
        );
        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
    }

    std::fs::create_dir_all(path.parent().unwrap())?;
    std::fs::write(&path, manifest.to_json())?;
    io::stdout().write_all(manifest.to_json().as_bytes())?;
    Ok(())
}

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

pub fn split(self, pivot: &K) -> (Self, Self)

Consume self and split into (left, right) where every key in left is strictly less than pivot and every key in right is greater-than-or-equal-to pivot.

Examples found in repository

examples/sample_app.rs (line 264)

fn partition_ladder() {
    use subms_treap::SplittableTreap;
    println!("\n== merge-split: partition at the touch ==");
    let mut book: SplittableTreap<u32, u64> = SplittableTreap::new(SEED);
    for (px, qty) in [
        (9_996u32, 600u64),
        (9_998, 1_000),
        (9_999, 250),
        (10_000, 650),
        (10_001, 900),
        (10_002, 400),
    ] {
        book.insert(px, qty);
    }

    // Everything strictly below 10000 is the resting book; 10000 and above is
    // the band a marketable order would clear against.
    let (resting, marketable) = book.split(&10_000);
    println!(
        "  below 10000: {} levels | 10000 and up: {} levels",
        resting.len(),
        marketable.len()
    );
    assert_eq!((resting.len(), marketable.len()), (3, 3));
    assert_eq!(
        marketable.collect_in_order().first().map(|(k, _)| **k),
        Some(10_000)
    );

    let rejoined = SplittableTreap::merge(resting, marketable);
    let keys: Vec<u32> = rejoined
        .collect_in_order()
        .into_iter()
        .map(|(k, _)| *k)
        .collect();
    println!("  rejoined: {keys:?}");
    assert_eq!(keys, vec![9_996, 9_998, 9_999, 10_000, 10_001, 10_002]);
}

examples/perf_features.rs (line 173)

fn main() -> io::Result<()> {
    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
        .join("..")
        .join(".subms")
        .join("features")
        .join("rust.json");
    let existing = std::fs::read_to_string(&path).unwrap_or_default();
    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
    // Stamp the box these numbers came from. The bench runs wherever it is
    // invoked, so an unstamped manifest is indistinguishable from a fleet
    // capture; the renderer will not publish one it cannot attribute.
    let (source, instance) = SubMsP99Source::from_env();
    manifest.set_p99_source(source, instance.as_deref());

    // The baseline: a base-treap lookup at the canonical size. A feature landing
    // at or under this costs nothing on the read path.
    let base = build(CANON);
    let base_p50 = keyed(CANON, |i| _ = base.get(&key_at(i)), true);
    eprintln!("base get p50: {base_p50}ns");

    // ---------- persistent: path-copying insert, old version stays valid ----------
    #[cfg(feature = "persistent")]
    {
        use subms_treap::PersistentTreap;
        // `insert` returns a NEW treap sharing everything off the copied path,
        // so the cost is the path length - O(log n), which should read flat.
        let sw = sweep("persistent/insert", |n| {
            let mut p = PersistentTreap::new(SEED);
            for i in 0..n {
                p = p.insert(key_at(i), i as u64);
            }
            keyed(n, |i| _ = p.insert(key_at(i), i as u64), true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p = PersistentTreap::new(SEED);
        for i in 0..CANON {
            p = p.insert(key_at(i), i as u64);
        }
        let mut p99 = BTreeMap::new();
        p99.insert(
            "insert".to_string(),
            keyed(CANON, |i| _ = p.insert(key_at(i), i as u64), false),
        );
        p99.insert(
            "get".to_string(),
            keyed(CANON, |i| _ = p.get(&key_at(i)), false),
        );
        p99.insert(
            "remove".to_string(),
            keyed(CANON, |i| _ = p.remove(&key_at(i)), false),
        );
        manifest.set_feature("persistent", cat, &p99, &reason);
    }

    // ---------- merge-split: split at a pivot, merge two ordered halves ----------
    #[cfg(feature = "merge-split")]
    {
        use subms_treap::SplittableTreap;
        // Timed as a split-then-merge ROUND TRIP, because `split` consumes the
        // treap: rebuilding one per rep would put an O(n log n) build inside the
        // timed region and the figure would be the build. A round trip restores
        // the original, so the input is set up once and every rep does identical
        // work.
        //
        // The sweep classifies this structural, and the reason is in `split`
        // rather than in `split_node`: the descent is O(log n), but split then
        // calls `count()` on BOTH halves to fill in their lengths, and that is a
        // full traversal. An O(log n) op with an O(n) bookkeeping tail.
        let make = |n: usize| {
            let mut t = SplittableTreap::new(SEED);
            for i in 0..n {
                t.insert(key_at(i), i as u64);
            }
            Some(t)
        };
        let round_trip = |slot: &mut Option<SplittableTreap<u64, u64>>| {
            let t = slot.take().expect("round trip restores the treap");
            let (l, r) = t.split(&(KEY_SPACE / 2));
            *slot = Some(SplittableTreap::merge(l, r));
        };
        let sw = sweep("merge-split/split+merge", |n| {
            bulk(|| make(n), round_trip, true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p99 = BTreeMap::new();
        p99.insert(
            "split_merge".to_string(),
            bulk(|| make(CANON), round_trip, false),
        );
        manifest.set_feature("merge-split", cat, &p99, &reason);
    }

    // ---------- concurrent-reads: a flattened immutable snapshot ----------
    #[cfg(feature = "concurrent-reads")]
    {
        use subms_treap::TreapSnapshot;
        // `from_treap` flattens the tree into a sorted Vec, so it is O(n) and the
        // sweep says so. Lookups on the result are a binary search over that Vec,
        // which is the point: readers pay O(log n) with no tree pointers and no
        // coordination with the writer.
        let sw = sweep("concurrent-reads/snapshot", |n| {
            let t = build(n);
            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let t = build(CANON);
        let snap = TreapSnapshot::from_treap(&t);
        let mut p99 = BTreeMap::new();
        p99.insert(
            "snapshot".to_string(),
            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), false),
        );
        p99.insert(
            "lookup_on_snapshot".to_string(),
            keyed(CANON, |i| _ = snap.get(&key_at(i)), false),
        );
        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
    }

    std::fs::create_dir_all(path.parent().unwrap())?;
    std::fs::write(&path, manifest.to_json())?;
    io::stdout().write_all(manifest.to_json().as_bytes())?;
    Ok(())
}

pub fn merge(left: Self, right: Self) -> Self

Consume left and right and produce a single treap. Every key in left must be strictly less than every key in right or the resulting BST invariant is violated.

Examples found in repository

examples/sample_app.rs (line 276)

fn partition_ladder() {
    use subms_treap::SplittableTreap;
    println!("\n== merge-split: partition at the touch ==");
    let mut book: SplittableTreap<u32, u64> = SplittableTreap::new(SEED);
    for (px, qty) in [
        (9_996u32, 600u64),
        (9_998, 1_000),
        (9_999, 250),
        (10_000, 650),
        (10_001, 900),
        (10_002, 400),
    ] {
        book.insert(px, qty);
    }

    // Everything strictly below 10000 is the resting book; 10000 and above is
    // the band a marketable order would clear against.
    let (resting, marketable) = book.split(&10_000);
    println!(
        "  below 10000: {} levels | 10000 and up: {} levels",
        resting.len(),
        marketable.len()
    );
    assert_eq!((resting.len(), marketable.len()), (3, 3));
    assert_eq!(
        marketable.collect_in_order().first().map(|(k, _)| **k),
        Some(10_000)
    );

    let rejoined = SplittableTreap::merge(resting, marketable);
    let keys: Vec<u32> = rejoined
        .collect_in_order()
        .into_iter()
        .map(|(k, _)| *k)
        .collect();
    println!("  rejoined: {keys:?}");
    assert_eq!(keys, vec![9_996, 9_998, 9_999, 10_000, 10_001, 10_002]);
}

examples/perf_features.rs (line 174)

fn main() -> io::Result<()> {
    let path = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
        .join("..")
        .join(".subms")
        .join("features")
        .join("rust.json");
    let existing = std::fs::read_to_string(&path).unwrap_or_default();
    let mut manifest = SubMsFeatureManifest::load_str("rust", &existing);
    // Stamp the box these numbers came from. The bench runs wherever it is
    // invoked, so an unstamped manifest is indistinguishable from a fleet
    // capture; the renderer will not publish one it cannot attribute.
    let (source, instance) = SubMsP99Source::from_env();
    manifest.set_p99_source(source, instance.as_deref());

    // The baseline: a base-treap lookup at the canonical size. A feature landing
    // at or under this costs nothing on the read path.
    let base = build(CANON);
    let base_p50 = keyed(CANON, |i| _ = base.get(&key_at(i)), true);
    eprintln!("base get p50: {base_p50}ns");

    // ---------- persistent: path-copying insert, old version stays valid ----------
    #[cfg(feature = "persistent")]
    {
        use subms_treap::PersistentTreap;
        // `insert` returns a NEW treap sharing everything off the copied path,
        // so the cost is the path length - O(log n), which should read flat.
        let sw = sweep("persistent/insert", |n| {
            let mut p = PersistentTreap::new(SEED);
            for i in 0..n {
                p = p.insert(key_at(i), i as u64);
            }
            keyed(n, |i| _ = p.insert(key_at(i), i as u64), true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p = PersistentTreap::new(SEED);
        for i in 0..CANON {
            p = p.insert(key_at(i), i as u64);
        }
        let mut p99 = BTreeMap::new();
        p99.insert(
            "insert".to_string(),
            keyed(CANON, |i| _ = p.insert(key_at(i), i as u64), false),
        );
        p99.insert(
            "get".to_string(),
            keyed(CANON, |i| _ = p.get(&key_at(i)), false),
        );
        p99.insert(
            "remove".to_string(),
            keyed(CANON, |i| _ = p.remove(&key_at(i)), false),
        );
        manifest.set_feature("persistent", cat, &p99, &reason);
    }

    // ---------- merge-split: split at a pivot, merge two ordered halves ----------
    #[cfg(feature = "merge-split")]
    {
        use subms_treap::SplittableTreap;
        // Timed as a split-then-merge ROUND TRIP, because `split` consumes the
        // treap: rebuilding one per rep would put an O(n log n) build inside the
        // timed region and the figure would be the build. A round trip restores
        // the original, so the input is set up once and every rep does identical
        // work.
        //
        // The sweep classifies this structural, and the reason is in `split`
        // rather than in `split_node`: the descent is O(log n), but split then
        // calls `count()` on BOTH halves to fill in their lengths, and that is a
        // full traversal. An O(log n) op with an O(n) bookkeeping tail.
        let make = |n: usize| {
            let mut t = SplittableTreap::new(SEED);
            for i in 0..n {
                t.insert(key_at(i), i as u64);
            }
            Some(t)
        };
        let round_trip = |slot: &mut Option<SplittableTreap<u64, u64>>| {
            let t = slot.take().expect("round trip restores the treap");
            let (l, r) = t.split(&(KEY_SPACE / 2));
            *slot = Some(SplittableTreap::merge(l, r));
        };
        let sw = sweep("merge-split/split+merge", |n| {
            bulk(|| make(n), round_trip, true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let mut p99 = BTreeMap::new();
        p99.insert(
            "split_merge".to_string(),
            bulk(|| make(CANON), round_trip, false),
        );
        manifest.set_feature("merge-split", cat, &p99, &reason);
    }

    // ---------- concurrent-reads: a flattened immutable snapshot ----------
    #[cfg(feature = "concurrent-reads")]
    {
        use subms_treap::TreapSnapshot;
        // `from_treap` flattens the tree into a sorted Vec, so it is O(n) and the
        // sweep says so. Lookups on the result are a binary search over that Vec,
        // which is the point: readers pay O(log n) with no tree pointers and no
        // coordination with the writer.
        let sw = sweep("concurrent-reads/snapshot", |n| {
            let t = build(n);
            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), true)
        });
        let (cat, reason) = classify_feature(&sw, Some(base_p50), None);

        let t = build(CANON);
        let snap = TreapSnapshot::from_treap(&t);
        let mut p99 = BTreeMap::new();
        p99.insert(
            "snapshot".to_string(),
            bulk(|| (), |()| _ = TreapSnapshot::from_treap(&t), false),
        );
        p99.insert(
            "lookup_on_snapshot".to_string(),
            keyed(CANON, |i| _ = snap.get(&key_at(i)), false),
        );
        manifest.set_feature("concurrent-reads", cat, &p99, &reason);
    }

    std::fs::create_dir_all(path.parent().unwrap())?;
    std::fs::write(&path, manifest.to_json())?;
    io::stdout().write_all(manifest.to_json().as_bytes())?;
    Ok(())
}

pub fn collect_in_order(&self) -> Vec<(&K, &V)>

Examples found in repository

examples/sample_app.rs (line 272)

fn partition_ladder() {
    use subms_treap::SplittableTreap;
    println!("\n== merge-split: partition at the touch ==");
    let mut book: SplittableTreap<u32, u64> = SplittableTreap::new(SEED);
    for (px, qty) in [
        (9_996u32, 600u64),
        (9_998, 1_000),
        (9_999, 250),
        (10_000, 650),
        (10_001, 900),
        (10_002, 400),
    ] {
        book.insert(px, qty);
    }

    // Everything strictly below 10000 is the resting book; 10000 and above is
    // the band a marketable order would clear against.
    let (resting, marketable) = book.split(&10_000);
    println!(
        "  below 10000: {} levels | 10000 and up: {} levels",
        resting.len(),
        marketable.len()
    );
    assert_eq!((resting.len(), marketable.len()), (3, 3));
    assert_eq!(
        marketable.collect_in_order().first().map(|(k, _)| **k),
        Some(10_000)
    );

    let rejoined = SplittableTreap::merge(resting, marketable);
    let keys: Vec<u32> = rejoined
        .collect_in_order()
        .into_iter()
        .map(|(k, _)| *k)
        .collect();
    println!("  rejoined: {keys:?}");
    assert_eq!(keys, vec![9_996, 9_998, 9_999, 10_000, 10_001, 10_002]);
}