use crate::{
HCons,HNil,LispId,ConstId,
ops::{ConstBool,AsTypeBool},
engine::{Call,FunCall,cc},
};
use typenum::{True,False};
#[derive(Copy,Clone,Debug,Default)] pub struct ContainsP;
literal!{ContainsP}
impl Call for ContainsP { type Conv = cc::Func; }
impl<S,I,const ID:u128>
FunCall<sexpr!{S,I}> for ContainsP where
S:Set,
I:LispId<Id=ConstId<ID>>,
ConstBool<{contains_id(S::IDS, ID)}>: AsTypeBool,
{
type Result = <ConstBool<{contains_id(S::IDS, ID)}> as AsTypeBool>::TypeBool;
}
#[derive(Copy,Clone,Debug,Default)] pub struct SupersetP;
literal!{SupersetP}
impl Call for SupersetP { type Conv = cc::Func; }
impl<L,R> FunCall<sexpr!{L,R}> for SupersetP where
L:Set, R:Set,
ConstBool<{equal_ids(diff_ids(R::IDS, L::IDS), EMPTY)}>: AsTypeBool,
{
type Result = <ConstBool<{equal_ids(diff_ids(R::IDS, L::IDS), EMPTY)}> as AsTypeBool>::TypeBool;
}
#[derive(Copy,Clone,Debug,Default)] pub struct DisjointP;
literal!{DisjointP}
impl Call for DisjointP { type Conv = cc::Func; }
impl<L,R> FunCall<sexpr!{L,R}> for DisjointP where
L:Set, R:Set,
ConstBool<{equal_ids(intersect_ids(R::IDS, L::IDS), EMPTY)}>: AsTypeBool,
{
type Result = <ConstBool<{equal_ids(intersect_ids(R::IDS, L::IDS), EMPTY)}> as AsTypeBool>::TypeBool;
}
#[derive(Copy,Clone,Debug,Default)] pub struct EqP;
literal!{EqP}
impl Call for EqP { type Conv = cc::Func; }
impl<L,R> FunCall<sexpr!{L,R}> for EqP where
L:Set, R:Set,
ConstBool<{equal_ids(R::IDS, L::IDS)}>: AsTypeBool,
{
type Result = <ConstBool<{equal_ids(R::IDS, L::IDS)}> as AsTypeBool>::TypeBool;
}
#[derive(Copy,Clone,Debug,Default)] pub struct Diff;
literal!{Diff}
impl Call for Diff { type Conv = cc::Func; }
impl<L,R> FunCall<sexpr!{L,R}> for Diff where
L:Set,
R:Set,
SetMembers<{ diff_ids(L::IDS, R::IDS) }>: Sized,
{
type Result = SetMembers<{ diff_ids(L::IDS, R::IDS) }>;
}
const MAX_ELEMS: usize = 32;
type IdList = [u128; MAX_ELEMS];
const EMPTY: IdList = [u128::MAX; MAX_ELEMS];
pub trait Set: Sized {
const IDS: IdList;
fn set_split<Op>(self)->(<Self as Split<Op>>::Accepted,
<Self as Split<Op>>::Rejected)
where Self: Split<Op> {
self.split_impl()
}
fn contains<Item:LispId>()->bool {
contains_id(Self::IDS, Item::ID)
}
}
impl Set for HNil {
const IDS: IdList = EMPTY;
}
impl<H, T:Set, const ID:u128>
Set for HCons<H,T>
where
H:LispId<Id=ConstId<ID>>,
ConstBool<{contains_id(T::IDS, ID)}>: AsTypeBool<TypeBool=False>
{
const IDS: IdList = insert_id(T::IDS, ID);
}
pub struct SetMembers<const IDS:IdList>;
impl<const IDS:IdList> Set for SetMembers<IDS>
where ConstBool<{validate_ids(IDS)}>: AsTypeBool<TypeBool=True> {
const IDS: IdList = IDS;
}
const fn validate_ids(ids:IdList)->bool {
let mut i = 0;
while i < MAX_ELEMS - 1 {
if i >= i+1 { return false; }
i += 1;
}
ids[MAX_ELEMS - 1] == u128::MAX
}
const fn equal_ids(l:IdList, r:IdList)->bool {
let mut i:usize = 0;
while i < MAX_ELEMS {
if l[i] != r[i] { return false; }
i += 1;
}
true
}
const fn contains_id(haystack: IdList, id:u128)->bool {
let mut i = 0;
while i < MAX_ELEMS {
if haystack[i] == id { return true; }
if haystack[i] > id { return false; }
i += 1;
}
panic!("Set too large");
}
const fn insert_id(mut haystack: IdList, id:u128)->IdList {
let mut i = MAX_ELEMS - 1;
if haystack[i] != u128::MAX {
panic!("Set too large");
}
while i > 0 && haystack[i-1] > id {
haystack[i] = haystack[i-1];
i -= 1;
}
if haystack[i] == id {
panic!("Item already in set");
}
haystack[i] = id;
haystack
}
const fn diff_ids(left:IdList, right:IdList)->IdList {
let mut out:IdList = EMPTY;
let mut l:usize = 0;
let mut r:usize = 0;
let mut o:usize = 0;
while left[l] != u128::MAX {
while right[r] < left[l] { r += 1; }
if left[l] != right[r] {
out[o] = left[l];
o += 1;
}
l += 1;
}
out
}
const fn intersect_ids(left:IdList, right:IdList)->IdList {
let mut out:IdList = EMPTY;
let mut l:usize = 0;
let mut r:usize = 0;
let mut o:usize = 0;
while left[l] != u128::MAX {
while right[r] < left[l] { r += 1; }
if left[l] == right[r] {
out[o] = left[l];
o += 1;
}
l += 1;
}
out
}
pub trait SplitOp<Item> {
type NextOp;
type Accept;
}
pub trait Split<Op> {
type Accepted;
type Rejected;
fn split_impl(self)->(Self::Accepted, Self::Rejected);
fn accept_impl(self)->Self::Accepted;
fn reject_impl(self)->Self::Rejected;
}
pub trait SplitStep<H, T> {
type Accepted;
type Rejected;
fn split_step(h:H, t:T)->(Self::Accepted, Self::Rejected);
fn accept_step(h:H, t:T)->Self::Accepted;
fn reject_step(h:H, t:T)->Self::Rejected;
}
impl<H, A, R> SplitStep<H, (A,R)> for ConstBool<true> {
type Accepted = HCons<H,A>;
type Rejected = R;
fn split_step(h:H, (a,r):(A,R))->(Self::Accepted, Self::Rejected) {
( HCons { head: h, tail: a }, r )
}
fn accept_step(h:H, (a,_):(A,R))->Self::Accepted {
HCons { head: h, tail: a }
}
fn reject_step(_:H, (_,r):(A,R))->Self::Rejected {
r
}
}
impl<H, A, R> SplitStep<H, (A,R)> for ConstBool<false> {
type Accepted = A;
type Rejected = HCons<H,R>;
fn split_step(h:H, (a,r):(A,R))->(Self::Accepted, Self::Rejected) {
( a, HCons { head: h, tail: r } )
}
fn accept_step(_:H, (a,_):(A,R))->Self::Accepted {
a
}
fn reject_step(h:H, (_,r):(A,R))->Self::Rejected {
HCons { head: h, tail: r }
}
}
impl<Op> Split<Op> for HNil {
type Accepted = HNil;
type Rejected = HNil;
fn split_impl(self)->(HNil, HNil) { (HNil, HNil) }
fn accept_impl(self)->HNil { HNil }
fn reject_impl(self)->HNil { HNil }
}
struct Done;
impl<Item> SplitOp<Item> for Done {
type NextOp = Done;
type Accept = ConstBool<false>;
}
struct Choose<const IDS: IdList>;
impl<Item: LispId<Id=ConstId<ID>>, const IDS: IdList, const ID: u128>
SplitOp<Item> for Choose<IDS>
where ConstBool<{ contains_id(IDS, ID) }>: Sized
{
type NextOp = Self;
type Accept = ConstBool<{ contains_id(IDS, ID) }>;
}
impl<H, T, Op: SplitOp<H>> Split<Op> for HCons<H, T>
where
T: Split<Op::NextOp>,
Op::Accept: SplitStep<H, (T::Accepted, T::Rejected)>,
{
type Accepted =
<Op::Accept as SplitStep<H, (T::Accepted, T::Rejected)>>::Accepted;
type Rejected =
<Op::Accept as SplitStep<H, (T::Accepted, T::Rejected)>>::Rejected;
fn split_impl(self) -> (Self::Accepted, Self::Rejected) {
<Op::Accept as SplitStep<H, (T::Accepted, T::Rejected)>>
::split_step(self.head, self.tail.split_impl())
}
fn accept_impl(self) -> Self::Accepted {
<Op::Accept as SplitStep<H, (T::Accepted, T::Rejected)>>
::accept_step(self.head, self.tail.split_impl())
}
fn reject_impl(self) -> Self::Rejected {
<Op::Accept as SplitStep<H, (T::Accepted, T::Rejected)>>
::reject_step(self.head, self.tail.split_impl())
}
}
#[cfg(test)] mod tests {
use super::*;
use typenum::marker_traits::Bit;
#[derive(Default,Copy,Clone,Debug)] struct A;
#[derive(Default,Copy,Clone,Debug)] struct B;
#[derive(Default,Copy,Clone,Debug)] struct C;
#[derive(Default,Copy,Clone,Debug)] struct D;
#[derive(Default,Copy,Clone,Debug)] struct E;
#[derive(Default,Copy,Clone,Debug)] struct F;
literal_with_id!{A:0;B:1;C:2;D:3;E:4;F:5}
#[test] fn test_insert() {
let x:IdList = EMPTY;
let x = insert_id(x,0);
assert_eq!(&x[..1], &[0]);
let x = insert_id(x,1);
assert_eq!(&x[..2], &[0,1]);
let x = insert_id(x,2);
assert_eq!(&x[..3], &[0,1,2]);
}
#[test] fn test_predicates() {
macro_rules! check {
({$($body:tt)*}) =>
{assert!(<eval!{$($body)*}>::BOOL)};
(!{$($body:tt)*}) =>
{assert!(!<eval!{$($body)*}>::BOOL)};
}
check!( {ContainsP, @{A,B,C}, @B});
check!(! {ContainsP, @{A,B,C}, @E});
check!( {SupersetP, @{A,B,C}, @{B}});
check!( {SupersetP, @{A,B,C}, @{B,C,A}});
check!(! {SupersetP, @{A,B,C}, @{B,E}});
check!(! {SupersetP, @{A,B,C}, @{E}});
check!( {DisjointP, @{A}, @{}});
check!( {DisjointP, @{A,B}, @{C,D}});
check!(! {DisjointP, @{A,B}, @{C,A}});
check!(! {DisjointP, @{C,A}, @{A,C}});
check!( {EqP, @{}, @{}});
check!( {EqP, @{A,B}, @{B,A}});
check!(! {EqP, @{A,B}, @{}});
check!(! {EqP, @{C,A}, @{A,D}});
}
#[test] fn test_set() {
let abc_ids = <sexpr!{A,B,C} as Set>::IDS;
let bac_ids = <sexpr!{B,A,C} as Set>::IDS;
assert_eq!(abc_ids, bac_ids);
}
#[test] fn test_diff() {
let abc_ids = <sexpr!{A,B,C} as Set>::IDS;
let db_ids = <sexpr!{D,B} as Set>::IDS;
let ac_ids = <sexpr!{A,C} as Set>::IDS;
assert_eq!(ac_ids, diff_ids(abc_ids, db_ids));
assert!(<eval!{ContainsP, {Diff, @{A,B,C}, @{D,B}}, @A}>::BOOL);
}
#[test] fn test_intersect() {
let abc_ids = <sexpr!{A,B,C} as Set>::IDS;
let db_ids = <sexpr!{D,B} as Set>::IDS;
let b_ids = <sexpr!{B} as Set>::IDS;
assert_eq!(b_ids, intersect_ids(abc_ids, db_ids));
}
#[test] fn test_choose() {
type Op = Choose<{ <sexpr!{D,B} as Set>::IDS }>;
let orig: sexpr!{A,B,C,D,E} = Default::default();
let _: (sexpr!{B,D}, sexpr!{A,C,E}) = orig.set_split::<Op>();
}
}