use std::cmp::Eq;
use std::collections::{BTreeSet, HashMap, HashSet};
use std::hash::Hash;
use std::marker::Sync;
use std::sync::{Arc, Mutex, MutexGuard};
use hashconsing::*;
use crate::{
zip::{self, BinaryKey, HKey, UnaryKey},
Zdd, ZddTree, ZddTreeOps,
};
pub trait FactoryUnOps<Label: Ord + Eq + Hash + Clone, ZDD> {
fn count(&self, z: ZDD) -> usize;
}
pub trait FactoryUnLblOps<Label: Ord + Eq + Hash + Clone, ZDD, LabelParam> {
fn offset(&self, zdd: ZDD, lbl: LabelParam) -> Zdd<Label>;
fn onset(&self, zdd: ZDD, lbl: LabelParam) -> Zdd<Label>;
fn change(&self, zdd: ZDD, lbl: LabelParam) -> Zdd<Label>;
}
pub trait FactoryBinOps<Label: Ord + Eq + Hash + Clone, LHS, RHS> {
fn union(&self, lhs: LHS, rhs: RHS) -> Zdd<Label>;
fn inter(&self, lhs: LHS, rhs: RHS) -> Zdd<Label>;
fn minus(&self, lhs: LHS, rhs: RHS) -> Zdd<Label>;
fn subset(&self, lhs: LHS, rhs: RHS) -> bool;
}
trait ZddFactory<Label: Eq + Hash + Clone> {
fn node(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label>;
}
pub trait ZddMaker<Label: Eq + Hash + Clone, Lft, Rgt> {
fn mk_node(&self, lbl: Label, lft: Lft, rgt: Rgt) -> Zdd<Label>;
}
pub struct Factory<Label>
where
Label: Eq + Hash + Clone,
{
consign: Mutex<HConsign<ZddTree<Label>>>,
one: Zdd<Label>,
zero: Zdd<Label>,
count_cache: Mutex<HashMap<UnaryKey<()>, usize>>,
offset_cache: Mutex<HashMap<UnaryKey<Label>, Zdd<Label>>>,
onset_cache: Mutex<HashMap<UnaryKey<Label>, Zdd<Label>>>,
change_cache: Mutex<HashMap<UnaryKey<Label>, Zdd<Label>>>,
union_cache: Mutex<HashMap<BinaryKey, Zdd<Label>>>,
inter_cache: Mutex<HashMap<BinaryKey, Zdd<Label>>>,
minus_cache: Mutex<HashMap<BinaryKey, Zdd<Label>>>,
subset_cache: Mutex<HashMap<BinaryKey, bool>>,
}
unsafe impl<Label: Eq + Hash + Clone> Sync for Factory<Label> {}
impl<Label: Ord + Eq + Hash + Clone> ZddFactory<Label> for Factory<Label> {
fn node(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
if rgt == self.zero {
lft
} else {
if let ZddTree::HasOne(ref lft) = *lft {
let node = self
.consign
.lock()
.unwrap()
.mk(ZddTree::Node(lbl, lft.clone(), rgt));
return self.consign.lock().unwrap().mk(ZddTree::HasOne(node));
};
self.consign
.lock()
.unwrap()
.mk(ZddTree::Node(lbl, lft, rgt))
}
}
}
impl<Label: Ord + Eq + Hash + Clone> ZddMaker<Label, Zdd<Label>, Zdd<Label>> for Factory<Label> {
fn mk_node(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
let lft = self.offset(lft, &lbl);
let rgt = self.change(rgt, &lbl);
self.union(lft, rgt)
}
}
impl<'a, 'b, Label: Ord + Eq + Hash + Clone> ZddMaker<Label, &'a Zdd<Label>, &'b Zdd<Label>>
for Factory<Label>
{
fn mk_node(&self, lbl: Label, lft: &'a Zdd<Label>, rgt: &'b Zdd<Label>) -> Zdd<Label> {
self.mk_node(lbl, lft.clone(), rgt.clone())
}
}
impl<'a, Label: Ord + Eq + Hash + Clone> ZddMaker<Label, &'a Zdd<Label>, Zdd<Label>>
for Factory<Label>
{
fn mk_node(&self, lbl: Label, lft: &'a Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
self.mk_node(lbl.clone(), lft.clone(), rgt)
}
}
impl<'a, Label: Ord + Eq + Hash + Clone> ZddMaker<Label, Zdd<Label>, &'a Zdd<Label>>
for Factory<Label>
{
fn mk_node(&self, lbl: Label, lft: Zdd<Label>, rgt: &'a Zdd<Label>) -> Zdd<Label> {
self.mk_node(lbl.clone(), lft, rgt.clone())
}
}
impl<'a, 'b, Label: Ord + Eq + Hash + Clone + 'a + 'b> Factory<Label>
where
Factory<Label>: FactoryUnOps<Label, Zdd<Label>>
+ FactoryUnOps<Label, &'a Zdd<Label>>
+ FactoryUnLblOps<Label, Zdd<Label>, Label>
+ FactoryUnLblOps<Label, &'a Zdd<Label>, Label>
+ FactoryUnLblOps<Label, Zdd<Label>, &'b Label>
+ FactoryUnLblOps<Label, &'a Zdd<Label>, &'b Label>
+ FactoryBinOps<Label, Zdd<Label>, Zdd<Label>>
+ FactoryBinOps<Label, &'a Zdd<Label>, Zdd<Label>>
+ FactoryBinOps<Label, Zdd<Label>, &'b Zdd<Label>>
+ FactoryBinOps<Label, &'a Zdd<Label>, &'b Zdd<Label>>,
{
pub fn mk(capacity: usize) -> Self {
let mut consign = HConsign::with_capacity(capacity);
let zero = consign.mk(ZddTree::Zero);
let one = consign.mk(ZddTree::HasOne(zero.clone()));
Factory {
consign: Mutex::new(consign),
one: one,
zero: zero,
count_cache: Mutex::new(HashMap::new()),
offset_cache: Mutex::new(HashMap::new()),
onset_cache: Mutex::new(HashMap::new()),
change_cache: Mutex::new(HashMap::new()),
union_cache: Mutex::new(HashMap::new()),
inter_cache: Mutex::new(HashMap::new()),
minus_cache: Mutex::new(HashMap::new()),
subset_cache: Mutex::new(HashMap::new()),
}
}
#[inline(always)]
pub fn zero(&self) -> Zdd<Label> {
self.zero.clone()
}
#[inline(always)]
pub fn one(&self) -> Zdd<Label> {
self.one.clone()
}
#[inline(always)]
pub fn add_one(&self, kid: &Zdd<Label>) -> Zdd<Label> {
match **kid {
ZddTree::HasOne(_) => kid.clone(),
_ => self
.consign
.lock()
.unwrap()
.mk(ZddTree::HasOne(kid.clone())),
}
}
#[inline(always)]
pub fn rm_one(&self, zdd: &Zdd<Label>) -> Zdd<Label> {
match **zdd {
ZddTree::HasOne(ref kid) => kid.clone(),
_ => zdd.clone(),
}
}
#[inline(always)]
pub fn lft(&self, zdd: &Zdd<Label>) -> Result<Zdd<Label>, bool> {
match **zdd {
ZddTree::Node(_, ref lft, _) => Ok(lft.clone()),
ZddTree::HasOne(ref kid) => match **kid {
ZddTree::Node(_, ref lft, _) => Ok(self.add_one(lft)),
ZddTree::Zero => Err(true),
_ => panic!("[lft] ZDD is ill-formed"),
},
ZddTree::Zero => Err(false),
}
}
#[inline(always)]
pub fn rgt(&self, zdd: &Zdd<Label>) -> Result<Zdd<Label>, bool> {
match **zdd {
ZddTree::Node(_, _, ref rgt) => Ok(rgt.clone()),
ZddTree::HasOne(ref kid) => match **kid {
ZddTree::Node(_, _, ref rgt) => Ok(rgt.clone()),
ZddTree::Zero => Err(true),
_ => panic!("[rgt] ZDD is ill-formed"),
},
ZddTree::Zero => Err(false),
}
}
#[inline(always)]
pub fn kids(&self, zdd: &Zdd<Label>) -> Result<(Zdd<Label>, Zdd<Label>), bool> {
match **zdd {
ZddTree::Node(_, ref lft, ref rgt) => Ok((lft.clone(), rgt.clone())),
ZddTree::HasOne(ref kid) => match **kid {
ZddTree::Node(_, ref lft, ref rgt) => Ok((self.add_one(lft), rgt.clone())),
ZddTree::Zero => Err(true),
_ => panic!("[rgt] ZDD is ill-formed"),
},
ZddTree::Zero => Err(false),
}
}
fn of_iterator<T: ::std::iter::Iterator<Item = &'b Label>>(&self, iter: T) -> Zdd<Label> {
let mut zdd = self.one();
for e in iter {
zdd = self.change(zdd, e);
}
zdd
}
pub fn of_btree_set(&self, set: &'b BTreeSet<Label>) -> Zdd<Label> {
self.of_iterator(set.iter())
}
pub fn of_hashset(&self, set: &'b HashSet<Label>) -> Zdd<Label> {
self.of_iterator(set.iter())
}
#[inline(always)]
fn unary_cache_get<Info: Eq + Hash + Clone, Out: Clone>(
cache: &MutexGuard<HashMap<UnaryKey<Info>, Out>>,
zdd: &Zdd<Label>,
info: &Info,
) -> Option<Out> {
match (*cache).get(&(zdd.uid(), info.clone())) {
None => None,
Some(out) => Some(out.clone()),
}
}
#[inline(always)]
fn count_cache_get(&self, zdd: &Zdd<Label>) -> Option<usize> {
Factory::unary_cache_get(&self.count_cache.lock().unwrap(), zdd, &())
}
#[inline(always)]
fn offset_cache_get(&self, zdd: &Zdd<Label>, lbl: &Label) -> Option<Zdd<Label>> {
Factory::unary_cache_get(&self.offset_cache.lock().unwrap(), zdd, lbl)
}
#[inline(always)]
fn onset_cache_get(&self, zdd: &Zdd<Label>, lbl: &Label) -> Option<Zdd<Label>> {
Factory::unary_cache_get(&self.onset_cache.lock().unwrap(), zdd, lbl)
}
#[inline(always)]
fn change_cache_get(&self, zdd: &Zdd<Label>, lbl: &Label) -> Option<Zdd<Label>> {
Factory::unary_cache_get(&self.change_cache.lock().unwrap(), zdd, lbl)
}
#[inline(always)]
fn binary_cache_get<T: Clone>(
cache: &MutexGuard<HashMap<BinaryKey, T>>,
lhs: &Zdd<Label>,
rhs: &Zdd<Label>,
) -> Option<T> {
match (*cache).get(&(lhs.uid(), rhs.uid())) {
None => None,
Some(zdd) => Some(zdd.clone()),
}
}
#[inline(always)]
fn union_cache_get(&self, lhs: &Zdd<Label>, rhs: &Zdd<Label>) -> Option<Zdd<Label>> {
Factory::binary_cache_get(&self.union_cache.lock().unwrap(), lhs, rhs)
}
#[inline(always)]
fn inter_cache_get(&self, lhs: &Zdd<Label>, rhs: &Zdd<Label>) -> Option<Zdd<Label>> {
Factory::binary_cache_get(&self.inter_cache.lock().unwrap(), lhs, rhs)
}
#[inline(always)]
fn minus_cache_get(&self, lhs: &Zdd<Label>, rhs: &Zdd<Label>) -> Option<Zdd<Label>> {
Factory::binary_cache_get(&self.minus_cache.lock().unwrap(), lhs, rhs)
}
#[inline(always)]
fn subset_cache_get(&self, lhs: &Zdd<Label>, rhs: &Zdd<Label>) -> Option<bool> {
Factory::binary_cache_get(&self.subset_cache.lock().unwrap(), lhs, rhs)
}
#[inline(always)]
pub fn consign_len(&self) -> usize {
self.consign.lock().unwrap().len()
}
#[inline(always)]
pub fn count_cache_len(&self) -> usize {
self.count_cache.lock().unwrap().len()
}
#[inline(always)]
pub fn offset_cache_len(&self) -> usize {
self.offset_cache.lock().unwrap().len()
}
#[inline(always)]
pub fn onset_cache_len(&self) -> usize {
self.onset_cache.lock().unwrap().len()
}
#[inline(always)]
pub fn change_cache_len(&self) -> usize {
self.change_cache.lock().unwrap().len()
}
#[inline(always)]
pub fn union_cache_len(&self) -> usize {
self.union_cache.lock().unwrap().len()
}
#[inline(always)]
pub fn inter_cache_len(&self) -> usize {
self.inter_cache.lock().unwrap().len()
}
#[inline(always)]
pub fn minus_cache_len(&self) -> usize {
self.minus_cache.lock().unwrap().len()
}
#[inline(always)]
pub fn subset_cache_len(&self) -> usize {
self.subset_cache.lock().unwrap().len()
}
}
impl<Label: Ord + Eq + Hash + Clone> FactoryUnOps<Label, Zdd<Label>> for Factory<Label> {
fn count(&self, mut zdd: Zdd<Label>) -> usize {
use zip::unary::Step::Lft;
let mut zip = zip::count();
loop {
zdd = match zdd.top() {
Err(false) => zip_up!(self > zip > 0),
Err(true) => zip_up!(self > zip > 1),
_ => match self.count_cache_get(&zdd) {
Some(count) => zip_up!(self > zip > count),
None => {
let key = zdd.uid();
let (lft, rgt) = self.kids(&zdd).unwrap();
zip.push(Lft(key, (), rgt));
lft
}
},
}
}
}
}
impl<'a, Label: Ord + Eq + Hash + Clone> FactoryUnOps<Label, &'a Zdd<Label>> for Factory<Label> {
fn count(&self, zdd: &'a Zdd<Label>) -> usize {
self.count(zdd.clone())
}
}
impl<Label: Ord + Eq + Hash + Clone> FactoryUnLblOps<Label, Zdd<Label>, Label> for Factory<Label> {
fn offset(&self, mut zdd: Zdd<Label>, lbl: Label) -> Zdd<Label> {
use zip::unary::Step::Lft;
let mut zip = zip::offset();
loop {
zdd = match zdd.top() {
Err(false) => zip_up!(self > zip > self.zero()),
Err(true) => zip_up!(self > zip > self.one()),
Ok(ref top) if top.gt(&lbl) => zip_up!(self > zip > zdd),
Ok(ref top) if top.eq(&lbl) => {
zip_up!(self > zip > self.lft(&zdd).unwrap())
}
Ok(ref top) => match self.offset_cache_get(&zdd, &lbl) {
Some(res) => zip_up!(self > zip > res),
None => {
let key = (zdd.uid(), lbl.clone());
let (lft, rgt) = self.kids(&zdd).unwrap();
zip.push(Lft(key, top.clone(), rgt));
lft
}
},
}
}
}
fn onset(&self, mut zdd: Zdd<Label>, lbl: Label) -> Zdd<Label> {
use zip::unary::Step::Lft;
let mut zip = zip::onset();
loop {
zdd = match zdd.top() {
Err(_) => zip_up!(self > zip > self.zero()),
Ok(ref top) if top.gt(&lbl) => zip_up!(self > zip > self.zero()),
Ok(ref top) if top.eq(&lbl) => {
let rgt = self.rgt(&zdd).unwrap();
zip_up!(self > zip > rgt)
}
Ok(ref top) => match self.onset_cache_get(&zdd, &lbl) {
Some(res) => zip_up!(self > zip > res),
None => {
let key = (zdd.uid(), lbl.clone());
let (lft, rgt) = self.kids(&zdd).unwrap();
zip.push(Lft(key, top.clone(), rgt));
lft
}
},
}
}
}
fn change(&self, mut zdd: Zdd<Label>, lbl: Label) -> Zdd<Label> {
use zip::unary::Step::Lft;
let mut zip = zip::change();
loop {
zdd = match zdd.top() {
Err(false) => zip_up!(self > zip > self.zero()),
Err(true) => {
let zero = self.zero();
let one = self.one();
let zdd = self.node(lbl.clone(), zero, one);
zip_up!(self > zip > zdd)
}
Ok(ref top) if top.gt(&lbl) => {
let zero = self.zero();
let zdd = self.node(lbl.clone(), zero, zdd.clone());
zip_up!(self > zip > zdd)
}
Ok(ref top) if top.eq(&lbl) => {
let (lft, rgt) = self.kids(&zdd).unwrap();
let zdd = self.node(top.clone(), rgt, lft);
zip_up!(self > zip > zdd)
}
Ok(ref top) => match self.change_cache_get(&zdd, &lbl) {
Some(res) => zip_up!(self > zip > res),
None => {
let key = (zdd.uid(), lbl.clone());
let (lft, rgt) = self.kids(&zdd).unwrap();
zip.push(Lft(key, top.clone(), rgt));
lft
}
},
}
}
}
}
impl<'a, Label: Ord + Eq + Hash + Clone> FactoryUnLblOps<Label, Zdd<Label>, &'a Label>
for Factory<Label>
{
fn offset(&self, zdd: Zdd<Label>, lbl: &'a Label) -> Zdd<Label> {
self.offset(zdd, lbl.clone())
}
fn onset(&self, zdd: Zdd<Label>, lbl: &'a Label) -> Zdd<Label> {
self.onset(zdd, lbl.clone())
}
fn change(&self, zdd: Zdd<Label>, lbl: &'a Label) -> Zdd<Label> {
self.change(zdd, lbl.clone())
}
}
impl<'a, Label: Ord + Eq + Hash + Clone> FactoryUnLblOps<Label, &'a Zdd<Label>, Label>
for Factory<Label>
{
fn offset(&self, zdd: &'a Zdd<Label>, lbl: Label) -> Zdd<Label> {
self.offset(zdd.clone(), lbl)
}
fn onset(&self, zdd: &'a Zdd<Label>, lbl: Label) -> Zdd<Label> {
self.onset(zdd.clone(), lbl)
}
fn change(&self, zdd: &'a Zdd<Label>, lbl: Label) -> Zdd<Label> {
self.change(zdd.clone(), lbl)
}
}
impl<'a, 'b, Label: Ord + Eq + Hash + Clone> FactoryUnLblOps<Label, &'a Zdd<Label>, &'b Label>
for Factory<Label>
{
fn offset(&self, zdd: &'a Zdd<Label>, lbl: &'b Label) -> Zdd<Label> {
self.offset(zdd.clone(), lbl.clone())
}
fn onset(&self, zdd: &'a Zdd<Label>, lbl: &'b Label) -> Zdd<Label> {
self.onset(zdd.clone(), lbl.clone())
}
fn change(&self, zdd: &'a Zdd<Label>, lbl: &'b Label) -> Zdd<Label> {
self.change(zdd.clone(), lbl.clone())
}
}
impl<Label: Ord + Eq + Hash + Clone> FactoryBinOps<Label, Zdd<Label>, Zdd<Label>>
for Factory<Label>
{
fn union(&self, lhs: Zdd<Label>, rhs: Zdd<Label>) -> Zdd<Label> {
use zip::binary::Step::{Lft, TLft};
let mut zip = zip::union();
let mut pair = (lhs, rhs);
loop {
let (lhs, rhs) = pair;
pair = if lhs == rhs {
zip_up!(self >> zip > lhs)
} else {
match (lhs.top(), rhs.top()) {
(Err(false), _) => zip_up!(self >> zip > rhs),
(_, Err(false)) => zip_up!(self >> zip > lhs),
(Err(true), _) => {
let zdd = self.add_one(&rhs);
zip_up!(self >> zip > zdd)
}
(_, Err(true)) => {
let zdd = self.add_one(&lhs);
zip_up!(self >> zip > zdd)
}
(Ok(l_top), Ok(r_top)) => {
let (lhs, rhs, l_top, r_top) = if l_top > r_top {
(rhs, lhs, r_top, l_top)
} else {
(lhs, rhs, l_top, r_top)
};
match self.union_cache_get(&lhs, &rhs) {
Some(res) => zip_up!(self >> zip > res),
None => {
let key = (lhs.uid(), rhs.uid());
if l_top == r_top {
let (l_lft, l_rgt) = self.kids(&lhs).unwrap();
let (r_lft, r_rgt) = self.kids(&rhs).unwrap();
zip.push(Lft(key, l_top, l_rgt, r_rgt));
(l_lft, r_lft)
} else {
assert!(l_top < r_top);
let (l_lft, l_rgt) = self.kids(&lhs).unwrap();
zip.push(TLft(key, l_top, l_rgt));
(l_lft, rhs)
}
}
}
}
}
};
}
}
fn inter(&self, lhs: Zdd<Label>, rhs: Zdd<Label>) -> Zdd<Label> {
use zip::binary::Step::Lft;
let mut zip = zip::inter();
let mut pair = (lhs, rhs);
loop {
let (lhs, rhs) = pair;
pair = if lhs == rhs {
zip_up!(self >> zip > lhs)
} else {
match (lhs.top(), rhs.top()) {
(Err(false), _) | (_, Err(false)) => zip_up!(self >> zip > self.zero()),
(Err(true), _) => {
let zdd = if rhs.has_one() { lhs } else { self.zero() };
zip_up!(self >> zip > zdd)
}
(_, Err(true)) => {
let zdd = if lhs.has_one() { rhs } else { self.zero() };
zip_up!(self >> zip > zdd)
}
(Ok(l_top), Ok(r_top)) => {
if l_top == r_top {
match self.inter_cache_get(&lhs, &rhs) {
Some(res) => zip_up!(self >> zip > res),
None => {
let key = (lhs.uid(), rhs.uid());
let (l_lft, l_rgt) = self.kids(&lhs).unwrap();
let (r_lft, r_rgt) = self.kids(&rhs).unwrap();
zip.push(Lft(key, l_top, l_rgt, r_rgt));
(l_lft, r_lft)
}
}
} else {
if l_top < r_top {
(self.lft(&lhs).unwrap(), rhs)
} else {
(self.lft(&rhs).unwrap(), lhs)
}
}
}
}
};
}
}
fn minus(&self, lhs: Zdd<Label>, rhs: Zdd<Label>) -> Zdd<Label> {
use zip::binary::Step::{Lft, TLft};
let mut zip = zip::minus();
let mut pair = (lhs, rhs);
loop {
let (lhs, rhs) = pair;
pair = if lhs == rhs {
zip_up!(self >> zip > self.zero())
} else {
match (lhs.top(), rhs.top()) {
(Err(false), _) | (_, Err(false)) => zip_up!(self >> zip > lhs),
(Err(true), _) => {
let zdd = if rhs.has_one() { self.zero() } else { lhs };
zip_up!(self >> zip > zdd)
}
(_, Err(true)) => {
let zdd = self.rm_one(&lhs);
zip_up!(self >> zip > zdd)
}
(Ok(l_top), Ok(r_top)) => match self.minus_cache_get(&lhs, &rhs) {
Some(res) => zip_up!(self >> zip > res),
None => {
let key = (lhs.uid(), rhs.uid());
if l_top < r_top {
let (l_lft, l_rgt) = self.kids(&lhs).unwrap();
zip.push(TLft(key, l_top, l_rgt));
(l_lft, rhs)
} else {
if r_top < l_top {
let r_lft = self.lft(&rhs).unwrap();
(lhs, r_lft)
} else {
let (l_lft, l_rgt) = self.kids(&lhs).unwrap();
let (r_lft, r_rgt) = self.kids(&rhs).unwrap();
zip.push(Lft(key, l_top, l_rgt, r_rgt));
(l_lft, r_lft)
}
}
}
},
}
};
}
}
fn subset(&self, lhs: Zdd<Label>, rhs: Zdd<Label>) -> bool {
use zip::binary::Step::{Lft, TLft};
let mut zip = zip::subset();
let mut pair = (rhs, lhs);
loop {
let (lhs, rhs) = pair;
pair = if lhs == rhs {
zip_up!(self >> zip > true)
} else {
match (lhs.top(), rhs.top()) {
(_, Err(false)) => zip_up!(self >> zip > true),
(Err(true), _) | (Err(false), _) => zip_up!(self >> zip > false),
(_, Err(true)) => zip_up!(self >> zip > lhs.has_one()),
(Ok(l_top), Ok(r_top)) => match self.subset_cache_get(&lhs, &rhs) {
Some(res) => zip_up!(self >> zip > res),
None => {
let key = (lhs.uid(), rhs.uid());
if l_top == r_top {
let (l_lft, l_rgt) = self.kids(&lhs).unwrap();
let (r_lft, r_rgt) = self.kids(&rhs).unwrap();
zip.push(Lft(key, (), l_rgt, r_rgt));
(l_lft, r_lft)
} else {
if l_top < r_top {
let l_lft = self.lft(&lhs).unwrap();
zip.push(TLft(key, (), true));
(l_lft, rhs)
} else {
zip_up!(self >> zip > false)
}
}
}
},
}
};
}
}
}
impl<'a, Label: Ord + Eq + Hash + Clone> FactoryBinOps<Label, &'a Zdd<Label>, Zdd<Label>>
for Factory<Label>
{
fn union(&self, lhs: &'a Zdd<Label>, rhs: Zdd<Label>) -> Zdd<Label> {
self.union(lhs.clone(), rhs)
}
fn inter(&self, lhs: &'a Zdd<Label>, rhs: Zdd<Label>) -> Zdd<Label> {
self.inter(lhs.clone(), rhs)
}
fn minus(&self, lhs: &'a Zdd<Label>, rhs: Zdd<Label>) -> Zdd<Label> {
self.minus(lhs.clone(), rhs)
}
fn subset(&self, lhs: &'a Zdd<Label>, rhs: Zdd<Label>) -> bool {
self.subset(lhs.clone(), rhs)
}
}
impl<'a, Label: Ord + Eq + Hash + Clone> FactoryBinOps<Label, Zdd<Label>, &'a Zdd<Label>>
for Factory<Label>
{
fn union(&self, lhs: Zdd<Label>, rhs: &'a Zdd<Label>) -> Zdd<Label> {
self.union(lhs, rhs.clone())
}
fn inter(&self, lhs: Zdd<Label>, rhs: &'a Zdd<Label>) -> Zdd<Label> {
self.inter(lhs, rhs.clone())
}
fn minus(&self, lhs: Zdd<Label>, rhs: &'a Zdd<Label>) -> Zdd<Label> {
self.minus(lhs, rhs.clone())
}
fn subset(&self, lhs: Zdd<Label>, rhs: &'a Zdd<Label>) -> bool {
self.subset(lhs, rhs.clone())
}
}
impl<'a, 'b, Label: Ord + Eq + Hash + Clone> FactoryBinOps<Label, &'a Zdd<Label>, &'b Zdd<Label>>
for Factory<Label>
{
fn union(&self, lhs: &'a Zdd<Label>, rhs: &'b Zdd<Label>) -> Zdd<Label> {
self.union(lhs.clone(), rhs.clone())
}
fn inter(&self, lhs: &'a Zdd<Label>, rhs: &'b Zdd<Label>) -> Zdd<Label> {
self.inter(lhs.clone(), rhs.clone())
}
fn minus(&self, lhs: &'a Zdd<Label>, rhs: &'b Zdd<Label>) -> Zdd<Label> {
self.minus(lhs.clone(), rhs.clone())
}
fn subset(&self, lhs: &'a Zdd<Label>, rhs: &'b Zdd<Label>) -> bool {
self.subset(lhs.clone(), rhs.clone())
}
}
#[cfg(test)]
#[inline(always)]
fn cache_overwrite<T>(insert_result: Option<T>, name: &str) {
match insert_result {
None => (),
Some(_) => panic!("cache overwrite in {} cache", name),
}
}
#[cfg(not(test))]
#[inline(always)]
fn cache_overwrite<T>(_: Option<T>, _: &str) {
()
}
impl<Label: Ord + Eq + Hash + Clone> zip::unary::Zip<HKey, Label, (), usize, zip::Count<Label>>
for Factory<Label>
{
fn cache_insert(&self, key: HKey, count: &usize) {
let _res = self.count_cache.lock().unwrap().insert((key, ()), *count);
cache_overwrite(_res, "count")
}
fn combine(&self, _: (), l_count: usize, r_count: usize) -> usize {
l_count + r_count
}
}
impl<Label: Ord + Eq + Hash + Clone>
zip::unary::Zip<(HKey, Label), Label, Label, Zdd<Label>, zip::Offset<Label>>
for Factory<Label>
{
fn cache_insert(&self, key: (HKey, Label), zdd: &Zdd<Label>) {
let _res = self.offset_cache.lock().unwrap().insert(key, zdd.clone());
cache_overwrite(_res, "offset")
}
fn combine(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
self.node(lbl, lft, rgt)
}
}
impl<Label: Ord + Eq + Hash + Clone>
zip::unary::Zip<(HKey, Label), Label, Label, Zdd<Label>, zip::Onset<Label>> for Factory<Label>
{
fn cache_insert(&self, key: (HKey, Label), zdd: &Zdd<Label>) {
let _res = self.onset_cache.lock().unwrap().insert(key, zdd.clone());
cache_overwrite(_res, "onset")
}
fn combine(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
self.node(lbl, lft, rgt)
}
}
impl<Label: Ord + Eq + Hash + Clone>
zip::unary::Zip<(HKey, Label), Label, Label, Zdd<Label>, zip::Change<Label>>
for Factory<Label>
{
fn cache_insert(&self, key: (HKey, Label), zdd: &Zdd<Label>) {
let _res = self.change_cache.lock().unwrap().insert(key, zdd.clone());
cache_overwrite(_res, "change")
}
fn combine(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
self.node(lbl, lft, rgt)
}
}
impl<Label: Ord + Eq + Hash + Clone>
zip::binary::Zip<(HKey, HKey), Label, Label, Zdd<Label>, zip::Union<Label>> for Factory<Label>
{
fn cache_insert(&self, key: (HKey, HKey), zdd: &Zdd<Label>) {
let _res = self.union_cache.lock().unwrap().insert(key, zdd.clone());
cache_overwrite(_res, "union")
}
fn combine(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
self.node(lbl, lft, rgt)
}
}
impl<Label: Ord + Eq + Hash + Clone>
zip::binary::Zip<(HKey, HKey), Label, Label, Zdd<Label>, zip::Inter<Label>> for Factory<Label>
{
fn cache_insert(&self, key: (HKey, HKey), zdd: &Zdd<Label>) {
let _res = self.inter_cache.lock().unwrap().insert(key, zdd.clone());
cache_overwrite(_res, "inter")
}
fn combine(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
self.node(lbl, lft, rgt)
}
}
impl<Label: Ord + Eq + Hash + Clone>
zip::binary::Zip<(HKey, HKey), Label, Label, Zdd<Label>, zip::Minus<Label>> for Factory<Label>
{
fn cache_insert(&self, key: (HKey, HKey), zdd: &Zdd<Label>) {
let _res = self.minus_cache.lock().unwrap().insert(key, zdd.clone());
cache_overwrite(_res, "minus")
}
fn combine(&self, lbl: Label, lft: Zdd<Label>, rgt: Zdd<Label>) -> Zdd<Label> {
self.node(lbl, lft, rgt)
}
}
impl<Label: Ord + Eq + Hash + Clone>
zip::binary::Zip<(HKey, HKey), Label, (), bool, zip::Subset<Label>> for Factory<Label>
{
fn cache_insert(&self, key: (HKey, HKey), val: &bool) {
let _res = self.subset_cache.lock().unwrap().insert(key, *val);
cache_overwrite(_res, "subset")
}
fn combine(&self, _: (), lft: bool, rgt: bool) -> bool {
lft && rgt
}
}
pub struct FactoryBuilder {
consign: usize,
count: usize,
offset: usize,
onset: usize,
change: usize,
union: usize,
inter: usize,
minus: usize,
subset: usize,
}
impl FactoryBuilder {
pub fn build<Label: Eq + Hash + Clone>(self) -> Factory<Label> {
let mut consign = HConsign::with_capacity(self.consign);
let zero = consign.mk(ZddTree::Zero);
let one = consign.mk(ZddTree::HasOne(zero.clone()));
Factory {
consign: Mutex::new(consign),
one: one,
zero: zero,
count_cache: Mutex::new(HashMap::with_capacity(self.count)),
offset_cache: Mutex::new(HashMap::with_capacity(self.offset)),
onset_cache: Mutex::new(HashMap::with_capacity(self.onset)),
change_cache: Mutex::new(HashMap::with_capacity(self.change)),
union_cache: Mutex::new(HashMap::with_capacity(self.union)),
inter_cache: Mutex::new(HashMap::with_capacity(self.inter)),
minus_cache: Mutex::new(HashMap::with_capacity(self.minus)),
subset_cache: Mutex::new(HashMap::with_capacity(self.subset)),
}
}
pub fn build_arc<Label: Eq + Hash + Clone>(self) -> Arc<Factory<Label>> {
Arc::new(self.build())
}
pub fn mk() -> Self {
FactoryBuilder {
consign: 0,
count: 0,
offset: 0,
onset: 0,
change: 0,
union: 0,
inter: 0,
minus: 0,
subset: 0,
}
}
pub fn len(mut self, l: usize) -> Self {
self.consign = l;
self.caches_len(l)
}
pub fn consign_len(mut self, l: usize) -> Self {
self.consign = l;
self
}
pub fn caches_len(mut self, l: usize) -> Self {
self.count = l;
self.offset = l;
self.onset = l;
self.change = l;
self.union = l;
self.inter = l;
self.minus = l;
self.subset = l;
self
}
pub fn count_cache_len(mut self, l: usize) -> Self {
self.count = l;
self
}
pub fn offset_cache_len(mut self, l: usize) -> Self {
self.offset = l;
self
}
pub fn onset_cache_len(mut self, l: usize) -> Self {
self.onset = l;
self
}
pub fn change_cache_len(mut self, l: usize) -> Self {
self.change = l;
self
}
pub fn union_cache_len(mut self, l: usize) -> Self {
self.union = l;
self
}
pub fn inter_cache_len(mut self, l: usize) -> Self {
self.inter = l;
self
}
pub fn minus_cache_len(mut self, l: usize) -> Self {
self.minus = l;
self
}
pub fn subset_cache_len(mut self, l: usize) -> Self {
self.subset = l;
self
}
}