#![allow(dead_code)]
pub mod distribution;
pub mod summary;
use std::cmp::Ordering;
use std::collections::HashMap;
use std::collections::HashSet;
use std::fmt;
use std::hash::Hash;
#[derive(Debug, Clone)]
pub struct Partition {
n_items: usize,
n_allocated_items: usize,
subsets: Vec<Subset>,
labels: Vec<Option<usize>>,
}
impl Partition {
pub fn new(n_items: usize) -> Partition {
Partition {
n_items,
n_allocated_items: 0,
subsets: Vec::new(),
labels: vec![None; n_items],
}
}
pub fn from<T>(labels: &[T]) -> Partition
where
T: Eq + Hash,
{
let n_items = labels.len();
let mut new_labels = vec![None; n_items];
let mut subsets = Vec::new();
let mut map = HashMap::new();
let mut next_label: usize = 0;
for i in 0..labels.len() {
let key = &labels[i];
let label = map.entry(key).or_insert_with(|| {
subsets.push(Subset::new());
let label = next_label;
next_label += 1;
label
});
subsets[*label].add(i);
new_labels[i] = Some(*label);
}
Partition {
n_items,
n_allocated_items: n_items,
subsets,
labels: new_labels,
}
}
pub fn n_items(&self) -> usize {
self.n_items
}
pub fn n_subsets(&self) -> usize {
self.subsets.len()
}
pub fn labels(&self) -> Vec<usize> {
self.labels.iter().map(|x| x.unwrap()).collect()
}
pub fn labels_with_missing(&self) -> &Vec<Option<usize>> {
&self.labels
}
pub fn subsets(&self) -> &Vec<Subset> {
&self.subsets
}
pub fn new_subset(&mut self) {
self.subsets.push(Subset::new());
}
pub fn add(&mut self, item_index: usize) -> &mut Partition {
self.check_item_index(item_index);
self.check_not_allocated(item_index);
self.n_allocated_items += 1;
self.subsets.push(Subset::new());
self.add_engine(item_index, self.subsets.len() - 1);
self
}
pub fn add_with_index(&mut self, item_index: usize, subset_index: usize) -> &mut Partition {
self.check_item_index(item_index);
self.check_not_allocated(item_index);
self.check_subset_index(subset_index);
self.n_allocated_items += 1;
self.add_engine(item_index, subset_index);
self
}
pub fn remove(&mut self, item_index: usize) -> &mut Partition {
self.check_item_index(item_index);
self.remove_engine(item_index, self.check_allocated(item_index));
self
}
pub fn remove_with_index(&mut self, item_index: usize, subset_index: usize) -> &mut Partition {
self.check_item_index(item_index);
self.check_item_in_subset(item_index, subset_index);
self.remove_engine(item_index, subset_index);
self
}
pub fn transfer(&mut self, item_index: usize) -> &mut Partition {
self.check_item_index(item_index);
let subset_index = self.check_allocated(item_index);
self.subsets[subset_index].remove(item_index);
self.subsets.push(Subset::new());
self.add_engine(item_index, self.subsets.len() - 1);
self
}
pub fn transfer_with_index(
&mut self,
item_index: usize,
old_subset_index: usize,
new_subset_index: usize,
) -> &mut Partition {
self.check_item_index(item_index);
self.check_item_in_subset(item_index, old_subset_index);
self.check_subset_index(new_subset_index);
self.subsets[old_subset_index].remove(item_index);
self.add_engine(item_index, new_subset_index);
self
}
pub fn canonicalize(&mut self) -> &mut Partition {
if self.n_allocated_items == 0 {
return self;
}
let mut new_labels = vec![None; self.n_items];
let mut next_label: usize = 0;
for i in 0..self.n_items {
match new_labels[i] {
Some(_) => (),
None => match self.labels[i] {
None => (),
Some(subset_index) => {
let subset = &mut self.subsets[subset_index];
subset.clean();
let some_label = Some(next_label);
next_label += 1;
for j in subset.vector.iter() {
new_labels[*j] = some_label;
}
}
},
}
}
self.subsets.sort_unstable_by(|x, y| {
if x.is_empty() {
if y.is_empty() {
Ordering::Equal
} else {
Ordering::Greater
}
} else {
if y.is_empty() {
Ordering::Less
} else {
new_labels[x.vector[0]]
.unwrap()
.cmp(&new_labels[y.vector[0]].unwrap())
}
}
});
while self.subsets.len() > 0 && self.subsets.last().unwrap().is_empty() {
self.subsets.pop();
}
self.labels = new_labels;
self
}
pub fn subsets_are_exhaustive(&self) -> bool {
self.n_allocated_items == self.n_items
}
pub fn subsets_are_nonempty(&self) -> bool {
self.subsets.iter().all(|x| !x.is_empty())
}
fn add_engine(&mut self, item_index: usize, subset_index: usize) {
self.labels[item_index] = Some(subset_index);
self.subsets[subset_index].add(item_index);
}
fn remove_engine(&mut self, item_index: usize, subset_index: usize) {
self.labels[item_index] = None;
self.subsets[subset_index].remove(item_index);
self.n_allocated_items -= 1;
}
fn check_item_index(&self, item_index: usize) {
if item_index >= self.n_items {
panic!(format!(
"Attempt to allocate item {} when only {} are available.",
item_index, self.n_items
));
};
}
fn check_subset_index(&self, subset_index: usize) {
if subset_index >= self.n_subsets() {
panic!(format!(
"Attempt to allocate to subset {} when only {} are available.",
subset_index,
self.n_subsets()
));
};
}
fn check_allocated(&self, item_index: usize) -> usize {
match self.labels[item_index] {
Some(subset_index) => subset_index,
None => panic!(format!("Item {} is not allocated.", item_index)),
}
}
fn check_not_allocated(&self, item_index: usize) {
match self.labels[item_index] {
Some(j) => panic!(format!(
"Item {} is already allocated to subset {}.",
item_index, j
)),
None => (),
};
}
fn check_item_in_subset(&self, item_index: usize, subset_index: usize) {
match self.labels[item_index] {
Some(j) => {
if j != subset_index {
panic!(format!(
"Item {} is already allocated to subset {}.",
item_index, j
));
};
}
None => panic!(format!(
"Item {} is not allocated to any subset.",
item_index
)),
};
}
}
impl fmt::Display for Partition {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
let mut str = "";
for i in 0..self.n_items {
fmt.write_str(str)?;
str = " ";
match self.labels[i] {
None => fmt.write_str("_")?,
Some(subset_index) => {
let x = subset_index.to_string();
fmt.write_str(&x[..])?;
}
};
}
Ok(())
}
}
impl PartialEq for Partition {
fn eq(&self, other: &Self) -> bool {
self.n_items() == other.n_items
&& self.n_allocated_items == other.n_allocated_items
&& self.subsets.len() == other.subsets.len()
&& {
let mut x = self.clone();
let x1 = x.canonicalize();
let mut y = other.clone();
let y1 = y.canonicalize();
x1.subsets == y1.subsets
}
}
}
#[cfg(test)]
mod tests_partition {
use super::*;
#[test]
fn test_complete() {
let mut p = Partition::new(6);
p.add(2);
for i in &[3, 4, 5] {
p.add_with_index(*i, 0);
}
assert_eq!(p.to_string(), "_ _ 0 0 0 0");
assert_eq!(p.subsets_are_exhaustive(), false);
p.add(1);
p.add_with_index(0, 1);
p.canonicalize();
assert_eq!(p.to_string(), "0 0 1 1 1 1");
p.remove_with_index(2, 1);
p.canonicalize();
assert_eq!(p.to_string(), "0 0 _ 1 1 1");
assert_ne!(p.subsets_are_exhaustive(), true);
p.remove_with_index(0, 0);
p.remove_with_index(1, 0);
assert_eq!(p.to_string(), "_ _ _ 1 1 1");
p.canonicalize();
assert_eq!(p.to_string(), "_ _ _ 0 0 0");
p.transfer(5);
p.transfer_with_index(3, 0, 1);
assert_eq!(p.to_string(), "_ _ _ 1 0 1");
p.add_with_index(1, 1);
assert_eq!(p.to_string(), "_ 1 _ 1 0 1");
p.canonicalize();
assert_eq!(p.to_string(), "_ 0 _ 0 1 0");
assert_eq!(p.n_subsets(), 2);
p.remove_with_index(4, 1);
assert_eq!(p.n_subsets(), 2);
p.canonicalize();
assert_eq!(p.n_subsets(), 1);
}
#[test]
fn test_canonicalize() {
let mut p = Partition::new(6);
p.add(0)
.add_with_index(1, 0)
.add(2)
.add_with_index(3, 1)
.add_with_index(4, 0);
assert_eq!(p.to_string(), "0 0 1 1 0 _");
p.add(5);
assert_eq!(p.to_string(), "0 0 1 1 0 2");
p.remove(2);
p.remove(3);
assert_eq!(p.to_string(), "0 0 _ _ 0 2");
p.canonicalize();
assert_eq!(p.to_string(), "0 0 _ _ 0 1");
}
#[test]
fn test_from() {
let p0 = Partition::from(&[45, 34, 23, 23, 23, 24, 45]);
assert_eq!(p0.to_string(), "0 1 2 2 2 3 0");
let p1 = Partition::from("ABCAADAABD".as_bytes());
assert_eq!(p1.to_string(), "0 1 2 0 0 3 0 0 1 3");
let p2 = Partition::from(p1.labels_with_missing());
assert_eq!(p1.to_string(), p2.to_string());
let p3 = Partition::from(p0.labels_with_missing());
assert_eq!(p0.to_string(), p3.to_string());
}
#[test]
fn test_equality() {
let p0 = Partition::from("ABCAADAABD".as_bytes());
let p1 = Partition::from("ABCAADAABD".as_bytes());
let p2 = Partition::from("ABCRRRRRRD".as_bytes());
assert_eq!(p0, p1);
assert_ne!(p0, p2);
}
}
#[derive(Debug, Clone)]
pub struct Subset {
n_items: usize,
set: HashSet<usize>,
vector: Vec<usize>,
is_clean: bool,
}
impl Subset {
fn new() -> Subset {
Subset {
n_items: 0,
set: HashSet::new(),
vector: Vec::new(),
is_clean: true,
}
}
fn from<'a, I>(x: I) -> Subset
where
I: Iterator<Item = &'a usize>,
{
let mut set = HashSet::new();
let mut vector = Vec::new();
let mut n_items = 0;
for i in x {
if set.insert(*i) {
n_items += 1;
vector.push(*i);
}
}
Subset {
n_items,
set,
vector,
is_clean: true,
}
}
fn add(&mut self, i: usize) -> bool {
if self.set.insert(i) {
self.n_items += 1;
if self.is_clean {
self.vector.push(i);
}
true
} else {
false
}
}
fn merge(&mut self, other: &Subset) -> bool {
let mut added = false;
if other.is_clean {
for i in other.vector.iter() {
added = self.add(*i) || added;
}
} else {
for i in other.set.iter() {
added = self.add(*i) || added;
}
}
added
}
fn remove(&mut self, i: usize) -> bool {
if self.set.remove(&i) {
self.n_items -= 1;
self.vector.clear();
self.is_clean = false;
true
} else {
false
}
}
fn clean(&mut self) {
if !self.is_clean {
for i in &self.set {
self.vector.push(*i);
}
self.is_clean = true;
}
}
pub fn n_items(&self) -> usize {
self.n_items
}
pub fn is_empty(&self) -> bool {
self.n_items == 0
}
pub fn items(&mut self) -> &Vec<usize> {
if !self.is_clean {
self.clean();
}
&self.vector
}
pub fn items_via_copying(&self) -> Vec<usize> {
if self.is_clean {
self.vector.clone()
} else {
let mut vector = Vec::new();
for i in &self.set {
vector.push(*i);
}
vector
}
}
}
impl fmt::Display for Subset {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
let mut clone = self.clone();
clone.clean();
clone.vector.sort_unstable();
fmt.write_str("{")?;
let mut str = "";
for i in clone.vector {
fmt.write_str(str)?;
fmt.write_str(&format!("{}", i))?;
str = ",";
}
fmt.write_str("}")?;
Ok(())
}
}
impl PartialEq for Subset {
fn eq(&self, other: &Self) -> bool {
self.set == other.set
}
}
#[cfg(test)]
mod tests_subset {
use super::*;
#[test]
fn test_add() {
let mut s = Subset::new();
assert_eq!(s.add(0), true);
assert_eq!(s.add(1), true);
assert_eq!(s.add(0), false);
assert_eq!(s.add(1), false);
assert_eq!(s.add(0), false);
assert_eq!(s.n_items(), 2);
assert_eq!(s.to_string(), "{0,1}");
}
#[test]
fn test_merge() {
let mut s1 = Subset::from([2, 1, 6, 2].iter());
let mut s2 = Subset::from([0, 2, 1].iter());
s1.merge(&mut s2);
assert_eq!(s1.to_string(), "{0,1,2,6}");
let mut s3 = Subset::from([7, 2].iter());
s3.merge(&mut s1);
assert_eq!(s3.to_string(), "{0,1,2,6,7}");
}
#[test]
fn test_remove() {
let mut s = Subset::from([2, 1, 6, 2].iter());
assert_eq!(s.remove(0), false);
assert_eq!(s.remove(2), true);
assert_eq!(s.to_string(), "{1,6}");
}
#[test]
fn test_equality() {
let s1 = Subset::from([2, 1, 6, 2].iter());
let s2 = Subset::from([6, 1, 2].iter());
assert_eq!(s1, s2);
let s3 = Subset::from([6, 1, 2, 3].iter());
assert_ne!(s1, s3);
}
}