Crate indexical

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

define_index_type

Creates a new index type and associates it with an object type.

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

FromIndexicalIterator

Generic interface for converting iterators into indexical collections.

IndexedValue

Links a type to its index.

IndexicalIteratorExt

Extension trait that adds collect_indexical to all iterators.

ToIndex

Implicit conversions from elements to indexes. Commonly used in the IndexSet and IndexMatrix interfaces.