indexical/
domain.rs

1use index_vec::{Idx, IndexVec};
2use rustc_hash::FxHashMap;
3use std::fmt;
4
5use crate::IndexedValue;
6
7/// An indexed collection of objects.
8///
9/// Contains a reverse-mapping from `T` to `T::Index` for efficient lookups of indices.
10#[derive(Clone)]
11#[cfg_attr(feature = "serde", derive(serde::Serialize))]
12pub struct IndexedDomain<T: IndexedValue> {
13    domain: IndexVec<T::Index, T>,
14    #[cfg_attr(feature = "serde", serde(skip))]
15    reverse_map: FxHashMap<T, T::Index>,
16}
17
18#[cfg(feature = "serde")]
19impl<'de, T: IndexedValue + serde::Deserialize<'de>> serde::Deserialize<'de> for IndexedDomain<T> {
20    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
21    where
22        D: serde::Deserializer<'de>,
23    {
24        #[derive(serde::Deserialize)]
25        struct IndexedDomain2<T: IndexedValue> {
26            domain: IndexVec<T::Index, T>,
27        }
28        let domain = IndexedDomain2::<T>::deserialize(deserializer)?;
29        let reverse_map = domain
30            .domain
31            .iter_enumerated()
32            .map(|(idx, value)| (value.clone(), idx))
33            .collect();
34        Ok(IndexedDomain {
35            domain: domain.domain,
36            reverse_map,
37        })
38    }
39}
40
41impl<T: IndexedValue> IndexedDomain<T> {
42    /// Creates an empty domain,
43    pub fn new() -> Self {
44        IndexedDomain {
45            domain: IndexVec::new(),
46            reverse_map: FxHashMap::default(),
47        }
48    }
49
50    /// Gets the object corresponding to `index`.
51    ///
52    /// Panics if `index` is not within the domain.
53    pub fn value(&self, index: T::Index) -> &T {
54        &self.domain[index]
55    }
56
57    /// Gets the index corresponding to `value`.
58    ///
59    /// Panics if `value` is not within the domain.
60    pub fn index(&self, value: &T) -> T::Index {
61        self.reverse_map[value]
62    }
63
64    /// Returns true if `value` is contained in the domain.
65    pub fn contains_value(&self, value: &T) -> bool {
66        self.reverse_map.contains_key(value)
67    }
68
69    /// Returns true if `index` is contained in the domain.
70    pub fn contains_index(&self, index: T::Index) -> bool {
71        index.index() < self.domain.len()
72    }
73
74    /// Adds `value` to the domain, returning its new index.
75    pub fn insert(&mut self, value: T) -> T::Index {
76        let idx = self.domain.push(value.clone());
77        self.reverse_map.insert(value, idx);
78        idx
79    }
80
81    /// Returns immutable access to the underlying indexed vector.
82    pub fn as_vec(&self) -> &IndexVec<T::Index, T> {
83        &self.domain
84    }
85
86    /// Returns the number of elements in the domain.
87    pub fn len(&self) -> usize {
88        self.domain.len()
89    }
90
91    /// Returns true if the domain is empty.
92    pub fn is_empty(&self) -> bool {
93        self.len() == 0
94    }
95
96    /// Similar to [`IndexedDomain::index`], except it adds `value`
97    /// to the domain if it does not exist yet.
98    pub fn ensure(&mut self, value: &T) -> T::Index {
99        if !self.contains_value(value) {
100            self.insert(value.clone())
101        } else {
102            self.index(value)
103        }
104    }
105
106    /// Returns an iterator over all elements of the domain.
107    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> + ExactSizeIterator<Item = &T> {
108        self.domain.iter()
109    }
110
111    /// Returns an iterator over all indices of the domain.
112    pub fn indices(
113        &self,
114    ) -> impl DoubleEndedIterator<Item = T::Index> + ExactSizeIterator<Item = T::Index> {
115        // Re-implementing `indices` because profiling suggests that
116        // the IndexVec impl is not getting inlined for some reason??
117        (0..self.domain.len()).map(T::Index::from_usize)
118    }
119
120    /// Returns an iterator over all pairs of indices and elements of the domain.
121    pub fn iter_enumerated(
122        &self,
123    ) -> impl DoubleEndedIterator<Item = (T::Index, &T)> + ExactSizeIterator<Item = (T::Index, &T)>
124    {
125        self.domain.iter_enumerated()
126    }
127}
128
129impl<T: IndexedValue> Default for IndexedDomain<T> {
130    fn default() -> Self {
131        IndexedDomain::new()
132    }
133}
134
135impl<T: IndexedValue> From<IndexVec<T::Index, T>> for IndexedDomain<T> {
136    /// Creates a new domain from an indexed vector.
137    ///
138    /// Consider using the [`FromIterator`] implementation if you don't want to manually construct
139    /// an [`IndexVec`] object.
140    fn from(domain: IndexVec<T::Index, T>) -> Self {
141        let reverse_map = domain
142            .iter_enumerated()
143            .map(|(idx, value)| (value.clone(), idx))
144            .collect();
145        IndexedDomain {
146            domain,
147            reverse_map,
148        }
149    }
150}
151
152impl<T: IndexedValue> FromIterator<T> for IndexedDomain<T> {
153    fn from_iter<Iter: IntoIterator<Item = T>>(iter: Iter) -> Self {
154        let domain = iter.into_iter().collect::<IndexVec<T::Index, T>>();
155        IndexedDomain::from(domain)
156    }
157}
158
159impl<T: IndexedValue + fmt::Debug> fmt::Debug for IndexedDomain<T> {
160    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
161        self.domain.fmt(f)
162    }
163}
164
165#[test]
166fn test_domain() {
167    fn mk(s: &str) -> String {
168        s.to_string()
169    }
170
171    let d = IndexedDomain::from_iter([mk("a"), mk("b")]);
172    let a = d.index(&mk("a"));
173    let b = d.index(&mk("b"));
174    assert_eq!(d.value(a), "a");
175    assert_eq!(d.value(b), "b");
176    assert!(d.contains_value(&mk("a")));
177    assert!(!d.contains_value(&mk("c")));
178    assert_eq!(d.len(), 2);
179
180    assert_eq!(d.iter().collect::<Vec<_>>(), vec!["a", "b"]);
181}
indexical/domain.rs

indexical/
domain.rs
