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                        && child.parent.as_ref() != Some(node_id)
203                    {
204                        self.set_parent(child_id, Some(node_id))?;
205                    }
206                }
207                if let Some(parent_id) = node.parent.as_ref()
208                    && let Some(parent) = self.get_node(parent_id)
209                    && !parent.children.contains(node_id)
210                {
211                    self.set_parent(node_id, Some(parent_id))?;
212                }
213            }
214            // Do a check if everything is up to speed now.
215            for node in nodes.iter() {
216                self.check_node(self.get_node_err(node.id())?)?;
217            }
218        }
219        Ok(replaced)
220    }
221
222    /// Check whether a node's references exist and it doesn't partake in cyclic
223    /// hierarchies.
224    fn check_node(&self, node: &Node) -> Result<(), NodeStoreError>
225    where
226        Self: Sized,
227    {
228        if let Some(parent_id) = &node.parent
229            && !self.has_node(parent_id)
230        {
231            return NodeNotInStoreSnafu {
232                id: parent_id.to_owned(),
233            }
234            .fail();
235        }
236        for child_id in node.children.iter() {
237            if !self.has_node(child_id) {
238                return NodeNotInStoreSnafu {
239                    id: child_id.to_owned(),
240                }
241                .fail();
242            }
243        }
244        if node.is_bus && node.parent.is_none() {
245            return BusWithoutParentSnafu {
246                id: node.id().to_owned(),
247            }
248            .fail();
249        }
250        // Use query functions in safe mode to detect any cyclic hierarchies.
251        // Pretty brute-force, but works.
252        self.ascendant_nodes(node.id(), true, true, None, None)
253            .try_fold((), |_, r| r.map(|_| ()))?;
254        self.descendant_nodes(node.id(), true, true, None, None)
255            .try_fold((), |_, r| r.map(|_| ()))?;
256        Ok(())
257    }
258
259    /// Get a reference to a node.
260    fn get_node(&self, id: &Uuid) -> Option<&Node> {
261        self.node_store().nodes.get(id)
262    }
263    /// Get a reference to a node as as result.
264    fn get_node_err(&self, id: &Uuid) -> Result<&Node, NodeStoreError> {
265        match self.node_store().nodes.get(id) {
266            Some(node) => Ok(node),
267            None => Err(NodeStoreError::NodeNotInStore { id: id.to_owned() }),
268        }
269    }
270
271    /// Get a mutable reference to a node.
272    fn get_node_mut(&mut self, node_id: &Uuid) -> Option<&mut Node> {
273        self.node_store_mut().nodes.get_mut(node_id)
274    }
275
276    /// Delete node from this store.
277    fn del_node(&mut self, node_id: &Uuid) -> Option<Node> {
278        let store = self.node_store_mut();
279        let deleted = store.nodes.remove(node_id);
280        if let Some(deleted) = deleted.as_ref() {
281            store.aggregate.subtract(deleted.get_meta());
282            store.roots.remove(node_id);
283            store.leafs.remove(node_id);
284            store.depth = None;
285        }
286        deleted
287    }
288
289    /// Update max node depth.
290    fn calculate_node_depth(&self) -> usize
291    where
292        Self: Sized,
293    {
294        self.leaf_ids()
295            .filter_map(|id| self.node_depth(&id, false, None, None).ok())
296            .max()
297            .unwrap_or(0)
298    }
299
300    /// Get all node IDs in this store.
301    fn all_node_ids(&self) -> impl Iterator<Item = Uuid> {
302        self.node_store().nodes.keys().copied()
303    }
304
305    /// Get all node IDs in this store.
306    fn all_nodes(&self) -> impl Iterator<Item = &Node> {
307        self.node_store().nodes.values()
308    }
309
310    /// Get all root node IDs in this store.
311    fn root_ids(&self) -> impl Iterator<Item = Uuid> {
312        self.node_store().roots.iter().copied()
313    }
314
315    /// Get all root nodes in this store.
316    fn root_nodes(&self) -> impl Iterator<Item = &Node> {
317        self.node_store()
318            .roots
319            .iter()
320            .filter_map(|id| self.get_node(id))
321    }
322
323    /// Get all leaf node IDs in this store.
324    fn leaf_ids(&self) -> impl Iterator<Item = Uuid> {
325        self.node_store().leafs.iter().copied()
326    }
327
328    /// Get all leaf nodes in this store.
329    fn leaf_nodes(&self) -> impl Iterator<Item = &Node> {
330        self.node_store()
331            .leafs
332            .iter()
333            .filter_map(|id| self.get_node(id))
334    }
335
336    /// Set a new parent value for the given child ID. Returns an error if the child
337    /// node does not exist in the store. Setting the parent ID to None removes the
338    /// parent-child relationship.
339    fn set_parent(
340        &mut self,
341        child_id: &Uuid,
342        parent_id: Option<&Uuid>,
343    ) -> Result<(), NodeStoreError> {
344        // Remove child from current parent.
345        if let Some(child) = self.get_node(child_id) {
346            if let Some(current_parent_id) = child.parent {
347                let add_to_leafs = {
348                    if let Some(current_parent) = self.get_node_mut(&current_parent_id) {
349                        current_parent.children.retain(|x| x != child_id);
350                        current_parent.is_leaf()
351                    } else {
352                        false
353                    }
354                };
355                if add_to_leafs {
356                    self.node_store_mut().leafs.insert(current_parent_id);
357                }
358            }
359        } else {
360            return Err(NodeStoreError::NodeNotInStore {
361                id: child_id.to_owned(),
362            });
363        }
364
365        // Set new parent value.
366        if let Some(parent_id) = parent_id {
367            if self.has_node(parent_id) {
368                if let Some(child) = self.get_node_mut(child_id) {
369                    child.parent = Some(parent_id.to_owned());
370                    self.node_store_mut().roots.remove(child_id);
371                }
372                if let Some(parent) = self.get_node_mut(parent_id) {
373                    if !parent.children.contains(child_id) {
374                        parent.children.push(child_id.to_owned())
375                    };
376                    self.node_store_mut().leafs.remove(parent_id);
377                }
378            } else {
379                return Err(NodeStoreError::NodeNotInStore {
380                    id: parent_id.to_owned(),
381                });
382            }
383        } else if let Some(child) = self.get_node_mut(child_id) {
384            child.parent = None;
385            child.is_bus = false;
386            self.node_store_mut().roots.insert(*child_id);
387        }
388        self.node_store_mut().depth = None;
389        Ok(())
390    }
391
392    /// Set the is_bus value of a given node ID.
393    fn set_bus(&mut self, node_id: &Uuid, is_bus: bool) -> Result<(), NodeStoreError> {
394        if let Some(node) = self.get_node_mut(node_id) {
395            if is_bus && node.parent.is_none() {
396                return Err(NodeStoreError::BusWithoutParent {
397                    id: node_id.to_owned(),
398                });
399            }
400            node.is_bus = is_bus;
401        } else {
402            return Err(NodeStoreError::NodeNotInStore {
403                id: node_id.to_owned(),
404            });
405        }
406        Ok(())
407    }
408
409    /// Get the bus node IDs that fall directly under the given parent ID.
410    fn bus_ids(&self, parent_id: &Uuid) -> Result<impl Iterator<Item = Uuid>, NodeStoreError> {
411        Ok(self.bus_nodes(parent_id)?.map(|node| node.id()).copied())
412    }
413
414    /// Get the bus nodes that fall directly under the given parent ID.
415    fn bus_nodes(&self, parent_id: &Uuid) -> Result<impl Iterator<Item = &Node>, NodeStoreError> {
416        self.get_node_err(parent_id).map(|parent| {
417            parent.children.iter().filter_map(|id| {
418                let node = self.get_node(id)?;
419                if node.is_bus { Some(node) } else { None }
420            })
421        })
422    }
423
424    /// Get ascendant node IDs of a given node. Setting `safe` checks for cyclic
425    /// hierarchies along the way. `only_root` only includes the final root node.
426    /// `root_ids` are nodes to consider as (additional) root nodes in this query.
427    /// `height` determines the maximum height at which the ancestor is considered a
428    /// root node.
429    fn ascendant_ids<'a, 'n>(
430        &'n self,
431        node_id: &'a Uuid,
432        safe: bool,
433        only_root: bool,
434        root_ids: Option<&'a BTreeSet<Uuid>>,
435        height: Option<usize>,
436    ) -> impl Iterator<Item = Result<&'n Uuid, NodeStoreError>>
437    where
438        Self: Sized,
439    {
440        AscendantIterator::new(self, node_id, safe, only_root, root_ids, height)
441    }
442
443    /// Get ascendant nodes of a given node. Setting `safe` checks for cyclic
444    /// hierarchies along the way. `only_root` only includes the final root node.
445    /// `root_ids` are nodes to consider as (additional) root nodes in this query.
446    /// `height` determines the maximum height at which the ancestor is considered a
447    /// root node.
448    fn ascendant_nodes<'a, 'n>(
449        &'n self,
450        node_id: &'a Uuid,
451        safe: bool,
452        only_root: bool,
453        root_ids: Option<&'a BTreeSet<Uuid>>,
454        height: Option<usize>,
455    ) -> impl Iterator<Item = Result<&'n Node, NodeStoreError>>
456    where
457        Self: Sized,
458    {
459        self.ascendant_ids(node_id, safe, only_root, root_ids, height)
460            .filter_map(|r| match r {
461                Ok(id) => self.get_node(id).map(Ok),
462                Err(e) => Some(Err(e)),
463            })
464    }
465
466    /// Node depth (i.e. the number of levels that exist above). Setting `safe` checks
467    /// for cyclic hierarchies along the way. `root_ids` are nodes to consider as (additional) root nodes in this query.
468    /// `height` determines the maximum height at which the ancestor is considered a
469    /// root node.
470    fn node_depth(
471        &self,
472        node_id: &Uuid,
473        safe: bool,
474        root_ids: Option<&BTreeSet<Uuid>>,
475        height: Option<usize>,
476    ) -> Result<usize, NodeStoreError>
477    where
478        Self: Sized,
479    {
480        self.ascendant_ids(node_id, safe, false, root_ids, height)
481            .try_fold(0usize, |acc, id| id.map(|_| acc + 1))
482    }
483
484    /// Get the descendant node IDs of a given node. Setting `safe` checks for cyclic
485    /// hierarchies. Setting `only_leaf` only includes only absolute or specified leaf
486    /// nodes in the result. `leaf_ids` restricts the search at the given node IDs,
487    /// disallowing it from going any further. `depth` specifies the maximum depth at
488    /// which nodes are also considered leaf nodes for this search.
489    fn descendant_ids<'a, 'n>(
490        &'n self,
491        node_id: &'a Uuid,
492        safe: bool,
493        only_leaf: bool,
494        leaf_ids: Option<&'a BTreeSet<Uuid>>,
495        depth: Option<usize>,
496    ) -> impl Iterator<Item = Result<&'n Uuid, NodeStoreError>>
497    where
498        Self: Sized,
499    {
500        DescendantIterator::new(self, node_id, safe, only_leaf, leaf_ids, depth)
501    }
502
503    /// Get the descendant nodes of a given node. Setting `safe` checks for cyclic
504    /// hierarchies. Setting `only_leaf` only includes only absolute or specified leaf
505    /// nodes in the result. `leaf_ids` restricts the search at the given node IDs,
506    /// disallowing it from going any further. `depth` specifies the maximum depth with
507    /// respect to the given node ID to search at.
508    fn descendant_nodes<'a, 'n>(
509        &'n self,
510        node_id: &'a Uuid,
511        safe: bool,
512        only_leaf: bool,
513        leaf_ids: Option<&'a BTreeSet<Uuid>>,
514        depth: Option<usize>,
515    ) -> impl Iterator<Item = Result<&'n Node, NodeStoreError>>
516    where
517        Self: Sized,
518    {
519        self.descendant_ids(node_id, safe, only_leaf, leaf_ids, depth)
520            .filter_map(|r| match r {
521                Ok(id) => self.get_node(id).map(Ok),
522                Err(e) => Some(Err(e)),
523            })
524    }
525
526    /// Node height (i.e. the number of levels that exist below). Setting `safe` checks
527    /// for cyclic hierarchies. `leaf_ids` restricts the search at the given node IDs,
528    /// disallowing it from going any further. `depth` specifies the maximum depth with
529    /// respect to the given node ID to search at.
530    fn node_height(
531        &self,
532        node_id: &Uuid,
533        safe: bool,
534        leaf_ids: Option<&BTreeSet<Uuid>>,
535        depth: Option<usize>,
536    ) -> Result<usize, NodeStoreError>
537    where
538        Self: Sized,
539    {
540        let mut iterator = DescendantIterator::new(self, node_id, safe, true, leaf_ids, depth);
541        for result in iterator.by_ref() {
542            result?;
543        }
544        Ok(iterator.max_level)
545    }
546
547    /// Node width in terms of (optionally specified) leaf nodes. Setting `safe` checks
548    /// for cyclic hierarchies. `leaf_ids` restricts the search at the given node IDs,
549    /// disallowing it from going any further. `depth` specifies the maximum depth with
550    /// respect to the given node ID to search at.
551    fn node_width(
552        &self,
553        node_id: &Uuid,
554        safe: bool,
555        leaf_ids: Option<&BTreeSet<Uuid>>,
556        depth: Option<usize>,
557    ) -> Result<usize, NodeStoreError>
558    where
559        Self: Sized,
560    {
561        self.descendant_ids(node_id, safe, true, leaf_ids, depth)
562            .try_fold(0usize, |acc, id| id.map(|_| acc + 1))
563    }
564
565    /// Get the aggregate.
566    fn node_aggregate(&self) -> &Aggregate {
567        &self.node_store().aggregate
568    }
569}
570
571pub struct AscendantIterator<'a, 'n, N>
572where
573    N: NodeStore,
574{
575    // Iterator input data.
576    /// Node store to retrieve data from.
577    nodes: &'n N,
578    /// Whether to check for cyclical references.
579    safe: bool,
580    /// Whether to only return a root node.
581    only_root: bool,
582    /// What nodes are considered root nodes in the search.
583    root_ids: Option<&'a BTreeSet<Uuid>>,
584    /// The maximum number of levels above this level to include.
585    height: Option<usize>,
586
587    // Iterator state.
588    /// Last retrieved node ID.
589    node_id: Uuid,
590    /// Seen set of IDs.
591    seen: BTreeSet<Uuid>,
592    /// Whether to stop after this iteration.
593    stop: bool,
594    /// Current level of height.
595    level: usize,
596    /// Error state, next iteration returns None.
597    error: bool,
598}
599impl<'a, 'n, N> AscendantIterator<'a, 'n, N>
600where
601    N: NodeStore,
602{
603    pub fn new(
604        nodes: &'n N,
605        node_id: &'a Uuid,
606        safe: bool,
607        only_root: bool,
608        root_ids: Option<&'a BTreeSet<Uuid>>,
609        height: Option<usize>,
610    ) -> Self {
611        Self {
612            nodes,
613            safe,
614            only_root,
615            root_ids,
616            height,
617            node_id: *node_id,
618            seen: BTreeSet::default(),
619            stop: false,
620            level: 0,
621            error: false,
622        }
623    }
624}
625impl<'n, N> Iterator for AscendantIterator<'_, 'n, N>
626where
627    N: NodeStore,
628{
629    type Item = Result<&'n Uuid, NodeStoreError>;
630
631    fn next(&mut self) -> Option<Self::Item> {
632        if self.stop || Some(self.level) == self.height || self.error {
633            return None;
634        }
635
636        // Get the parent of the current node ID under investigation.
637        let parent_id = self.nodes.get_node(&self.node_id)?.parent.as_ref()?;
638
639        // Safety cycle check if enabled.
640        if self.safe && !self.seen.insert(*parent_id) {
641            self.error = true;
642            return Some(Err(NodeStoreError::CyclicAscendants { id: self.node_id }));
643        }
644
645        // The parent node under investigation.
646        let parent: &'n Node = self.nodes.get_node(parent_id)?;
647
648        // Bookkeeping for each iteration.
649        self.level += 1;
650
651        // If we have an absolute root or node we consider to be root, stop.
652        if parent.is_root()
653            || self.height.map(|h| h == 1).unwrap_or(false)
654            || self
655                .root_ids
656                .map(|x| x.contains(parent_id))
657                .unwrap_or(false)
658        {
659            self.stop = true;
660            Some(Ok(parent_id))
661        } else {
662            // Set the node ID under investigation to the current parent.
663            self.node_id = *parent_id;
664
665            // We have a non-root node, check if we should only return roots and recurse
666            // immediately.
667            if self.only_root {
668                self.next()
669            } else {
670                Some(Ok(parent_id))
671            }
672        }
673    }
674}
675
676pub struct DescendantIterator<'a, 'n, N>
677where
678    N: NodeStore,
679{
680    // Iterator input data.
681    /// Node store to retrieve data from.
682    nodes: &'n N,
683    /// Whether to check for cyclical references.
684    safe: bool,
685    /// Whether to only return a leaf nodes.
686    only_leaf: bool,
687    /// What nodes are considered leaf nodes in the search.
688    leaf_ids: Option<&'a BTreeSet<Uuid>>,
689    /// The maximum number of levels beneath the starting node to include.
690    depth: Option<usize>,
691
692    // Iterator state.
693    /// Current descendant candidates.
694    descendants: Vec<Vec<Uuid>>,
695    /// Seen set of IDs.
696    seen: BTreeSet<Uuid>,
697    /// Current level of depth we're looping over.
698    level: usize,
699    /// Maximum depth we've seen.
700    max_level: usize,
701    /// Error state, next iteration returns None.
702    stop: bool,
703}
704impl<'a, 'n, N> DescendantIterator<'a, 'n, N>
705where
706    N: NodeStore,
707{
708    pub fn new(
709        nodes: &'n N,
710        node_id: &'a Uuid,
711        safe: bool,
712        only_leaf: bool,
713        leaf_ids: Option<&'a BTreeSet<Uuid>>,
714        depth: Option<usize>,
715    ) -> Self {
716        let (stop, level, descendants) = if depth.is_none() || depth != Some(0) {
717            let mut descendants = nodes
718                .get_node(node_id)
719                .map(|n| n.children.clone())
720                .unwrap_or_default();
721            if descendants.is_empty() {
722                (true, 0, vec![])
723            } else {
724                descendants.reverse();
725                (false, 1, descendants)
726            }
727        } else {
728            (true, 0, vec![])
729        };
730        Self {
731            nodes,
732            safe,
733            only_leaf,
734            leaf_ids,
735            depth,
736            descendants: vec![descendants],
737            seen: BTreeSet::from([*node_id]),
738            level,
739            max_level: level,
740            stop,
741        }
742    }
743}
744impl<'n, N> Iterator for DescendantIterator<'_, 'n, N>
745where
746    N: NodeStore,
747{
748    type Item = Result<&'n Uuid, NodeStoreError>;
749
750    fn next(&mut self) -> Option<Self::Item> {
751        if self.stop {
752            return None;
753        }
754
755        // Get the next node ID
756        while self
757            .descendants
758            .last()
759            .map(|ds| ds.is_empty())
760            .unwrap_or_default()
761        {
762            self.descendants.pop();
763            self.level -= 1;
764        }
765        let node_id = self.descendants.last_mut().and_then(|ds| ds.pop())?;
766
767        // Do a safety cycle check if enabled. Get the node right after.
768        if self.safe && !self.seen.insert(node_id) {
769            self.stop = true;
770            return Some(Err(NodeStoreError::CyclicDescendants { id: node_id }));
771        }
772        let node = self.nodes.get_node(&node_id)?;
773
774        // If it is an absolute leaf or a considered leaf node or at the depth, return it.
775        if node.is_leaf()
776            || self
777                .leaf_ids
778                .map(|ids| ids.contains(&node_id))
779                .unwrap_or(false)
780            || self.depth.map(|d| d == self.level).unwrap_or(false)
781        {
782            Some(Ok(node.id()))
783        } else {
784            // We have a non-leaf node, so go to try and return the next one if we want only leafs.
785            // Append this node's children to the list in reversed order, so they are attempted first.
786            if self.depth.is_none() || self.level < self.depth.unwrap_or_default() {
787                let mut children = node.children.clone();
788                children.reverse();
789                self.descendants.push(children);
790                self.level += 1;
791                self.max_level = self.max_level.max(self.level);
792            }
793            if self.only_leaf {
794                self.next()
795            } else {
796                Some(Ok(node.id()))
797            }
798        }
799    }
800}
ratio_graph/node.rs

ratio_graph/
node.rs
