Struct Treap 

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

Implementations

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

pub fn range<'a>( &'a self, from: RangeBound<'a, K>, to: RangeBound<'a, K>, ) -> RangeIter<'a, K, V>

Iterate every (&K, &V) with from <= key <= to (or whichever inclusion shape the bounds declare), in ascending key order.

Examples found in repository

examples/sample_app.rs (line 192)

fn band_depth() {
    use subms_treap::RangeBound;
    println!("\n== range-query: depth in a price band ==");
    let book = build_book();
    let (lo, hi) = (9_996u32, 10_000u32);
    let band: Vec<(u32, u64)> = book
        .range(RangeBound::Inclusive(&lo), RangeBound::Inclusive(&hi))
        .map(|(k, v)| (*k, *v))
        .collect();
    let depth: u64 = band.iter().map(|(_, q)| *q).sum();
    println!("  [{lo}, {hi}] -> {} levels, {depth} lots", band.len());
    assert_eq!(
        band.iter().map(|(k, _)| *k).collect::<Vec<_>>(),
        vec![9_996, 9_998, 9_999, 10_000]
    );
    assert_eq!(depth, 2_500);

    // Exclusive upper bound drops the touch itself.
    let inside: u64 = book
        .range(RangeBound::Inclusive(&lo), RangeBound::Exclusive(&hi))
        .map(|(_, q)| *q)
        .sum();
    println!("  same band, exclusive of {hi}: {inside} lots");
    assert_eq!(inside, 1_850);
}

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

pub fn new(seed: u64) -> Self

Examples found in repository

examples/perf_features.rs (line 44)

fn build(n: usize) -> Treap<u64, u64> {
    let mut t = Treap::new(SEED);
    for i in 0..n {
        t.insert(key_at(i), i as u64);
    }
    t
}

examples/sample_app.rs (line 294)

fn published_snapshot() {
    use std::thread;
    use subms_treap::TreapSnapshot;
    println!("\n== concurrent-reads: published book snapshot ==");
    let mut book: Treap<u32, u64> = Treap::new(SEED);
    for px in 9_990..10_010u32 {
        book.insert(px, (px as u64) * 10);
    }
    let snap = TreapSnapshot::from_treap(&book);

    let readers: Vec<_> = (0..4)
        .map(|_| {
            let s = snap.clone();
            thread::spawn(move || s.range(&9_995, &10_004).count())
        })
        .collect();

    // Writer churn after the snapshot: readers must not observe it.
    book.insert(12_345, 1);
    book.remove(&9_990);

    for r in readers {
        assert_eq!(
            r.join().unwrap(),
            10,
            "reader sees the frozen 10-level band"
        );
    }
    println!("  4 readers each counted 10 levels in [9995, 10004]");
    assert!(
        snap.get(&12_345).is_none(),
        "snapshot isolated from later writes"
    );
    assert_eq!(snap.len(), 20);
}

pub fn with_capacity(seed: u64, capacity: usize) -> Self

Construct with capacity pre-allocated. Use when an upper bound on the working set is known: avoids the doubling-vec growth path during the first burst of inserts.

Examples found in repository

examples/sample_app.rs (line 79)

fn build_book() -> Treap<u32, u64> {
    let mut book: Treap<u32, u64> = Treap::with_capacity(SEED, TAPE.len());
    for event in &TAPE {
        match event {
            Event::Post(px, qty) => {
                book.insert(*px, *qty);
            }
            Event::Amend(px, delta) => {
                if let Some(qty) = book.get_mut(px) {
                    *qty = qty.saturating_add_signed(*delta);
                }
            }
            Event::Cancel(px) => {
                book.remove(px);
            }
        }
    }
    assert_eq!(book.len(), 9);
    assert_eq!(
        book.get(&10_000).copied(),
        Some(650),
        "amend applied in place"
    );
    assert!(!book.contains_key(&9997), "cancelled level is gone");
    book
}

pub fn from_entropy() -> Self

Seed the priority stream from the OS rather than from a constant.

The default constructor takes an explicit seed because a reproducible tree shape is what makes a benchmark and a bug report mean anything. That same property is a liability when an attacker can both choose the keys and observe the latency: the priority sequence is then known, and a chosen key order can force the spine the randomized bound rules out. Reach for this when the key stream is untrusted, and accept that two runs no longer produce the same tree.

