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    #[must_use]
44    pub fn new() -> Self {
45        IndexedDomain {
46            domain: IndexVec::new(),
47            reverse_map: FxHashMap::default(),
48        }
49    }
50
51    /// Gets the object corresponding to `index`.
52    ///
53    /// Panics if `index` is not within the domain.
54    pub fn value(&self, index: T::Index) -> &T {
55        &self.domain[index]
56    }
57
58    /// Gets the index corresponding to `value`.
59    ///
60    /// Panics if `value` is not within the domain.
61    pub fn index(&self, value: &T) -> T::Index {
62        self.reverse_map[value]
63    }
64
65    /// Returns true if `value` is contained in the domain.
66    pub fn contains_value(&self, value: &T) -> bool {
67        self.reverse_map.contains_key(value)
68    }
69
70    /// Returns true if `index` is contained in the domain.
71    pub fn contains_index(&self, index: T::Index) -> bool {
72        index.index() < self.domain.len()
73    }
74
75    /// Adds `value` to the domain, returning its new index.
76    pub fn insert(&mut self, value: T) -> T::Index {
77        let idx = self.domain.push(value.clone());
78        self.reverse_map.insert(value, idx);
79        idx
80    }
81
82    /// Returns immutable access to the underlying indexed vector.
83    #[must_use]
84    pub fn as_vec(&self) -> &IndexVec<T::Index, T> {
85        &self.domain
86    }
87
88    /// Returns the number of elements in the domain.
89    #[must_use]
90    pub fn len(&self) -> usize {
91        self.domain.len()
92    }
93
94    /// Returns true if the domain is empty.
95    #[must_use]
96    pub fn is_empty(&self) -> bool {
97        self.len() == 0
98    }
99
100    /// Similar to [`IndexedDomain::index`], except it adds `value`
101    /// to the domain if it does not exist yet.
102    pub fn ensure(&mut self, value: &T) -> T::Index {
103        if self.contains_value(value) {
104            self.index(value)
105        } else {
106            self.insert(value.clone())
107        }
108    }
109
110    /// Returns an iterator over all elements of the domain.
111    #[must_use]
112    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> + ExactSizeIterator<Item = &T> {
113        self.domain.iter()
114    }
115
116    /// Returns an iterator over all indices of the domain.
117    pub fn indices(
118        &self,
119    ) -> impl DoubleEndedIterator<Item = T::Index> + ExactSizeIterator<Item = T::Index> {
120        // Re-implementing `indices` because profiling suggests that
121        // the IndexVec impl is not getting inlined for some reason??
122        (0..self.domain.len()).map(T::Index::from_usize)
123    }
124
125    /// Returns an iterator over all pairs of indices and elements of the domain.
126    #[must_use]
127    pub fn iter_enumerated(
128        &self,
129    ) -> impl DoubleEndedIterator<Item = (T::Index, &T)> + ExactSizeIterator<Item = (T::Index, &T)>
130    {
131        self.domain.iter_enumerated()
132    }
133}
134
135impl<T: IndexedValue> Default for IndexedDomain<T> {
136    fn default() -> Self {
137        IndexedDomain::new()
138    }
139}
140
141impl<T: IndexedValue> From<IndexVec<T::Index, T>> for IndexedDomain<T> {
142    /// Creates a new domain from an indexed vector.
143    ///
144    /// Consider using the [`FromIterator`] implementation if you don't want to manually construct
145    /// an [`IndexVec`] object.
146    fn from(domain: IndexVec<T::Index, T>) -> Self {
147        let reverse_map = domain
148            .iter_enumerated()
149            .map(|(idx, value)| (value.clone(), idx))
150            .collect();
151        IndexedDomain {
152            domain,
153            reverse_map,
154        }
155    }
156}
157
158impl<T: IndexedValue> FromIterator<T> for IndexedDomain<T> {
159    fn from_iter<Iter: IntoIterator<Item = T>>(iter: Iter) -> Self {
160        let domain = iter.into_iter().collect::<IndexVec<T::Index, T>>();
161        IndexedDomain::from(domain)
162    }
163}
164
165impl<T: IndexedValue + fmt::Debug> fmt::Debug for IndexedDomain<T> {
166    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
167        self.domain.fmt(f)
168    }
169}
170
171#[test]
172fn test_domain() {
173    fn mk(s: &str) -> String {
174        s.to_string()
175    }
176
177    let d = IndexedDomain::from_iter([mk("a"), mk("b")]);
178    let a = d.index(&mk("a"));
179    let b = d.index(&mk("b"));
180    assert_eq!(d.value(a), "a");
181    assert_eq!(d.value(b), "b");
182    assert!(d.contains_value(&mk("a")));
183    assert!(!d.contains_value(&mk("c")));
184    assert_eq!(d.len(), 2);
185
186    assert_eq!(d.iter().collect::<Vec<_>>(), vec!["a", "b"]);
187}
indexical/domain.rs

indexical/
domain.rs
