nb_tree/tree/entry/
detached.rs

1use std::{
2    hash::Hash,
3    ops::{Deref, DerefMut},
4};
5
6use crate::{
7    path::Path,
8    tree::{
9        position::{AttachedPosition, DetachedPosition},
10        Position,
11    },
12};
13
14use super::{node::Node, Entry, NodeIDX, Tree, TREEBOUND};
15
16pub struct DetachedEntry<R, N, B, const BOUND: bool>
17where
18    R: Deref<Target = Tree<N, B>>,
19{
20    pub(super) tree: R,
21    pub(super) position: DetachedPosition<B, usize>,
22}
23
24impl<R, N, B, const BOUND: bool> From<(R, Path<B>, Path<NodeIDX>)> for DetachedEntry<R, N, B, BOUND>
25where
26    R: Deref<Target = Tree<N, B>>,
27{
28    fn from((tree, path, idxs): (R, Path<B>, Path<NodeIDX>)) -> Self {
29        Self {
30            tree,
31            position: DetachedPosition::from(path, idxs),
32        }
33    }
34}
35impl<R, N, B, const BOUND: bool> DetachedEntry<R, N, B, BOUND>
36where
37    R: Deref<Target = Tree<N, B>>,
38{
39    pub fn from(tree: R, position: DetachedPosition<B, usize>) -> Self {
40        Self { tree, position }
41    }
42
43    pub(super) fn into_node(self, position: AttachedPosition<B, NodeIDX>) -> Node<R, N, B, BOUND> {
44        Node {
45            tree: self.tree,
46            position,
47        }
48    }
49    pub fn into_entry(self) -> Entry<R, N, B, BOUND> {
50        self.into()
51    }
52
53    pub fn branch(&self) -> Option<&B> {
54        self.position.at_branch()
55    }
56
57    pub fn path(&self) -> &Path<B> {
58        self.position.path()
59    }
60
61    pub fn iter_detached_path(&self) -> std::collections::vec_deque::Iter<'_, B> {
62        self.position.iter_detached_path()
63    }
64}
65impl<R, N, B, const BOUND: bool> DetachedEntry<R, N, B, BOUND>
66where
67    R: DerefMut<Target = Tree<N, B>>,
68    B: Eq + Hash + Clone,
69{
70    pub fn insert(
71        mut self,
72        value: N,
73    ) -> Result<Node<R, N, B, BOUND>, DetachedEntry<R, N, B, BOUND>> {
74        if self.position.is_empty() {
75            // Insert at root
76            self.tree.insert_root(value);
77            let idx = self.tree.get_root_idx().unwrap();
78            let pos = self.position.attach(idx).unwrap_attached();
79            return Ok(Node::from(self.tree, pos));
80        }
81        if !self.position.is_rooted() {
82            return Err(self);
83        }
84        let path: Path<B> = self.position.iter_detached_path().cloned().collect();
85        match path.len() {
86            1 => {
87                let idx = self
88                    .tree
89                    .insert_at(
90                        *self.position.detached_at().unwrap(),
91                        path.last().unwrap().clone(),
92                        value,
93                    )
94                    .1;
95                let pos = self.position.attach(idx).unwrap_attached();
96                Ok(Node::from(self.tree, pos))
97            }
98            0 => {
99                unreachable!("DetachedEntry is not detached");
100            }
101            _ => Err(self),
102        }
103    }
104}
105
106impl<R, N, B> DetachedEntry<R, N, B, TREEBOUND>
107where
108    R: DerefMut<Target = Tree<N, B>>,
109    N: Default,
110    B: Default + Eq + Hash + Clone,
111{
112    pub fn insert_extend(mut self, value: N) -> Node<R, N, B, TREEBOUND> {
113        let detached_path = self.position.iter_detached_path().cloned().collect();
114        let pos = if let Some(idx) = self.position.detached_at().copied() {
115            self.position
116                .attach_all(self.tree.extend(&detached_path, Some(idx)))
117                .unwrap_attached()
118        } else {
119            self.tree.insert_root(Default::default());
120            let idx = self.tree.get_root_idx().unwrap();
121            let pos = self.position.attach(idx);
122            if pos.is_attached() {
123                pos.unwrap_attached()
124            } else {
125                pos.unwrap_detached()
126                    .attach_all(self.tree.extend(&detached_path, Some(idx)))
127                    .unwrap_attached()
128            }
129        };
130        self.tree.nodes[*pos.at()].value = value;
131        Node::from(self.tree, pos)
132    }
133}
134
135impl<R, N, B> DetachedEntry<R, N, B, TREEBOUND>
136where
137    R: Deref<Target = Tree<N, B>>,
138{
139    pub fn move_to_attached(
140        self,
141    ) -> Result<Node<R, N, B, TREEBOUND>, DetachedEntry<R, N, B, TREEBOUND>> {
142        match self.position.move_to_attached() {
143            Ok(attached_position) => Ok(Node::from(self.tree, attached_position)),
144            Err(detached_position) => Err(DetachedEntry::from(self.tree, detached_position)),
145        }
146    }
147
148    pub fn move_down(&mut self, path: Path<B>) {
149        for branch in path {
150            self.position.move_down(branch);
151        }
152    }
153
154    pub fn move_down_branch(&mut self, branch: B) {
155        self.position.move_down(branch);
156    }
157
158    pub fn move_up(mut self, up: usize) -> (Entry<R, N, B, TREEBOUND>, Option<usize>) {
159        let (pos, overflow) = self.position.move_up(up);
160        (
161            match pos {
162                Position::Attached(position) => Node::from(self.tree, position).into(),
163                Position::Detached(position) => {
164                    self.position = position;
165                    self.into()
166                }
167            },
168            overflow,
169        )
170    }
171}
172
173impl<R, N, B, const BOUND: bool> DetachedEntry<R, N, B, BOUND>
174where
175    R: Deref<Target = Tree<N, B>>,
176{
177    pub fn offshoot_len(&self) -> usize {
178        self.position.offshoot_len()
179    }
180    /*
181    fn into_node(self) -> Node<R, N, B> {
182        assert!(
183            self.position.is_attached(),
184            "Cannot convert to Node, position is detached"
185        );
186        Node {
187            tree: self.tree,
188            position: self.position,
189        }
190    }*/
191}
nb_tree/tree/entry/detached.rs

nb_tree/tree/entry/
detached.rs
