Crate indexical

source ·
Expand description

Indexical: Human-Friendly Indexed Collections

Indexical is a library for conveniently and efficiently working with indexed collections of objects. “Indexed” means that the domain of objects is finite, and you can assign a numeric index to each object. This enables the use of efficient data structures like bit-sets.

Indexical is a layer on top of existing bit-set libraries like bitvec and rustc_index::bit_set. Those data structures only “understand” raw indexes, not the objects represented by the index. Indexical provides utilities for converting between the object domain and the index domain.

Example

use indexical::{IndexedDomain, IndexedValue, bitset::bitvec::IndexSet};
use std::rc::Rc;

// 1. Define a custom type.
#[derive(PartialEq, Eq, Clone, Hash)]
pub struct MyString(String);

// 2. Define a new index for your custom type.
indexical::define_index_type! {
    pub struct StringIndex for MyString = u32;
}

// 3. Create an immutable indexed domain from a collection of objects.
// By default this is Rc-wrapped, but you can also use Arc or &-refs.
let domain = Rc::new(IndexedDomain::from_iter([
    MyString(String::from("Hello")), MyString(String::from("world"))
]));

// 4. Now you can make a set! Notice how you can pass either a `MyString`
// or a `StringIndex` to `set.insert(..)` and `set.contains(..)`.
let mut set = IndexSet::new(&domain);
set.insert(MyString(String::from("Hello")));
set.insert(StringIndex::from_usize(1));
assert!(set.contains(&MyString(String::from("world"))));

Design

The key idea is that the IndexedDomain is shared pervasively across all Indexical types. All types can then use the IndexedDomain to convert between indexes and objects, usually via the ToIndex trait.

IndexSet and IndexMatrix are generic with respect to two things:

  1. The choice of bit-set implementation. By default, Indexical includes the bitvec crate and provides the bitset::bitvec::IndexSet type. You can provide your own bit-set implementation via the bitset::BitSet trait.
  2. The choice of domain pointer. By default, Indexical uses the Rc pointer via the RcFamily type. You can choose to use the ArcFamily if you need concurrency, or the RefFamily if you want to avoid reference-counting.

Modules

  • bitset
    Abstraction over bit-set implementations.
  • map
    Map-like collections for indexed keys.
  • pointer
    Abstraction over smart pointers.

Macros

Structs

  • IndexMatrix
    An unordered collections of pairs (R, C), implemented with a sparse bit-matrix.
  • IndexSet
    An unordered collections of Ts, implemented with a bit-set.
  • IndexedDomain
    An indexed collection of objects.
  • MarkerIndex
    Coherence hack for the ToIndex trait.
  • MarkerOwned
    Coherence hack for the ToIndex trait.
  • MarkerRef
    Coherence hack for the ToIndex trait.

Traits