pub fn from_sorted( seed: u64, items: impl IntoIterator<Item = (K, V)>, ) -> Result<Self, TreapError>

Build from already-sorted input in O(n), skipping the n rotating inserts a naive rebuild would pay.

Keys must be strictly ascending; duplicates are rejected rather than collapsed, because silently dropping one of two entries is the wrong answer for every workload that reaches for this. Pairs with Treap::collect_in_order as a snapshot / restore round trip.

use subms_treap::Treap;
let t = Treap::from_sorted(1, [(1u32, "a"), (2, "b"), (3, "c")]).unwrap();
assert_eq!(t.len(), 3);
assert_eq!(t.get(&2).copied(), Some("b"));

Examples found in repository

examples/sample_app.rs (line 168)

fn restore_from_snapshot(book: &Treap<u32, u64>) {
    let snapshot: Vec<(u32, u64)> = book.iter().map(|(k, v)| (*k, *v)).collect();
    let restored = Treap::from_sorted(SEED, snapshot.clone()).expect("snapshot is sorted");
    println!(
        "  restored {} levels from a sorted snapshot, height {}",
        restored.len(),
        restored.height()
    );
    let round_tripped: Vec<(u32, u64)> = restored.iter().map(|(k, v)| (*k, *v)).collect();
    assert_eq!(round_tripped, snapshot);

    // Unsorted input is rejected rather than silently reordered.
    let bad = Treap::from_sorted(SEED, [(2u32, 1u64), (1, 1)]);
    assert!(bad.is_err(), "strictly-ascending precondition enforced");
}

pub fn len(&self) -> usize

Examples found in repository

examples/sample_app.rs (line 74)

fn apply_tape() -> Treap<u32, u64> {
    println!("== bid-side depth book ==");
    let book = build_book();
    println!("  applied {} events -> {} levels", TAPE.len(), book.len());
    book
}

fn build_book() -> Treap<u32, u64> {
    let mut book: Treap<u32, u64> = Treap::with_capacity(SEED, TAPE.len());
    for event in &TAPE {
        match event {
            Event::Post(px, qty) => {
                book.insert(*px, *qty);
            }
            Event::Amend(px, delta) => {
                if let Some(qty) = book.get_mut(px) {
                    *qty = qty.saturating_add_signed(*delta);
                }
            }
            Event::Cancel(px) => {
                book.remove(px);
            }
        }
    }
    assert_eq!(book.len(), 9);
    assert_eq!(
        book.get(&10_000).copied(),
        Some(650),
        "amend applied in place"
    );
    assert!(!book.contains_key(&9997), "cancelled level is gone");
    book
}

/// Read the book the way a trader does: best price first, then the touch and
/// its neighbours. `iter_rev` walks the ladder high to low; `floor` and
/// `predecessor` answer "what is at or below this price" without a scan.
fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

/// Sweep an aggressive sell through the bid side. `pop_last` takes the best
/// level in expected O(log n) and hands back both key and value, so the fill
/// loop never re-descends to find the next price.
fn sweep_the_touch(book: &mut Treap<u32, u64>) {
    let mut to_fill = 1_200u64;
    let mut fills = Vec::new();
    while to_fill > 0 {
        let Some((px, qty)) = book.pop_last() else {
            break;
        };
        let take = qty.min(to_fill);
        to_fill -= take;
        fills.push((px, take));
        if qty > take {
            book.insert(px, qty - take); // partial fill, level survives
        }
    }
    println!("  sweep 1200 lots -> {fills:?}");
    assert_eq!(fills, vec![(10_002, 400), (10_001, 800)]);
    assert_eq!(book.len(), 8);
    assert_eq!(
        book.last().map(|(k, _)| *k),
        Some(10_001),
        "partial fill left the level"
    );
}

/// End-of-day restore. `collect_in_order` gives a sorted snapshot; `from_sorted`
/// rebuilds in O(n) instead of paying n rotating inserts.
fn restore_from_snapshot(book: &Treap<u32, u64>) {
    let snapshot: Vec<(u32, u64)> = book.iter().map(|(k, v)| (*k, *v)).collect();
    let restored = Treap::from_sorted(SEED, snapshot.clone()).expect("snapshot is sorted");
    println!(
        "  restored {} levels from a sorted snapshot, height {}",
        restored.len(),
        restored.height()
    );
    let round_tripped: Vec<(u32, u64)> = restored.iter().map(|(k, v)| (*k, *v)).collect();
    assert_eq!(round_tripped, snapshot);

    // Unsorted input is rejected rather than silently reordered.
    let bad = Treap::from_sorted(SEED, [(2u32, 1u64), (1, 1)]);
    assert!(bad.is_err(), "strictly-ascending precondition enforced");
}

