]>
git.proxmox.com Git - rustc.git/blob - src/vendor/quine-mc_cluskey/src/lib.rs
5 /// can be any number in `0..32`, anything else will cause panics or wrong results
7 /// needs to contain at least two elements
9 /// needs to contain at least two elements
14 #[cfg(feature="quickcheck")]
15 extern crate quickcheck
;
17 #[cfg(feature="quickcheck")]
18 impl quickcheck
::Arbitrary
for Bool
{
19 fn arbitrary
<G
: quickcheck
::Gen
>(g
: &mut G
) -> Self {
21 arbitrary_bool(g
, 10, &mut terms
)
23 fn shrink(&self) -> Box
<Iterator
<Item
=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(),
33 #[cfg(feature="quickcheck")]
34 fn arbitrary_bool
<G
: quickcheck
::Gen
>(g
: &mut G
, depth
: usize, terms
: &mut u8) -> Bool
{
36 match g
.gen_range(0, 3) {
39 2 => arbitrary_term(g
, terms
),
43 match g
.gen_range(0, 6) {
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
))),
55 #[cfg(feature="quickcheck")]
56 fn arbitrary_term
<G
: quickcheck
::Gen
>(g
: &mut G
, terms
: &mut u8) -> Bool
{
59 } else if *terms
< 32 && g
.gen_weighted_bool(3) {
61 // every term needs to show up at least once
62 Bool
::Term(*terms
- 1)
64 Bool
::Term(g
.gen_range(0, *terms
))
68 #[cfg(feature="quickcheck")]
69 fn 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()
73 impl PartialEq
for Bool
{
74 fn eq(&self, other
: &Self) -> bool
{
78 (&False
, &False
) => true,
79 (&Term(a
), &Term(b
)) => a
== b
,
80 (&Not(ref a
), &Not(ref b
)) => a
== b
,
81 (&And(ref a
), &And(ref b
)) |
82 (&Or(ref a
), &Or(ref b
)) => {
83 if a
.len() != b
.len() {
87 if !b
.iter().any(|b
| b
== a
) {
98 impl std
::ops
::Not
for Bool
{
100 fn not(self) -> Bool
{
105 t @
Term(_
) => Not(Box
::new(t
)),
108 *el
= !std
::mem
::replace(el
, False
);
114 *el
= !std
::mem
::replace(el
, False
);
118 Not(inner
) => *inner
,
123 impl std
::ops
::BitAnd
for Bool
{
125 fn bitand(self, rhs
: Bool
) -> Bool
{
128 (And(mut v
), And(rhs
)) => {
136 (other
, And(mut v
)) |
137 (And(mut v
), other
) => {
141 (a
, b
) => And(vec
![a
, b
]),
146 impl std
::ops
::BitOr
for Bool
{
148 fn bitor(self, rhs
: Bool
) -> Bool
{
151 (Or(mut v
), Or(rhs
)) => {
160 (Or(mut v
), other
) => {
164 (a
, b
) => Or(vec
![a
, b
]),
170 pub fn terms(&self) -> u32 {
175 And(ref a
) => a
.iter().fold(0, |state
, item
| { state | item.terms() }
),
176 Not(ref a
) => a
.terms(),
181 pub fn eval(&self, terms
: u32) -> bool
{
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
),
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()
200 pub fn simplify(&self) -> Vec
<Bool
> {
201 let minterms
= self.minterms();
202 if minterms
.is_empty() {
203 return vec
![Bool
::False
];
205 let variables
= self.terms().count_ones();
207 return vec
![Bool
::True
];
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();
214 .filter(|v
| v
.len() == shortest
)
216 let mut v
= v
.into_iter()
217 .map(|i
| essentials
.essentials
[i
as usize]
218 .to_bool_expr(variables
));
222 Bool
::Or(v
.collect())
228 impl std
::fmt
::Debug
for Bool
{
229 fn fmt(&self, fmt
: &mut std
::fmt
::Formatter
) -> std
::fmt
::Result
{
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
),
243 And(_
) | Or(_
) => try
!(write
!(fmt
, "({:?})", a
)),
244 _
=> try
!(write
!(fmt
, "{:?}", a
)),
250 try
!(write
!(fmt
, "{:?}", a
[0]));
253 Or(_
) => try
!(write
!(fmt
, " + ({:?})", a
)),
254 _
=> try
!(write
!(fmt
, " + {:?}", a
)),
264 pub struct Essentials
{
265 pub minterms
: Vec
<Term
>,
266 pub essentials
: Vec
<Term
>,
269 pub fn simplify_prime_implicant_expr(mut e
: Vec
<Vec
<Vec
<u32>>>) -> Vec
<Vec
<u32>> {
271 let a
= e
.pop().unwrap();
272 if let Some(b
) = e
.pop() {
273 let distributed
= distribute(&a
, &b
);
274 let simplified
= simplify(distributed
);
285 fn simplify(mut e
: Vec
<Vec
<u32>>) -> Vec
<Vec
<u32>> {
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
)) {
300 } else if b
.len() < a
.len() && b
.iter().all(|x
| a
.iter().any(|y
| y
== x
)) {
301 // AB + A -> delete AB
308 for del
in del
.into_iter().rev() {
314 // (AB + CD)(EF + GH) -> ABEF + ABGH + CDEF + CDGH
315 fn distribute(l
: &[Vec
<u32>], r
: &[Vec
<u32>]) -> Vec
<Vec
<u32>> {
316 let mut ret
= Vec
::new();
317 assert
!(!l
.is_empty());
318 assert
!(!r
.is_empty());
321 ret
.push(l
.iter().chain(r
).cloned().collect());
329 pub fn prime_implicant_expr(&self) -> Vec
<Vec
<Vec
<u32>>> {
330 let mut v
= Vec
::new();
331 for t
in &self.minterms
{
332 let mut w
= Vec
::new();
333 for (i
, e
) in self.essentials
.iter().enumerate() {
335 assert_eq
!(i
as u32 as usize, i
);
336 w
.push(vec
![i
as u32]);
345 #[derive(Clone, Eq, Ord)]
351 #[cfg(feature="quickcheck")]
352 impl quickcheck
::Arbitrary
for Term
{
353 fn arbitrary
<G
: quickcheck
::Gen
>(g
: &mut G
) -> Self {
355 dontcare
: u32::arbitrary(g
),
356 term
: u32::arbitrary(g
),
361 impl 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
) {
366 other
=> return other
,
368 let l
= self.term
& !self.dontcare
;
369 let r
= rhs
.term
& !rhs
.dontcare
;
374 impl std
::fmt
::Debug
for Term
{
375 fn fmt(&self, fmt
: &mut std
::fmt
::Formatter
) -> std
::fmt
::Result
{
376 for i
in (0..32).rev() {
377 if (self.dontcare
& (1 << i
)) == 0 {
378 if (self.term
& (1 << i
)) == 0 {
379 try
!(write
!(fmt
, "0"));
381 try
!(write
!(fmt
, "1"));
384 try
!(write
!(fmt
, "-"));
391 impl 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
))
397 #[derive(Debug, Eq, PartialEq)]
398 pub enum TermFromStrError
{
399 Only32TermsSupported
,
400 UnsupportedCharacter(char),
403 impl std
::str::FromStr
for Term
{
404 type Err
= TermFromStrError
;
405 fn from_str(s
: &str) -> Result
<Self, Self::Err
> {
407 return Err(TermFromStrError
::Only32TermsSupported
);
409 let mut term
= Term
::new(0);
410 for (i
, c
) in s
.chars().rev().enumerate() {
412 '
-'
=> term
.dontcare
|= 1 << i
,
413 '
1'
=> term
.term
|= 1 << i
,
415 c
=> return Err(TermFromStrError
::UnsupportedCharacter(c
)),
423 pub fn new(i
: u32) -> Self {
430 pub fn with_dontcare(term
: u32, dontcare
: u32) -> Self {
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()) {
443 (1, 0) => Some(Term
{
444 dontcare
: dc_mask
| term
,
451 pub fn contains(&self, other
: &Self) -> bool
{
452 ((self.dontcare
| other
.dontcare
) == self.dontcare
) &&
453 (((self.term ^ other
.term
) & !self.dontcare
) == 0)
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))))
465 v
.push(Bool
::Term(bit
as u8))
471 1 => v
.into_iter().next().unwrap(),
477 pub fn essential_minterms(mut minterms
: Vec
<Term
>) -> Essentials
{
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
);
493 if !combined_terms
.contains(&i
) {
494 essentials
.push(term
.clone());
502 essentials
: essentials
,