avltriee/
update.rs

1mod balance;
2mod delete;
3
4use std::{cmp::Ordering, num::NonZeroU32};
5
6use crate::{AvltrieeAllocator, AvltrieeSearch, search::Edge};
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        unsafe {
79            self.allocate(row);
80
81            *self.node_unchecked_mut(row) = AvltrieeNode::new(edge.0, value);
82            if let Some(found_row) = edge.0 {
83                let p = self.node_unchecked_mut(found_row);
84                if edge.1 == Ordering::Greater {
85                    p.left = Some(row);
86                } else {
87                    p.right = Some(row);
88                }
89                self.balance(row);
90            } else {
91                self.set_root(Some(row));
92            }
93        }
94    }
95
96    fn reset_height(&mut self, row: NonZeroU32) {
97        let node = unsafe { self.node_unchecked(row) };
98
99        let left_height = node.left.map_or(
100            0,
101            |left: NonZeroU32| unsafe { self.node_unchecked(left) }.height,
102        );
103
104        let right_height = node
105            .right
106            .map_or(0, |right| unsafe { self.node_unchecked(right) }.height);
107
108        unsafe { self.node_unchecked_mut(row) }.height =
109            std::cmp::max(left_height, right_height) + 1;
110    }
111
112    fn replace_child(
113        &mut self,
114        parent: Option<NonZeroU32>,
115        current_child: NonZeroU32,
116        new_child: Option<NonZeroU32>,
117    ) {
118        if let Some(parent) = parent {
119            unsafe { self.node_unchecked_mut(parent) }.changeling(current_child, new_child);
120        } else {
121            self.set_root(new_child);
122        }
123    }
124}
avltriee/update.rs

avltriee/
update.rs