pub fn is_empty(&self) -> bool

pub fn height(&self) -> usize

Longest root-to-leaf path in edges; 0 for an empty or single-node tree. The randomized-priority bound puts this near 3 * ln(n) in expectation, so it is the cheapest way to see whether the priority stream is doing its job on real keys.

Examples found in repository

examples/sample_app.rs (line 112)

fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

/// Sweep an aggressive sell through the bid side. `pop_last` takes the best
/// level in expected O(log n) and hands back both key and value, so the fill
/// loop never re-descends to find the next price.
fn sweep_the_touch(book: &mut Treap<u32, u64>) {
    let mut to_fill = 1_200u64;
    let mut fills = Vec::new();
    while to_fill > 0 {
        let Some((px, qty)) = book.pop_last() else {
            break;
        };
        let take = qty.min(to_fill);
        to_fill -= take;
        fills.push((px, take));
        if qty > take {
            book.insert(px, qty - take); // partial fill, level survives
        }
    }
    println!("  sweep 1200 lots -> {fills:?}");
    assert_eq!(fills, vec![(10_002, 400), (10_001, 800)]);
    assert_eq!(book.len(), 8);
    assert_eq!(
        book.last().map(|(k, _)| *k),
        Some(10_001),
        "partial fill left the level"
    );
}

/// End-of-day restore. `collect_in_order` gives a sorted snapshot; `from_sorted`
/// rebuilds in O(n) instead of paying n rotating inserts.
fn restore_from_snapshot(book: &Treap<u32, u64>) {
    let snapshot: Vec<(u32, u64)> = book.iter().map(|(k, v)| (*k, *v)).collect();
    let restored = Treap::from_sorted(SEED, snapshot.clone()).expect("snapshot is sorted");
    println!(
        "  restored {} levels from a sorted snapshot, height {}",
        restored.len(),
        restored.height()
    );
    let round_tripped: Vec<(u32, u64)> = restored.iter().map(|(k, v)| (*k, *v)).collect();
    assert_eq!(round_tripped, snapshot);

    // Unsorted input is rejected rather than silently reordered.
    let bad = Treap::from_sorted(SEED, [(2u32, 1u64), (1, 1)]);
    assert!(bad.is_err(), "strictly-ascending precondition enforced");
}

pub fn clear(&mut self)

Drop every entry and reset to empty, keeping the arena’s capacity so a rebuild does not pay the growth path again.

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

Examples found in repository

examples/perf_features.rs (line 46)

fn build(n: usize) -> Treap<u64, u64> {
    let mut t = Treap::new(SEED);
    for i in 0..n {
        t.insert(key_at(i), i as u64);
    }
    t
}

examples/sample_app.rs (line 83)

fn build_book() -> Treap<u32, u64> {
    let mut book: Treap<u32, u64> = Treap::with_capacity(SEED, TAPE.len());
    for event in &TAPE {
        match event {
            Event::Post(px, qty) => {
                book.insert(*px, *qty);
            }
            Event::Amend(px, delta) => {
                if let Some(qty) = book.get_mut(px) {
                    *qty = qty.saturating_add_signed(*delta);
                }
            }
            Event::Cancel(px) => {
                book.remove(px);
            }
        }
    }
    assert_eq!(book.len(), 9);
    assert_eq!(
        book.get(&10_000).copied(),
        Some(650),
        "amend applied in place"
    );
    assert!(!book.contains_key(&9997), "cancelled level is gone");
    book
}

/// Read the book the way a trader does: best price first, then the touch and
/// its neighbours. `iter_rev` walks the ladder high to low; `floor` and
/// `predecessor` answer "what is at or below this price" without a scan.
fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

