devscout_rs/query/
seq.rs

1use std::collections::{HashMap, HashSet};
2
3// ============================================================================
4// Order-preserving scratch structures (private -- see module header).
5// ============================================================================
6
7/// Insertion-order-preserving set: `insert` is a no-op when the value is
8/// already present (first insertion wins the position). Public because it
9/// appears in [`ImpactWalkResult`]'s public fields.
10#[derive(Debug, Clone)]
11pub struct SeqSet<T: Eq + std::hash::Hash + Clone> {
12    order: Vec<T>,
13    seen: HashSet<T>,
14}
15
16impl<T: Eq + std::hash::Hash + Clone> SeqSet<T> {
17    /// Creates an empty insertion-ordered set.
18    pub fn new() -> Self {
19        Self {
20            order: Vec::new(),
21            seen: HashSet::new(),
22        }
23    }
24    /// Inserts `value` if it is not already present.
25    pub fn insert(&mut self, value: T) {
26        if self.seen.insert(value.clone()) {
27            self.order.push(value);
28        }
29    }
30    /// Returns whether `value` is present.
31    pub fn contains(&self, value: &T) -> bool {
32        self.seen.contains(value)
33    }
34    /// Returns the number of values.
35    pub fn len(&self) -> usize {
36        self.order.len()
37    }
38    /// Iterates over values in insertion order.
39    pub fn iter(&self) -> std::slice::Iter<'_, T> {
40        self.order.iter()
41    }
42    /// Consumes the set and returns its values in insertion order.
43    pub fn into_vec(self) -> Vec<T> {
44        self.order
45    }
46}
47
48impl<T: Eq + std::hash::Hash + Clone> Default for SeqSet<T> {
49    fn default() -> Self {
50        SeqSet::new()
51    }
52}
53
54/// Insertion-order-preserving `String`-keyed map with a mutable
55/// get-or-insert-default accessor. Same shape as `graph::OrderedMap`, kept as
56/// a separate small type here because that one exposes no `get_mut`/entry-style
57/// API. Public for the same reason as [`SeqSet`] -- appears in
58/// [`ImpactWalkResult::visited`].
59#[derive(Debug, Clone)]
60pub struct SeqMap<V> {
61    entries: Vec<(String, V)>,
62    index: HashMap<String, usize>,
63}
64
65impl<V> SeqMap<V> {
66    /// Creates an empty insertion-ordered map.
67    pub fn new() -> Self {
68        Self {
69            entries: Vec::new(),
70            index: HashMap::new(),
71        }
72    }
73    /// Returns whether `key` is present.
74    pub fn contains_key(&self, key: &str) -> bool {
75        self.index.contains_key(key)
76    }
77    /// Inserts or replaces the value for `key` while preserving key order.
78    pub fn insert(&mut self, key: String, value: V) {
79        match self.index.get(&key) {
80            Some(&i) => self.entries[i].1 = value,
81            None => {
82                self.index.insert(key.clone(), self.entries.len());
83                self.entries.push((key, value));
84            }
85        }
86    }
87    /// Iterates over entries in insertion order.
88    pub fn iter(&self) -> impl Iterator<Item = (&String, &V)> {
89        self.entries.iter().map(|(k, v)| (k, v))
90    }
91    /// Iterates over keys in insertion order.
92    pub fn keys(&self) -> impl Iterator<Item = &String> {
93        self.entries.iter().map(|(k, _)| k)
94    }
95}
96
97impl<V: Default> SeqMap<V> {
98    pub(super) fn get_or_insert_default(&mut self, key: &str) -> &mut V {
99        if let Some(&i) = self.index.get(key) {
100            return &mut self.entries[i].1;
101        }
102        self.index.insert(key.to_string(), self.entries.len());
103        self.entries.push((key.to_string(), V::default()));
104        let last = self.entries.len() - 1;
105        &mut self.entries[last].1
106    }
107}
108
109pub(super) fn push_ordered_unique(map: &mut HashMap<String, Vec<usize>>, key: &str, value: usize) {
110    let v = map.entry(key.to_string()).or_default();
111    if !v.contains(&value) {
112        v.push(value);
113    }
114}
devscout_rs/query/seq.rs

devscout_rs/query/
seq.rs
