blob: d3630284d8b843b5d041df20941a1e451cb09d63 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
/*******************************************************************************
* Copyright (c) 2009 Elliott Baron
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*
* Contributors:
* Elliott Baron - initial API and implementation
*******************************************************************************/
package org.eclipse.cdt.codan.extension;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
public class QuineMcCluskeySimplifier<E> {
protected List<Minterm<E>> minterms;
protected List<E> variables;
protected List<Minterm<E>> implicantCover;
public QuineMcCluskeySimplifier(ITruthTable<E> tt) {
minterms = tt.getMinterms();
variables = tt.getVariables();
List<Minterm<E>> inputMinterms = new ArrayList<Minterm<E>>(minterms);
List<Minterm<E>> primeImplicants = new ArrayList<Minterm<E>>(minterms);
boolean change = true;
while (change && minterms.size() > 1) { // Iterate until we achieve a steady state
change = false;
Queue<Minterm<E>> primary = new LinkedList<Minterm<E>>();
primary.addAll(minterms);
while (!primary.isEmpty()) { // Iterate through all combinations
Minterm<E> one = primary.remove();
Queue<Minterm<E>> secondary = new LinkedList<Minterm<E>>();
secondary.addAll(minterms);
while (!secondary.isEmpty()) {
Minterm<E> two = secondary.remove();
Minterm<E> combined = one.combineTerms(two);
if (combined != null) {
if (!minterms.contains(combined)) {
change = true;
minterms.add(combined);
}
// Combined one and two so neither are prime implicants
primeImplicants.remove(one);
primeImplicants.remove(two);
if (!primeImplicants.contains(combined)) {
primeImplicants.add(combined);
}
}
}
}
}
// Determine which prime implicants cover which original minterms
Map<Minterm<E>, List<Minterm<E>>> implications = new HashMap<Minterm<E>, List<Minterm<E>>>();
for (Minterm<E> implicant : primeImplicants) {
implications.put(implicant, new ArrayList<Minterm<E>>());
for (Minterm<E> minterm : inputMinterms) {
if (implicant.implies(minterm)) {
implications.get(implicant).add(minterm);
}
}
}
implicantCover = new ArrayList<Minterm<E>>();
// remove minterms which are implied by an essential implicant
List<Minterm<E>> mintermsCopy = new ArrayList<Minterm<E>>(inputMinterms);
for (Minterm<E> minterm : mintermsCopy) {
Minterm<E> implicant = null;
int numImplications = 0;
for (Minterm<E> pi : primeImplicants) {
List<Minterm<E>> impl = implications.get(pi);
if (impl.contains(minterm)) {
implicant = pi;
numImplications++;
}
}
// essential implicant
if (numImplications == 1) {
inputMinterms.removeAll(implications.get(implicant));
if (!implicantCover.contains(implicant)) {
implicantCover.add(implicant);
}
}
}
// Remove essential implicants from our list
primeImplicants.removeAll(implicantCover);
// find a cover for the remaining minterms
while (inputMinterms.size() > 0) {
Minterm<E> maxImplicant = null;
for (Minterm<E> pi : primeImplicants) {
if (maxImplicant == null
|| implications.get(pi).size() >= implications.get(maxImplicant).size()) {
maxImplicant = pi;
}
}
inputMinterms.removeAll(implications.get(maxImplicant));
primeImplicants.remove(maxImplicant);
implicantCover.add(maxImplicant);
}
}
public List<Minterm<E>> getImplicantCover() {
return implicantCover;
}
}
|