/// Sweep an aggressive sell through the bid side. `pop_last` takes the best
/// level in expected O(log n) and hands back both key and value, so the fill
/// loop never re-descends to find the next price.
fn sweep_the_touch(book: &mut Treap<u32, u64>) {
    let mut to_fill = 1_200u64;
    let mut fills = Vec::new();
    while to_fill > 0 {
        let Some((px, qty)) = book.pop_last() else {
            break;
        };
        let take = qty.min(to_fill);
        to_fill -= take;
        fills.push((px, take));
        if qty > take {
            book.insert(px, qty - take); // partial fill, level survives
        }
    }
    println!("  sweep 1200 lots -> {fills:?}");
    assert_eq!(fills, vec![(10_002, 400), (10_001, 800)]);
    assert_eq!(book.len(), 8);
    assert_eq!(
        book.last().map(|(k, _)| *k),
        Some(10_001),
        "partial fill left the level"
    );
}

/// End-of-day restore. `collect_in_order` gives a sorted snapshot; `from_sorted`
/// rebuilds in O(n) instead of paying n rotating inserts.
fn restore_from_snapshot(book: &Treap<u32, u64>) {
    let snapshot: Vec<(u32, u64)> = book.iter().map(|(k, v)| (*k, *v)).collect();
    let restored = Treap::from_sorted(SEED, snapshot.clone()).expect("snapshot is sorted");
    println!(
        "  restored {} levels from a sorted snapshot, height {}",
        restored.len(),
        restored.height()
    );
    let round_tripped: Vec<(u32, u64)> = restored.iter().map(|(k, v)| (*k, *v)).collect();
    assert_eq!(round_tripped, snapshot);

    // Unsorted input is rejected rather than silently reordered.
    let bad = Treap::from_sorted(SEED, [(2u32, 1u64), (1, 1)]);
    assert!(bad.is_err(), "strictly-ascending precondition enforced");
}

/// Sum resting depth in a price band without
/// materialising the whole ladder. `range` descends to the low bound in
/// expected O(log N), then walks only the window in ascending order. Each
/// bound is independently inclusive, exclusive, or unbounded.
fn band_depth() {
    use subms_treap::RangeBound;
    println!("\n== range-query: depth in a price band ==");
    let book = build_book();
    let (lo, hi) = (9_996u32, 10_000u32);
    let band: Vec<(u32, u64)> = book
        .range(RangeBound::Inclusive(&lo), RangeBound::Inclusive(&hi))
        .map(|(k, v)| (*k, *v))
        .collect();
    let depth: u64 = band.iter().map(|(_, q)| *q).sum();
    println!("  [{lo}, {hi}] -> {} levels, {depth} lots", band.len());
    assert_eq!(
        band.iter().map(|(k, _)| *k).collect::<Vec<_>>(),
        vec![9_996, 9_998, 9_999, 10_000]
    );
    assert_eq!(depth, 2_500);

    // Exclusive upper bound drops the touch itself.
    let inside: u64 = book
        .range(RangeBound::Inclusive(&lo), RangeBound::Exclusive(&hi))
        .map(|(_, q)| *q)
        .sum();
    println!("  same band, exclusive of {hi}: {inside} lots");
    assert_eq!(inside, 1_850);
}

/// `persistent` feature: version the book so a prior state stays queryable.
/// Each `insert` / `remove` returns a NEW book and leaves the receiver
/// untouched - the shape a risk what-if branch or an audit trail wants.
#[cfg(feature = "persistent")]
fn versioned_book() {
    use subms_treap::PersistentTreap;
    println!("\n== persistent: versioned book ==");
    let open: PersistentTreap<u32, u64> = PersistentTreap::new(SEED);
    let open = open
        .insert(9_999, 250)
        .insert(10_000, 500)
        .insert(10_001, 100);

    // Branch: what does the book look like if the 9999 level fills?
    let after_fill = open.remove(&9_999);
    println!(
        "  open: {} levels, depth@9999 {:?}",
        open.len(),
        open.get(&9_999).copied()
    );
    println!(
        "  after fill: {} levels, depth@9999 {:?}",
        after_fill.len(),
        after_fill.get(&9_999)
    );
    assert_eq!(open.get(&9_999).copied(), Some(250), "prior version intact");
    assert_eq!(after_fill.get(&9_999), None);
    assert_eq!((open.len(), after_fill.len()), (3, 2));
}

/// `merge-split` feature: partition the ladder at the touch in expected
/// O(log N), then stitch it back. This is the treap's distinguishing
/// operation - a red-black tree has no cheap equivalent. `merge` requires
/// every key on the left to be strictly less than every key on the right.
#[cfg(feature = "merge-split")]
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]);
}

