catlog/zero/
column.rs

1//! Data structures for mappings and columns, as found in data tables.
2
3use std::collections::HashMap;
4use std::hash::Hash;
5use std::marker::PhantomData;
6
7use derivative::Derivative;
8use indexmap::IndexMap;
9use nonempty::NonEmpty;
10use thiserror::Error;
11
12use super::set::{FinSet, Set, SkelFinSet};
13use crate::validate::{self, Validate};
14
15/// A functional mapping.
16///
17/// A mapping sends values of type [`Dom`](Self::Dom) to values of type
18/// [`Cod`](Self::Cod). Unlike a function, a mapping need not be defined on its
19/// whole domain. A mapping is thus more like a partial function, but it does not
20/// even know its intended domain of definition, nor the codomain to which its image
21/// should restrict. If needed, that information should be provided separately as
22/// [sets](Set). Neither domain nor codomain are assumed to be finite.
23///
24/// This trait encompasses mappings that compute their values on the fly and
25/// mappings that own their data, say in the form of a vector or hash map. Achieving
26/// this flexiblity in Rust is delicate due to the sharp distinction between values
27/// and references, but as a user, deciding which method to call is simple enough.
28/// To evaluate at a point that you own and can consume, call
29/// [`apply`](Self::apply). To evaluate at a point that you have only by reference
30/// or can't consume, call [`apply_to_ref`](Self::apply_to_ref).
31pub trait Mapping {
32    /// Type of elements in domain of mapping.
33    type Dom: Eq + Clone;
34
35    /// Type of elements in codomain of mapping.
36    type Cod: Eq + Clone;
37
38    /// Applies the mapping at a point possibly in the domain.
39    fn apply(&self, x: Self::Dom) -> Option<Self::Cod>;
40
41    /// Applies the mapping at a *reference* to a point possibly in the domain.
42    ///
43    /// The default implementation just calls [`apply`](Self::apply) after cloning.
44    /// Mappings that own their data should give a more efficient implementation.
45    fn apply_to_ref(&self, x: &Self::Dom) -> Option<Self::Cod> {
46        self.apply(x.clone())
47    }
48
49    /// Is the mapping defined at a point?
50    ///
51    /// The default implementation just checks whether
52    /// [`apply_to_ref`](Self::apply_to_ref) returns something, but a more efficient
53    /// implementation that avoids allocating should usually be given.
54    fn is_set(&self, x: &Self::Dom) -> bool {
55        self.apply_to_ref(x).is_some()
56    }
57}
58
59/// A mutable [mapping](Mapping).
60///
61/// Besides being mutable, such a mapping is also assumed to own its values (how
62/// else could they be mutated?) and thus also allows access by reference.
63pub trait MutMapping: Mapping {
64    /// Gets the value of the mapping at a point possibly in the domain.
65    ///
66    /// The same as [`apply`](Mapping::apply) but returns by reference rather than
67    /// by value.
68    fn get(&self, x: &Self::Dom) -> Option<&Self::Cod>;
69
70    /// Sets the mapping at a point.
71    ///
72    /// The old value is returned, if one was set.
73    fn set(&mut self, x: Self::Dom, y: Self::Cod) -> Option<Self::Cod>;
74
75    /// Un-sets the mapping at a point, making it undefined at that point.
76    ///
77    /// The old value is returned, if one was set.
78    fn unset(&mut self, x: &Self::Dom) -> Option<Self::Cod>;
79
80    /// Updates the mapping at a point, setting or unsetting it.
81    ///
82    /// The old value is returned, if one was set.
83    fn update(&mut self, x: Self::Dom, maybe_y: Option<Self::Cod>) -> Option<Self::Cod> {
84        match maybe_y {
85            Some(y) => self.set(x, y),
86            None => self.unset(&x),
87        }
88    }
89}
90
91/// A [mapping](Mapping) with finite support.
92///
93/// While its domain and codomain can be infinite, such a mapping is defined at only
94/// finitely many values in the domain. It is thus a "column of data", as found in
95/// data tables and relational databases.
96pub trait Column: Mapping {
97    /// Iterates over the column's pairs of elements.
98    fn iter(&self) -> impl Iterator<Item = (Self::Dom, &Self::Cod)>;
99
100    /// Iterates over the column's values.
101    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
102        self.iter().map(|(_, y)| y)
103    }
104
105    /// Computes the preimage of the mapping at a value in the codomain.
106    ///
107    /// Depending on whether the implementation maintains a reverse index for
108    /// the mapping, this method will take time linear in either the size of the
109    /// preimage or the size of the whole column.
110    fn preimage(&self, y: &Self::Cod) -> impl Iterator<Item = Self::Dom> {
111        self.iter().filter(|&(_, z)| *z == *y).map(|(x, _)| x)
112    }
113
114    /// Gets the number of values in the domain on which the column is defined.
115    fn len(&self) -> usize {
116        self.iter().count()
117    }
118
119    /// Is the mapping not defined anywhere?
120    fn is_empty(&self) -> bool {
121        self.iter().next().is_none()
122    }
123}
124
125/// A [mutable mapping](MutMapping) with finite support.
126///
127/// Being a finite column that owns its data, a mutable column can be converted
128/// to/from an iterator of pairs.
129pub trait MutColumn:
130    MutMapping
131    + Column
132    + IntoIterator<Item = (Self::Dom, Self::Cod)>
133    + FromIterator<(Self::Dom, Self::Cod)>
134{
135    /// Post-composes the column with another mapping.
136    ///
137    /// This is composition of partial functions. Note that the codomain element
138    /// type must stay the same, which is the only thing that makes sense at this
139    /// level of type specifity.
140    fn postcompose<F>(self, f: &F) -> Self
141    where
142        F: Mapping<Dom = Self::Cod, Cod = Self::Cod>,
143    {
144        self.into_iter().filter_map(|(x, y)| f.apply(y).map(|z| (x, z))).collect()
145    }
146}
147
148/// A function between sets defined by a [mapping](Mapping).
149///
150/// This struct borrows its data, and exists mainly as a convenient interface to
151/// validate that a mapping defines a valid function.
152pub struct Function<'a, Map, Dom, Cod>(pub &'a Map, pub &'a Dom, pub &'a Cod);
153
154impl<'a, Map, Dom, Cod> Function<'a, Map, Dom, Cod>
155where
156    Map: Mapping,
157    Dom: FinSet<Elem = Map::Dom>,
158    Cod: Set<Elem = Map::Cod>,
159{
160    /// Iterates over failures to be a function.
161    pub fn iter_invalid(
162        &self,
163    ) -> impl Iterator<Item = InvalidFunction<Map::Dom>> + 'a + use<'a, Map, Dom, Cod> {
164        let Function(mapping, dom, cod) = self;
165        dom.iter().filter_map(|x| match mapping.apply_to_ref(&x) {
166            Some(y) => {
167                if cod.contains(&y) {
168                    None
169                } else {
170                    Some(InvalidFunction::Cod(x))
171                }
172            }
173            None => Some(InvalidFunction::Dom(x)),
174        })
175    }
176}
177
178impl<Map, Dom, Cod> Validate for Function<'_, Map, Dom, Cod>
179where
180    Map: Mapping,
181    Dom: FinSet<Elem = Map::Dom>,
182    Cod: Set<Elem = Map::Cod>,
183{
184    type ValidationError = InvalidFunction<Map::Dom>;
185
186    fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>> {
187        validate::wrap_errors(self.iter_invalid())
188    }
189}
190
191/// A failure of a mapping to restrict to a function between two sets.
192#[derive(Debug, Error, PartialEq, Eq)]
193pub enum InvalidFunction<T> {
194    /// The mapping is not defined at a point in the domain.
195    #[error("Mapping not defined at point `{0}` in domain")]
196    Dom(T),
197
198    /// The image of a point in the domain is not contained in the codomain.
199    #[error("Image of mapping at point `{0}` is not in codomain")]
200    Cod(T),
201}
202
203impl<T> InvalidFunction<T> {
204    pub(crate) fn take(self) -> T {
205        match self {
206            InvalidFunction::Dom(x) | InvalidFunction::Cod(x) => x,
207        }
208    }
209}
210
211/// Finds a retraction of the mapping, if it exists.
212///
213/// A retraction (left inverse) exists if and only if the mapping is injective. The
214/// retraction is unique when it exists because it is defined only on the image of
215/// the mapping. When the mapping is not injective, a pair of elements having the
216/// same image is returned.
217pub fn retraction<Dom, Cod, InvMap>(
218    mapping: &impl Column<Dom = Dom, Cod = Cod>,
219) -> Result<InvMap, (Dom, Dom)>
220where
221    Dom: Clone,
222    Cod: Clone,
223    InvMap: MutMapping<Dom = Cod, Cod = Dom> + Default,
224{
225    let mut inv = InvMap::default();
226    for (x, y) in mapping.iter() {
227        if let Some(other_x) = inv.set(y.clone(), x.clone()) {
228            return Err((x, other_x));
229        }
230    }
231    Ok(inv)
232}
233
234/// An unindexed column backed by a vector.
235#[derive(Clone, Debug, Derivative)]
236#[derivative(Default(bound = ""))]
237#[derivative(PartialEq(bound = "T: PartialEq"))]
238#[derivative(Eq(bound = "T: Eq"))]
239pub struct VecColumn<T>(Vec<Option<T>>);
240
241/// Iterator over a [vector column](VecColumn).
242pub struct VecColumnIter<T> {
243    vec: Vec<Option<T>>,
244    index: usize,
245}
246
247impl<T> VecColumn<T> {
248    /// Creates a vector-backed column by consuming an existing vector.
249    pub fn new(values: Vec<T>) -> Self {
250        Self(values.into_iter().map(Some).collect())
251    }
252}
253
254impl<T> Iterator for VecColumnIter<T> {
255    type Item = (usize, T);
256
257    fn next(&mut self) -> Option<Self::Item> {
258        let n = self.vec.len();
259        while self.index < n && self.vec[self.index].is_none() {
260            self.index += 1;
261        }
262        if self.index < n {
263            Some((self.index, self.vec[self.index].take().unwrap()))
264        } else {
265            None
266        }
267    }
268}
269
270impl<T> IntoIterator for VecColumn<T> {
271    type Item = (usize, T);
272    type IntoIter = VecColumnIter<T>;
273
274    fn into_iter(self) -> Self::IntoIter {
275        VecColumnIter { vec: self.0, index: 0 }
276    }
277}
278
279impl<T> FromIterator<(usize, T)> for VecColumn<T> {
280    fn from_iter<Iter: IntoIterator<Item = (usize, T)>>(iter: Iter) -> Self {
281        let mut vec = Vec::new();
282        for (i, y) in iter {
283            if i >= vec.len() {
284                vec.resize_with(i + 1, Default::default);
285            }
286            vec[i] = Some(y);
287        }
288        VecColumn(vec)
289    }
290}
291
292impl<T: Eq + Clone> Mapping for VecColumn<T> {
293    type Dom = usize;
294    type Cod = T;
295
296    fn apply(&self, i: usize) -> Option<T> {
297        self.0.get(i).cloned().flatten()
298    }
299
300    fn apply_to_ref(&self, i: &usize) -> Option<T> {
301        self.apply(*i)
302    }
303
304    fn is_set(&self, i: &usize) -> bool {
305        *i < self.0.len() && self.0[*i].is_some()
306    }
307}
308
309impl<T: Eq + Clone> MutMapping for VecColumn<T> {
310    fn get(&self, i: &usize) -> Option<&T> {
311        if *i < self.0.len() {
312            self.0[*i].as_ref()
313        } else {
314            None
315        }
316    }
317
318    fn set(&mut self, i: usize, y: T) -> Option<T> {
319        if i >= self.0.len() {
320            self.0.resize_with(i + 1, Default::default);
321        }
322        self.0[i].replace(y)
323    }
324
325    fn unset(&mut self, i: &usize) -> Option<T> {
326        if *i < self.0.len() {
327            self.0[*i].take()
328        } else {
329            None
330        }
331    }
332}
333
334impl<T: Eq + Clone> Column for VecColumn<T> {
335    fn iter(&self) -> impl Iterator<Item = (usize, &T)> {
336        let filtered = self.0.iter().enumerate().filter(|(_, y)| y.is_some());
337        filtered.map(|(i, y)| (i, y.as_ref().unwrap()))
338    }
339
340    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
341        self.0.iter().flatten()
342    }
343
344    fn len(&self) -> usize {
345        self.0.iter().filter(|y| y.is_some()).count()
346    }
347
348    fn is_empty(&self) -> bool {
349        self.0.iter().all(|y| y.is_none())
350    }
351}
352
353impl<T: Eq + Clone> MutColumn for VecColumn<T> {}
354
355/// An unindexed column backed by an integer-valued vector.
356pub type SkelColumn = VecColumn<usize>;
357
358impl SkelColumn {
359    /// Is the mapping a function between the finite sets `[m]` and `[n]`?
360    pub fn is_function(&self, m: usize, n: usize) -> bool {
361        let (dom, cod): (SkelFinSet, SkelFinSet) = (m.into(), n.into());
362        Function(self, &dom, &cod).iter_invalid().next().is_none()
363    }
364
365    /// Is the mapping a partial injection, i.e., injective where it is defined?
366    pub fn is_partial_injection(&self) -> bool {
367        let result: Result<Self, _> = retraction(self);
368        result.is_ok()
369    }
370
371    /// Is the mapping an injection between the finite sets `[m]` and `[n]`?
372    pub fn is_injection(&self, m: usize, n: usize) -> bool {
373        self.is_function(m, n) && self.is_partial_injection()
374    }
375
376    /// Is the mapping a permutation of the finite set `[n]`?
377    pub fn is_permutation(&self, n: usize) -> bool {
378        self.is_injection(n, n)
379    }
380}
381
382/// An unindexed column backed by a hash map.
383///
384/// A stable order is guaranteed when iterating over the preimage of an element.
385/// Currently, this is achieved (in the unindexed case) by using an [`IndexMap`]
386/// rather than a `HashMap` for the underlying data structure.
387#[derive(Clone, Debug, Derivative)]
388#[derivative(PartialEq(bound = "K: Eq + Hash, V: PartialEq"))]
389#[derivative(Eq(bound = "K: Eq + Hash, V: Eq"))]
390#[derivative(Default(bound = ""))]
391pub struct HashColumn<K, V>(IndexMap<K, V>);
392
393impl<K, V> IntoIterator for HashColumn<K, V> {
394    type Item = (K, V);
395    type IntoIter = indexmap::map::IntoIter<K, V>;
396
397    fn into_iter(self) -> Self::IntoIter {
398        self.0.into_iter()
399    }
400}
401
402impl<K, V> FromIterator<(K, V)> for HashColumn<K, V>
403where
404    K: Eq + Hash,
405{
406    fn from_iter<Iter: IntoIterator<Item = (K, V)>>(iter: Iter) -> Self {
407        HashColumn(IndexMap::from_iter(iter))
408    }
409}
410
411impl<K, V> Mapping for HashColumn<K, V>
412where
413    K: Eq + Hash + Clone,
414    V: Eq + Clone,
415{
416    type Dom = K;
417    type Cod = V;
418
419    fn apply(&self, x: K) -> Option<V> {
420        self.apply_to_ref(&x)
421    }
422    fn apply_to_ref(&self, x: &K) -> Option<V> {
423        self.0.get(x).cloned()
424    }
425    fn is_set(&self, x: &K) -> bool {
426        self.0.contains_key(x)
427    }
428}
429
430impl<K, V> MutMapping for HashColumn<K, V>
431where
432    K: Eq + Hash + Clone,
433    V: Eq + Clone,
434{
435    fn get(&self, x: &K) -> Option<&V> {
436        self.0.get(x)
437    }
438    fn set(&mut self, x: K, y: V) -> Option<V> {
439        self.0.insert(x, y)
440    }
441    fn unset(&mut self, x: &K) -> Option<V> {
442        self.0.swap_remove(x)
443    }
444}
445
446impl<K, V> Column for HashColumn<K, V>
447where
448    K: Eq + Hash + Clone,
449    V: Eq + Clone,
450{
451    fn iter(&self) -> impl Iterator<Item = (K, &V)> {
452        self.0.iter().map(|(k, v)| (k.clone(), v))
453    }
454    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
455        self.0.values()
456    }
457    fn len(&self) -> usize {
458        self.0.len()
459    }
460    fn is_empty(&self) -> bool {
461        self.0.is_empty()
462    }
463}
464
465impl<K, V> MutColumn for HashColumn<K, V>
466where
467    K: Eq + Hash + Clone,
468    V: Eq + Clone,
469{
470}
471
472/// An index in a column.
473///
474/// An index is a cache of preimages of a mapping, like an index in a relational
475/// database. For the time being, indices are not a public interface, just a
476/// convenient abstraction for implementing columns.
477trait Index {
478    type Dom;
479    type Cod;
480
481    /// Gets the cached preimage.
482    fn preimage(&self, y: &Self::Cod) -> impl Iterator<Item = Self::Dom>;
483
484    /// Inserts a new pair into the index.
485    fn insert(&mut self, x: Self::Dom, y: &Self::Cod);
486
487    /// Removes a pair from the index.
488    ///
489    /// Assumes that the pair is already indexed, and may panic if not.
490    fn remove(&mut self, x: &Self::Dom, y: &Self::Cod);
491}
492
493/// An index implemented as a vector of vectors.
494#[derive(Clone, Debug, Derivative)]
495#[derivative(Default(bound = ""))]
496struct VecIndex<T>(Vec<Vec<T>>);
497
498impl<T: Eq + Clone> Index for VecIndex<T> {
499    type Dom = T;
500    type Cod = usize;
501
502    fn preimage(&self, y: &usize) -> impl Iterator<Item = T> {
503        let iter = match self.0.get(*y) {
504            Some(vec) => vec.iter(),
505            None => ([] as [T; 0]).iter(),
506        };
507        iter.cloned()
508    }
509
510    fn insert(&mut self, x: T, y: &usize) {
511        let i = *y;
512        if i >= self.0.len() {
513            self.0.resize_with(i + 1, Default::default);
514        }
515        self.0[i].push(x);
516    }
517
518    fn remove(&mut self, x: &T, y: &usize) {
519        let vec = &mut self.0[*y];
520        let i = vec.iter().rposition(|w| *w == *x).unwrap();
521        vec.remove(i);
522    }
523}
524
525/// An index implemented by a hash map into vectors.
526#[derive(Clone, Debug, Derivative)]
527#[derivative(Default(bound = ""))]
528struct HashIndex<X, Y>(HashMap<Y, Vec<X>>);
529
530impl<X, Y> Index for HashIndex<X, Y>
531where
532    X: Eq + Clone,
533    Y: Eq + Hash + Clone,
534{
535    type Dom = X;
536    type Cod = Y;
537
538    fn preimage(&self, y: &Y) -> impl Iterator<Item = X> {
539        let iter = match self.0.get(y) {
540            Some(vec) => vec.iter(),
541            None => ([] as [X; 0]).iter(),
542        };
543        iter.cloned()
544    }
545
546    fn insert(&mut self, x: X, y: &Y) {
547        match self.0.get_mut(y) {
548            Some(vec) => {
549                vec.push(x);
550            }
551            None => {
552                self.0.insert(y.clone(), vec![x]);
553            }
554        }
555    }
556
557    fn remove(&mut self, x: &X, y: &Y) {
558        let vec = self.0.get_mut(y).unwrap();
559        let i = vec.iter().rposition(|w| *w == *x).unwrap();
560        vec.remove(i);
561    }
562}
563
564/// An indexed column comprising a forward mapping and a separate index.
565///
566/// This common pattern is used to implement more specific columns but, like the
567/// `Index` trait, is not directly exposed.
568#[derive(Clone, Derivative, Debug)]
569#[derivative(PartialEq, Eq)]
570struct IndexedColumn<Dom, Cod, Col, Ind> {
571    mapping: Col,
572    #[derivative(PartialEq = "ignore")]
573    index: Ind,
574    dom_type: PhantomData<Dom>,
575    cod_type: PhantomData<Cod>,
576}
577
578impl<Dom, Cod, Col, Ind> Default for IndexedColumn<Dom, Cod, Col, Ind>
579where
580    Col: Default,
581    Ind: Default,
582{
583    fn default() -> Self {
584        Self {
585            mapping: Default::default(),
586            index: Default::default(),
587            dom_type: PhantomData,
588            cod_type: PhantomData,
589        }
590    }
591}
592
593impl<Dom, Cod, Col, Ind> IntoIterator for IndexedColumn<Dom, Cod, Col, Ind>
594where
595    Col: IntoIterator<Item = (Dom, Cod)>,
596{
597    type Item = (Dom, Cod);
598    type IntoIter = Col::IntoIter;
599
600    fn into_iter(self) -> Self::IntoIter {
601        self.mapping.into_iter()
602    }
603}
604
605impl<Dom, Cod, Col, Ind> FromIterator<(Dom, Cod)> for IndexedColumn<Dom, Cod, Col, Ind>
606where
607    Dom: Eq + Clone,
608    Cod: Eq + Clone,
609    Col: Default + MutMapping<Dom = Dom, Cod = Cod>,
610    Ind: Default + Index<Dom = Dom, Cod = Cod>,
611{
612    fn from_iter<Iter: IntoIterator<Item = (Dom, Cod)>>(iter: Iter) -> Self {
613        let mut col: Self = Default::default();
614        for (x, y) in iter {
615            col.set(x, y);
616        }
617        col
618    }
619}
620
621impl<Dom, Cod, Col, Ind> Mapping for IndexedColumn<Dom, Cod, Col, Ind>
622where
623    Dom: Eq + Clone,
624    Cod: Eq + Clone,
625    Col: Mapping<Dom = Dom, Cod = Cod>,
626{
627    type Dom = Dom;
628    type Cod = Cod;
629
630    fn apply(&self, x: Dom) -> Option<Cod> {
631        self.mapping.apply(x)
632    }
633    fn apply_to_ref(&self, x: &Dom) -> Option<Cod> {
634        self.mapping.apply_to_ref(x)
635    }
636    fn is_set(&self, x: &Dom) -> bool {
637        self.mapping.is_set(x)
638    }
639}
640
641impl<Dom, Cod, Col, Ind> MutMapping for IndexedColumn<Dom, Cod, Col, Ind>
642where
643    Dom: Eq + Clone,
644    Cod: Eq + Clone,
645    Col: MutMapping<Dom = Dom, Cod = Cod>,
646    Ind: Index<Dom = Dom, Cod = Cod>,
647{
648    fn get(&self, x: &Dom) -> Option<&Cod> {
649        self.mapping.get(x)
650    }
651
652    fn set(&mut self, x: Dom, y: Cod) -> Option<Cod> {
653        if let Some(y_prev) = self.mapping.get(&x) {
654            self.index.remove(&x, y_prev);
655        }
656        self.index.insert(x.clone(), &y);
657        self.mapping.set(x, y)
658    }
659
660    fn unset(&mut self, x: &Dom) -> Option<Cod> {
661        let old = self.mapping.unset(x);
662        if let Some(y) = &old {
663            self.index.remove(x, y);
664        }
665        old
666    }
667}
668
669impl<Dom, Cod, Col, Ind> Column for IndexedColumn<Dom, Cod, Col, Ind>
670where
671    Dom: Eq + Clone,
672    Cod: Eq + Clone,
673    Col: Column<Dom = Dom, Cod = Cod>,
674    Ind: Index<Dom = Dom, Cod = Cod>,
675{
676    fn iter(&self) -> impl Iterator<Item = (Dom, &Cod)> {
677        self.mapping.iter()
678    }
679    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
680        self.mapping.values()
681    }
682    fn preimage(&self, y: &Cod) -> impl Iterator<Item = Dom> {
683        self.index.preimage(y)
684    }
685    fn len(&self) -> usize {
686        self.mapping.len()
687    }
688    fn is_empty(&self) -> bool {
689        self.mapping.is_empty()
690    }
691}
692
693/// An indexed column backed by an integer-valued vector.
694///
695/// The column has the natural numbers (`usize`) as both its domain and codomain,
696/// making it suitable for use with skeletal finite sets.
697#[derive(Clone, Debug, Derivative, PartialEq, Eq, Default)]
698pub struct SkelIndexedColumn(IndexedColumn<usize, usize, VecColumn<usize>, VecIndex<usize>>);
699
700impl SkelIndexedColumn {
701    /// Creates a new vector-backed column from an existing vector.
702    pub fn new(values: &[usize]) -> Self {
703        let mut col: Self = Default::default();
704        for (x, y) in values.iter().enumerate() {
705            col.set(x, *y);
706        }
707        col
708    }
709}
710
711impl IntoIterator for SkelIndexedColumn {
712    type Item = (usize, usize);
713    type IntoIter = VecColumnIter<usize>;
714
715    fn into_iter(self) -> Self::IntoIter {
716        self.0.into_iter()
717    }
718}
719
720impl FromIterator<(usize, usize)> for SkelIndexedColumn {
721    fn from_iter<Iter: IntoIterator<Item = (usize, usize)>>(iter: Iter) -> Self {
722        Self(IndexedColumn::from_iter(iter))
723    }
724}
725
726impl Mapping for SkelIndexedColumn {
727    type Dom = usize;
728    type Cod = usize;
729
730    fn apply(&self, x: usize) -> Option<usize> {
731        self.0.apply(x)
732    }
733    fn apply_to_ref(&self, x: &usize) -> Option<usize> {
734        self.0.apply(*x)
735    }
736    fn is_set(&self, x: &usize) -> bool {
737        self.0.is_set(x)
738    }
739}
740
741impl MutMapping for SkelIndexedColumn {
742    fn get(&self, x: &usize) -> Option<&usize> {
743        self.0.get(x)
744    }
745    fn set(&mut self, x: usize, y: usize) -> Option<usize> {
746        self.0.set(x, y)
747    }
748    fn unset(&mut self, x: &usize) -> Option<usize> {
749        self.0.unset(x)
750    }
751}
752
753impl Column for SkelIndexedColumn {
754    fn iter(&self) -> impl Iterator<Item = (usize, &usize)> {
755        self.0.iter()
756    }
757    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
758        self.0.values()
759    }
760    fn preimage(&self, y: &usize) -> impl Iterator<Item = usize> {
761        self.0.preimage(y)
762    }
763    fn len(&self) -> usize {
764        self.0.len()
765    }
766    fn is_empty(&self) -> bool {
767        self.0.is_empty()
768    }
769}
770
771impl MutColumn for SkelIndexedColumn {}
772
773/// An indexed column backed by a vector.
774///
775/// The domain of the column is the natural numbers (`usize`). Since the codomain is
776/// an arbitrary type (`T`), the index is implemented using a hash map.
777#[derive(Clone, Debug, Derivative, PartialEq, Eq)]
778#[derivative(Default(bound = ""))]
779pub struct IndexedVecColumn<T>(IndexedColumn<usize, T, VecColumn<T>, HashIndex<usize, T>>);
780
781impl<T: Eq + Hash + Clone> IndexedVecColumn<T> {
782    /// Creates a new vector-backed column from an existing vector.
783    pub fn new(values: &[T]) -> Self {
784        values.iter().cloned().enumerate().collect()
785    }
786}
787
788impl<T> IntoIterator for IndexedVecColumn<T> {
789    type Item = (usize, T);
790    type IntoIter = VecColumnIter<T>;
791
792    fn into_iter(self) -> Self::IntoIter {
793        self.0.into_iter()
794    }
795}
796
797impl<T: Eq + Hash + Clone> FromIterator<(usize, T)> for IndexedVecColumn<T> {
798    fn from_iter<Iter: IntoIterator<Item = (usize, T)>>(iter: Iter) -> Self {
799        Self(IndexedColumn::from_iter(iter))
800    }
801}
802
803impl<T: Eq + Hash + Clone> Mapping for IndexedVecColumn<T> {
804    type Dom = usize;
805    type Cod = T;
806
807    fn apply(&self, x: usize) -> Option<T> {
808        self.0.apply(x)
809    }
810    fn apply_to_ref(&self, x: &usize) -> Option<T> {
811        self.0.apply(*x)
812    }
813    fn is_set(&self, x: &usize) -> bool {
814        self.0.is_set(x)
815    }
816}
817
818impl<T: Eq + Hash + Clone> MutMapping for IndexedVecColumn<T> {
819    fn get(&self, x: &usize) -> Option<&T> {
820        self.0.get(x)
821    }
822    fn set(&mut self, x: usize, y: T) -> Option<T> {
823        self.0.set(x, y)
824    }
825    fn unset(&mut self, x: &usize) -> Option<T> {
826        self.0.unset(x)
827    }
828}
829
830impl<T: Eq + Hash + Clone> Column for IndexedVecColumn<T> {
831    fn iter(&self) -> impl Iterator<Item = (usize, &T)> {
832        self.0.iter()
833    }
834    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
835        self.0.values()
836    }
837    fn preimage(&self, y: &T) -> impl Iterator<Item = usize> {
838        self.0.preimage(y)
839    }
840    fn len(&self) -> usize {
841        self.0.len()
842    }
843    fn is_empty(&self) -> bool {
844        self.0.is_empty()
845    }
846}
847
848impl<T: Eq + Hash + Clone> MutColumn for IndexedVecColumn<T> {}
849
850/// An indexed column backed by hash maps.
851#[derive(Clone, Derivative, Debug)]
852#[derivative(Default(bound = ""))]
853#[derivative(PartialEq(bound = "K: Eq + Hash, V: PartialEq"))]
854#[derivative(Eq(bound = "K: Eq + Hash, V: Eq"))]
855pub struct IndexedHashColumn<K, V>(IndexedColumn<K, V, HashColumn<K, V>, HashIndex<K, V>>);
856
857impl<K, V> IntoIterator for IndexedHashColumn<K, V>
858where
859    K: Eq + Hash,
860    V: Eq + Hash,
861{
862    type Item = (K, V);
863    type IntoIter = <HashColumn<K, V> as IntoIterator>::IntoIter;
864
865    fn into_iter(self) -> Self::IntoIter {
866        self.0.into_iter()
867    }
868}
869
870impl<K, V> FromIterator<(K, V)> for IndexedHashColumn<K, V>
871where
872    K: Eq + Hash + Clone,
873    V: Eq + Hash + Clone,
874{
875    fn from_iter<Iter: IntoIterator<Item = (K, V)>>(iter: Iter) -> Self {
876        Self(IndexedColumn::from_iter(iter))
877    }
878}
879
880impl<K, V> Mapping for IndexedHashColumn<K, V>
881where
882    K: Eq + Hash + Clone,
883    V: Eq + Hash + Clone,
884{
885    type Dom = K;
886    type Cod = V;
887
888    fn apply(&self, x: K) -> Option<V> {
889        self.0.apply(x)
890    }
891    fn apply_to_ref(&self, x: &K) -> Option<V> {
892        self.0.apply_to_ref(x)
893    }
894    fn is_set(&self, x: &K) -> bool {
895        self.0.is_set(x)
896    }
897}
898
899impl<K, V> MutMapping for IndexedHashColumn<K, V>
900where
901    K: Eq + Hash + Clone,
902    V: Eq + Hash + Clone,
903{
904    fn get(&self, x: &K) -> Option<&V> {
905        self.0.get(x)
906    }
907    fn set(&mut self, x: K, y: V) -> Option<V> {
908        self.0.set(x, y)
909    }
910    fn unset(&mut self, x: &K) -> Option<V> {
911        self.0.unset(x)
912    }
913}
914
915impl<K, V> Column for IndexedHashColumn<K, V>
916where
917    K: Eq + Hash + Clone,
918    V: Eq + Hash + Clone,
919{
920    fn iter(&self) -> impl Iterator<Item = (K, &V)> {
921        self.0.iter()
922    }
923    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
924        self.0.values()
925    }
926    fn preimage(&self, y: &V) -> impl Iterator<Item = K> {
927        self.0.preimage(y)
928    }
929    fn len(&self) -> usize {
930        self.0.len()
931    }
932    fn is_empty(&self) -> bool {
933        self.0.is_empty()
934    }
935}
936
937impl<K, V> MutColumn for IndexedHashColumn<K, V>
938where
939    K: Eq + Hash + Clone,
940    V: Eq + Hash + Clone,
941{
942}
943
944#[cfg(test)]
945mod tests {
946    use super::*;
947
948    #[test]
949    fn vec_column() {
950        let mut col = VecColumn::new(vec!["foo", "bar", "baz"]);
951        assert!(!col.is_empty());
952        assert_eq!(col.len(), 3);
953        assert!(col.is_set(&2));
954        assert_eq!(col.apply(2), Some("baz"));
955        assert_eq!(col.apply(3), None);
956        assert_eq!(col.apply_to_ref(&2), Some("baz"));
957        assert_eq!(col.get(&2), Some(&"baz"));
958        assert_eq!(col.update(2, None), Some("baz"));
959        assert!(!col.is_set(&2));
960
961        col.set(5, "baz");
962        col.set(3, "bar");
963        let preimage: Vec<_> = col.preimage(&"bar").collect();
964        assert_eq!(preimage, vec![1, 3]);
965
966        let data: Vec<_> = col.clone().into_iter().collect();
967        assert_eq!(data, vec![(0, "foo"), (1, "bar"), (3, "bar"), (5, "baz")]);
968        let new_col: VecColumn<_> = data.into_iter().collect();
969        assert_eq!(new_col, col);
970    }
971
972    #[test]
973    fn hash_column() {
974        let mut col: HashColumn<char, &str> = Default::default();
975        assert!(col.is_empty());
976        col.set('a', "foo");
977        col.set('b', "bar");
978        col.set('c', "baz");
979        assert!(!col.is_empty());
980        assert_eq!(col.len(), 3);
981        assert_eq!(col.apply('c'), Some("baz"));
982        assert_eq!(col.apply_to_ref(&'c'), Some("baz"));
983        assert_eq!(col.get(&'c'), Some(&"baz"));
984        assert_eq!(col.unset(&'c'), Some("baz"));
985        assert!(!col.is_set(&'c'));
986        col.set('c', "bar");
987
988        let mut preimage: Vec<_> = col.preimage(&"bar").collect();
989        preimage.sort();
990        assert_eq!(preimage, vec!['b', 'c']);
991
992        let mut data: Vec<_> = col.clone().into_iter().collect();
993        data.sort();
994        assert_eq!(data, vec![('a', "foo"), ('b', "bar"), ('c', "bar")]);
995        let new_col: HashColumn<_, _> = data.into_iter().collect();
996        assert_eq!(new_col, col);
997    }
998
999    #[test]
1000    fn skel_function_properties() {
1001        let map = SkelColumn::new(vec![1, 3, 5]);
1002        assert!(!map.is_function(3, 5));
1003        assert!(map.is_injection(3, 6));
1004        let map = SkelColumn::new(vec![0, 1, 0]);
1005        assert!(map.is_function(3, 2));
1006        assert!(!map.is_injection(3, 2));
1007        let map = SkelColumn::new(vec![3, 1, 2, 0]);
1008        assert!(map.is_permutation(4));
1009    }
1010
1011    #[test]
1012    fn skel_indexed_column() {
1013        let mut col = SkelIndexedColumn::new(&[1, 3, 5]);
1014        assert!(!col.is_empty());
1015        assert_eq!(col.len(), 3);
1016        assert!(col.is_set(&2));
1017        assert_eq!(col.apply(2), Some(5));
1018        assert_eq!(col.apply_to_ref(&2), Some(5));
1019        assert_eq!(col.get(&2), Some(&5));
1020        let preimage: Vec<_> = col.preimage(&5).collect();
1021        assert_eq!(preimage, vec![2]);
1022
1023        assert_eq!(col.set(0, 5), Some(1));
1024        assert_eq!(col.preimage(&1).count(), 0);
1025        let mut preimage: Vec<_> = col.preimage(&5).collect();
1026        preimage.sort();
1027        assert_eq!(preimage, vec![0, 2]);
1028
1029        let new_col: SkelIndexedColumn = col.clone().into_iter().collect();
1030        assert_eq!(new_col, col);
1031    }
1032
1033    #[test]
1034    fn indexed_vec_column() {
1035        let mut col = IndexedVecColumn::new(&["foo", "bar", "baz"]);
1036        assert!(!col.is_empty());
1037        assert_eq!(col.len(), 3);
1038        assert!(col.is_set(&2));
1039        assert_eq!(col.apply(2), Some("baz"));
1040        let preimage: Vec<_> = col.preimage(&"baz").collect();
1041        assert_eq!(preimage, vec![2]);
1042
1043        assert_eq!(col.set(0, "baz"), Some("foo"));
1044        assert_eq!(col.preimage(&"foo").count(), 0);
1045        let mut preimage: Vec<_> = col.preimage(&"baz").collect();
1046        preimage.sort();
1047        assert_eq!(preimage, vec![0, 2]);
1048
1049        let new_col: IndexedVecColumn<_> = col.clone().into_iter().collect();
1050        assert_eq!(new_col, col);
1051    }
1052
1053    #[test]
1054    fn indexed_hash_column() {
1055        let mut col: IndexedHashColumn<char, &str> = Default::default();
1056        assert!(col.is_empty());
1057        col.set('a', "foo");
1058        col.set('b', "bar");
1059        col.set('c', "baz");
1060        assert!(!col.is_empty());
1061        assert_eq!(col.len(), 3);
1062        assert_eq!(col.apply('c'), Some("baz"));
1063        let preimage: Vec<_> = col.preimage(&"baz").collect();
1064        assert_eq!(preimage, vec!['c']);
1065
1066        assert_eq!(col.set('a', "baz"), Some("foo"));
1067        assert_eq!(col.preimage(&"foo").count(), 0);
1068        let mut preimage: Vec<_> = col.preimage(&"baz").collect();
1069        preimage.sort();
1070        assert_eq!(preimage, vec!['a', 'c']);
1071
1072        let new_col: IndexedHashColumn<_, _> = col.clone().into_iter().collect();
1073        assert_eq!(new_col, col);
1074    }
1075
1076    #[test]
1077    fn validate_function() {
1078        let col = VecColumn::new(vec![1, 2, 4]);
1079        let validate = |m, n| Function(&col, &SkelFinSet::from(m), &SkelFinSet::from(n)).validate();
1080        assert!(validate(3, 5).is_ok());
1081        assert_eq!(validate(4, 5).unwrap_err(), NonEmpty::new(InvalidFunction::Dom::<usize>(3)));
1082        assert_eq!(validate(3, 4).unwrap_err(), NonEmpty::new(InvalidFunction::Cod::<usize>(2)));
1083    }
1084}
catlog/zero/column.rs

catlog/zero/
column.rs
