avltriee 0.78.0

Customized version of AVLTree library.Process the same value in the third branch. One data is immovable from one row, and positional relationships such as left, right, and parent are all referenced by row numbers. No search is required for value reference by specifying a row.
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

#[cfg(doctest)]
#[doc = include_str!("../README.md")]
struct ReadmeDoctests;

pub mod search;

mod allocator;
mod default;
mod head;
mod iter;
mod node;
mod update;

use std::{marker::PhantomData, num::NonZeroU32};

use allocator::VecAvltrieeAllocator;

pub use allocator::AvltrieeAllocator;
pub use iter::AvltrieeIter;
pub use node::AvltrieeNode;
pub use search::AvltrieeSearch;
pub use update::AvltrieeUpdate;

pub struct Avltriee<T, I: ?Sized = T, A = VecAvltrieeAllocator<T>> {
    allocator: A,
    _marker: PhantomData<fn(I, T)>,
}

impl<T: Default> Avltriee<T, T, VecAvltrieeAllocator<T>> {
    /// Creates the Avltriee with Default allocator.
    pub fn new() -> Self {
        Self {
            allocator: VecAvltrieeAllocator::new(),
            _marker: PhantomData,
        }
    }
}

impl<T: Default> Default for Avltriee<T, T, VecAvltrieeAllocator<T>> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T, I: ?Sized, A: AvltrieeAllocator<T>> Avltriee<T, I, A> {
    /// Creates the Avltriee with [AvltrieeAllocator].
    pub fn new_in(allocator: A) -> Self {
        Self {
            allocator,
            _marker: PhantomData,
        }
    }

    /// Returns the node of the specified row.
    pub fn node(&self, row: NonZeroU32) -> Option<&AvltrieeNode<T>> {
        self.allocator
            .get(row)
            .and_then(|node| (node.height != 0).then(|| unsafe { self.node_unchecked(row) }))
    }

    /// Returns the node of the specified row without checking that the row exists.
    ///
    /// # Safety
    /// `row` must be within the allocated rows of the tree.
    pub unsafe fn node_unchecked(&self, row: NonZeroU32) -> &AvltrieeNode<T> {
        unsafe { &*self.allocator.as_ptr().offset(row.get() as isize) }
    }

    unsafe fn node_unchecked_mut(&mut self, row: NonZeroU32) -> &mut AvltrieeNode<T> {
        unsafe { &mut *self.allocator.as_mut_ptr().offset(row.get() as isize) }
    }

    /// Checks whether the specified row is a node with a unique value.
    pub fn is_unique(&self, row: NonZeroU32) -> Option<(bool, &AvltrieeNode<T>)> {
        self.node(row).map(|node| {
            (
                node.same.is_none()
                    && node.parent.is_some_and(|parent| {
                        unsafe { self.node_unchecked(parent) }.same != Some(row)
                    }),
                node,
            )
        })
    }

    /// Makes sure that the specified row is allocated.
    ///
    /// Rows up to `rows_count` are already allocated, so this only grows.
    /// Shrinking here would drop or overwrite existing rows when an existing
    /// row is updated.
    fn allocate(&mut self, row: NonZeroU32) {
        let row = row.get();
        if row > self.rows_count() {
            self.allocator.resize(row);
            self.set_rows_count(row);
        }
    }

    fn min(&self, t: Option<NonZeroU32>) -> Option<NonZeroU32> {
        let mut t = t;
        while let Some(t_inner) = t {
            let l = unsafe { self.node_unchecked(t_inner) }.left;
            if l.is_some() {
                t = l;
            } else {
                break;
            }
        }
        t
    }

    fn max(&self, t: Option<NonZeroU32>) -> Option<NonZeroU32> {
        let mut t = t;
        while let Some(t_inner) = t {
            let r = unsafe { self.node_unchecked(t_inner) }.right;
            if r.is_some() {
                t = r;
            } else {
                break;
            }
        }
        t
    }
}