/// `concurrent-reads` feature: freeze the book into a shared snapshot and fan
/// it out to reader threads (market-data / risk consumers) while the writer
/// keeps applying updates. Every reader sees a stable point-in-time book.
#[cfg(feature = "concurrent-reads")]
fn published_snapshot() {
    use std::thread;
    use subms_treap::TreapSnapshot;
    println!("\n== concurrent-reads: published book snapshot ==");
    let mut book: Treap<u32, u64> = Treap::new(SEED);
    for px in 9_990..10_010u32 {
        book.insert(px, (px as u64) * 10);
    }
    let snap = TreapSnapshot::from_treap(&book);

    let readers: Vec<_> = (0..4)
        .map(|_| {
            let s = snap.clone();
            thread::spawn(move || s.range(&9_995, &10_004).count())
        })
        .collect();

    // Writer churn after the snapshot: readers must not observe it.
    book.insert(12_345, 1);
    book.remove(&9_990);

    for r in readers {
        assert_eq!(
            r.join().unwrap(),
            10,
            "reader sees the frozen 10-level band"
        );
    }
    println!("  4 readers each counted 10 levels in [9995, 10004]");
    assert!(
        snap.get(&12_345).is_none(),
        "snapshot isolated from later writes"
    );
    assert_eq!(snap.len(), 20);
}

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

Examples found in repository

examples/sample_app.rs (line 97)

fn build_book() -> Treap<u32, u64> {
    let mut book: Treap<u32, u64> = Treap::with_capacity(SEED, TAPE.len());
    for event in &TAPE {
        match event {
            Event::Post(px, qty) => {
                book.insert(*px, *qty);
            }
            Event::Amend(px, delta) => {
                if let Some(qty) = book.get_mut(px) {
                    *qty = qty.saturating_add_signed(*delta);
                }
            }
            Event::Cancel(px) => {
                book.remove(px);
            }
        }
    }
    assert_eq!(book.len(), 9);
    assert_eq!(
        book.get(&10_000).copied(),
        Some(650),
        "amend applied in place"
    );
    assert!(!book.contains_key(&9997), "cancelled level is gone");
    book
}

examples/perf_features.rs (line 112)

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_mut(&mut self, key: &K) -> Option<&mut V>

Mutable access to a resting value. The amend path for a price level: no re-descent through insert, no priority redraw, no rotation.

Examples found in repository

examples/sample_app.rs (line 86)

fn build_book() -> Treap<u32, u64> {
    let mut book: Treap<u32, u64> = Treap::with_capacity(SEED, TAPE.len());
    for event in &TAPE {
        match event {
            Event::Post(px, qty) => {
                book.insert(*px, *qty);
            }
            Event::Amend(px, delta) => {
                if let Some(qty) = book.get_mut(px) {
                    *qty = qty.saturating_add_signed(*delta);
                }
            }
            Event::Cancel(px) => {
                book.remove(px);
            }
        }
    }
    assert_eq!(book.len(), 9);
    assert_eq!(
        book.get(&10_000).copied(),
        Some(650),
        "amend applied in place"
    );
    assert!(!book.contains_key(&9997), "cancelled level is gone");
    book
}

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

Examples found in repository

examples/sample_app.rs (line 101)

fn build_book() -> Treap<u32, u64> {
    let mut book: Treap<u32, u64> = Treap::with_capacity(SEED, TAPE.len());
    for event in &TAPE {
        match event {
            Event::Post(px, qty) => {
                book.insert(*px, *qty);
            }
            Event::Amend(px, delta) => {
                if let Some(qty) = book.get_mut(px) {
                    *qty = qty.saturating_add_signed(*delta);
                }
            }
            Event::Cancel(px) => {
                book.remove(px);
            }
        }
    }
    assert_eq!(book.len(), 9);
    assert_eq!(
        book.get(&10_000).copied(),
        Some(650),
        "amend applied in place"
    );
    assert!(!book.contains_key(&9997), "cancelled level is gone");
    book
}

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

Examples found in repository

examples/sample_app.rs (line 91)

