Struct dahl_partition::Partition

pub struct Partition { /* fields omitted */ }

A partition of n_items is a set of subsets such that the subsets are mutually exclusive, nonempty, and exhaustive. This data structure enforces mutually exclusivity and provides methods to test for the other two properties: subsets_are_nonempty and subsets_are_exhaustive. Zero-based numbering is used, e.g., the first item is index 0 and the first subset is subset 0. When a subset is added to the data structure, the next available integer label is used for its subset index. To remove empty subsets and relabel subsets into the canonical form, use the canonicalize method.

Methods

impl Partition

pub fn new(n_items: usize) -> Partition

Instantiates a partition for n_items, none of which are initially allocated.

Examples

use dahl_partition::*;
let partition = Partition::new(10);
assert_eq!(partition.n_items(), 10);
assert_eq!(partition.n_subsets(), 0);
assert_eq!(partition.to_string(), "_ _ _ _ _ _ _ _ _ _");

pub fn one_subset(n_items: usize) -> Partition

Instantiates a partition for n_items, with all items allocated to one subset.

pub fn singleton_subsets(n_items: usize) -> Partition

Instantiates a partition for n_items, with each item allocated to its own subset.

pub fn from<T>(labels: &[T]) -> Partition where
    T: Eq + Hash, 

Instantiates a partition from a slice of subset labels. Items i and j are in the subset if and only if their labels are equal.

Examples

use dahl_partition::*;
let labels = vec!('a', 'a', 'a', 't', 't', 'a', 'a', 'w', 'a', 'w');
let partition1 = Partition::from(&labels[..]);
let partition2 = Partition::from(&[2,2,2,5,5,2,2,7,2,7]);
let partition3 = Partition::from("AAABBAACAC".as_bytes());
assert_eq!(partition1, partition2);
assert_eq!(partition2, partition3);
assert_eq!(partition1.n_items(), labels.len());
assert_eq!(partition1.n_subsets(), {
    let mut x = labels.clone();
    x.sort();
    x.dedup();
    x.len()
});
assert_eq!(partition1.to_string(), "0 0 0 1 1 0 0 2 0 2");

pub fn iter(n_items: usize) -> PartitionIterator

An iterator over all possible partitions for the specified number of items.

pub fn iter_sharded(n_shards: u32, n_items: usize) -> Vec<PartitionIterator>

A vector of iterators, which together go over all possible partitions for the specified number of items. This can be useful in multi-thread situations.

pub fn n_items(&self) -> usize

Number of items that can be allocated to the partition.

Examples

use dahl_partition::*;
let partition = Partition::from("AAABBAACAC".as_bytes());
assert_eq!(partition.n_items(), 10);

pub fn n_subsets(&self) -> usize

Number of subsets in the partition.

Examples

use dahl_partition::*;
let mut partition = Partition::from("AAABBAACAC".as_bytes());
assert_eq!(partition.n_subsets(), 3);
partition.remove(7);
partition.remove(9);
assert_eq!(partition.n_subsets(), 3);
partition.canonicalize();
assert_eq!(partition.n_subsets(), 2);

pub fn labels_via_copying(&self) -> Vec<usize>

A vector of length n_items whose elements are subset labels. Panics if any items are not allocated.

pub fn labels(&self) -> &Vec<Option<usize>>

A reference to a vector of length n_items whose elements are None for items that are not allocated (i.e., missing) and, for items that are allocated, Some(subset_index) where subset_index is the index of the subset to which the item is allocated.

pub fn label_of(&self, item_index: usize) -> Option<usize>

Either None for an item that is not allocated (i.e., missing) and, for an item that is allocated, Some(subset_index) where subset_index is the index of the subset to which the item is allocated.

pub fn subsets(&self) -> &Vec<Subset>

A reference to a vector of length n_subsets giving subsets, some of which may be empty.

pub fn clean_subset(&mut self, subset_index: usize)

A reference to a vector of length n_subsets giving subsets, some of which may be empty.

pub fn new_subset(&mut self)

Add a new empty subset to the partition.

Examples

