augmented-rbtree 0.3.0

An augmented red-black tree with generic, user-defined per-node statistics — enables interval trees, order-statistics trees, range-sum trees, and more.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#![cfg(any(feature = "alloc", feature = "allocator-api", feature = "nightly"))]
#![cfg_attr(feature = "nightly", feature(allocator_api))]

mod helpers;

use std::iter::repeat_with;

use augmented_rbtree::AugmentedRBTree;
use itertools::Itertools;
use rand::RngExt;

use crate::helpers::common::{
    custom_augment_a::{
        CustomAugment, CustomKey, CustomValue, DROP_CUSTOM_KEY_LOGGER, DROP_CUSTOM_STATS_LOGGER,
        DROP_CUSTOM_VALUE_LOGGER, reset_drop_loggers,
    },
    test_rng,
};

#[test]
fn check_keys_values_stats_are_droped() {
    reset_drop_loggers();
    let mut rng = test_rng();
    let keys: Vec<i32> = repeat_with(|| rng.random_range(1..100))
        .unique()
        .take(20)
        .collect();
    {
        let mut tree = AugmentedRBTree::<CustomKey, CustomValue, CustomAugment>::new();

        for &key in &keys {
            tree.insert(CustomKey(key), CustomValue(key.to_string()));
        }
    }
    let mut dropped_keys = DROP_CUSTOM_KEY_LOGGER.with_borrow(std::clone::Clone::clone);
    let mut orig_keys = keys
        .iter()
        .map(std::string::ToString::to_string)
        .collect::<Vec<_>>();
    dropped_keys.sort();
    orig_keys.sort();
    assert_eq!(dropped_keys, orig_keys);
    let mut dropped_values = DROP_CUSTOM_VALUE_LOGGER.with_borrow(std::clone::Clone::clone);
    let mut orig_values = keys
        .iter()
        .map(std::string::ToString::to_string)
        .collect::<Vec<_>>();
    dropped_values.sort();
    orig_values.sort();
    assert_eq!(dropped_values, orig_values);
    let dropped_stats_len = DROP_CUSTOM_STATS_LOGGER.with_borrow(std::vec::Vec::len);

    println!(
        "dropped_stats_len: {} dropped_keys_len: {}",
        dropped_stats_len,
        dropped_keys.len()
    );
    assert!(dropped_stats_len > dropped_keys.len());
}

#[test]
fn check_into_iter_drops_remaining_values() {
    reset_drop_loggers();
    let mut rng = test_rng();
    let keys: Vec<i32> = repeat_with(|| rng.random_range(1..100))
        .unique()
        .take(20)
        .collect();

    {
        let mut tree = AugmentedRBTree::<CustomKey, CustomValue, CustomAugment>::new();

        for &key in &keys {
            tree.insert(CustomKey(key), CustomValue(key.to_string()));
        }

        let mut consumed = tree.into_iter();

        let _ = consumed.next();
        let _ = consumed.next();

        assert_eq!(consumed.len(), 18);
    }

    let mut dropped_keys = DROP_CUSTOM_KEY_LOGGER.with_borrow(std::clone::Clone::clone);
    let mut orig_keys = keys
        .iter()
        .map(std::string::ToString::to_string)
        .collect::<Vec<_>>();
    dropped_keys.sort();
    orig_keys.sort();
    assert_eq!(dropped_keys, orig_keys);

    let mut dropped_values = DROP_CUSTOM_VALUE_LOGGER.with_borrow(std::clone::Clone::clone);
    let mut orig_values = keys
        .iter()
        .map(std::string::ToString::to_string)
        .collect::<Vec<_>>();
    dropped_values.sort();
    orig_values.sort();
    assert_eq!(dropped_values, orig_values);
}