fn build_book() -> Treap<u32, u64> {
    let mut book: Treap<u32, u64> = Treap::with_capacity(SEED, TAPE.len());
    for event in &TAPE {
        match event {
            Event::Post(px, qty) => {
                book.insert(*px, *qty);
            }
            Event::Amend(px, delta) => {
                if let Some(qty) = book.get_mut(px) {
                    *qty = qty.saturating_add_signed(*delta);
                }
            }
            Event::Cancel(px) => {
                book.remove(px);
            }
        }
    }
    assert_eq!(book.len(), 9);
    assert_eq!(
        book.get(&10_000).copied(),
        Some(650),
        "amend applied in place"
    );
    assert!(!book.contains_key(&9997), "cancelled level is gone");
    book
}

/// Read the book the way a trader does: best price first, then the touch and
/// its neighbours. `iter_rev` walks the ladder high to low; `floor` and
/// `predecessor` answer "what is at or below this price" without a scan.
fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

/// Sweep an aggressive sell through the bid side. `pop_last` takes the best
/// level in expected O(log n) and hands back both key and value, so the fill
/// loop never re-descends to find the next price.
fn sweep_the_touch(book: &mut Treap<u32, u64>) {
    let mut to_fill = 1_200u64;
    let mut fills = Vec::new();
    while to_fill > 0 {
        let Some((px, qty)) = book.pop_last() else {
            break;
        };
        let take = qty.min(to_fill);
        to_fill -= take;
        fills.push((px, take));
        if qty > take {
            book.insert(px, qty - take); // partial fill, level survives
        }
    }
    println!("  sweep 1200 lots -> {fills:?}");
    assert_eq!(fills, vec![(10_002, 400), (10_001, 800)]);
    assert_eq!(book.len(), 8);
    assert_eq!(
        book.last().map(|(k, _)| *k),
        Some(10_001),
        "partial fill left the level"
    );
}

/// End-of-day restore. `collect_in_order` gives a sorted snapshot; `from_sorted`
/// rebuilds in O(n) instead of paying n rotating inserts.
fn restore_from_snapshot(book: &Treap<u32, u64>) {
    let snapshot: Vec<(u32, u64)> = book.iter().map(|(k, v)| (*k, *v)).collect();
    let restored = Treap::from_sorted(SEED, snapshot.clone()).expect("snapshot is sorted");
    println!(
        "  restored {} levels from a sorted snapshot, height {}",
        restored.len(),
        restored.height()
    );
    let round_tripped: Vec<(u32, u64)> = restored.iter().map(|(k, v)| (*k, *v)).collect();
    assert_eq!(round_tripped, snapshot);

    // Unsorted input is rejected rather than silently reordered.
    let bad = Treap::from_sorted(SEED, [(2u32, 1u64), (1, 1)]);
    assert!(bad.is_err(), "strictly-ascending precondition enforced");
}

/// Sum resting depth in a price band without
/// materialising the whole ladder. `range` descends to the low bound in
/// expected O(log N), then walks only the window in ascending order. Each
/// bound is independently inclusive, exclusive, or unbounded.
fn band_depth() {
    use subms_treap::RangeBound;
    println!("\n== range-query: depth in a price band ==");
    let book = build_book();
    let (lo, hi) = (9_996u32, 10_000u32);
    let band: Vec<(u32, u64)> = book
        .range(RangeBound::Inclusive(&lo), RangeBound::Inclusive(&hi))
        .map(|(k, v)| (*k, *v))
        .collect();
    let depth: u64 = band.iter().map(|(_, q)| *q).sum();
    println!("  [{lo}, {hi}] -> {} levels, {depth} lots", band.len());
    assert_eq!(
        band.iter().map(|(k, _)| *k).collect::<Vec<_>>(),
        vec![9_996, 9_998, 9_999, 10_000]
    );
    assert_eq!(depth, 2_500);

    // Exclusive upper bound drops the touch itself.
    let inside: u64 = book
        .range(RangeBound::Inclusive(&lo), RangeBound::Exclusive(&hi))
        .map(|(_, q)| *q)
        .sum();
    println!("  same band, exclusive of {hi}: {inside} lots");
    assert_eq!(inside, 1_850);
}