use dahl_partition::*;
let mut partition = Partition::from("AAABBAACAC".as_bytes());
assert_eq!(partition.n_subsets(), 3);
assert!(partition.subsets_are_nonempty());
partition.new_subset();
assert!(!partition.subsets_are_nonempty());
assert_eq!(partition.n_subsets(), 4);

pub fn add(&mut self, item_index: usize) -> &mut Partition

Add a new subset containing item_index to the partition.

Examples

use dahl_partition::*;
let mut partition = Partition::new(3);
partition.add(1);
assert_eq!(partition.to_string(), "_ 0 _");
partition.add(0);
assert_eq!(partition.to_string(), "1 0 _");
partition.canonicalize();
assert_eq!(partition.to_string(), "0 1 _");

pub fn add_with_index(
    &mut self,
    item_index: usize,
    subset_index: usize
) -> &mut Partition

Add item item_index to the subset subset_index of the partition.

Examples

use dahl_partition::*;
let mut partition = Partition::new(3);
partition.add(1);
assert_eq!(partition.to_string(), "_ 0 _");
partition.add_with_index(2, 0);
assert_eq!(partition.to_string(), "_ 0 0");

pub fn remove(&mut self, item_index: usize) -> &mut Partition

Remove item item_index from the partition.

Examples

use dahl_partition::*;
let mut partition = Partition::from("AAABBAACAC".as_bytes());
partition.remove(1);
partition.remove(4);
assert_eq!(partition.to_string(), "0 _ 0 1 _ 0 0 2 0 2");
partition.remove(3);
assert_eq!(partition.to_string(), "0 _ 0 _ _ 0 0 2 0 2");
partition.canonicalize();
assert_eq!(partition.to_string(), "0 _ 0 _ _ 0 0 1 0 1");

pub fn remove_with_index(
    &mut self,
    item_index: usize,
    subset_index: usize
) -> &mut Partition

Remove item item_index from the subset subset_index of the partition.

Examples

use dahl_partition::*;
let mut partition = Partition::from("AAABBAACAC".as_bytes());
partition.remove_with_index(1,0);
partition.remove_with_index(4,1);
assert_eq!(partition.to_string(), "0 _ 0 1 _ 0 0 2 0 2");
partition.remove_with_index(3,1);
assert_eq!(partition.to_string(), "0 _ 0 _ _ 0 0 2 0 2");
partition.canonicalize();
assert_eq!(partition.to_string(), "0 _ 0 _ _ 0 0 1 0 1");

pub fn pop(&mut self, subset_index: usize) -> Option<usize>

Removes that last item from the subset subset_index of the partition. This may or may not be the most recently added item.

Examples

use dahl_partition::*;
let mut partition = Partition::from("AAABBAACAC".as_bytes());
assert_eq!(partition.pop(1),Some(4));

pub fn transfer(&mut self, item_index: usize) -> &mut Partition

Transfers item item_index to a new empty subset.

pub fn transfer_with_index(
    &mut self,
    item_index: usize,
    old_subset_index: usize,
    new_subset_index: usize
) -> &mut Partition

Transfers item item_index from the subset old_subset_index to another subset new_subset_index.

pub fn canonicalize(&mut self) -> &mut Partition

Put partition into canonical form, removing empty subsets and consecutively numbering subsets starting at 0.

Examples

use dahl_partition::*;
let mut partition = Partition::new(3);
partition.add(1);
assert_eq!(partition.to_string(), "_ 0 _");
partition.add(0);
assert_eq!(partition.to_string(), "1 0 _");
partition.canonicalize();
assert_eq!(partition.to_string(), "0 1 _");

pub fn subsets_are_exhaustive(&self) -> bool

Test whether subsets are exhaustive.

pub fn subsets_are_nonempty(&self) -> bool

Test whether subsets are nonempty.

Trait Implementations

impl PartialEq<Partition> for Partition

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use] fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl Clone for Partition

fn clone(&self) -> Partition

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Display for Partition

fn fmt(&self, fmt: &mut Formatter) -> Result

Formats the value using the given formatter.

impl Debug for Partition

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.