use std::iter;
use std::slice;
use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
use std::collections::VecDeque;
use smallvec::SmallVec;
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum CubeVar {
False,
True,
DontCare,
}
const CUBE_ALLOCED_SIZE: usize = 16;
#[derive(Clone, Debug)]
pub struct Cube(SmallVec<[CubeVar; CUBE_ALLOCED_SIZE]>);
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum CubeMergeResult {
None,
CancelLeft,
CancelRight,
Merge(Cube),
ExpandLeft(Cube),
ExpandRight(Cube),
}
impl Cube {
pub fn true_cube(vars: usize) -> Cube {
Cube(iter::repeat(CubeVar::DontCare).take(vars).collect())
}
pub fn vars(&self) -> slice::Iter<CubeVar> {
self.0.iter()
}
pub fn merge_with(&self, other: &Cube) -> CubeMergeResult {
if self.0.len() != other.0.len() {
CubeMergeResult::None
} else if self == other {
CubeMergeResult::CancelRight
} else {
let mut mismatches = 0;
let mut mismatch_pos = 0;
let mut left_covered = 0;
let mut right_covered = 0;
for (i, (lvar, rvar)) in self.0.iter().zip(other.0.iter()).enumerate() {
match (lvar, rvar) {
(&CubeVar::False, &CubeVar::True) | (&CubeVar::True, &CubeVar::False) => {
mismatches += 1;
mismatch_pos = i;
}
(&CubeVar::False, &CubeVar::DontCare)
| (&CubeVar::True, &CubeVar::DontCare) => {
left_covered += 1;
}
(&CubeVar::DontCare, &CubeVar::False)
| (&CubeVar::DontCare, &CubeVar::True) => {
right_covered += 1;
}
_ => {}
}
}
if mismatches == 0 && left_covered > 0 && right_covered == 0 {
CubeMergeResult::CancelLeft
} else if mismatches == 0 && right_covered > 0 && left_covered == 0 {
CubeMergeResult::CancelRight
} else if mismatches == 1 && right_covered == 0 && left_covered == 0 {
CubeMergeResult::Merge(self.with_var(mismatch_pos, CubeVar::DontCare))
} else if mismatches == 1 && right_covered > 0 && left_covered == 0 {
CubeMergeResult::ExpandRight(other.with_var(mismatch_pos, CubeVar::DontCare))
} else if mismatches == 1 && right_covered == 0 && left_covered > 0 {
CubeMergeResult::ExpandLeft(self.with_var(mismatch_pos, CubeVar::DontCare))
} else {
CubeMergeResult::None
}
}
}
pub fn with_var(&self, idx: usize, val: CubeVar) -> Cube {
Cube(
self.0
.iter()
.enumerate()
.map(|(i, var)| {
if i == idx {
val.clone()
} else {
var.clone()
}
})
.collect(),
)
}
}
impl PartialEq for Cube {
fn eq(&self, other: &Self) -> bool {
self.cmp(other) == Ordering::Equal
}
}
impl Eq for Cube {}
impl PartialOrd for Cube {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Cube {
fn cmp(&self, other: &Self) -> Ordering {
self.0.iter().cmp(other.0.iter())
}
}
const CUBELIST_ALLOCED_SIZE: usize = 4;
#[derive(Clone, Debug)]
pub struct CubeList(SmallVec<[Cube; CUBE_ALLOCED_SIZE]>);
impl PartialEq for CubeList {
fn eq(&self, other: &Self) -> bool {
self.0.iter().cmp(other.0.iter()) == Ordering::Equal
}
}
impl CubeList {
pub fn new() -> CubeList {
CubeList(SmallVec::new())
}
pub fn from_list(cubes: &[Cube]) -> CubeList {
CubeList(cubes.iter().map(|c| c.clone()).collect())
}
pub fn cubes(&self) -> slice::Iter<Cube> {
self.0.iter()
}
pub fn merge(&self, other: &CubeList) -> CubeList {
let mut out: SmallVec<[Cube; CUBE_ALLOCED_SIZE]> = SmallVec::new();
let mut canceled: SmallVec<[bool; CUBE_ALLOCED_SIZE]> = SmallVec::new();
for cube in self.0.iter().chain(other.0.iter()) {
out.push(cube.clone());
canceled.push(false);
}
let mut worklist = VecDeque::new();
for i in 0..out.len() {
worklist.push_back(i);
}
while let Some(i) = worklist.pop_front() {
if canceled[i] {
continue;
}
for j in 0..out.len() {
if i == j {
continue;
}
if canceled[i] {
break;
}
if canceled[j] {
continue;
}
match out[i].merge_with(&out[j]) {
CubeMergeResult::None => {}
CubeMergeResult::CancelLeft => {
canceled[i] = true;
}
CubeMergeResult::CancelRight => {
canceled[j] = true;
}
CubeMergeResult::Merge(n) => {
out[i] = n;
worklist.push_back(i);
canceled[j] = true;
}
CubeMergeResult::ExpandLeft(n) => {
out[i] = n;
worklist.push_back(i);
}
CubeMergeResult::ExpandRight(n) => {
out[j] = n;
worklist.push_back(j);
}
}
}
}
let out = out.into_iter()
.zip(canceled.iter())
.filter(|&(_, flag)| !flag)
.map(|(cube, _)| cube)
.collect();
CubeList(out)
}
pub fn with_var(&self, idx: usize, val: CubeVar) -> CubeList {
CubeList(
self.0
.iter()
.map(|c| c.with_var(idx, val.clone()))
.collect(),
)
}
}
mod test {
use super::*;
fn make_cube(elems: &[u32]) -> Cube {
Cube(
elems
.iter()
.map(|i| match *i {
0 => CubeVar::False,
1 => CubeVar::True,
_ => CubeVar::DontCare,
})
.collect(),
)
}
#[test]
fn cube_eq() {
assert!(make_cube(&[1, 0, 0]) == make_cube(&[1, 0, 0]));
assert!(make_cube(&[1, 0, 0]) != make_cube(&[1, 0, 1]));
}
#[test]
fn cube_ord() {
assert!(make_cube(&[1, 0, 0]) < make_cube(&[1, 1, 0]));
assert!(make_cube(&[1, 0, 2]) > make_cube(&[1, 0, 1]));
}
#[test]
fn cube_with_var() {
assert!(make_cube(&[0, 1, 0]).with_var(2, CubeVar::True) == make_cube(&[0, 1, 1]));
}
#[test]
fn cube_merge() {
assert!(make_cube(&[0, 0]).merge_with(&make_cube(&[0])) == CubeMergeResult::None);
assert!(make_cube(&[0, 0]).merge_with(&make_cube(&[0, 0])) == CubeMergeResult::CancelRight);
assert!(make_cube(&[1, 0]).merge_with(&make_cube(&[0, 1])) == CubeMergeResult::None);
assert!(make_cube(&[1, 2]).merge_with(&make_cube(&[2, 1])) == CubeMergeResult::None);
assert!(
make_cube(&[1, 2, 2]).merge_with(&make_cube(&[1, 1, 0]))
== CubeMergeResult::CancelRight
);
assert!(
make_cube(&[1, 1, 2]).merge_with(&make_cube(&[1, 0, 0]))
== CubeMergeResult::ExpandRight(make_cube(&[1, 2, 0]))
);
assert!(
make_cube(&[1, 1, 0]).merge_with(&make_cube(&[1, 2, 2])) == CubeMergeResult::CancelLeft
);
assert!(
make_cube(&[1, 0, 0]).merge_with(&make_cube(&[1, 1, 2]))
== CubeMergeResult::ExpandLeft(make_cube(&[1, 2, 0]))
);
assert!(
make_cube(&[1, 1, 0]).merge_with(&make_cube(&[1, 1, 1]))
== CubeMergeResult::Merge(make_cube(&[1, 1, 2]))
);
assert!(make_cube(&[1, 1, 0]).merge_with(&make_cube(&[1, 0, 1])) == CubeMergeResult::None);
}
#[test]
fn cubelist_merge() {
assert!(
CubeList::new().merge(&CubeList::from_list(&[
make_cube(&[1, 0, 0]),
make_cube(&[0, 1, 1])
])) == CubeList::from_list(&[make_cube(&[1, 0, 0]), make_cube(&[0, 1, 1])])
);
assert!(
CubeList::new().merge(&CubeList::from_list(&[
make_cube(&[1, 0, 0]),
make_cube(&[1, 1, 1]),
make_cube(&[1, 0, 1]),
make_cube(&[1, 1, 0])
])) == CubeList::from_list(&[make_cube(&[1, 2, 2])])
);
assert!(
CubeList::new().merge(&CubeList::from_list(&[
make_cube(&[1, 0, 0]),
make_cube(&[0, 1, 1]),
make_cube(&[1, 0, 1])
])) == CubeList::from_list(&[make_cube(&[1, 0, 2]), make_cube(&[0, 1, 1])])
);
assert!(
CubeList::new().merge(&CubeList::from_list(&[
make_cube(&[1, 0, 0]),
make_cube(&[1, 2, 2])
])) == CubeList::from_list(&[make_cube(&[1, 2, 2])])
);
assert!(
CubeList::new().merge(&CubeList::from_list(&[
make_cube(&[1, 2, 2]),
make_cube(&[1, 0, 0])
])) == CubeList::from_list(&[make_cube(&[1, 2, 2])])
);
}
}