/// `persistent` feature: version the book so a prior state stays queryable.
/// Each `insert` / `remove` returns a NEW book and leaves the receiver
/// untouched - the shape a risk what-if branch or an audit trail wants.
#[cfg(feature = "persistent")]
fn versioned_book() {
    use subms_treap::PersistentTreap;
    println!("\n== persistent: versioned book ==");
    let open: PersistentTreap<u32, u64> = PersistentTreap::new(SEED);
    let open = open
        .insert(9_999, 250)
        .insert(10_000, 500)
        .insert(10_001, 100);

    // Branch: what does the book look like if the 9999 level fills?
    let after_fill = open.remove(&9_999);
    println!(
        "  open: {} levels, depth@9999 {:?}",
        open.len(),
        open.get(&9_999).copied()
    );
    println!(
        "  after fill: {} levels, depth@9999 {:?}",
        after_fill.len(),
        after_fill.get(&9_999)
    );
    assert_eq!(open.get(&9_999).copied(), Some(250), "prior version intact");
    assert_eq!(after_fill.get(&9_999), None);
    assert_eq!((open.len(), after_fill.len()), (3, 2));
}

/// `merge-split` feature: partition the ladder at the touch in expected
/// O(log N), then stitch it back. This is the treap's distinguishing
/// operation - a red-black tree has no cheap equivalent. `merge` requires
/// every key on the left to be strictly less than every key on the right.
#[cfg(feature = "merge-split")]
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]);
}

/// `concurrent-reads` feature: freeze the book into a shared snapshot and fan
/// it out to reader threads (market-data / risk consumers) while the writer
/// keeps applying updates. Every reader sees a stable point-in-time book.
#[cfg(feature = "concurrent-reads")]
fn published_snapshot() {
    use std::thread;
    use subms_treap::TreapSnapshot;
    println!("\n== concurrent-reads: published book snapshot ==");
    let mut book: Treap<u32, u64> = Treap::new(SEED);
    for px in 9_990..10_010u32 {
        book.insert(px, (px as u64) * 10);
    }
    let snap = TreapSnapshot::from_treap(&book);

    let readers: Vec<_> = (0..4)
        .map(|_| {
            let s = snap.clone();
            thread::spawn(move || s.range(&9_995, &10_004).count())
        })
        .collect();

    // Writer churn after the snapshot: readers must not observe it.
    book.insert(12_345, 1);
    book.remove(&9_990);

    for r in readers {
        assert_eq!(
            r.join().unwrap(),
            10,
            "reader sees the frozen 10-level band"
        );
    }
    println!("  4 readers each counted 10 levels in [9995, 10004]");
    assert!(
        snap.get(&12_345).is_none(),
        "snapshot isolated from later writes"
    );
    assert_eq!(snap.len(), 20);
}

pub fn first(&self) -> Option<(&K, &V)>

Smallest key and its value.

pub fn last(&self) -> Option<(&K, &V)>

Largest key and its value.

Examples found in repository

examples/sample_app.rs (line 109)

fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

/// Sweep an aggressive sell through the bid side. `pop_last` takes the best
/// level in expected O(log n) and hands back both key and value, so the fill
/// loop never re-descends to find the next price.
fn sweep_the_touch(book: &mut Treap<u32, u64>) {
    let mut to_fill = 1_200u64;
    let mut fills = Vec::new();
    while to_fill > 0 {
        let Some((px, qty)) = book.pop_last() else {
            break;
        };
        let take = qty.min(to_fill);
        to_fill -= take;
        fills.push((px, take));
        if qty > take {
            book.insert(px, qty - take); // partial fill, level survives
        }
    }
    println!("  sweep 1200 lots -> {fills:?}");
    assert_eq!(fills, vec![(10_002, 400), (10_001, 800)]);
    assert_eq!(book.len(), 8);
    assert_eq!(
        book.last().map(|(k, _)| *k),
        Some(10_001),
        "partial fill left the level"
    );
}

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

Greatest key <= key.

Examples found in repository

examples/sample_app.rs (line 130)

fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

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

Least key >= key.

Examples found in repository

examples/sample_app.rs (line 131)

fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

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

Greatest key strictly < key.

Examples found in repository

examples/sample_app.rs (line 121)

fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

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

Least key strictly > key.

pub fn pop_first(&mut self) -> Option<(K, V)>

Remove and return the smallest entry. The top-of-book sweep.

pub fn pop_last(&mut self) -> Option<(K, V)>

Remove and return the largest entry.

Examples found in repository

examples/sample_app.rs (line 144)

