zenoh_keyexpr/keyexpr_tree/traits/
mod.rs

1//
2// Copyright (c) 2023 ZettaScale Technology
3//
4// This program and the accompanying materials are made available under the
5// terms of the Eclipse Public License 2.0 which is available at
6// http://www.eclipse.org/legal/epl-2.0, or the Apache License, Version 2.0
7// which is available at https://www.apache.org/licenses/LICENSE-2.0.
8//
9// SPDX-License-Identifier: EPL-2.0 OR Apache-2.0
10//
11// Contributors:
12//   ZettaScale Zenoh Team, <zenoh@zettascale.tech>
13//
14
15use alloc::boxed::Box;
16
17use crate::{keyexpr, OwnedKeyExpr};
18pub mod default_impls;
19
20/// The basic immutable methods of all KeTrees.
21pub trait IKeyExprTree<'a, Weight> {
22    /// The type of a given node in the KeTree.
23    ///
24    /// The methods of nodes are exposed in the [`IKeyExprTreeNode`] and [`IKeyExprTreeNodeMut`] traits
25    type Node: IKeyExprTreeNodeMut<Weight>;
26
27    /// Accesses the node at `key` if it exists, treating KEs as if they were completely verbatim keys.
28    ///
29    /// Returns `None` if `key` is not present in the KeTree.
30    fn node(&'a self, key: &keyexpr) -> Option<&'a Self::Node>;
31
32    /// Returns a reference to the weight of the node at `key` if it exists.
33    fn weight_at(&'a self, key: &keyexpr) -> Option<&'a Weight> {
34        self.node(key)
35            .and_then(<Self::Node as IKeyExprTreeNode<Weight>>::weight)
36    }
37
38    type TreeIterItem;
39    type TreeIter: Iterator<Item = Self::TreeIterItem>;
40
41    /// Iterates over the whole tree, including nodes with no weight.
42    ///
43    /// [`IKeyExprTree::key_value_pairs`] provides an iterator over all key-value pairs in the tree.
44    fn tree_iter(&'a self) -> Self::TreeIter;
45
46    /// Iterates through weighted nodes, yielding their KE and Weight.
47    #[allow(clippy::type_complexity)]
48    fn key_value_pairs(
49        &'a self,
50    ) -> core::iter::FilterMap<
51        Self::TreeIter,
52        fn(Self::TreeIterItem) -> Option<(OwnedKeyExpr, &'a Weight)>,
53    >
54    where
55        Self::TreeIterItem: AsNode<Box<Self::Node>>,
56    {
57        self.tree_iter().filter_map(|node| {
58            unsafe {
59                core::mem::transmute::<Option<&Weight>, Option<&Weight>>(node.as_node().weight())
60            }
61            .map(|w| (node.as_node().keyexpr(), w))
62        })
63    }
64
65    type IntersectionItem;
66    type Intersection: Iterator<Item = Self::IntersectionItem>;
67
68    /// Iterates over all nodes of the tree whose KE intersects with the given `key`.
69    ///
70    /// Note that nodes without a `Weight` will also be yielded by the iterator.
71    ///
72    /// You can obtain an iterator over key-value pairs using `iter.filter_map(|node| node.weight.map(|w| (node.keyexpr(), w)))`,
73    /// keep in mind that the full keyexpr of nodes is not stored in them by default, but computed using the tree:
74    /// if you need to get a node's key often, inserting its keyexpr in the `Weight` could be a good idea.
75    fn intersecting_nodes(&'a self, key: &'a keyexpr) -> Self::Intersection;
76
77    /// Returns an iterator over the KEs contained in the tree that intersect with `key`
78    fn intersecting_keys(
79        &'a self,
80        key: &'a keyexpr,
81    ) -> Keys<Self::Intersection, Self::IntersectionItem>
82    where
83        Self::IntersectionItem: AsNode<Self::Node>,
84        Self::Node: IKeyExprTreeNode<Weight>,
85    {
86        self.intersecting_nodes(key)
87            .filter_map(filter_map_weighted_node_to_key)
88    }
89
90    type InclusionItem;
91    type Inclusion: Iterator<Item = Self::InclusionItem>;
92
93    /// Iterates over all nodes of the tree whose KE is included by the given `key`.
94    ///
95    /// Note that nodes without a `Weight` will also be yielded by the iterator.
96    ///
97    /// You can obtain an iterator over key-value pairs using `iter.filter_map(|node| node.weight.map(|w| (node.keyexpr(), w)))`,
98    /// keep in mind that the full keyexpr of nodes is not stored in them by default, but computed using the tree:
99    /// if you need to get a node's key often, inserting its keyexpr in the `Weight` could be a good idea.
100    fn included_nodes(&'a self, key: &'a keyexpr) -> Self::Inclusion;
101
102    /// Returns an iterator over the KEs contained in the tree that are included by `key`
103    fn included_keys(&'a self, key: &'a keyexpr) -> Keys<Self::Inclusion, Self::InclusionItem>
104    where
105        Self::InclusionItem: AsNode<Self::Node>,
106        Self::Node: IKeyExprTreeNode<Weight>,
107    {
108        self.included_nodes(key)
109            .filter_map(filter_map_weighted_node_to_key)
110    }
111
112    type IncluderItem;
113    type Includer: Iterator<Item = Self::IncluderItem>;
114
115    /// Iterates over all nodes of the tree whose KE includes the given `key`.
116    ///
117    /// Note that nodes without a `Weight` will also be yielded by the iterator.
118    ///
119    /// You can obtain an iterator over key-value pairs using `iter.filter_map(|node| node.weight.map(|w| (node.keyexpr(), w)))`,
120    /// keep in mind that the full keyexpr of nodes is not stored in them by default, but computed using the tree:
121    /// if you need to get a node's key often, inserting its keyexpr in the `Weight` could be a good idea.
122    fn nodes_including(&'a self, key: &'a keyexpr) -> Self::Includer;
123
124    /// Returns an iterator over the KEs contained in the tree that include `key`
125    fn keys_including(&'a self, key: &'a keyexpr) -> Keys<Self::Includer, Self::IncluderItem>
126    where
127        Self::IncluderItem: AsNode<Self::Node>,
128        Self::Node: IKeyExprTreeNode<Weight>,
129    {
130        self.nodes_including(key)
131            .filter_map(filter_map_weighted_node_to_key)
132    }
133}
134
135/// The basic mutable methods of all KeTrees.
136pub trait IKeyExprTreeMut<'a, Weight>: IKeyExprTree<'a, Weight> {
137    /// Mutably accesses the node at `key` if it exists, treating KEs as if they were completely verbatim keys.
138    ///
139    /// Returns `None` if `key` is not present. Use [`IKeyExprTreeMut::node_mut_or_create`] if you wish to construct the node if it doesn't exist.
140    fn node_mut<'b>(&'b mut self, key: &keyexpr) -> Option<&'b mut Self::Node>;
141
142    /// Returns a mutable reference to the weight of the node at `key`.
143    fn weight_at_mut(&'a mut self, key: &keyexpr) -> Option<&'a mut Weight> {
144        self.node_mut(key)
145            .and_then(<Self::Node as IKeyExprTreeNodeMut<Weight>>::weight_mut)
146    }
147
148    /// Mutably accesses the node at `key`, creating it if necessary.
149    fn node_mut_or_create<'b>(&'b mut self, key: &keyexpr) -> &'b mut Self::Node;
150
151    /// Inserts a weight at `key`, returning the previous weight if it existed.
152    fn insert(&mut self, key: &keyexpr, weight: Weight) -> Option<Weight> {
153        self.node_mut_or_create(key).insert_weight(weight)
154    }
155
156    /// Clears the weight of the node at `key`, but doesn't actually destroy the node.
157    ///
158    /// To actually destroy nodes, [`IKeyExprTreeMut::prune_where`] or [`IKeyExprTreeMut::prune`] must be called.
159    fn remove(&mut self, key: &keyexpr) -> Option<Weight>;
160
161    type TreeIterItemMut;
162    type TreeIterMut: Iterator<Item = Self::TreeIterItemMut>;
163
164    /// Iterates over the whole tree, including nodes with no weight.
165    fn tree_iter_mut(&'a mut self) -> Self::TreeIterMut;
166
167    type IntersectionItemMut;
168    type IntersectionMut: Iterator<Item = Self::IntersectionItemMut>;
169
170    /// Iterates over all nodes of the tree whose KE intersects with the given `key`.
171    ///
172    /// Note that nodes without a `Weight` will also be yielded by the iterator.
173    fn intersecting_nodes_mut(&'a mut self, key: &'a keyexpr) -> Self::IntersectionMut;
174    type InclusionItemMut;
175    type InclusionMut: Iterator<Item = Self::InclusionItemMut>;
176
177    /// Iterates over all nodes of the tree whose KE is included by the given `key`.
178    ///
179    /// Note that nodes without a `Weight` will also be yielded by the iterator.
180    fn included_nodes_mut(&'a mut self, key: &'a keyexpr) -> Self::InclusionMut;
181    type IncluderItemMut;
182    type IncluderMut: Iterator<Item = Self::IncluderItemMut>;
183
184    /// Iterates over all nodes of the tree whose KE includes the given `key`.
185    ///
186    /// Note that nodes without a `Weight` will also be yielded by the iterator.
187    fn nodes_including_mut(&'a mut self, key: &'a keyexpr) -> Self::IncluderMut;
188    /// Prunes node from the tree where the predicate returns `true`.
189    ///
190    /// Note that nodes that still have children will not be pruned.
191    fn prune_where<F: FnMut(&mut Self::Node) -> bool>(&mut self, predicate: F);
192
193    /// Prunes empty nodes from the tree, unless they have at least one non-empty descendent.
194    fn prune(&mut self) {
195        self.prune_where(|node| node.weight().is_none())
196    }
197}
198/// The basic operations of a KeTree when a Token is necessary to access data.
199pub trait ITokenKeyExprTree<'a, Weight, Token> {
200    /// An immutable guard to a node of the tree.
201    type Node: IKeyExprTreeNode<Weight>;
202    // A mutable guard to a node of the tree.
203    type NodeMut: IKeyExprTreeNodeMut<Weight>;
204
205    /// Accesses the node at `key` if it exists, treating KEs as if they were completely verbatim keys.
206    ///
207    /// Returns `None` if `key` is not present in the KeTree.
208    fn node(&'a self, token: &'a Token, key: &keyexpr) -> Option<Self::Node>;
209
210    /// Mutably accesses the node at `key` if it exists, treating KEs as if they were completely verbatim keys.
211    ///
212    /// Returns `None` if `key` is not present. Use [`IKeyExprTreeMut::node_mut_or_create`] if you wish to construct the node if it doesn't exist.
213    fn node_mut(&'a self, token: &'a mut Token, key: &keyexpr) -> Option<Self::NodeMut>;
214
215    /// Mutably accesses the node at `key`, creating it if necessary.
216    fn node_or_create(&'a self, token: &'a mut Token, key: &keyexpr) -> Self::NodeMut;
217
218    /// Inserts a weight at `key`, returning the previous weight if it existed.
219    fn insert(&'a self, token: &'a mut Token, at: &keyexpr, weight: Weight) -> Option<Weight> {
220        self.node_or_create(token, at).insert_weight(weight)
221    }
222
223    /// Clears the weight of the node at `key`, but doesn't actually destroy the node.
224    ///
225    /// To actually destroy nodes, [`ITokenKeyExprTree::prune_where`] or [`ITokenKeyExprTree::prune`] must be called.
226    fn remove(&'a mut self, token: &'a mut Token, key: &keyexpr) -> Option<Weight> {
227        self.node_mut(token, key)
228            .and_then(|mut node| node.take_weight())
229    }
230
231    type TreeIterItem;
232    type TreeIter: Iterator<Item = Self::TreeIterItem>;
233
234    /// Iterates over the whole tree, including nodes with no weight.
235    fn tree_iter(&'a self, token: &'a Token) -> Self::TreeIter;
236
237    type TreeIterItemMut;
238    type TreeIterMut: Iterator<Item = Self::TreeIterItemMut>;
239
240    /// Iterates over the whole tree, including nodes with no weight.
241    fn tree_iter_mut(&'a self, token: &'a mut Token) -> Self::TreeIterMut;
242
243    type IntersectionItem;
244    type Intersection: Iterator<Item = Self::IntersectionItem>;
245
246    /// Iterates over all nodes of the tree whose KE intersects with the given `key`.
247    ///
248    /// Note that nodes without a `Weight` will also be yielded by the iterator.
249    ///
250    /// You can obtain an iterator over key-value pairs using `iter.filter_map(|node| node.weight.map(|w| (node.keyexpr(), w)))`,
251    /// keep in mind that the full keyexpr of nodes is not stored in them by default, but computed using the tree:
252    /// if you need to get a node's key often, inserting its keyexpr in the `Weight` could be a good idea.
253    fn intersecting_nodes(&'a self, token: &'a Token, key: &'a keyexpr) -> Self::Intersection;
254
255    /// Returns an iterator over the KEs contained in the tree that intersect with `key`
256    fn intersecting_keys(
257        &'a self,
258        token: &'a Token,
259        key: &'a keyexpr,
260    ) -> Keys<Self::Intersection, Self::IntersectionItem>
261    where
262        Self::IntersectionItem: AsNode<Self::Node>,
263        Self::Node: IKeyExprTreeNode<Weight>,
264    {
265        self.intersecting_nodes(token, key)
266            .filter_map(filter_map_weighted_node_to_key)
267    }
268
269    type IntersectionItemMut;
270    type IntersectionMut: Iterator<Item = Self::IntersectionItemMut>;
271
272    /// Iterates over all nodes of the tree whose KE intersects with the given `key`.
273    ///
274    /// Note that nodes without a `Weight` will also be yielded by the iterator.
275    fn intersecting_nodes_mut(
276        &'a self,
277        token: &'a mut Token,
278        key: &'a keyexpr,
279    ) -> Self::IntersectionMut;
280
281    type InclusionItem;
282    type Inclusion: Iterator<Item = Self::InclusionItem>;
283
284    /// Iterates over all nodes of the tree whose KE is included by the given `key`.
285    ///
286    /// Note that nodes without a `Weight` will also be yielded by the iterator.
287    fn included_nodes(&'a self, token: &'a Token, key: &'a keyexpr) -> Self::Inclusion;
288
289    /// Returns an iterator over the KEs contained in the tree that are included by `key`
290    fn included_keys(
291        &'a self,
292        token: &'a Token,
293        key: &'a keyexpr,
294    ) -> Keys<Self::Inclusion, Self::InclusionItem>
295    where
296        Self::InclusionItem: AsNode<Self::Node>,
297        Self::Node: IKeyExprTreeNode<Weight>,
298    {
299        self.included_nodes(token, key)
300            .filter_map(filter_map_weighted_node_to_key)
301    }
302
303    type InclusionItemMut;
304    type InclusionMut: Iterator<Item = Self::InclusionItemMut>;
305
306    /// Iterates over all nodes of the tree whose KE is included by the given `key`.
307    ///
308    /// Note that nodes without a `Weight` will also be yielded by the iterator.
309    fn included_nodes_mut(&'a self, token: &'a mut Token, key: &'a keyexpr) -> Self::InclusionMut;
310
311    type IncluderItem;
312    type Includer: Iterator<Item = Self::IncluderItem>;
313
314    /// Iterates over all nodes of the tree whose KE includes the given `key`.
315    ///
316    /// Note that nodes without a `Weight` will also be yielded by the iterator.
317    fn nodes_including(&'a self, token: &'a Token, key: &'a keyexpr) -> Self::Includer;
318
319    /// Returns an iterator over the KEs contained in the tree that include `key`
320    fn keys_including(
321        &'a self,
322        token: &'a Token,
323        key: &'a keyexpr,
324    ) -> Keys<Self::Includer, Self::IncluderItem>
325    where
326        Self::IncluderItem: AsNode<Self::Node>,
327        Self::Node: IKeyExprTreeNode<Weight>,
328    {
329        self.nodes_including(token, key)
330            .filter_map(filter_map_weighted_node_to_key)
331    }
332
333    type IncluderItemMut;
334    type IncluderMut: Iterator<Item = Self::IncluderItemMut>;
335
336    /// Iterates over all nodes of the tree whose KE includes the given `key`.
337    ///
338    /// Note that nodes without a `Weight` will also be yielded by the iterator.
339    fn nodes_including_mut(&'a self, token: &'a mut Token, key: &'a keyexpr) -> Self::IncluderMut;
340
341    type PruneNode: IKeyExprTreeNodeMut<Weight>;
342
343    fn prune_where<F: FnMut(&mut Self::PruneNode) -> bool>(&self, token: &mut Token, predicate: F);
344    fn prune(&self, token: &mut Token) {
345        self.prune_where(token, |node| node.weight().is_none())
346    }
347}
348
349/// The non-mutating methods of a KeTree node.
350pub trait IKeyExprTreeNode<Weight>: UIKeyExprTreeNode<Weight> {
351    /// Access the parent node if it exists (the node isn't the first chunk of a key-expression).
352    fn parent(&self) -> Option<&Self::Parent> {
353        unsafe { self.__parent() }
354    }
355    /// Compute this node's full key expression.
356    ///
357    /// Note that KeTrees don't normally store each node's full key expression.
358    /// If you need to repeatedly access a node's full key expression, it is suggested
359    /// to store that key expression as part of the node's `Weight` (it's optional value).
360    fn keyexpr(&self) -> OwnedKeyExpr {
361        unsafe { self.__keyexpr() }
362    }
363
364    /// Access the node's weight (or value).
365    ///
366    /// Weights can be assigned to a node through many of [`IKeyExprTreeNodeMut`]'s methods, as well as through [`IKeyExprTreeMut::insert`].
367    ///
368    /// Nodes may not have a value in any of the following cases:
369    /// - The node is a parent to other nodes, but was never assigned a weight itself (or that weight has been removed).
370    /// - The node is a leaf of the KeTree whose value was [`IKeyExprTreeMut::remove`]d, but [`IKeyExprTreeMut::prune`] hasn't been called yet.
371    fn weight(&self) -> Option<&Weight> {
372        unsafe { self.__weight() }
373    }
374
375    /// Access a node's children.
376    fn children(&self) -> &Self::Children {
377        unsafe { self.__children() }
378    }
379}
380
381#[doc(hidden)]
382pub trait UIKeyExprTreeNode<Weight> {
383    type Parent;
384    unsafe fn __parent(&self) -> Option<&Self::Parent>;
385    unsafe fn __keyexpr(&self) -> OwnedKeyExpr;
386    unsafe fn __weight(&self) -> Option<&Weight>;
387    type Child;
388    type Children: IChildren<Self::Child>;
389    unsafe fn __children(&self) -> &Self::Children;
390}
391
392/// The mutating methods of a KeTree node.
393pub trait IKeyExprTreeNodeMut<Weight>: IKeyExprTreeNode<Weight> {
394    /// Mutably access the parent node if it exists (the node isn't the first chunk of a key-expression).
395    fn parent_mut(&mut self) -> Option<&mut Self::Parent>;
396
397    /// Mutably access the node's weight.
398    fn weight_mut(&mut self) -> Option<&mut Weight>;
399
400    /// Remove the node's weight.
401    fn take_weight(&mut self) -> Option<Weight>;
402
403    /// Assign a weight to the node, returning the previous weight if the node had one.
404    fn insert_weight(&mut self, weight: Weight) -> Option<Weight>;
405
406    /// Mutably access the node's children.
407    fn children_mut(&mut self) -> &mut Self::Children;
408}
409
410/// Nodes from a token-locked tree need a token to obtain read/write permissions.
411///
412/// This trait allows tokenizing a node, allowing to use [`IKeyExprTreeNode`] and [`IKeyExprTreeNodeMut`]'s methods on it.
413pub trait ITokenKeyExprTreeNode<'a, Weight, Token> {
414    type Tokenized: IKeyExprTreeNode<Weight>;
415    /// Wrap the node with the an immutable reference to the token to allow immutable access to its contents.
416    fn tokenize(&'a self, token: &'a Token) -> Self::Tokenized;
417    type TokenizedMut: IKeyExprTreeNodeMut<Weight>;
418    /// Wrap the node with a mutable reference to the token to allow mutable access to its contents
419    fn tokenize_mut(&'a self, token: &'a mut Token) -> Self::TokenizedMut;
420}
421impl<'a, T: 'a, Weight, Token: 'a> ITokenKeyExprTreeNode<'a, Weight, Token> for T
422where
423    (&'a T, &'a Token): IKeyExprTreeNode<Weight>,
424    (&'a T, &'a mut Token): IKeyExprTreeNodeMut<Weight>,
425{
426    type Tokenized = (&'a T, &'a Token);
427    fn tokenize(&'a self, token: &'a Token) -> Self::Tokenized {
428        (self, token)
429    }
430    type TokenizedMut = (&'a T, &'a mut Token);
431    fn tokenize_mut(&'a self, token: &'a mut Token) -> Self::TokenizedMut {
432        (self, token)
433    }
434}
435
436/// Provides a data-structure to store children to the KeTree.
437pub trait IChildrenProvider<T> {
438    type Assoc: Default + 'static;
439}
440
441pub trait IChildren<T: ?Sized> {
442    type Node: HasChunk + AsNode<T> + AsNodeMut<T>;
443    fn len(&self) -> usize;
444    fn is_empty(&self) -> bool {
445        self.len() == 0
446    }
447    fn child_at<'a>(&'a self, chunk: &keyexpr) -> Option<&'a Self::Node>;
448    fn child_at_mut<'a>(&'a mut self, chunk: &keyexpr) -> Option<&'a mut Self::Node>;
449    type Entry<'a, 'b>: IEntry<'a, 'b, T>
450    where
451        Self: 'a,
452        'a: 'b,
453        T: 'b;
454    fn remove(&mut self, chunk: &keyexpr) -> Option<Self::Node>;
455    fn entry<'a, 'b>(&'a mut self, chunk: &'b keyexpr) -> Self::Entry<'a, 'b>
456    where
457        Self: 'a + 'b,
458        T: 'b;
459    type Iter<'a>: Iterator<Item = &'a Self::Node>
460    where
461        Self: 'a,
462        Self::Node: 'a;
463    fn children<'a>(&'a self) -> Self::Iter<'a>
464    where
465        Self: 'a;
466    type IterMut<'a>: Iterator<Item = &'a mut Self::Node>
467    where
468        Self: 'a,
469        Self::Node: 'a;
470    fn children_mut<'a>(&'a mut self) -> Self::IterMut<'a>
471    where
472        Self: 'a;
473    type Intersection<'a>: Iterator<Item = &'a Self::Node>
474    where
475        Self: 'a,
476        Self::Node: 'a;
477    fn intersection<'a>(&'a self, key: &'a keyexpr) -> Self::Intersection<'a>;
478    type IntersectionMut<'a>: Iterator<Item = &'a mut Self::Node>
479    where
480        Self: 'a,
481        Self::Node: 'a;
482    fn intersection_mut<'a>(&'a mut self, key: &'a keyexpr) -> Self::IntersectionMut<'a>;
483    type Inclusion<'a>: Iterator<Item = &'a Self::Node>
484    where
485        Self: 'a,
486        Self::Node: 'a;
487    fn inclusion<'a>(&'a self, key: &'a keyexpr) -> Self::Inclusion<'a>;
488    type InclusionMut<'a>: Iterator<Item = &'a mut Self::Node>
489    where
490        Self: 'a,
491        Self::Node: 'a;
492    fn inclusion_mut<'a>(&'a mut self, key: &'a keyexpr) -> Self::InclusionMut<'a>;
493    fn filter_out<F: FnMut(&mut T) -> bool>(&mut self, predicate: &mut F);
494}
495
496pub trait IEntry<'a, 'b, T: ?Sized> {
497    fn get_or_insert_with<F: FnOnce(&'b keyexpr) -> T>(self, f: F) -> &'a mut T;
498}
499
500pub trait HasChunk {
501    fn chunk(&self) -> &keyexpr;
502}
503
504pub trait AsNode<T: ?Sized> {
505    fn as_node(&self) -> &T;
506}
507pub trait AsNodeMut<T: ?Sized>: AsNode<T> {
508    fn as_node_mut(&mut self) -> &mut T;
509}
510
511type Keys<I, Item> = core::iter::FilterMap<I, fn(Item) -> Option<OwnedKeyExpr>>;
512fn filter_map_weighted_node_to_key<N: IKeyExprTreeNode<W>, I: AsNode<N>, W>(
513    item: I,
514) -> Option<OwnedKeyExpr> {
515    let node: &N = item.as_node();
516    node.weight().is_some().then(|| node.keyexpr())
517}
zenoh_keyexpr/keyexpr_tree/traits/mod.rs

zenoh_keyexpr/keyexpr_tree/traits/
mod.rs
