Struct Partition

pub struct Partition { /* private fields */ }

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.

Implementations

impl Partition

pub fn new(n_items: usize) -> Self

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) -> Self

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

pub fn singleton_subsets(n_items: usize) -> Self

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

pub fn from<T>(labels: &[T]) -> Self

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_into_slice<T, U>(&self, slice: &mut [T], f: U)

where U: Fn(&Option<usize>) -> T,

Copy subset labels into a slice. Panics if any items are not allocated or if the slice is not the correct length.

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) or, 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 subset_of(&self, item_index: usize) -> Option<&Subset>

Either None for an item that is not allocated (i.e., missing) or, for an item that is allocated, Some(&subset) where &subset is a reference to the subset to which the item is allocated.

pub fn paired(&self, item1_index: usize, item2_index: usize) -> bool

Returns true if and only if both items are allocated (i.e., not missing) and are allocated to the same subset.

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

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

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 Self

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 Self

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 Self

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_clean_and_relabel<T>( &mut self, item_index: usize, callback: T, ) -> &mut Self

where T: FnMut(usize, usize),

Remove item item_index from the partition and, if this creates an empty subset, relabel.

Examples

use dahl_partition::*;
let mut partition = Partition::from("AAABBAACAC".as_bytes());
partition.remove_clean_and_relabel(1, |x,y| {});
partition.remove_clean_and_relabel(4, |x,y| {});
partition.remove_clean_and_relabel(3, |x,y| {});
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 Self

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_item(&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_item(1),Some(4));

pub fn pop_subset(&mut self) -> Option<Subset>

Removes that last subset of the partition if it empty.

Examples

use dahl_partition::*;
let mut partition = Partition::from("AAABBAACAC".as_bytes());
partition.new_subset();
assert_ne!(partition.pop_subset(),None);

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

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 Self

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

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

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);
partition.add(2);
partition.add(0);
assert_eq!(partition.to_string(), "2 0 1");
partition.canonicalize();
assert_eq!(partition.to_string(), "0 1 2");

pub fn canonicalize_by_permutation( &mut self, permutation: Option<&Permutation>, ) -> &mut Self

Put partition into canonical form according to a permutation, removing empty subsets and consecutively numbering subsets starting at 0 based on the supplied permutation. If None is supplied, the natural permutation is used.

Examples

use dahl_partition::*;
use std::fs::canonicalize;
let mut partition = Partition::new(3);
partition.add(1);
partition.add(2);
partition.add(0);
assert_eq!(partition.to_string(), "2 0 1");
partition.canonicalize_by_permutation(Some(&Permutation::from_slice(&[0,2,1]).unwrap()));
assert_eq!(partition.to_string(), "0 2 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 Clone for Partition

fn clone(&self) -> Partition

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Partition

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

Formats the value using the given formatter.

impl Display for Partition

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

Formats the value using the given formatter.

impl PartialEq for Partition

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

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.