1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

use crate::collections::HashMap;
use crate::Component;
use std::mem;

#[derive(Default, Debug)]
struct Node {
    /// If this is a terminating node that can be imported or not..
    term: bool,
    /// The children of this node.
    children: HashMap<Component, Node>,
}

/// A tree of names.
#[derive(Default, Debug)]
pub struct Names {
    root: Node,
}

impl Names {
    /// Construct a collection of names.
    pub fn new() -> Self {
        Self::default()
    }

    /// Insert the given item as an import.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use runestick::Names;
    ///
    /// let mut names = Names::new();
    /// assert!(!names.contains(&["test"]));
    /// assert!(names.insert(&["test"]));
    /// assert!(names.contains(&["test"]));
    /// assert!(!names.insert(&["test"]));
    /// ```
    pub fn insert<I>(&mut self, iter: I) -> bool
    where
        I: IntoIterator,
        I::Item: Into<Component>,
    {
        let mut current = &mut self.root;

        for c in iter {
            current = current.children.entry(c.into()).or_default();
        }

        !mem::replace(&mut current.term, true)
    }

    /// Test if the given import exists.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use runestick::Names;
    ///
    /// let mut names = Names::new();
    /// assert!(!names.contains(&["test"]));
    /// assert!(names.insert(&["test"]));
    /// assert!(names.contains(&["test"]));
    /// assert!(!names.insert(&["test"]));
    /// ```
    pub fn contains<I>(&self, iter: I) -> bool
    where
        I: IntoIterator,
        I::Item: Into<Component>,
    {
        self.find_node(iter).map(|n| n.term).unwrap_or_default()
    }

    /// Test if we contain the given prefix.
    pub fn contains_prefix<I>(&self, iter: I) -> bool
    where
        I: IntoIterator,
        I::Item: Into<Component>,
    {
        self.find_node(iter).is_some()
    }

    /// Iterate over all known components immediately under the specified `iter`
    /// path.
    pub fn iter_components<I>(&self, iter: I) -> impl Iterator<Item = &'_ Component>
    where
        I: IntoIterator,
        I::Item: Into<Component>,
    {
        let mut current = &self.root;

        for c in iter {
            let c = c.into();

            current = match current.children.get(&c) {
                Some(node) => node,
                None => return IterComponents(None),
            };
        }

        return IterComponents(Some(current.children.keys()));

        struct IterComponents<I>(Option<I>);

        impl<'a, I> Iterator for IterComponents<I>
        where
            I: Iterator<Item = &'a Component>,
        {
            type Item = &'a Component;

            fn next(&mut self) -> Option<Self::Item> {
                let mut iter = self.0.take()?;
                let next = iter.next()?;
                self.0 = Some(iter);
                Some(next)
            }
        }
    }

    /// Find the node corresponding to the given path.
    fn find_node<I>(&self, iter: I) -> Option<&Node>
    where
        I: IntoIterator,
        I::Item: Into<Component>,
    {
        let mut current = &self.root;

        for c in iter {
            let c = c.into();
            current = current.children.get(&c)?;
        }

        Some(current)
    }
}