avltriee/
lib.rs

1pub mod search;
2
3mod allocator;
4mod default;
5mod head;
6mod iter;
7mod node;
8mod update;
9
10use std::{marker::PhantomData, num::NonZeroU32};
11
12use allocator::VecAvltrieeAllocator;
13
14pub use allocator::AvltrieeAllocator;
15pub use iter::AvltrieeIter;
16pub use node::AvltrieeNode;
17pub use search::AvltrieeSearch;
18pub use update::AvltrieeUpdate;
19
20pub struct Avltriee<T, I: ?Sized = T, A = VecAvltrieeAllocator<T>> {
21    allocator: A,
22    _marker: PhantomData<fn(I, T)>,
23}
24
25impl<T: Default> Avltriee<T, T, VecAvltrieeAllocator<T>> {
26    /// Creates the Avltriee with Default allocator.
27    pub fn new() -> Self {
28        Self {
29            allocator: VecAvltrieeAllocator::new(),
30            _marker: PhantomData,
31        }
32    }
33}
34
35impl<T, I: ?Sized, A: AvltrieeAllocator<T>> Avltriee<T, I, A> {
36    /// Creates the Avltriee with [AvltrieeAllocator].
37    pub fn with_allocator(allocator: A) -> Self {
38        Self {
39            allocator,
40            _marker: PhantomData,
41        }
42    }
43
44    /// Returns the node of the specified row.
45    pub fn node(&self, row: NonZeroU32) -> Option<&AvltrieeNode<T>> {
46        self.allocator
47            .get(row)
48            .and_then(|node| (node.height != 0).then(|| unsafe { self.node_unchecked(row) }))
49    }
50
51    pub unsafe fn node_unchecked(&self, row: NonZeroU32) -> &AvltrieeNode<T> {
52        &*self.allocator.as_ptr().offset(row.get() as isize)
53    }
54
55    unsafe fn node_unchecked_mut(&mut self, row: NonZeroU32) -> &mut AvltrieeNode<T> {
56        &mut *self.allocator.as_mut_ptr().offset(row.get() as isize)
57    }
58
59    /// Checks whether the specified row is a node with a unique value.
60    pub fn is_unique(&self, row: NonZeroU32) -> Option<(bool, &AvltrieeNode<T>)> {
61        self.node(row).map(|node| {
62            (
63                node.same.is_none()
64                    && node.parent.is_some_and(|parent| {
65                        unsafe { self.node_unchecked(parent) }.same != Some(row)
66                    }),
67                node,
68            )
69        })
70    }
71
72    fn allocate(&mut self, rows: NonZeroU32) {
73        self.allocator.resize(rows.get());
74        self.set_rows_count(rows.get());
75    }
76
77    fn min(&self, t: Option<NonZeroU32>) -> Option<NonZeroU32> {
78        let mut t = t;
79        while let Some(t_inner) = t {
80            let l = unsafe { self.node_unchecked(t_inner) }.left;
81            if l.is_some() {
82                t = l;
83            } else {
84                break;
85            }
86        }
87        t
88    }
89
90    fn max(&self, t: Option<NonZeroU32>) -> Option<NonZeroU32> {
91        let mut t = t;
92        while let Some(t_inner) = t {
93            let r = unsafe { self.node_unchecked(t_inner) }.right;
94            if r.is_some() {
95                t = r;
96            } else {
97                break;
98            }
99        }
100        t
101    }
102}
avltriee/lib.rs

avltriee/
lib.rs
