ratio_graph/
node.rs

1//! # Node module
2//!
3//! ## License
4//!
5//! This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0.
6//! If a copy of the MPL was not distributed with this file,
7//! You can obtain one at <https://mozilla.org/MPL/2.0/>.
8//!
9//! **Code examples both in the docstrings and rendered documentation are free to use.**
10
11use std::collections::{BTreeMap, BTreeSet};
12
13use snafu::Snafu;
14use uuid::Uuid;
15
16#[cfg(feature = "serde")]
17use crate::serde_utils::*;
18use crate::{Aggregate, Meta, Metadata};
19
20/// Node error.
21#[derive(Clone, Debug, Snafu)]
22#[snafu(visibility(pub(crate)))]
23pub enum NodeStoreError {
24    /// No node in store with this id: {id}.
25    NodeNotInStore { id: Uuid },
26    /// Node {id} is a bus node without a parent.
27    BusWithoutParent { id: Uuid },
28    /// Cyclic hierarchy detected, node {id} occurs in its own ascendants.
29    CyclicAscendants { id: Uuid },
30    /// Cyclic hierarchy detected, node {id} occurs in its own descendants.
31    CyclicDescendants { id: Uuid },
32}
33
34/// A node in a graph.
35#[derive(Clone, Debug, Default, PartialEq)]
36#[cfg_attr(
37    feature = "serde",
38    derive(serde::Serialize, serde::Deserialize),
39    serde(rename_all = "camelCase")
40)]
41pub struct Node {
42    /// Instance metadata.
43    pub metadata: Metadata,
44    /// ID of the parent of this node, if any.
45    #[cfg_attr(
46        feature = "serde",
47        serde(default, skip_serializing_if = "Option::is_none")
48    )]
49    pub parent: Option<Uuid>,
50    /// IDs of this node's children,
51    #[cfg_attr(
52        feature = "serde",
53        serde(default, skip_serializing_if = "is_empty_vec")
54    )]
55    pub children: Vec<Uuid>,
56    /// Whether this node is a bus node for its parent.
57    #[cfg_attr(feature = "serde", serde(default, skip_serializing_if = "is_default"))]
58    pub is_bus: bool,
59}
60impl Node {
61    /// Create a new node struct with arguments.
62    pub fn new(
63        metadata: Option<Metadata>,
64        parent: Option<Uuid>,
65        children: Option<Vec<Uuid>>,
66        is_bus: Option<bool>,
67    ) -> Self {
68        Node {
69            metadata: metadata.unwrap_or_default(),
70            parent,
71            children: children.unwrap_or_default(),
72            is_bus: is_bus.unwrap_or(false),
73        }
74    }
75
76    /// Whether this node has no parent and is thus a root node.
77    pub fn is_root(&self) -> bool {
78        self.parent.is_none()
79    }
80
81    /// Whether this node has no children and is thus a leaf node.
82    pub fn is_leaf(&self) -> bool {
83        self.children.is_empty()
84    }
85
86    /// Number of children.
87    pub fn dim(&self) -> usize {
88        self.children.len()
89    }
90}
91
92impl Meta for Node {
93    /// Get node metadata.
94    fn get_meta(&self) -> &Metadata {
95        &self.metadata
96    }
97}
98
99#[derive(Clone, Debug, Default, PartialEq)]
100#[cfg_attr(
101    feature = "serde",
102    derive(serde::Serialize, serde::Deserialize),
103    serde(default)
104)]
105pub struct NodeStoreData {
106    nodes: BTreeMap<Uuid, Node>,
107    roots: BTreeSet<Uuid>,
108    leafs: BTreeSet<Uuid>,
109    aggregate: Aggregate,
110    depth: Option<usize>,
111}
112impl HasNodeStore for NodeStoreData {
113    /// Get a reference to the node store.
114    fn node_store(&self) -> &NodeStoreData {
115        self
116    }
117    /// Get a mutable reference to the node store.
118    fn node_store_mut(&mut self) -> &mut NodeStoreData {
119        self
120    }
121}
122impl NodeStore for NodeStoreData {}
123
124pub trait HasNodeStore {
125    fn node_store(&self) -> &NodeStoreData;
126    fn node_store_mut(&mut self) -> &mut NodeStoreData;
127}
128
129pub trait NodeStore: HasNodeStore {
130    /// The number of nodes in this store.
131    fn nodes_len(&self) -> usize {
132        self.node_store().nodes.len()
133    }
134
135    /// Maximum node depth or height.
136    fn max_node_depth(&mut self) -> usize
137    where
138        Self: Sized,
139    {
140        if let Some(depth) = self.node_store().depth {
141            return depth;
142        }
143        let depth = self.calculate_node_depth();
144        self.node_store_mut().depth = Some(depth);
145        depth
146    }
147
148    /// Whether this node store is empty.
149    fn is_nodes_empty(&self) -> bool {
150        self.nodes_len() == 0
151    }
152
153    /// Check whether this store contains a node with the given node ID.
154    fn has_node(&self, id: &Uuid) -> bool {
155        self.node_store().nodes.contains_key(id)
156    }
157
158    /// Add a single node to this store. Setting 'safe' checks whether this node's
159    /// references exist and detects cyclic hierarchies.
160    fn add_node(&mut self, node: Node, safe: bool) -> Result<Option<Node>, NodeStoreError>
161    where
162        Self: Sized,
163    {
164        if safe {
165            self.check_node(&node)?;
166        }
167        let id = node.id().to_owned();
168        let replaced = self.del_node(&id);
169        self.node_store_mut().aggregate.add(node.get_meta());
170        if node.is_leaf() {
171            self.node_store_mut().leafs.insert(id);
172        }
173        if node.is_root() {
174            self.node_store_mut().roots.insert(id);
175        }
176        if node.parent.is_some() || !node.children.is_empty() {
177            self.node_store_mut().depth = None;
178        }
179        self.node_store_mut().nodes.insert(id, node);
180        Ok(replaced)
181    }
182
183    /// Extend this node store with new nodes. Setting 'safe' checks whether all node
184    /// references exist and detects cyclic hierarchies after adding them to the store
185    /// first.
186    fn extend_nodes(&mut self, nodes: Vec<Node>, safe: bool) -> Result<Vec<Node>, NodeStoreError>
187    where
188        Self: Sized,
189    {
190        let mut replaced = vec![];
191        for node in nodes.clone().into_iter() {
192            if let Some(node) = self.add_node(node, false)? {
193                replaced.push(node);
194            }
195        }
196        if safe {
197            // Handle one-sided relations.
198            for node in nodes.iter() {
199                let node_id = node.id();
200                for child_id in node.children.iter() {
201                    if let Some(child) = self.get_node(child_id) {
202                        if child.parent.as_ref() != Some(node_id) {
203                            self.set_parent(child_id, Some(node_id))?;
204                        }
205                    }
206                }
207                if let Some(parent_id) = node.parent.as_ref() {
208                    if let Some(parent) = self.get_node(parent_id) {
209                        if !parent.children.contains(node_id) {
210                            self.set_parent(node_id, Some(parent_id))?;
211                        }
212                    }
213                }
214            }
215            // Do a check if everything is up to speed now.
216            for node in nodes.iter() {
217                self.check_node(self.get_node_err(node.id())?)?;
218            }
219        }
220        Ok(replaced)
221    }
222
223    /// Check whether a node's references exist and it doesn't partake in cyclic
224    /// hierarchies.
225    fn check_node(&self, node: &Node) -> Result<(), NodeStoreError>
226    where
227        Self: Sized,
228    {
229        if let Some(parent_id) = &node.parent {
230            if !self.has_node(parent_id) {
231                return NodeNotInStoreSnafu {
232                    id: parent_id.to_owned(),
233                }
234                .fail();
235            }
236        }
237        for child_id in node.children.iter() {
238            if !self.has_node(child_id) {
239                return NodeNotInStoreSnafu {
240                    id: child_id.to_owned(),
241                }
242                .fail();
243            }
244        }
245        if node.is_bus && node.parent.is_none() {
246            return BusWithoutParentSnafu {
247                id: node.id().to_owned(),
248            }
249            .fail();
250        }
251        // Use query functions in safe mode to detect any cyclic hierarchies.
252        // Pretty brute-force, but works.
253        self.ascendant_nodes(node.id(), true, true, None, None)
254            .try_fold((), |_, r| r.map(|_| ()))?;
255        self.descendant_nodes(node.id(), true, true, None, None)
256            .try_fold((), |_, r| r.map(|_| ()))?;
257        Ok(())
258    }
259
260    /// Get a reference to a node.
261    fn get_node(&self, id: &Uuid) -> Option<&Node> {
262        self.node_store().nodes.get(id)
263    }
264    /// Get a reference to a node as as result.
265    fn get_node_err(&self, id: &Uuid) -> Result<&Node, NodeStoreError> {
266        match self.node_store().nodes.get(id) {
267            Some(node) => Ok(node),
268            None => Err(NodeStoreError::NodeNotInStore { id: id.to_owned() }),
269        }
270    }
271
272    /// Get a mutable reference to a node.
273    fn get_node_mut(&mut self, node_id: &Uuid) -> Option<&mut Node> {
274        self.node_store_mut().nodes.get_mut(node_id)
275    }
276
277    /// Delete node from this store.
278    fn del_node(&mut self, node_id: &Uuid) -> Option<Node> {
279        let store = self.node_store_mut();
280        let deleted = store.nodes.remove(node_id);
281        if let Some(deleted) = deleted.as_ref() {
282            store.aggregate.subtract(deleted.get_meta());
283            store.roots.remove(node_id);
284            store.leafs.remove(node_id);
285            store.depth = None;
286        }
287        deleted
288    }
289
290    /// Update max node depth.
291    fn calculate_node_depth(&self) -> usize
292    where
293        Self: Sized,
294    {
295        self.leaf_ids()
296            .filter_map(|id| self.node_depth(&id, false, None, None).ok())
297            .max()
298            .unwrap_or(0)
299    }
300
301    /// Get all node IDs in this store.
302    fn all_node_ids(&self) -> impl Iterator<Item = Uuid> {
303        self.node_store().nodes.keys().copied()
304    }
305
306    /// Get all node IDs in this store.
307    fn all_nodes(&self) -> impl Iterator<Item = &Node> {
308        self.node_store().nodes.values()
309    }
310
311    /// Get all root node IDs in this store.
312    fn root_ids(&self) -> impl Iterator<Item = Uuid> {
313        self.node_store().roots.iter().copied()
314    }
315
316    /// Get all root nodes in this store.
317    fn root_nodes(&self) -> impl Iterator<Item = &Node> {
318        self.node_store()
319            .roots
320            .iter()
321            .filter_map(|id| self.get_node(id))
322    }
323
324    /// Get all leaf node IDs in this store.
325    fn leaf_ids(&self) -> impl Iterator<Item = Uuid> {
326        self.node_store().leafs.iter().copied()
327    }
328
329    /// Get all leaf nodes in this store.
330    fn leaf_nodes(&self) -> impl Iterator<Item = &Node> {
331        self.node_store()
332            .leafs
333            .iter()
334            .filter_map(|id| self.get_node(id))
335    }
336
337    /// Set a new parent value for the given child ID. Returns an error if the child
338    /// node does not exist in the store. Setting the parent ID to None removes the
339    /// parent-child relationship.
340    fn set_parent(
341        &mut self,
342        child_id: &Uuid,
343        parent_id: Option<&Uuid>,
344    ) -> Result<(), NodeStoreError> {
345        // Remove child from current parent.
346        if let Some(child) = self.get_node(child_id) {
347            if let Some(current_parent_id) = child.parent {
348                let add_to_leafs = {
349                    if let Some(current_parent) = self.get_node_mut(&current_parent_id) {
350                        current_parent.children.retain(|x| x != child_id);
351                        current_parent.is_leaf()
352                    } else {
353                        false
354                    }
355                };
356                if add_to_leafs {
357                    self.node_store_mut().leafs.insert(current_parent_id);
358                }
359            }
360        } else {
361            return Err(NodeStoreError::NodeNotInStore {
362                id: child_id.to_owned(),
363            });
364        }
365
366        // Set new parent value.
367        if let Some(parent_id) = parent_id {
368            if self.has_node(parent_id) {
369                if let Some(child) = self.get_node_mut(child_id) {
370                    child.parent = Some(parent_id.to_owned());
371                    self.node_store_mut().roots.remove(child_id);
372                }
373                if let Some(parent) = self.get_node_mut(parent_id) {
374                    if !parent.children.contains(child_id) {
375                        parent.children.push(child_id.to_owned())
376                    };
377                    self.node_store_mut().leafs.remove(parent_id);
378                }
379            } else {
380                return Err(NodeStoreError::NodeNotInStore {
381                    id: parent_id.to_owned(),
382                });
383            }
384        } else if let Some(child) = self.get_node_mut(child_id) {
385            child.parent = None;
386            child.is_bus = false;
387            self.node_store_mut().roots.insert(*child_id);
388        }
389        self.node_store_mut().depth = None;
390        Ok(())
391    }
392
393    /// Set the is_bus value of a given node ID.
394    fn set_bus(&mut self, node_id: &Uuid, is_bus: bool) -> Result<(), NodeStoreError> {
395        if let Some(node) = self.get_node_mut(node_id) {
396            if is_bus && node.parent.is_none() {
397                return Err(NodeStoreError::BusWithoutParent {
398                    id: node_id.to_owned(),
399                });
400            }
401            node.is_bus = is_bus;
402        } else {
403            return Err(NodeStoreError::NodeNotInStore {
404                id: node_id.to_owned(),
405            });
406        }
407        Ok(())
408    }
409
410    /// Get the bus node IDs that fall directly under the given parent ID.
411    fn bus_ids(&self, parent_id: &Uuid) -> Result<impl Iterator<Item = Uuid>, NodeStoreError> {
412        Ok(self.bus_nodes(parent_id)?.map(|node| node.id()).copied())
413    }
414
415    /// Get the bus nodes that fall directly under the given parent ID.
416    fn bus_nodes(&self, parent_id: &Uuid) -> Result<impl Iterator<Item = &Node>, NodeStoreError> {
417        self.get_node_err(parent_id).map(|parent| {
418            parent.children.iter().filter_map(|id| {
419                let node = self.get_node(id)?;
420                if node.is_bus { Some(node) } else { None }
421            })
422        })
423    }
424
425    /// Get ascendant node IDs of a given node. Setting `safe` checks for cyclic
426    /// hierarchies along the way. `only_root` only includes the final root node.
427    /// `root_ids` are nodes to consider as (additional) root nodes in this query.
428    /// `height` determines the maximum height at which the ancestor is considered a
429    /// root node.
430    fn ascendant_ids<'a, 'n>(
431        &'n self,
432        node_id: &'a Uuid,
433        safe: bool,
434        only_root: bool,
435        root_ids: Option<&'a BTreeSet<Uuid>>,
436        height: Option<usize>,
437    ) -> impl Iterator<Item = Result<&'n Uuid, NodeStoreError>>
438    where
439        Self: Sized,
440    {
441        AscendantIterator::new(self, node_id, safe, only_root, root_ids, height)
442    }
443
444    /// Get ascendant nodes of a given node. Setting `safe` checks for cyclic
445    /// hierarchies along the way. `only_root` only includes the final root node.
446    /// `root_ids` are nodes to consider as (additional) root nodes in this query.
447    /// `height` determines the maximum height at which the ancestor is considered a
448    /// root node.
449    fn ascendant_nodes<'a, 'n>(
450        &'n self,
451        node_id: &'a Uuid,
452        safe: bool,
453        only_root: bool,
454        root_ids: Option<&'a BTreeSet<Uuid>>,
455        height: Option<usize>,
456    ) -> impl Iterator<Item = Result<&'n Node, NodeStoreError>>
457    where
458        Self: Sized,
459    {
460        self.ascendant_ids(node_id, safe, only_root, root_ids, height)
461            .filter_map(|r| match r {
462                Ok(id) => self.get_node(id).map(Ok),
463                Err(e) => Some(Err(e)),
464            })
465    }
466
467    /// Node depth (i.e. the number of levels that exist above). Setting `safe` checks
468    /// for cyclic hierarchies along the way. `root_ids` are nodes to consider as (additional) root nodes in this query.
469    /// `height` determines the maximum height at which the ancestor is considered a
470    /// root node.
471    fn node_depth(
472        &self,
473        node_id: &Uuid,
474        safe: bool,
475        root_ids: Option<&BTreeSet<Uuid>>,
476        height: Option<usize>,
477    ) -> Result<usize, NodeStoreError>
478    where
479        Self: Sized,
480    {
481        self.ascendant_ids(node_id, safe, false, root_ids, height)
482            .try_fold(0usize, |acc, id| id.map(|_| acc + 1))
483    }
484
485    /// Get the descendant node IDs of a given node. Setting `safe` checks for cyclic
486    /// hierarchies. Setting `only_leaf` only includes only absolute or specified leaf
487    /// nodes in the result. `leaf_ids` restricts the search at the given node IDs,
488    /// disallowing it from going any further. `depth` specifies the maximum depth at
489    /// which nodes are also considered leaf nodes for this search.
490    fn descendant_ids<'a, 'n>(
491        &'n self,
492        node_id: &'a Uuid,
493        safe: bool,
494        only_leaf: bool,
495        leaf_ids: Option<&'a BTreeSet<Uuid>>,
496        depth: Option<usize>,
497    ) -> impl Iterator<Item = Result<&'n Uuid, NodeStoreError>>
498    where
499        Self: Sized,
500    {
501        DescendantIterator::new(self, node_id, safe, only_leaf, leaf_ids, depth)
502    }
503
504    /// Get the descendant nodes of a given node. Setting `safe` checks for cyclic
505    /// hierarchies. Setting `only_leaf` only includes only absolute or specified leaf
506    /// nodes in the result. `leaf_ids` restricts the search at the given node IDs,
507    /// disallowing it from going any further. `depth` specifies the maximum depth with
508    /// respect to the given node ID to search at.
509    fn descendant_nodes<'a, 'n>(
510        &'n self,
511        node_id: &'a Uuid,
512        safe: bool,
513        only_leaf: bool,
514        leaf_ids: Option<&'a BTreeSet<Uuid>>,
515        depth: Option<usize>,
516    ) -> impl Iterator<Item = Result<&'n Node, NodeStoreError>>
517    where
518        Self: Sized,
519    {
520        self.descendant_ids(node_id, safe, only_leaf, leaf_ids, depth)
521            .filter_map(|r| match r {
522                Ok(id) => self.get_node(id).map(Ok),
523                Err(e) => Some(Err(e)),
524            })
525    }
526
527    /// Node height (i.e. the number of levels that exist below). Setting `safe` checks
528    /// for cyclic hierarchies. `leaf_ids` restricts the search at the given node IDs,
529    /// disallowing it from going any further. `depth` specifies the maximum depth with
530    /// respect to the given node ID to search at.
531    fn node_height(
532        &self,
533        node_id: &Uuid,
534        safe: bool,
535        leaf_ids: Option<&BTreeSet<Uuid>>,
536        depth: Option<usize>,
537    ) -> Result<usize, NodeStoreError>
538    where
539        Self: Sized,
540    {
541        let mut iterator = DescendantIterator::new(self, node_id, safe, true, leaf_ids, depth);
542        for result in iterator.by_ref() {
543            result?;
544        }
545        Ok(iterator.max_level)
546    }
547
548    /// Node width in terms of (optionally specified) leaf nodes. Setting `safe` checks
549    /// for cyclic hierarchies. `leaf_ids` restricts the search at the given node IDs,
550    /// disallowing it from going any further. `depth` specifies the maximum depth with
551    /// respect to the given node ID to search at.
552    fn node_width(
553        &self,
554        node_id: &Uuid,
555        safe: bool,
556        leaf_ids: Option<&BTreeSet<Uuid>>,
557        depth: Option<usize>,
558    ) -> Result<usize, NodeStoreError>
559    where
560        Self: Sized,
561    {
562        self.descendant_ids(node_id, safe, true, leaf_ids, depth)
563            .try_fold(0usize, |acc, id| id.map(|_| acc + 1))
564    }
565
566    /// Get the aggregate.
567    fn node_aggregate(&self) -> &Aggregate {
568        &self.node_store().aggregate
569    }
570}
571
572pub struct AscendantIterator<'a, 'n, N>
573where
574    N: NodeStore,
575{
576    // Iterator input data.
577    /// Node store to retrieve data from.
578    nodes: &'n N,
579    /// Whether to check for cyclical references.
580    safe: bool,
581    /// Whether to only return a root node.
582    only_root: bool,
583    /// What nodes are considered root nodes in the search.
584    root_ids: Option<&'a BTreeSet<Uuid>>,
585    /// The maximum number of levels above this level to include.
586    height: Option<usize>,
587
588    // Iterator state.
589    /// Last retrieved node ID.
590    node_id: Uuid,
591    /// Seen set of IDs.
592    seen: BTreeSet<Uuid>,
593    /// Whether to stop after this iteration.
594    stop: bool,
595    /// Current level of height.
596    level: usize,
597    /// Error state, next iteration returns None.
598    error: bool,
599}
600impl<'a, 'n, N> AscendantIterator<'a, 'n, N>
601where
602    N: NodeStore,
603{
604    pub fn new(
605        nodes: &'n N,
606        node_id: &'a Uuid,
607        safe: bool,
608        only_root: bool,
609        root_ids: Option<&'a BTreeSet<Uuid>>,
610        height: Option<usize>,
611    ) -> Self {
612        Self {
613            nodes,
614            safe,
615            only_root,
616            root_ids,
617            height,
618            node_id: *node_id,
619            seen: BTreeSet::default(),
620            stop: false,
621            level: 0,
622            error: false,
623        }
624    }
625}
626impl<'n, N> Iterator for AscendantIterator<'_, 'n, N>
627where
628    N: NodeStore,
629{
630    type Item = Result<&'n Uuid, NodeStoreError>;
631
632    fn next(&mut self) -> Option<Self::Item> {
633        if self.stop || Some(self.level) == self.height || self.error {
634            return None;
635        }
636
637        // Get the parent of the current node ID under investigation.
638        let parent_id = self.nodes.get_node(&self.node_id)?.parent.as_ref()?;
639
640        // Safety cycle check if enabled.
641        if self.safe && !self.seen.insert(*parent_id) {
642            self.error = true;
643            return Some(Err(NodeStoreError::CyclicAscendants { id: self.node_id }));
644        }
645
646        // The parent node under investigation.
647        let parent: &'n Node = self.nodes.get_node(parent_id)?;
648
649        // Bookkeeping for each iteration.
650        self.level += 1;
651
652        // If we have an absolute root or node we consider to be root, stop.
653        if parent.is_root()
654            || self.height.map(|h| h == 1).unwrap_or(false)
655            || self
656                .root_ids
657                .map(|x| x.contains(parent_id))
658                .unwrap_or(false)
659        {
660            self.stop = true;
661            Some(Ok(parent_id))
662        } else {
663            // Set the node ID under investigation to the current parent.
664            self.node_id = *parent_id;
665
666            // We have a non-root node, check if we should only return roots and recurse
667            // immediately.
668            if self.only_root {
669                self.next()
670            } else {
671                Some(Ok(parent_id))
672            }
673        }
674    }
675}
676
677pub struct DescendantIterator<'a, 'n, N>
678where
679    N: NodeStore,
680{
681    // Iterator input data.
682    /// Node store to retrieve data from.
683    nodes: &'n N,
684    /// Whether to check for cyclical references.
685    safe: bool,
686    /// Whether to only return a leaf nodes.
687    only_leaf: bool,
688    /// What nodes are considered leaf nodes in the search.
689    leaf_ids: Option<&'a BTreeSet<Uuid>>,
690    /// The maximum number of levels beneath the starting node to include.
691    depth: Option<usize>,
692
693    // Iterator state.
694    /// Current descendant candidates.
695    descendants: Vec<Vec<Uuid>>,
696    /// Seen set of IDs.
697    seen: BTreeSet<Uuid>,
698    /// Current level of depth we're looping over.
699    level: usize,
700    /// Maximum depth we've seen.
701    max_level: usize,
702    /// Error state, next iteration returns None.
703    stop: bool,
704}
705impl<'a, 'n, N> DescendantIterator<'a, 'n, N>
706where
707    N: NodeStore,
708{
709    pub fn new(
710        nodes: &'n N,
711        node_id: &'a Uuid,
712        safe: bool,
713        only_leaf: bool,
714        leaf_ids: Option<&'a BTreeSet<Uuid>>,
715        depth: Option<usize>,
716    ) -> Self {
717        let (stop, level, descendants) = if depth.is_none() || depth != Some(0) {
718            let mut descendants = nodes
719                .get_node(node_id)
720                .map(|n| n.children.clone())
721                .unwrap_or_default();
722            if descendants.is_empty() {
723                (true, 0, vec![])
724            } else {
725                descendants.reverse();
726                (false, 1, descendants)
727            }
728        } else {
729            (true, 0, vec![])
730        };
731        Self {
732            nodes,
733            safe,
734            only_leaf,
735            leaf_ids,
736            depth,
737            descendants: vec![descendants],
738            seen: BTreeSet::from([*node_id]),
739            level,
740            max_level: level,
741            stop,
742        }
743    }
744}
745impl<'n, N> Iterator for DescendantIterator<'_, 'n, N>
746where
747    N: NodeStore,
748{
749    type Item = Result<&'n Uuid, NodeStoreError>;
750
751    fn next(&mut self) -> Option<Self::Item> {
752        if self.stop {
753            return None;
754        }
755
756        // Get the next node ID
757        while self
758            .descendants
759            .last()
760            .map(|ds| ds.is_empty())
761            .unwrap_or_default()
762        {
763            self.descendants.pop();
764            self.level -= 1;
765        }
766        let node_id = self.descendants.last_mut().and_then(|ds| ds.pop())?;
767
768        // Do a safety cycle check if enabled. Get the node right after.
769        if self.safe && !self.seen.insert(node_id) {
770            self.stop = true;
771            return Some(Err(NodeStoreError::CyclicDescendants { id: node_id }));
772        }
773        let node = self.nodes.get_node(&node_id)?;
774
775        // If it is an absolute leaf or a considered leaf node or at the depth, return it.
776        if node.is_leaf()
777            || self
778                .leaf_ids
779                .map(|ids| ids.contains(&node_id))
780                .unwrap_or(false)
781            || self.depth.map(|d| d == self.level).unwrap_or(false)
782        {
783            Some(Ok(node.id()))
784        } else {
785            // We have a non-leaf node, so go to try and return the next one if we want only leafs.
786            // Append this node's children to the list in reversed order, so they are attempted first.
787            if self.depth.is_none() || self.level < self.depth.unwrap_or_default() {
788                let mut children = node.children.clone();
789                children.reverse();
790                self.descendants.push(children);
791                self.level += 1;
792                self.max_level = self.max_level.max(self.level);
793            }
794            if self.only_leaf {
795                self.next()
796            } else {
797                Some(Ok(node.id()))
798            }
799        }
800    }
801}
ratio_graph/node.rs

ratio_graph/
node.rs
