1#[derive(Eq, Clone)]
2pub enum Bool {
3 True,
4 False,
5 /// can be any number in `0..32`, anything else will cause panics or wrong results
6 Term(u8),
7 /// needs to contain at least two elements
8 And(Vec<Bool>),
9 /// needs to contain at least two elements
10 Or(Vec<Bool>),
11 Not(Box<Bool>),
12}
13
14#[cfg(feature="quickcheck")]
15extern crate quickcheck;
16
17#[cfg(feature="quickcheck")]
18impl quickcheck::Arbitrary for Bool {
19 fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self {
20 let mut terms = 0;
21 arbitrary_bool(g, 10, &mut terms)
22 }
23 fn shrink(&self) -> Box<Iterator<Item=Self>> {
24 match *self {
25 Bool::And(ref v) => Box::new(v.shrink().filter(|v| v.len() > 2).map(Bool::And)),
26 Bool::Or(ref v) => Box::new(v.shrink().filter(|v| v.len() > 2).map(Bool::Or)),
27 Bool::Not(ref inner) => Box::new(inner.shrink().map(|b| Bool::Not(Box::new(b)))),
28 _ => quickcheck::empty_shrinker(),
29 }
30 }
31}
32
33#[cfg(feature="quickcheck")]
34fn arbitrary_bool<G: quickcheck::Gen>(g: &mut G, depth: usize, terms: &mut u8) -> Bool {
35 if depth == 0 {
36 match g.gen_range(0, 3) {
37 0 => Bool::True,
38 1 => Bool::False,
39 2 => arbitrary_term(g, terms),
40 _ => unreachable!(),
41 }
42 } else {
43 match g.gen_range(0, 6) {
44 0 => Bool::True,
45 1 => Bool::False,
46 2 => arbitrary_term(g, terms),
47 3 => Bool::And(arbitrary_vec(g, depth - 1, terms)),
48 4 => Bool::Or(arbitrary_vec(g, depth - 1, terms)),
49 5 => Bool::Not(Box::new(arbitrary_bool(g, depth - 1, terms))),
50 _ => unreachable!(),
51 }
52 }
53}
54
55#[cfg(feature="quickcheck")]
56fn arbitrary_term<G: quickcheck::Gen>(g: &mut G, terms: &mut u8) -> Bool {
57 if *terms == 0 {
58 Bool::Term(*terms)
59 } else if *terms < 32 && g.gen_weighted_bool(3) {
60 *terms += 1;
61 // every term needs to show up at least once
62 Bool::Term(*terms - 1)
63 } else {
64 Bool::Term(g.gen_range(0, *terms))
65 }
66}
67
68#[cfg(feature="quickcheck")]
69fn arbitrary_vec<G: quickcheck::Gen>(g: &mut G, depth: usize, terms: &mut u8) -> Vec<Bool> {
70 (0..g.gen_range(2, 20)).map(|_| arbitrary_bool(g, depth, terms)).collect()
71}
72
73impl PartialEq for Bool {
74 fn eq(&self, other: &Self) -> bool {
75 use self::Bool::*;
76 match (self, other) {
77 (&True, &True) |
78 (&False, &False) => true,
79 (&Term(a: u8), &Term(b: u8)) => a == b,
80 (&Not(ref a: &Box), &Not(ref b: &Box)) => a == b,
81 (&And(ref a: &Vec), &And(ref b: &Vec)) |
82 (&Or(ref a: &Vec), &Or(ref b: &Vec)) => {
83 if a.len() != b.len() {
84 return false;
85 }
86 for a: &Bool in a {
87 if !b.iter().any(|b: &Bool| b == a) {
88 return false;
89 }
90 }
91 true
92 },
93 _ => false,
94 }
95 }
96}
97
98impl std::ops::Not for Bool {
99 type Output = Bool;
100 fn not(self) -> Bool {
101 use self::Bool::*;
102 match self {
103 True => False,
104 False => True,
105 t: Bool @ Term(_) => Not(Box::new(t)),
106 And(mut v: Vec) => {
107 for el: &mut Bool in &mut v {
108 *el = !std::mem::replace(dest:el, src:False);
109 }
110 Or(v)
111 },
112 Or(mut v: Vec) => {
113 for el: &mut Bool in &mut v {
114 *el = !std::mem::replace(dest:el, src:False);
115 }
116 And(v)
117 },
118 Not(inner: Box) => *inner,
119 }
120 }
121}
122
123impl std::ops::BitAnd for Bool {
124 type Output = Self;
125 fn bitand(self, rhs: Bool) -> Bool {
126 use self::Bool::*;
127 match (self, rhs) {
128 (And(mut v: Vec), And(rhs: Vec)) => {
129 v.extend(iter:rhs);
130 And(v)
131 },
132 (False, _) |
133 (_, False) => False,
134 (b: Bool, True) |
135 (True, b: Bool) => b,
136 (other: Bool, And(mut v: Vec)) |
137 (And(mut v: Vec), other: Bool) => {
138 v.push(other);
139 And(v)
140 },
141 (a: Bool, b: Bool) => And(vec![a, b]),
142 }
143 }
144}
145
146impl std::ops::BitOr for Bool {
147 type Output = Self;
148 fn bitor(self, rhs: Bool) -> Bool {
149 use self::Bool::*;
150 match (self, rhs) {
151 (Or(mut v: Vec), Or(rhs: Vec)) => {
152 v.extend(iter:rhs);
153 Or(v)
154 },
155 (False, b: Bool) |
156 (b: Bool, False) => b,
157 (_, True) |
158 (True, _) => True,
159 (other: Bool, Or(mut v: Vec)) |
160 (Or(mut v: Vec), other: Bool) => {
161 v.push(other);
162 Or(v)
163 },
164 (a: Bool, b: Bool) => Or(vec![a, b]),
165 }
166 }
167}
168
169impl Bool {
170 pub fn terms(&self) -> u32 {
171 use self::Bool::*;
172 match *self {
173 Term(u) => 1 << u,
174 Or(ref a) |
175 And(ref a) => a.iter().fold(0, |state, item| { state | item.terms() }),
176 Not(ref a) => a.terms(),
177 True | False => 0,
178 }
179 }
180
181 pub fn eval(&self, terms: u32) -> bool {
182 use self::Bool::*;
183 match *self {
184 True => true,
185 False => false,
186 Term(i) => (terms & (1 << i)) != 0,
187 And(ref a) => a.iter().all(|item| item.eval(terms)),
188 Or(ref a) => a.iter().any(|item| item.eval(terms)),
189 Not(ref a) => !a.eval(terms),
190 }
191 }
192
193 pub fn minterms(&self) -> Vec<Term> {
194 let terms = self.terms();
195 let number_of_terms = terms.count_ones();
196 assert!((0..number_of_terms).all(|i| (terms & (1 << i)) != 0), "non-continuous naming scheme");
197 (0..(1 << number_of_terms)).filter(|&i| self.eval(i)).map(Term::new).collect()
198 }
199
200 pub fn simplify(&self) -> Vec<Bool> {
201 let minterms = self.minterms();
202 if minterms.is_empty() {
203 return vec![Bool::False];
204 }
205 let variables = self.terms().count_ones();
206 if variables == 0 {
207 return vec![Bool::True];
208 }
209 let essentials = essential_minterms(minterms);
210 let expr = essentials.prime_implicant_expr();
211 let simple = simplify_prime_implicant_expr(expr);
212 let shortest = simple.iter().map(Vec::len).min().unwrap();
213 simple.into_iter()
214 .filter(|v| v.len() == shortest)
215 .map(|v| {
216 let mut v = v.into_iter()
217 .map(|i| essentials.essentials[i as usize]
218 .to_bool_expr(variables));
219 if v.len() == 1 {
220 v.next().unwrap()
221 } else {
222 Bool::Or(v.collect())
223 }
224 }).collect()
225 }
226}
227
228impl std::fmt::Debug for Bool {
229 fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
230 use self::Bool::*;
231 match *self {
232 True => write!(fmt, "T"),
233 False => write!(fmt, "F"),
234 Term(i) if i > 32 => write!(fmt, "<bad term id {}>", i),
235 Term(i) => write!(fmt, "{}", "abcdefghijklmnopqrstuvwxyzαβγδεζη".chars().nth(i as usize).unwrap()),
236 Not(ref a) => match **a {
237 And(_) | Or(_) => write!(fmt, "({:?})'", a),
238 _ => write!(fmt, "{:?}'", a),
239 },
240 And(ref a) => {
241 for a in a {
242 match *a {
243 And(_) | Or(_) => try!(write!(fmt, "({:?})", a)),
244 _ => try!(write!(fmt, "{:?}", a)),
245 }
246 }
247 Ok(())
248 },
249 Or(ref a) => {
250 try!(write!(fmt, "{:?}", a[0]));
251 for a in &a[1..] {
252 match *a {
253 Or(_) => try!(write!(fmt, " + ({:?})", a)),
254 _ => try!(write!(fmt, " + {:?}", a)),
255 }
256 }
257 Ok(())
258 }
259 }
260 }
261}
262
263#[derive(Debug)]
264pub struct Essentials {
265 pub minterms: Vec<Term>,
266 pub essentials: Vec<Term>,
267}
268
269pub fn simplify_prime_implicant_expr(mut e: Vec<Vec<Vec<u32>>>) -> Vec<Vec<u32>> {
270 loop {
271 let a: Vec> = e.pop().unwrap();
272 if let Some(b: Vec>) = e.pop() {
273 let distributed: Vec> = distribute(&a, &b);
274 let simplified: Vec> = simplify(distributed);
275 e.push(simplified);
276 } else {
277 return a;
278 }
279 }
280}
281
282// AA -> A
283// A + AB -> A
284// A + A -> A
285fn simplify(mut e: Vec<Vec<u32>>) -> Vec<Vec<u32>> {
286 for e in &mut e {
287 e.sort();
288 e.dedup();
289 }
290 e.sort();
291 e.dedup();
292 let mut del = Vec::new();
293 for (i, a) in e.iter().enumerate() {
294 for (j, b) in e[i..].iter().enumerate() {
295 if a.len() < b.len() {
296 // A + AB -> delete AB
297 if a.iter().all(|x| b.iter().any(|y| y == x)) {
298 del.push(j + i);
299 }
300 } else if b.len() < a.len() && b.iter().all(|x| a.iter().any(|y| y == x)) {
301 // AB + A -> delete AB
302 del.push(i);
303 }
304 }
305 }
306 del.sort();
307 del.dedup();
308 for del in del.into_iter().rev() {
309 e.swap_remove(del);
310 }
311 e
312}
313
314// (AB + CD)(EF + GH) -> ABEF + ABGH + CDEF + CDGH
315fn distribute(l: &[Vec<u32>], r: &[Vec<u32>]) -> Vec<Vec<u32>> {
316 let mut ret: Vec> = Vec::new();
317 assert!(!l.is_empty());
318 assert!(!r.is_empty());
319 for l: &Vec in l {
320 for r: &Vec in r {
321 ret.push(l.iter().chain(r).cloned().collect());
322 }
323 }
324 ret
325}
326
327
328impl Essentials {
329 pub fn prime_implicant_expr(&self) -> Vec<Vec<Vec<u32>>> {
330 let mut v: Vec>> = Vec::new();
331 for t: &Term in &self.minterms {
332 let mut w: Vec> = Vec::new();
333 for (i: usize, e: &Term) in self.essentials.iter().enumerate() {
334 if e.contains(t) {
335 assert_eq!(i as u32 as usize, i);
336 w.push(vec![i as u32]);
337 }
338 }
339 v.push(w);
340 }
341 v
342 }
343}
344
345#[derive(Clone, Eq, Ord)]
346pub struct Term {
347 dontcare: u32,
348 term: u32,
349}
350
351#[cfg(feature="quickcheck")]
352impl quickcheck::Arbitrary for Term {
353 fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self {
354 Term {
355 dontcare: u32::arbitrary(g),
356 term: u32::arbitrary(g),
357 }
358 }
359}
360
361impl std::cmp::PartialOrd for Term {
362 fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
363 use std::cmp::Ordering::*;
364 match self.dontcare.partial_cmp(&rhs.dontcare) {
365 Some(Equal) => {},
366 other: Option => return other,
367 }
368 let l: u32 = self.term & !self.dontcare;
369 let r: u32 = rhs.term & !rhs.dontcare;
370 l.partial_cmp(&r)
371 }
372}
373
374impl std::fmt::Debug for Term {
375 fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
376 for i: i32 in (0..32).rev() {
377 if (self.dontcare & (1 << i)) == 0 {
378 if (self.term & (1 << i)) == 0 {
379 try!(write!(fmt, "0"));
380 } else {
381 try!(write!(fmt, "1"));
382 }
383 } else {
384 try!(write!(fmt, "-"));
385 }
386 }
387 Ok(())
388 }
389}
390
391impl std::cmp::PartialEq for Term {
392 fn eq(&self, other: &Self) -> bool {
393 (self.dontcare == other.dontcare) && ((self.term & !self.dontcare) == (other.term & !other.dontcare))
394 }
395}
396
397#[derive(Debug, Eq, PartialEq)]
398pub enum TermFromStrError {
399 Only32TermsSupported,
400 UnsupportedCharacter(char),
401}
402
403impl std::str::FromStr for Term {
404 type Err = TermFromStrError;
405 fn from_str(s: &str) -> Result<Self, Self::Err> {
406 if s.len() > 32 {
407 return Err(TermFromStrError::Only32TermsSupported);
408 }
409 let mut term: Term = Term::new(0);
410 for (i: usize, c: char) in s.chars().rev().enumerate() {
411 match c {
412 '-' => term.dontcare |= 1 << i,
413 '1' => term.term |= 1 << i,
414 '0' => {},
415 c: char => return Err(TermFromStrError::UnsupportedCharacter(c)),
416 }
417 }
418 Ok(term)
419 }
420}
421
422impl Term {
423 pub fn new(i: u32) -> Self {
424 Term {
425 dontcare: 0,
426 term: i,
427 }
428 }
429
430 pub fn with_dontcare(term: u32, dontcare: u32) -> Self {
431 Term {
432 dontcare: dontcare,
433 term: term,
434 }
435 }
436
437 pub fn combine(&self, other: &Term) -> Option<Term> {
438 let dc = self.dontcare ^ other.dontcare;
439 let term = self.term ^ other.term;
440 let dc_mask = self.dontcare | other.dontcare;
441 match (dc.count_ones(), (!dc_mask & term).count_ones()) {
442 (0, 1) |
443 (1, 0) => Some(Term {
444 dontcare: dc_mask | term,
445 term: self.term,
446 }),
447 _ => None,
448 }
449 }
450
451 pub fn contains(&self, other: &Self) -> bool {
452 ((self.dontcare | other.dontcare) == self.dontcare) &&
453 (((self.term ^ other.term) & !self.dontcare) == 0)
454 }
455
456 pub fn to_bool_expr(&self, n_variables: u32) -> Bool {
457 assert!(self.dontcare < (1 << n_variables));
458 assert!(self.term < (1 << n_variables));
459 let mut v = Vec::new();
460 for bit in 0..n_variables {
461 if (self.dontcare & (1 << bit)) == 0 {
462 if (self.term & (1 << bit)) == 0 {
463 v.push(Bool::Not(Box::new(Bool::Term(bit as u8))))
464 } else {
465 v.push(Bool::Term(bit as u8))
466 }
467 }
468 }
469 match v.len() {
470 0 => Bool::True,
471 1 => v.into_iter().next().unwrap(),
472 _ => Bool::And(v),
473 }
474 }
475}
476
477pub fn essential_minterms(mut minterms: Vec<Term>) -> Essentials {
478 minterms.sort();
479 let minterms = minterms;
480 let mut terms = minterms.clone();
481 let mut essentials: Vec<Term> = Vec::new();
482 while !terms.is_empty() {
483 let old = std::mem::replace(&mut terms, Vec::new());
484 let mut combined_terms = std::collections::BTreeSet::new();
485 for (i, term) in old.iter().enumerate() {
486 for (other_i, other) in old[i..].iter().enumerate() {
487 if let Some(new_term) = term.combine(other) {
488 terms.push(new_term);
489 combined_terms.insert(other_i + i);
490 combined_terms.insert(i);
491 }
492 }
493 if !combined_terms.contains(&i) {
494 essentials.push(term.clone());
495 }
496 }
497 terms.sort();
498 terms.dedup();
499 }
500 Essentials {
501 minterms: minterms,
502 essentials: essentials,
503 }
504}
505