Crate prime_bag

prime bag

A bag datatype that used unsigned integers for storage. This works by assigning each possible item a prime number. The contents of the bag is represented by the product of those prime numbers. This works best if the set of possible items is constrained and some items are much more common than others. To maximize the possible size of the bag, assign lower prime numbers to more common items.

Using prime bags, certain operations can be done very efficiently: Adding an element or combining two bags is achieved by multiplication. Removing an element or bag of elements is achieved by division. Testing for the presence of an element is achieved by modulus.

Set Operation	Math Operation
Insert / Extend	Multiplication
Remove	Division
Contains / Superset	Modulus
Intersection	Greatest Common Factor

Elements of the Bag must implement PrimeBagElement Currently only 128 different element values are supported, but if necessary I could increase this

Getting started

use prime_bag::*;

#[derive(Debug)]
pub struct MyElement(usize);

impl PrimeBagElement for MyElement {
    fn into_prime_index(&self) -> usize {
        self.0
    }

    fn from_prime_index(value: usize) -> Self {
        Self(value)
    }
}

fn main() {
    let bag = PrimeBag16::<MyElement>::try_from_iter([MyElement(1), MyElement(2), MyElement(2)]).unwrap();
    let bag2 = bag.try_extend([MyElement(3), MyElement(3), MyElement(3)]).unwrap();

    let items : Vec<(MyElement, core::num::NonZeroUsize)> = bag2.iter_groups().collect();
    let inner_items: Vec<(usize, usize)> = items.into_iter().map(|(element, count)|(element.0, count.get())).collect();

    assert_eq!(inner_items, vec![(1,1), (2,2), (3,3)])
}

Modules

• group_iter
  Iterator of groups of elements
• iter
  Iterator of elements

Structs

• PrimeBag8
  Represents a bag (multi-set) of elements The bag will have a maximum capacity Use larger sized bags (e.g. PrimeBag64``, PrimeBag128`)
• PrimeBag16
  Represents a bag (multi-set) of elements The bag will have a maximum capacity Use larger sized bags (e.g. PrimeBag64``, PrimeBag128`)
• PrimeBag32
  Represents a bag (multi-set) of elements The bag will have a maximum capacity Use larger sized bags (e.g. PrimeBag64``, PrimeBag128`)
• PrimeBag64
  Represents a bag (multi-set) of elements The bag will have a maximum capacity Use larger sized bags (e.g. PrimeBag64``, PrimeBag128`)
• PrimeBag128
  Represents a bag (multi-set) of elements The bag will have a maximum capacity Use larger sized bags (e.g. PrimeBag64``, PrimeBag128`)

Traits

• PrimeBagElement
  Indicates a type that can be put into a Prime Bag To implement correctly, every possible value of this type must map to a unique number And that number must map back to that element. To maximize possible bag size and performance, use the lowest numbers possible and assign lower numbers to more common elements. The element which maps to 0 will be able to use compiler intrinsics for some operations, particularly count_instances making them much faster