avltriee/
update.rs

1mod balance;
2mod delete;
3
4use std::{cmp::Ordering, num::NonZeroU32};
5
6use crate::{search::Edge, AvltrieeAllocator, AvltrieeSearch};
7
8use super::{Avltriee, AvltrieeNode};
9
10pub trait AvltrieeUpdate<T, I: ?Sized, A: AvltrieeAllocator<T>>:
11    AsMut<Avltriee<T, I, A>> + AvltrieeSearch<T, I, A>
12{
13    fn convert_on_insert_unique(&mut self, input: &I) -> T;
14    fn on_delete(&mut self, _row: NonZeroU32) {}
15
16    /// Creates a new row and assigns a value to it.
17    fn insert(&mut self, value: &I) -> NonZeroU32
18    where
19        T: Clone,
20    {
21        let row = unsafe { NonZeroU32::new_unchecked(self.as_ref().rows_count() + 1) };
22        self.update(row, value);
23        row
24    }
25
26    /// Updates the value in the specified row.
27    fn update(&mut self, row: NonZeroU32, value: &I)
28    where
29        T: Clone,
30    {
31        if let Some(node_value) = self.value(row) {
32            if Self::cmp(node_value, value) == Ordering::Equal {
33                return; //update value eq exists value
34            }
35            self.delete(row);
36        }
37
38        let edge = self.edge(value);
39        if let (Some(same_row), Ordering::Equal) = edge {
40            let triee = self.as_mut();
41
42            triee.allocate(row);
43
44            let same_node = unsafe { triee.node_unchecked_mut(same_row) };
45            let same_left = same_node.left;
46            let same_right = same_node.right;
47            let same_parent = same_node.parent;
48
49            *unsafe { triee.node_unchecked_mut(row) } = same_node.same_clone(same_row, row);
50
51            triee.replace_child(same_parent, same_row, Some(row));
52
53            if let Some(left) = same_left {
54                unsafe { triee.node_unchecked_mut(left) }.parent = Some(row);
55            }
56            if let Some(right) = same_right {
57                unsafe { triee.node_unchecked_mut(right) }.parent = Some(row);
58            }
59        } else {
60            let value = self.convert_on_insert_unique(value);
61            unsafe { self.as_mut().insert_unique_unchecked(row, value, edge) };
62        }
63    }
64
65    /// Delete the specified row.
66    fn delete(&mut self, row: NonZeroU32) {
67        self.on_delete(row);
68        self.as_mut().delete_inner(row);
69    }
70}
71
72impl<T, I: ?Sized, A: AvltrieeAllocator<T>> Avltriee<T, I, A> {
73    /// Insert a unique value.
74    /// If you specify a row that does not exist, space will be automatically allocated. If you specify a row that is too large, memory may be allocated unnecessarily.
75    /// # Safety
76    /// value must be unique.
77    pub unsafe fn insert_unique_unchecked(&mut self, row: NonZeroU32, value: T, edge: Edge) {
78        self.allocate(row);
79
80        *self.node_unchecked_mut(row) = AvltrieeNode::new(edge.0, value);
81        if let Some(found_row) = edge.0 {
82            let p = self.node_unchecked_mut(found_row);
83            if edge.1 == Ordering::Greater {
84                p.left = Some(row);
85            } else {
86                p.right = Some(row);
87            }
88            self.balance(row);
89        } else {
90            self.set_root(Some(row));
91        }
92    }
93
94    fn reset_height(&mut self, row: NonZeroU32) {
95        let node = unsafe { self.node_unchecked(row) };
96
97        let left_height = node.left.map_or(
98            0,
99            |left: NonZeroU32| unsafe { self.node_unchecked(left) }.height,
100        );
101
102        let right_height = node
103            .right
104            .map_or(0, |right| unsafe { self.node_unchecked(right) }.height);
105
106        unsafe { self.node_unchecked_mut(row) }.height =
107            std::cmp::max(left_height, right_height) + 1;
108    }
109
110    fn replace_child(
111        &mut self,
112        parent: Option<NonZeroU32>,
113        current_child: NonZeroU32,
114        new_child: Option<NonZeroU32>,
115    ) {
116        if let Some(parent) = parent {
117            unsafe { self.node_unchecked_mut(parent) }.changeling(current_child, new_child);
118        } else {
119            self.set_root(new_child);
120        }
121    }
122}
avltriee/update.rs

avltriee/
update.rs
