mech_set/operations/
powerset.rs

1
2use std::cell::RefCell;
3
4use crate::*;
5
6use indexmap::set::IndexSet;
7use mech_core::set::MechSet;
8
9// Powerset ------------------------------------------------------------------------
10
11#[derive(Debug)]
12struct SetPowersetFxn {
13  input: Ref<MechSet>,
14  out: Ref<MechSet>,
15}
16impl MechFunctionFactory for SetPowersetFxn {
17  fn new(args: FunctionArgs) -> MResult<Box<dyn MechFunction>> {
18    match args {
19      FunctionArgs::Unary(out, input) => {
20        let input: Ref<MechSet> = unsafe { input.as_unchecked() }.clone();
21        let out: Ref<MechSet> = unsafe { out.as_unchecked() }.clone();
22        Ok(Box::new(SetPowersetFxn {input, out }))
23      },
24      _ => Err(MechError2::new(IncorrectNumberOfArguments { expected: 1, found: args.len() }, None).with_compiler_loc()),
25    }
26  }    
27}
28
29fn powerset_recursive<T>(set: &Vec<T>) -> Vec<Vec<T>>
30    where T: std::fmt::Debug + Clone,
31{
32    if set.len() == 0
33    {
34        return vec![vec![]];
35    }
36    let mut with_set = powerset_recursive_aux(set, vec![vec![set[0].clone()]], 1);
37    let mut without_set = powerset_recursive_aux(set, vec![vec![]], 1);
38    with_set.append(&mut without_set);
39    with_set.sort_by(|a, b| a.len().cmp(&b.len()));
40    with_set
41}
42
43fn powerset_recursive_aux<T>(set: &Vec<T>, mut unfinished_set: Vec<Vec<T>>, index: usize) -> Vec<Vec<T>>
44    where T: std::fmt::Debug + Clone,
45{
46    if index == set.len()
47    {
48        return unfinished_set;
49    }
50    let mut with_set = powerset_recursive_aux(set, unfinished_set.iter_mut().
51        map(|x| {let mut y = x.clone(); y.push(set[index].clone()); y}).collect(), index + 1);
52    let mut without_set = powerset_recursive_aux(set, unfinished_set, index + 1);
53    with_set.append(&mut without_set);
54    with_set
55}
56
57impl MechFunctionImpl for SetPowersetFxn {
58  fn solve(&self) {
59    unsafe {
60      // Get mutable reference to the output set
61      let out_ptr: &mut MechSet = &mut *(self.out.as_mut_ptr());
62
63      // Get references to lhs and rhs sets
64      let input_ptr: &MechSet = &*(self.input.as_ptr());
65
66      // Clear the output set first (optional, depending on semantics)
67      out_ptr.set.clear();
68
69      // Powerset input into output
70      let vec_set = powerset_recursive(&(input_ptr.set.clone().into_iter().collect()));
71      for set in vec_set
72      {
73        out_ptr.set.insert(Value::Set(Ref::new(MechSet::from_vec(set))));
74      }
75
76      // Update metadata
77      out_ptr.num_elements = out_ptr.set.len();
78      out_ptr.kind = ValueKind::Set(Box::new(input_ptr.kind.clone()), None);
79    }
80  }
81  fn out(&self) -> Value { Value::Set(self.out.clone()) }
82  fn to_string(&self) -> String { format!("{:#?}", self) }
83}
84#[cfg(feature = "compiler")]
85impl MechFunctionCompiler for SetPowersetFxn {
86  fn compile(&self, ctx: &mut CompileCtx) -> MResult<Register> {
87    let name = format!("SetPowersetFxn");
88    compile_unop!(name, self.out, self.input, ctx, FeatureFlag::Custom(hash_str("set/powerset")));
89  }
90}
91register_descriptor! {
92  FunctionDescriptor {
93    name: "SetPowersetFxn",
94    ptr: SetPowersetFxn::new,
95  }
96}
97
98fn set_powerset_fxn(input: Value) -> MResult<Box<dyn MechFunction>> {
99  match (input) {
100    (Value::Set(input)) => {
101      Ok(Box::new(SetPowersetFxn { input: input.clone(), out: Ref::new(MechSet::new(input.borrow().kind.clone(), 2_u32.pow(input.borrow().num_elements as u32) as usize)) }))
102    },
103    x => Err(MechError2::new(
104      UnhandledFunctionArgumentKind1 { arg: x.kind(), fxn_name: "set/powerset".to_string() },
105      None
106    ).with_compiler_loc()),
107  }
108}
109
110pub struct SetPowerset {}
111impl NativeFunctionCompiler for SetPowerset {
112  fn compile(&self, arguments: &Vec<Value>) -> MResult<Box<dyn MechFunction>> {
113    if arguments.len() != 1 {
114      return Err(MechError2::new(IncorrectNumberOfArguments { expected: 1, found: arguments.len() }, None).with_compiler_loc());
115    }
116    let input = arguments[0].clone();
117    match set_powerset_fxn(input.clone()) {
118      Ok(fxn) => Ok(fxn),
119      Err(x) => {
120        match input {
121          Value::MutableReference(input) => { set_powerset_fxn(input.borrow().clone()) },
122          input => { set_powerset_fxn(input.clone()) },
123          x => Err(MechError2::new(
124            UnhandledFunctionArgumentKind1 { arg: x.kind(), fxn_name: "set/powerset".to_string() },
125            None
126          ).with_compiler_loc()),
127        }
128      }
129    }
130  }
131}
132
133register_descriptor! {
134  FunctionCompilerDescriptor {
135    name: "set/powerset",
136    ptr: &SetPowerset{},
137  }
138}
mech_set/operations/powerset.rs

mech_set/operations/
powerset.rs
