catlog/zero/
column.rs

1//! Data structures for mappings and columns, as found in data tables.
2
3use std::collections::HashMap;
4use std::hash::{BuildHasher, BuildHasherDefault, Hash, RandomState};
5use std::marker::PhantomData;
6
7use derivative::Derivative;
8use derive_more::From;
9use nonempty::NonEmpty;
10use thiserror::Error;
11use ustr::{IdentityHasher, Ustr};
12
13use super::set::{FinSet, Set};
14use crate::validate::{self, Validate};
15
16/** A functional mapping.
17
18A mapping sends values of type [`Dom`](Self::Dom) to values of type
19[`Cod`](Self::Cod). Unlike a function, a mapping need not be defined on its
20whole domain. A mapping is thus more like a partial function, but it does not
21actually know its intended domain of definition. If needed, that information
22should be provided separately, preferably as a [`Set`].
23
24Neither the domain nor the codomain of the mapping are assumed to be finite.
25 */
26pub trait Mapping {
27    /// Type of elements in domain of mapping.
28    type Dom: Eq + Clone;
29
30    /// Type of elements in codomain of mapping.
31    type Cod: Eq + Clone;
32
33    /// Applies the mapping at a point possibly in the domain.
34    fn apply(&self, x: &Self::Dom) -> Option<Self::Cod>;
35
36    /** Is the mapping defined at a point?
37
38    The default implementation checks whether [`apply`](Self::apply) returns
39    something. Often this method can be given a more efficient implementation
40    that avoids allocating.
41    */
42    fn is_set(&self, x: &Self::Dom) -> bool {
43        self.apply(x).is_some()
44    }
45}
46
47/** A mutable [mapping](Mapping).
48
49Besides being mutable, such a mapping is also assumed to own its values (how
50else could they be mutated?) and thus also allows access by reference.
51 */
52pub trait MutMapping: Mapping {
53    /** Gets the value of the mapping at a point possibly in the domain.
54
55    The same as [`apply`](Mapping::apply) but returns by reference rather than
56    by value.
57    */
58    fn get(&self, x: &Self::Dom) -> Option<&Self::Cod>;
59
60    /** Sets the mapping at a point.
61
62    The old value is returned, if one was set.
63    */
64    fn set(&mut self, x: Self::Dom, y: Self::Cod) -> Option<Self::Cod>;
65
66    /** Un-sets the mapping at a point, making it undefined at that point.
67
68    The old value is returned, if one was set.
69    */
70    fn unset(&mut self, x: &Self::Dom) -> Option<Self::Cod>;
71
72    /** Updates the mapping at a point, setting or unsetting it.
73
74    The old value is returned, if one was set.
75     */
76    fn update(&mut self, x: Self::Dom, maybe_y: Option<Self::Cod>) -> Option<Self::Cod> {
77        match maybe_y {
78            Some(y) => self.set(x, y),
79            None => self.unset(&x),
80        }
81    }
82}
83
84/** A mapping with finite support.
85
86While its domain and codomain can be infinite, such a mapping is defined at only
87finitely many values in the domain. It is thus a "column of data", as found in
88data tables and relational databases.
89 */
90pub trait Column: Mapping {
91    /// Iterates over pairs stored by the column.
92    fn iter(&self) -> impl Iterator<Item = (Self::Dom, &Self::Cod)>;
93
94    /// Iterates over values stored by the column.
95    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
96        self.iter().map(|(_, y)| y)
97    }
98
99    /** Computes the preimage of the mapping at a value in the codomain.
100
101    Depending on whether the implementation maintains a reverse index for the
102    mapping, this method can be cheap or expensive.
103    */
104    fn preimage(&self, y: &Self::Cod) -> impl Iterator<Item = Self::Dom> {
105        self.iter().filter(|&(_, z)| *z == *y).map(|(x, _)| x)
106    }
107
108    /// Is the mapping not defined anywhere?
109    fn is_empty(&self) -> bool {
110        self.iter().next().is_none()
111    }
112}
113
114/** A function between sets defined by a [mapping](Mapping).
115
116This struct borrows its data, and exists mainly as a convenient interface to
117validate that a mapping defines a valid function.
118 */
119pub struct Function<'a, Map, Dom, Cod>(pub &'a Map, pub &'a Dom, pub &'a Cod);
120
121impl<'a, Map, Dom, Cod> Function<'a, Map, Dom, Cod>
122where
123    Map: Mapping,
124    Dom: FinSet<Elem = Map::Dom>,
125    Cod: Set<Elem = Map::Cod>,
126{
127    /// Iterates over failures to be a function.
128    pub fn iter_invalid(
129        &self,
130    ) -> impl Iterator<Item = InvalidFunction<Map::Dom>> + 'a + use<'a, Map, Dom, Cod> {
131        let Function(mapping, dom, cod) = self;
132        dom.iter().filter_map(|x| match mapping.apply(&x) {
133            Some(y) => {
134                if cod.contains(&y) {
135                    None
136                } else {
137                    Some(InvalidFunction::Cod(x))
138                }
139            }
140            None => Some(InvalidFunction::Dom(x)),
141        })
142    }
143}
144
145impl<Map, Dom, Cod> Validate for Function<'_, Map, Dom, Cod>
146where
147    Map: Mapping,
148    Dom: FinSet<Elem = Map::Dom>,
149    Cod: Set<Elem = Map::Cod>,
150{
151    type ValidationError = InvalidFunction<Map::Dom>;
152
153    fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>> {
154        validate::wrap_errors(self.iter_invalid())
155    }
156}
157
158/// A failure of a mapping to restrict to a function between two sets.
159#[derive(Debug, Error, PartialEq, Eq)]
160pub enum InvalidFunction<T> {
161    /// The mapping is not defined at a point in the domain.
162    #[error("Mapping not defined at point `{0}` in domain")]
163    Dom(T),
164
165    /// The image of a point in the domain is not contained in the codomain.
166    #[error("Image of mapping at point `{0}` is not in codomain")]
167    Cod(T),
168}
169
170impl<T> InvalidFunction<T> {
171    pub(crate) fn take(self) -> T {
172        match self {
173            InvalidFunction::Dom(x) | InvalidFunction::Cod(x) => x,
174        }
175    }
176}
177
178/** An unindexed column backed by a vector.
179 */
180#[derive(Clone, Debug, Derivative)]
181#[derivative(Default(bound = ""))]
182#[derivative(PartialEq(bound = "T: PartialEq"))]
183#[derivative(Eq(bound = "T: Eq"))]
184pub struct VecColumn<T>(Vec<Option<T>>);
185
186impl<T> VecColumn<T> {
187    /// Creates a vector-backed column by consuming an existing vector.
188    pub fn new(values: Vec<T>) -> Self {
189        Self(values.into_iter().map(Some).collect())
190    }
191}
192
193impl<T: Eq + Clone> Mapping for VecColumn<T> {
194    type Dom = usize;
195    type Cod = T;
196
197    fn apply(&self, i: &usize) -> Option<T> {
198        self.get(i).cloned()
199    }
200
201    fn is_set(&self, i: &usize) -> bool {
202        *i < self.0.len() && self.0[*i].is_some()
203    }
204}
205
206impl<T: Eq + Clone> MutMapping for VecColumn<T> {
207    fn get(&self, i: &usize) -> Option<&T> {
208        if *i < self.0.len() {
209            self.0[*i].as_ref()
210        } else {
211            None
212        }
213    }
214
215    fn set(&mut self, i: usize, y: T) -> Option<T> {
216        if i >= self.0.len() {
217            self.0.resize_with(i + 1, Default::default);
218        }
219        std::mem::replace(&mut self.0[i], Some(y))
220    }
221
222    fn unset(&mut self, i: &usize) -> Option<T> {
223        if *i < self.0.len() {
224            self.0[*i].take()
225        } else {
226            None
227        }
228    }
229}
230
231impl<T: Eq + Clone> Column for VecColumn<T> {
232    fn iter(&self) -> impl Iterator<Item = (usize, &T)> {
233        let filtered = self.0.iter().enumerate().filter(|(_, y)| y.is_some());
234        filtered.map(|(i, y)| (i, y.as_ref().unwrap()))
235    }
236
237    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
238        self.0.iter().flatten()
239    }
240
241    fn is_empty(&self) -> bool {
242        self.0.iter().all(|y| y.is_none())
243    }
244}
245
246/** An unindexed column backed by a hash map.
247 */
248#[derive(Clone, From, Debug, Derivative)]
249#[derivative(Default(bound = "S: Default"))]
250#[derivative(PartialEq(bound = "K: Eq + Hash, V: PartialEq, S: BuildHasher"))]
251#[derivative(Eq(bound = "K: Eq + Hash, V: Eq, S: BuildHasher"))]
252pub struct HashColumn<K, V, S = RandomState>(HashMap<K, V, S>);
253
254/// An unindexed column with keys of type `Ustr`.
255pub type UstrColumn<V> = HashColumn<Ustr, V, BuildHasherDefault<IdentityHasher>>;
256
257impl<K, V, S> Mapping for HashColumn<K, V, S>
258where
259    K: Eq + Hash + Clone,
260    V: Eq + Clone,
261    S: BuildHasher,
262{
263    type Dom = K;
264    type Cod = V;
265
266    fn apply(&self, x: &K) -> Option<V> {
267        self.0.get(x).cloned()
268    }
269    fn is_set(&self, x: &K) -> bool {
270        self.0.contains_key(x)
271    }
272}
273
274impl<K, V, S> MutMapping for HashColumn<K, V, S>
275where
276    K: Eq + Hash + Clone,
277    V: Eq + Clone,
278    S: BuildHasher,
279{
280    fn get(&self, x: &K) -> Option<&V> {
281        self.0.get(x)
282    }
283    fn set(&mut self, x: K, y: V) -> Option<V> {
284        self.0.insert(x, y)
285    }
286    fn unset(&mut self, x: &K) -> Option<V> {
287        self.0.remove(x)
288    }
289}
290
291impl<K, V, S> Column for HashColumn<K, V, S>
292where
293    K: Eq + Hash + Clone,
294    V: Eq + Clone,
295    S: BuildHasher,
296{
297    fn iter(&self) -> impl Iterator<Item = (K, &V)> {
298        self.0.iter().map(|(k, v)| (k.clone(), v))
299    }
300
301    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
302        self.0.values()
303    }
304
305    fn is_empty(&self) -> bool {
306        self.0.is_empty()
307    }
308}
309
310/** An index in a column.
311
312An index is a cache of preimages of a mapping, like an index in a relational
313database. For the time being, indices are not a public interface, just a
314convenient abstraction for implementing columns.
315*/
316trait Index {
317    type Dom;
318    type Cod;
319
320    /// Gets the cached preimage.
321    fn preimage(&self, y: &Self::Cod) -> impl Iterator<Item = Self::Dom>;
322
323    /// Inserts a new pair into the index.
324    fn insert(&mut self, x: Self::Dom, y: &Self::Cod);
325
326    /** Removes a pair from the index.
327
328    Assumes that the pair is already indexed, and may panic if not.
329     */
330    fn remove(&mut self, x: &Self::Dom, y: &Self::Cod);
331}
332
333/** An index implemented as a vector of vectors.
334 */
335#[derive(Clone, Derivative)]
336#[derivative(Default(bound = ""))]
337struct VecIndex<T>(Vec<Vec<T>>);
338
339impl<T: Eq + Clone> Index for VecIndex<T> {
340    type Dom = T;
341    type Cod = usize;
342
343    fn preimage(&self, y: &usize) -> impl Iterator<Item = T> {
344        let iter = match self.0.get(*y) {
345            Some(vec) => vec.iter(),
346            None => ([] as [T; 0]).iter(),
347        };
348        iter.cloned()
349    }
350
351    fn insert(&mut self, x: T, y: &usize) {
352        let i = *y;
353        if i >= self.0.len() {
354            self.0.resize_with(i + 1, Default::default);
355        }
356        self.0[i].push(x);
357    }
358
359    fn remove(&mut self, x: &T, y: &usize) {
360        let vec = &mut self.0[*y];
361        let i = vec.iter().rposition(|w| *w == *x).unwrap();
362        vec.remove(i);
363    }
364}
365
366/** An index implemented by a hash map into vectors.
367 */
368#[derive(Clone, Derivative, Debug)]
369#[derivative(Default(bound = "S: Default"))]
370struct HashIndex<X, Y, S = RandomState>(HashMap<Y, Vec<X>, S>);
371
372impl<X, Y, S> Index for HashIndex<X, Y, S>
373where
374    X: Eq + Clone,
375    Y: Eq + Hash + Clone,
376    S: BuildHasher,
377{
378    type Dom = X;
379    type Cod = Y;
380
381    fn preimage(&self, y: &Y) -> impl Iterator<Item = X> {
382        let iter = match self.0.get(y) {
383            Some(vec) => vec.iter(),
384            None => ([] as [X; 0]).iter(),
385        };
386        iter.cloned()
387    }
388
389    fn insert(&mut self, x: X, y: &Y) {
390        match self.0.get_mut(y) {
391            Some(vec) => {
392                vec.push(x);
393            }
394            None => {
395                self.0.insert(y.clone(), vec![x]);
396            }
397        }
398    }
399
400    fn remove(&mut self, x: &X, y: &Y) {
401        let vec = self.0.get_mut(y).unwrap();
402        let i = vec.iter().rposition(|w| *w == *x).unwrap();
403        vec.remove(i);
404    }
405}
406
407/** An indexed column comprising a forward mapping and a separate index.
408
409This common pattern is used to implement more specific columns but, like the
410`Index` trait, is not directly exposed.
411 */
412#[derive(Clone, Derivative, Debug)]
413#[derivative(PartialEq, Eq)]
414struct IndexedColumn<Dom, Cod, Col, Ind> {
415    mapping: Col,
416    #[derivative(PartialEq = "ignore")]
417    index: Ind,
418    dom_type: PhantomData<Dom>,
419    cod_type: PhantomData<Cod>,
420}
421
422impl<Dom, Cod, Col, Ind> Default for IndexedColumn<Dom, Cod, Col, Ind>
423where
424    Col: Default,
425    Ind: Default,
426{
427    fn default() -> Self {
428        Self {
429            mapping: Default::default(),
430            index: Default::default(),
431            dom_type: PhantomData,
432            cod_type: PhantomData,
433        }
434    }
435}
436
437impl<Dom, Cod, Col, Ind> Mapping for IndexedColumn<Dom, Cod, Col, Ind>
438where
439    Dom: Eq + Clone,
440    Cod: Eq + Clone,
441    Col: Mapping<Dom = Dom, Cod = Cod>,
442{
443    type Dom = Dom;
444    type Cod = Cod;
445
446    fn apply(&self, x: &Dom) -> Option<Cod> {
447        self.mapping.apply(x)
448    }
449    fn is_set(&self, x: &Dom) -> bool {
450        self.mapping.is_set(x)
451    }
452}
453
454impl<Dom, Cod, Col, Ind> MutMapping for IndexedColumn<Dom, Cod, Col, Ind>
455where
456    Dom: Eq + Clone,
457    Cod: Eq + Clone,
458    Col: MutMapping<Dom = Dom, Cod = Cod>,
459    Ind: Index<Dom = Dom, Cod = Cod>,
460{
461    fn get(&self, x: &Dom) -> Option<&Cod> {
462        self.mapping.get(x)
463    }
464
465    fn set(&mut self, x: Dom, y: Cod) -> Option<Cod> {
466        let old = self.unset(&x);
467        self.index.insert(x.clone(), &y);
468        self.mapping.set(x, y);
469        old
470    }
471
472    fn unset(&mut self, x: &Dom) -> Option<Cod> {
473        let old = self.mapping.unset(x);
474        if let Some(ref y) = old {
475            self.index.remove(x, y);
476        }
477        old
478    }
479}
480
481impl<Dom, Cod, Col, Ind> Column for IndexedColumn<Dom, Cod, Col, Ind>
482where
483    Dom: Eq + Clone,
484    Cod: Eq + Clone,
485    Col: Column<Dom = Dom, Cod = Cod>,
486    Ind: Index<Dom = Dom, Cod = Cod>,
487{
488    fn iter(&self) -> impl Iterator<Item = (Dom, &Cod)> {
489        self.mapping.iter()
490    }
491    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
492        self.mapping.values()
493    }
494    fn preimage(&self, y: &Cod) -> impl Iterator<Item = Dom> {
495        self.index.preimage(y)
496    }
497    fn is_empty(&self) -> bool {
498        self.mapping.is_empty()
499    }
500}
501
502/** An indexed column backed by an integer-valued vector.
503
504The column has the natural numbers (`usize`) as both its domain and codomain,
505making it suitable for use with skeletal finite sets.
506*/
507#[derive(Clone, Derivative, PartialEq, Eq)]
508#[derivative(Default(bound = ""))]
509pub struct SkelIndexedColumn(IndexedColumn<usize, usize, VecColumn<usize>, VecIndex<usize>>);
510
511impl SkelIndexedColumn {
512    /// Creates a new vector-backed column from an existing vector.
513    pub fn new(values: &[usize]) -> Self {
514        let mut col: Self = Default::default();
515        for (x, y) in values.iter().enumerate() {
516            col.set(x, *y);
517        }
518        col
519    }
520}
521
522impl Mapping for SkelIndexedColumn {
523    type Dom = usize;
524    type Cod = usize;
525    fn apply(&self, x: &usize) -> Option<usize> {
526        self.0.apply(x)
527    }
528    fn is_set(&self, x: &usize) -> bool {
529        self.0.is_set(x)
530    }
531}
532
533impl MutMapping for SkelIndexedColumn {
534    fn get(&self, x: &usize) -> Option<&usize> {
535        self.0.get(x)
536    }
537    fn set(&mut self, x: usize, y: usize) -> Option<usize> {
538        self.0.set(x, y)
539    }
540    fn unset(&mut self, x: &usize) -> Option<usize> {
541        self.0.unset(x)
542    }
543}
544
545impl Column for SkelIndexedColumn {
546    fn iter(&self) -> impl Iterator<Item = (usize, &usize)> {
547        self.0.iter()
548    }
549    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
550        self.0.values()
551    }
552    fn preimage(&self, y: &usize) -> impl Iterator<Item = usize> {
553        self.0.preimage(y)
554    }
555    fn is_empty(&self) -> bool {
556        self.0.is_empty()
557    }
558}
559
560/** An indexed column backed by a vector.
561
562The domain of the column is the natural numbers (`usize`). Since the codomain is
563an arbitrary type (`T`), the index is implemented using a hash map.
564*/
565#[derive(Clone, Derivative, PartialEq, Eq)]
566#[derivative(Default(bound = ""))]
567pub struct IndexedVecColumn<T>(IndexedColumn<usize, T, VecColumn<T>, HashIndex<usize, T>>);
568
569impl<T: Eq + Hash + Clone> IndexedVecColumn<T> {
570    /// Creates a new vector-backed column from an existing vector.
571    pub fn new(values: &[T]) -> Self {
572        let mut col: Self = Default::default();
573        for (x, y) in values.iter().cloned().enumerate() {
574            col.set(x, y);
575        }
576        col
577    }
578}
579
580impl<T: Eq + Hash + Clone> Mapping for IndexedVecColumn<T> {
581    type Dom = usize;
582    type Cod = T;
583    fn apply(&self, x: &usize) -> Option<T> {
584        self.0.apply(x)
585    }
586    fn is_set(&self, x: &usize) -> bool {
587        self.0.is_set(x)
588    }
589}
590
591impl<T: Eq + Hash + Clone> MutMapping for IndexedVecColumn<T> {
592    fn get(&self, x: &usize) -> Option<&T> {
593        self.0.get(x)
594    }
595    fn set(&mut self, x: usize, y: T) -> Option<T> {
596        self.0.set(x, y)
597    }
598    fn unset(&mut self, x: &usize) -> Option<T> {
599        self.0.unset(x)
600    }
601}
602
603impl<T: Eq + Hash + Clone> Column for IndexedVecColumn<T> {
604    fn iter(&self) -> impl Iterator<Item = (usize, &T)> {
605        self.0.iter()
606    }
607    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
608        self.0.values()
609    }
610    fn preimage(&self, y: &T) -> impl Iterator<Item = usize> {
611        self.0.preimage(y)
612    }
613    fn is_empty(&self) -> bool {
614        self.0.is_empty()
615    }
616}
617
618/// An indexed column backed by hash maps.
619#[derive(Clone, Derivative, Debug)]
620#[derivative(Default(bound = "S: Default"))]
621#[derivative(PartialEq(bound = "K: Eq + Hash, V: PartialEq, S: BuildHasher"))]
622#[derivative(Eq(bound = "K: Eq + Hash, V: Eq, S: BuildHasher"))]
623#[allow(clippy::type_complexity)]
624pub struct IndexedHashColumn<K, V, S = RandomState>(
625    IndexedColumn<K, V, HashColumn<K, V, S>, HashIndex<K, V, S>>,
626);
627
628/// An indexed column with keys and values of type `Ustr`.
629#[allow(clippy::type_complexity)]
630pub type IndexedUstrColumn = IndexedHashColumn<Ustr, Ustr, BuildHasherDefault<IdentityHasher>>;
631
632impl<K, V, S> Mapping for IndexedHashColumn<K, V, S>
633where
634    K: Eq + Hash + Clone,
635    V: Eq + Hash + Clone,
636    S: BuildHasher,
637{
638    type Dom = K;
639    type Cod = V;
640    fn apply(&self, x: &K) -> Option<V> {
641        self.0.apply(x)
642    }
643    fn is_set(&self, x: &K) -> bool {
644        self.0.is_set(x)
645    }
646}
647
648impl<K, V, S> MutMapping for IndexedHashColumn<K, V, S>
649where
650    K: Eq + Hash + Clone,
651    V: Eq + Hash + Clone,
652    S: BuildHasher,
653{
654    fn get(&self, x: &K) -> Option<&V> {
655        self.0.get(x)
656    }
657    fn set(&mut self, x: K, y: V) -> Option<V> {
658        self.0.set(x, y)
659    }
660    fn unset(&mut self, x: &K) -> Option<V> {
661        self.0.unset(x)
662    }
663}
664
665impl<K, V, S> Column for IndexedHashColumn<K, V, S>
666where
667    K: Eq + Hash + Clone,
668    V: Eq + Hash + Clone,
669    S: BuildHasher,
670{
671    fn iter(&self) -> impl Iterator<Item = (K, &V)> {
672        self.0.iter()
673    }
674    fn values(&self) -> impl Iterator<Item = &Self::Cod> {
675        self.0.values()
676    }
677    fn preimage(&self, y: &V) -> impl Iterator<Item = K> {
678        self.0.preimage(y)
679    }
680    fn is_empty(&self) -> bool {
681        self.0.is_empty()
682    }
683}
684
685#[cfg(test)]
686mod tests {
687    use super::super::set::SkelFinSet;
688    use super::*;
689
690    #[test]
691    fn vec_column() {
692        let mut col = VecColumn::new(vec!["foo", "bar", "baz"]);
693        assert!(!col.is_empty());
694        assert!(col.is_set(&2));
695        assert_eq!(col.get(&2), Some(&"baz"));
696        assert_eq!(col.apply(&2), Some("baz"));
697        assert_eq!(col.apply(&3), None);
698        assert_eq!(col.update(2, None), Some("baz"));
699        assert!(!col.is_set(&2));
700
701        col.set(4, "baz");
702        col.set(3, "bar");
703        let preimage: Vec<_> = col.preimage(&"bar").collect();
704        assert_eq!(preimage, vec![1, 3]);
705    }
706
707    #[test]
708    fn hash_column() {
709        let mut col: HashColumn<char, &str> = Default::default();
710        assert!(col.is_empty());
711        col.set('a', "foo");
712        col.set('b', "bar");
713        col.set('c', "baz");
714        assert!(!col.is_empty());
715        assert_eq!(col.get(&'c'), Some(&"baz"));
716        assert_eq!(col.apply(&'c'), Some("baz"));
717        assert_eq!(col.unset(&'c'), Some("baz"));
718        assert!(!col.is_set(&'c'));
719        col.set('c', "bar");
720
721        let mut preimage: Vec<_> = col.preimage(&"bar").collect();
722        preimage.sort();
723        assert_eq!(preimage, vec!['b', 'c']);
724    }
725
726    #[test]
727    fn skel_indexed_column() {
728        let mut col = SkelIndexedColumn::new(&[1, 3, 5]);
729        assert!(!col.is_empty());
730        assert!(col.is_set(&2));
731        assert_eq!(col.get(&2), Some(&5));
732        assert_eq!(col.apply(&2), Some(5));
733        let preimage: Vec<_> = col.preimage(&5).collect();
734        assert_eq!(preimage, vec![2]);
735
736        assert_eq!(col.set(0, 5), Some(1));
737        assert_eq!(col.preimage(&1).count(), 0);
738        let mut preimage: Vec<_> = col.preimage(&5).collect();
739        preimage.sort();
740        assert_eq!(preimage, vec![0, 2]);
741    }
742
743    #[test]
744    fn indexed_vec_column() {
745        let mut col = IndexedVecColumn::new(&["foo", "bar", "baz"]);
746        assert!(!col.is_empty());
747        assert!(col.is_set(&2));
748        assert_eq!(col.apply(&2), Some("baz"));
749        let preimage: Vec<_> = col.preimage(&"baz").collect();
750        assert_eq!(preimage, vec![2]);
751
752        assert_eq!(col.set(0, "baz"), Some("foo"));
753        assert_eq!(col.preimage(&"foo").count(), 0);
754        let mut preimage: Vec<_> = col.preimage(&"baz").collect();
755        preimage.sort();
756        assert_eq!(preimage, vec![0, 2]);
757    }
758
759    #[test]
760    fn indexed_hash_column() {
761        let mut col: IndexedHashColumn<char, &str> = Default::default();
762        assert!(col.is_empty());
763        col.set('a', "foo");
764        col.set('b', "bar");
765        col.set('c', "baz");
766        assert!(!col.is_empty());
767        assert_eq!(col.apply(&'c'), Some("baz"));
768        let preimage: Vec<_> = col.preimage(&"baz").collect();
769        assert_eq!(preimage, vec!['c']);
770
771        assert_eq!(col.set('a', "baz"), Some("foo"));
772        assert_eq!(col.preimage(&"foo").count(), 0);
773        let mut preimage: Vec<_> = col.preimage(&"baz").collect();
774        preimage.sort();
775        assert_eq!(preimage, vec!['a', 'c']);
776    }
777
778    #[test]
779    fn validate_function() {
780        let col = VecColumn::new(vec![1, 2, 4]);
781        let validate = |m, n| Function(&col, &SkelFinSet::from(m), &SkelFinSet::from(n)).validate();
782        assert!(validate(3, 5).is_ok());
783        assert_eq!(validate(4, 5).unwrap_err(), NonEmpty::new(InvalidFunction::Dom::<usize>(3)));
784        assert_eq!(validate(3, 4).unwrap_err(), NonEmpty::new(InvalidFunction::Cod::<usize>(2)));
785    }
786}
catlog/zero/column.rs

catlog/zero/
column.rs
