tensor4all_tcicore/
indexset.rs

1//! Index set for managing ordered collections with bidirectional lookup.
2//!
3//! [`IndexSet`] maintains insertion order while providing O(1) lookup in both
4//! directions: from positional index to value and from value to positional
5//! index. Duplicate insertions are silently ignored.
6//!
7//! This is used throughout the TCI infrastructure for managing pivot indices
8//! in matrix cross interpolation algorithms.
9
10use std::collections::HashMap;
11use std::hash::Hash;
12
13/// A bidirectional index set for efficient lookup
14///
15/// Provides O(1) lookup from integer index to value and from value to integer index.
16///
17/// # Examples
18///
19/// ```
20/// use tensor4all_tcicore::IndexSet;
21///
22/// let mut set: IndexSet<String> = IndexSet::new();
23/// set.push("alpha".to_string());
24/// set.push("beta".to_string());
25/// set.push("alpha".to_string()); // duplicate, ignored
26///
27/// assert_eq!(set.len(), 2);
28/// assert_eq!(set.get(0), Some(&"alpha".to_string()));
29/// assert_eq!(set.pos(&"beta".to_string()), Some(1));
30/// assert!(set.contains(&"alpha".to_string()));
31/// assert!(!set.contains(&"gamma".to_string()));
32/// ```
33#[derive(Debug, Clone)]
34pub struct IndexSet<T: Clone + Eq + Hash> {
35    /// Map from value to integer index
36    to_int: HashMap<T, usize>,
37    /// Map from integer index to value
38    from_int: Vec<T>,
39}
40
41impl<T: Clone + Eq + Hash> Default for IndexSet<T> {
42    fn default() -> Self {
43        Self::new()
44    }
45}
46
47impl<T: Clone + Eq + Hash> IndexSet<T> {
48    /// Create an empty index set.
49    ///
50    /// # Examples
51    ///
52    /// ```
53    /// use tensor4all_tcicore::IndexSet;
54    ///
55    /// let set: IndexSet<usize> = IndexSet::new();
56    /// assert!(set.is_empty());
57    /// assert_eq!(set.len(), 0);
58    /// ```
59    pub fn new() -> Self {
60        Self {
61            to_int: HashMap::new(),
62            from_int: Vec::new(),
63        }
64    }
65
66    /// Create an index set from a vector
67    ///
68    /// Duplicate values are removed, keeping the first occurrence.
69    ///
70    /// # Examples
71    ///
72    /// ```
73    /// use tensor4all_tcicore::IndexSet;
74    ///
75    /// let set = IndexSet::from_vec(vec![10usize, 20, 10, 30]);
76    /// assert_eq!(set.len(), 3);
77    /// assert_eq!(set[0], 10);
78    /// assert_eq!(set[1], 20);
79    /// assert_eq!(set[2], 30);
80    /// ```
81    pub fn from_vec(values: Vec<T>) -> Self {
82        let mut to_int = HashMap::new();
83        let mut from_int = Vec::new();
84        for value in values {
85            if !to_int.contains_key(&value) {
86                let idx = from_int.len();
87                to_int.insert(value.clone(), idx);
88                from_int.push(value);
89            }
90        }
91        Self { to_int, from_int }
92    }
93
94    /// Get the value at a positional index, or `None` if out of range.
95    ///
96    /// # Examples
97    ///
98    /// ```
99    /// use tensor4all_tcicore::IndexSet;
100    ///
101    /// let set = IndexSet::from_vec(vec![10, 20, 30]);
102    /// assert_eq!(set.get(0), Some(&10));
103    /// assert_eq!(set.get(2), Some(&30));
104    /// assert_eq!(set.get(3), None);
105    /// ```
106    pub fn get(&self, i: usize) -> Option<&T> {
107        self.from_int.get(i)
108    }
109
110    /// Get the positional index of a value, or `None` if not present.
111    ///
112    /// # Examples
113    ///
114    /// ```
115    /// use tensor4all_tcicore::IndexSet;
116    ///
117    /// let set = IndexSet::from_vec(vec![10, 20, 30]);
118    /// assert_eq!(set.pos(&20), Some(1));
119    /// assert_eq!(set.pos(&99), None);
120    /// ```
121    pub fn pos(&self, value: &T) -> Option<usize> {
122        self.to_int.get(value).copied()
123    }
124
125    /// Get positional indices for a slice of values.
126    ///
127    /// Returns `None` if any value is not present in the set.
128    ///
129    /// # Examples
130    ///
131    /// ```
132    /// use tensor4all_tcicore::IndexSet;
133    ///
134    /// let set = IndexSet::from_vec(vec![10, 20, 30]);
135    /// assert_eq!(set.positions(&[30, 10]), Some(vec![2, 0]));
136    /// assert_eq!(set.positions(&[10, 99]), None);
137    /// ```
138    pub fn positions(&self, values: &[T]) -> Option<Vec<usize>> {
139        values.iter().map(|v| self.pos(v)).collect()
140    }
141
142    /// Push a new value to the set.
143    ///
144    /// If the value already exists in the set, this is a no-op.
145    ///
146    /// # Examples
147    ///
148    /// ```
149    /// use tensor4all_tcicore::IndexSet;
150    ///
151    /// let mut set = IndexSet::new();
152    /// set.push(10);
153    /// set.push(20);
154    /// set.push(10); // duplicate, ignored
155    /// assert_eq!(set.len(), 2);
156    /// assert_eq!(set[0], 10);
157    /// assert_eq!(set[1], 20);
158    /// ```
159    pub fn push(&mut self, value: T) {
160        if self.to_int.contains_key(&value) {
161            return;
162        }
163        let idx = self.from_int.len();
164        self.from_int.push(value.clone());
165        self.to_int.insert(value, idx);
166    }
167
168    /// Check if the set contains a value.
169    ///
170    /// # Examples
171    ///
172    /// ```
173    /// use tensor4all_tcicore::IndexSet;
174    ///
175    /// let set = IndexSet::from_vec(vec![10, 20]);
176    /// assert!(set.contains(&10));
177    /// assert!(!set.contains(&30));
178    /// ```
179    pub fn contains(&self, value: &T) -> bool {
180        self.to_int.contains_key(value)
181    }
182
183    /// Number of elements in the set
184    pub fn len(&self) -> usize {
185        self.from_int.len()
186    }
187
188    /// Check if the set is empty
189    pub fn is_empty(&self) -> bool {
190        self.from_int.is_empty()
191    }
192
193    /// Iterate over values in insertion order.
194    ///
195    /// # Examples
196    ///
197    /// ```
198    /// use tensor4all_tcicore::IndexSet;
199    ///
200    /// let set = IndexSet::from_vec(vec![10, 20, 30]);
201    /// let collected: Vec<_> = set.iter().copied().collect();
202    /// assert_eq!(collected, vec![10, 20, 30]);
203    /// ```
204    pub fn iter(&self) -> impl Iterator<Item = &T> {
205        self.from_int.iter()
206    }
207
208    /// Get all values as a slice in insertion order.
209    ///
210    /// # Examples
211    ///
212    /// ```
213    /// use tensor4all_tcicore::IndexSet;
214    ///
215    /// let set = IndexSet::from_vec(vec![10, 20, 30]);
216    /// assert_eq!(set.values(), &[10, 20, 30]);
217    /// ```
218    pub fn values(&self) -> &[T] {
219        &self.from_int
220    }
221}
222
223impl<T: Clone + Eq + Hash> std::ops::Index<usize> for IndexSet<T> {
224    type Output = T;
225
226    fn index(&self, i: usize) -> &Self::Output {
227        &self.from_int[i]
228    }
229}
230
231impl<T: Clone + Eq + Hash> IntoIterator for IndexSet<T> {
232    type Item = T;
233    type IntoIter = std::vec::IntoIter<T>;
234
235    fn into_iter(self) -> Self::IntoIter {
236        self.from_int.into_iter()
237    }
238}
239
240impl<'a, T: Clone + Eq + Hash> IntoIterator for &'a IndexSet<T> {
241    type Item = &'a T;
242    type IntoIter = std::slice::Iter<'a, T>;
243
244    fn into_iter(self) -> Self::IntoIter {
245        self.from_int.iter()
246    }
247}
248
249/// A multi-index: a vector of site-local indices.
250pub type MultiIndex = Vec<usize>;
251
252/// A single site-local index.
253pub type LocalIndex = usize;
254
255#[cfg(test)]
256mod tests;
tensor4all_tcicore/indexset.rs

tensor4all_tcicore/
indexset.rs
