#finite #bijection #enum #bitmap #compression

no-std cantor

A general toolkit for working with types that have a small number of values

4 releases

Uses new Rust 2021

0.1.3 May 6, 2022
0.1.2 Apr 17, 2022
0.1.1 Apr 6, 2022
0.1.0 Apr 5, 2022

#414 in Rust patterns

MIT/Apache

35KB
882 lines

Cantor is a general toolkit for working with types that have a small number of values (typically, but not exclusively enums). This crate defines the Finite trait and implements several efficient zero-allocation algorithms on top of it.

Applications

  • Iterating over possible values
  • Value compression
  • Array-based maps
  • Bitmap sets

Example

// Define a "Finite" type
#[derive(Finite, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug)]
enum MyType {
	A,
	B(bool),
	C(bool, bool)
}

// Value iteration
let mut num_values = 0;
for _ in MyType::iter() {
	num_values += 1;
}
assert_eq!(num_values, 7);

// Value compression
let value = MyType::B(false);
assert_eq!(size_of_val(&value), 3);
let compressed = compress(value);
assert_eq!(size_of_val(&compressed), 1);
assert_eq!(value, compressed.expand());

// Array map
let mut map = ArrayMap::default();
map[MyType::B(true)] = 1;
map[MyType::C(true, true)] = 2;
assert_eq!(map[MyType::A], 0);
assert_eq!(map[MyType::B(true)], 1);
assert_eq!(map[MyType::C(true, true)], 2);

// Bitmap set
let mut set = BitmapSet::none();
set.include(MyType::A);
set.include(MyType::B(false));
set.include(MyType::C(true, false));
assert_eq!(set.size(), 3);
assert!(set.contains(MyType::B(false)));
assert!(!set.contains(MyType::C(false, true)));

Dependencies

~240–650KB
~15K SLoC