fn sweep_the_touch(book: &mut Treap<u32, u64>) {
    let mut to_fill = 1_200u64;
    let mut fills = Vec::new();
    while to_fill > 0 {
        let Some((px, qty)) = book.pop_last() else {
            break;
        };
        let take = qty.min(to_fill);
        to_fill -= take;
        fills.push((px, take));
        if qty > take {
            book.insert(px, qty - take); // partial fill, level survives
        }
    }
    println!("  sweep 1200 lots -> {fills:?}");
    assert_eq!(fills, vec![(10_002, 400), (10_001, 800)]);
    assert_eq!(book.len(), 8);
    assert_eq!(
        book.last().map(|(k, _)| *k),
        Some(10_001),
        "partial fill left the level"
    );
}

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

Cut the treap at pivot, keeping everything below it and returning everything at or above it.

The cut itself is the treap’s distinguishing operation against a red-black tree: one descent, expected O(log n), no rebalancing pass. The arena then charges for what it buys elsewhere - the upper half’s m nodes are relocated into their own arena, so the whole call is expected O(log n) + O(m). Where that relocation matters, the merge-split feature’s SplittableTreap is the pointer-backed variant that hands the detached subtree over without touching it.

use subms_treap::Treap;
let mut book: Treap<u32, u64> = Treap::new(7);
for px in [9998u32, 9999, 10_000, 10_001] { book.insert(px, 100); }
let marketable = book.split_off(&10_000);
assert_eq!(book.len(), 2);
assert_eq!(marketable.len(), 2);
assert_eq!(marketable.first().map(|(k, _)| *k), Some(10_000));

pub fn join(&mut self, other: Self) -> Result<(), TreapError>

Splice other onto the end of self. Every key in self must be strictly below every key in other.

The splice is expected O(log n); as with Treap::split_off, moving other’s m nodes into this arena adds O(m). An overlapping range is refused rather than silently corrupting the BST invariant, and both treaps are left as they were.

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

Ascending in-order iteration. Lazy: the only allocation is the traversal stack, sized to the tree’s height.

Examples found in repository

examples/sample_app.rs (line 167)

fn restore_from_snapshot(book: &Treap<u32, u64>) {
    let snapshot: Vec<(u32, u64)> = book.iter().map(|(k, v)| (*k, *v)).collect();
    let restored = Treap::from_sorted(SEED, snapshot.clone()).expect("snapshot is sorted");
    println!(
        "  restored {} levels from a sorted snapshot, height {}",
        restored.len(),
        restored.height()
    );
    let round_tripped: Vec<(u32, u64)> = restored.iter().map(|(k, v)| (*k, *v)).collect();
    assert_eq!(round_tripped, snapshot);

    // Unsorted input is rejected rather than silently reordered.
    let bad = Treap::from_sorted(SEED, [(2u32, 1u64), (1, 1)]);
    assert!(bad.is_err(), "strictly-ascending precondition enforced");
}

pub fn iter_rev(&self) -> IterRev<'_, K, V>

Descending in-order iteration. A bid ladder is read best price first, which is the reverse of the stored order.

Examples found in repository

examples/sample_app.rs (line 117)

fn report(book: &Treap<u32, u64>) {
    let (best_px, best_qty) = book.last().map(|(k, v)| (*k, *v)).expect("non-empty");
    println!(
        "  best bid {best_px} x {best_qty} | height {} | {} levels",
        book.height(),
        book.len()
    );

    println!("  top 5, best first:");
    for (px, qty) in book.iter_rev().take(5) {
        println!("    {px}  {qty:>5}");
    }

    let inside = book.predecessor(&best_px).map(|(k, _)| *k).unwrap();
    println!("  next level down: {inside}");
    assert_eq!(inside, 10_001);

    // A price that is not a resting level still answers, which is the whole
    // reason for an ordered index over a hash map.
    let probe = 9_990u32;
    println!(
        "  probe {probe}: floor {:?}, ceiling {:?}",
        book.floor(&probe).map(|(k, _)| *k),
        book.ceiling(&probe).map(|(k, _)| *k)
    );
    assert_eq!(book.floor(&probe), None);
    assert_eq!(book.ceiling(&probe).map(|(k, _)| *k), Some(9993));
}

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

In-order traversal; pushes (key, value) references into a Vec.

Trait Implementations

impl<K: Ord + Debug, V: Debug> Debug for Treap<K, V>

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

Formats the value using the given formatter.

impl<K, V> Drop for Treap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<'a, K: Ord, V> IntoIterator for &'a Treap<K, V>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.