tagged_tree/
lib.rs

1mod iterators;
2
3pub use iterators::*;
4
5#[cfg(feature = "serde")]
6use serde::{Deserialize, Serialize};
7use std::{
8    borrow::Borrow,
9    collections::btree_map::{
10        self, BTreeMap, IntoKeys, IntoValues, Keys, Values, ValuesMut,
11    },
12    ops::Index,
13};
14
15#[derive(Debug, Clone, Default, Ord, PartialOrd, Eq, PartialEq, Hash)]
16#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
17pub struct Tree<K: Ord, V> {
18    value: V,
19    children: BTreeMap<K, Tree<K, V>>,
20}
21
22impl<K: Ord, V> Tree<K, V> {
23    #[inline]
24    pub fn new(value: V) -> Tree<K, V> {
25        Tree {
26            value,
27            children: BTreeMap::new(),
28        }
29    }
30
31    #[inline]
32    pub fn value(&self) -> &V {
33        &self.value
34    }
35
36    #[inline]
37    pub fn value_mut(&mut self) -> &mut V {
38        &mut self.value
39    }
40    #[inline]
41    pub fn set_value(&mut self, mut value: V) -> V {
42        std::mem::swap(&mut self.value, &mut value);
43        value
44    }
45
46    #[inline]
47    pub fn children_keys(&self) -> Keys<'_, K, Self> {
48        self.children.keys()
49    }
50
51    #[inline]
52    pub fn children(&self) -> Values<'_, K, Self> {
53        self.children.values()
54    }
55
56    #[inline]
57    pub fn children_mut(&mut self) -> ValuesMut<'_, K, Self> {
58        self.children.values_mut()
59    }
60
61    /// An iterator visiting the children without nesting
62    #[inline]
63    pub fn iter_single(&self) -> btree_map::Iter<K, Self> {
64        self.children.iter()
65    }
66
67    /// An iterator visiting the children without nesting and returning mutable
68    /// references
69    #[inline]
70    pub fn iter_single_mut(&mut self) -> btree_map::IterMut<K, Self> {
71        self.children.iter_mut()
72    }
73
74    #[inline]
75    pub fn iter_depth_first(&self) -> DepthFirstIter<K, V> {
76        DepthFirstIter::new(self)
77    }
78
79    #[inline]
80    pub fn iter_depth_first_mut(&mut self) -> DepthFirstIterMut<K, V> {
81        DepthFirstIterMut::new(self)
82    }
83
84    #[inline]
85    pub fn iter_breadth_first(&self) -> BreadthFirstIter<K, V> {
86        BreadthFirstIter::new(self)
87    }
88
89    #[inline]
90    pub fn iter_breadth_first_mut(&mut self) -> BreadthFirstIterMut<K, V> {
91        BreadthFirstIterMut::new(self)
92    }
93
94    #[inline]
95    pub fn child_count(&mut self) -> usize {
96        self.children.len()
97    }
98
99    #[inline]
100    pub fn is_childless(&self) -> bool {
101        self.children.is_empty()
102    }
103
104    #[inline]
105    pub fn clear(&mut self) {
106        self.children.clear()
107    }
108
109    #[inline]
110    pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
111        match self.children.entry(key) {
112            btree_map::Entry::Occupied(entry) => {
113                Entry::Occupied(OccupiedEntry(entry))
114            }
115            btree_map::Entry::Vacant(entry) => {
116                Entry::Vacant(VacantEntry(entry))
117            }
118        }
119    }
120
121    #[inline]
122    pub fn get_child<Q: ?Sized>(&self, key: &Q) -> Option<&Self>
123    where
124        K: Borrow<Q>,
125        Q: Ord,
126    {
127        self.children.get(key)
128    }
129
130    #[inline]
131    pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &Self)>
132    where
133        K: Borrow<Q>,
134        Q: Ord,
135    {
136        self.children.get_key_value(key)
137    }
138
139    #[inline]
140    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
141    where
142        K: Borrow<Q>,
143        Q: Ord,
144    {
145        self.children.contains_key(key)
146    }
147
148    #[inline]
149    pub fn get_child_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut Self>
150    where
151        K: Borrow<Q>,
152        Q: Ord,
153    {
154        self.children.get_mut(key)
155    }
156
157    #[inline]
158    pub fn add_child(
159        &mut self,
160        key: K,
161        mut value: V,
162    ) -> (Option<V>, &mut Self) {
163        match self.entry(key) {
164            Entry::Occupied(entry) => {
165                let child = entry.into_mut();
166                std::mem::swap(&mut value, &mut child.value);
167                (Some(value), child)
168            }
169            Entry::Vacant(entry) => (None, entry.insert(value)),
170        }
171    }
172
173    #[inline]
174    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<Self>
175    where
176        K: Borrow<Q>,
177        Q: Ord,
178    {
179        self.children.remove(key)
180    }
181
182    #[inline]
183    pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, Self)>
184    where
185        K: Borrow<Q>,
186        Q: Ord,
187    {
188        self.children.remove_entry(key)
189    }
190
191    #[inline]
192    pub fn retain<F>(&mut self, f: F)
193    where
194        F: FnMut(&K, &mut Self) -> bool,
195    {
196        self.children.retain(f)
197    }
198
199    #[inline]
200    pub fn into_keys(self) -> IntoKeys<K, Self> {
201        self.children.into_keys()
202    }
203
204    #[inline]
205    pub fn into_values(self) -> IntoValues<K, Self> {
206        self.children.into_values()
207    }
208}
209
210impl<K, Q, V> Index<&'_ Q> for Tree<K, V>
211where
212    K: Borrow<Q> + Ord,
213    Q: Ord + ?Sized,
214{
215    type Output = Self;
216
217    #[inline]
218    fn index(&self, index: &'_ Q) -> &Self::Output {
219        self.children.index(index)
220    }
221}
222
223impl<K: Ord, V> IntoIterator for Tree<K, V> {
224    type Item = (K, Tree<K, V>);
225    type IntoIter = btree_map::IntoIter<K, Tree<K, V>>;
226
227    fn into_iter(self) -> Self::IntoIter {
228        self.children.into_iter()
229    }
230}
231
232#[derive(Debug)]
233pub enum Entry<'a, K: Ord, V> {
234    Occupied(OccupiedEntry<'a, K, V>),
235    Vacant(VacantEntry<'a, K, V>),
236}
237
238impl<'a, K: Ord, V> Entry<'a, K, V> {
239    #[inline]
240    pub fn or_insert(self, default: V) -> &'a mut Tree<K, V> {
241        match self {
242            Entry::Occupied(entry) => entry.into_mut(),
243            Entry::Vacant(entry) => entry.insert(default),
244        }
245    }
246
247    #[inline]
248    pub fn or_insert_tree(self, default: Tree<K, V>) -> &'a mut Tree<K, V> {
249        match self {
250            Entry::Occupied(entry) => entry.into_mut(),
251            Entry::Vacant(entry) => entry.insert_tree(default),
252        }
253    }
254
255    #[inline]
256    pub fn or_insert_with<F: FnOnce() -> V>(
257        self,
258        default: F,
259    ) -> &'a mut Tree<K, V> {
260        match self {
261            Entry::Occupied(entry) => entry.into_mut(),
262            Entry::Vacant(entry) => entry.insert(default()),
263        }
264    }
265
266    #[inline]
267    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(
268        self,
269        default: F,
270    ) -> &'a mut Tree<K, V> {
271        match self {
272            Entry::Occupied(entry) => entry.into_mut(),
273            Entry::Vacant(entry) => {
274                let value = default(entry.key());
275                entry.insert(value)
276            }
277        }
278    }
279
280    #[inline]
281    pub fn key(&self) -> &K {
282        match *self {
283            Entry::Occupied(ref entry) => entry.key(),
284            Entry::Vacant(ref entry) => entry.key(),
285        }
286    }
287
288    #[inline]
289    pub fn and_modify<F>(self, f: F) -> Self
290    where
291        F: FnOnce(&mut Tree<K, V>),
292    {
293        match self {
294            Entry::Occupied(mut entry) => {
295                f(entry.get_mut());
296                Entry::Occupied(entry)
297            }
298            Entry::Vacant(entry) => Entry::Vacant(entry),
299        }
300    }
301}
302
303#[derive(Debug)]
304pub struct OccupiedEntry<'a, K: Ord, V>(
305    btree_map::OccupiedEntry<'a, K, Tree<K, V>>,
306);
307
308impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
309    #[inline]
310    pub fn key(&self) -> &K {
311        self.0.key()
312    }
313
314    #[inline]
315    pub fn remove_entry(self) -> (K, Tree<K, V>) {
316        self.0.remove_entry()
317    }
318
319    #[inline]
320    pub fn get(&self) -> &Tree<K, V> {
321        self.0.get()
322    }
323
324    #[inline]
325    pub fn get_mut(&mut self) -> &mut Tree<K, V> {
326        self.0.get_mut()
327    }
328
329    #[inline]
330    pub fn into_mut(self) -> &'a mut Tree<K, V> {
331        self.0.into_mut()
332    }
333
334    #[inline]
335    pub fn insert(&mut self, mut value: V) -> (V, &mut Tree<K, V>) {
336        let child = self.get_mut();
337        std::mem::swap(&mut value, &mut child.value);
338        (value, child)
339    }
340
341    #[inline]
342    pub fn insert_tree(&mut self, tree: Tree<K, V>) -> Tree<K, V> {
343        self.0.insert(tree)
344    }
345
346    #[inline]
347    pub fn remove(self) -> Tree<K, V> {
348        self.0.remove()
349    }
350}
351
352#[derive(Debug)]
353pub struct VacantEntry<'a, K: 'a + Ord, V: 'a>(
354    btree_map::VacantEntry<'a, K, Tree<K, V>>,
355);
356
357impl<'a, K: 'a + Ord, V: 'a> VacantEntry<'a, K, V> {
358    #[inline]
359    pub fn key(&self) -> &K {
360        self.0.key()
361    }
362
363    #[inline]
364    pub fn into_key(self) -> K {
365        self.0.into_key()
366    }
367
368    #[inline]
369    pub fn insert(self, value: V) -> &'a mut Tree<K, V> {
370        self.0.insert(Tree::new(value))
371    }
372
373    #[inline]
374    pub fn insert_tree(self, tree: Tree<K, V>) -> &'a mut Tree<K, V> {
375        self.0.insert(tree)
376    }
377}
378
379#[cfg(doctest)]
380doc_comment::doctest!("../README.md");
tagged_tree/lib.rs

tagged_tree/
lib.rs
