1 /***************************************************************************
2 quinegroup.cpp - description
3 -------------------
4 begin : Thu Oct 4 2001
5 copyright : (C) 2001 by Dannel Albert
6 email : dalbert@capitol-college.edu
7 ***************************************************************************/
8
9 /***************************************************************************
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the GNU General Public License as published by *
13 * the Free Software Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 ***************************************************************************/
17
18 #include <cassert>
19 #include <cmath>
20 #include "quinegroup.h"
21
22 using namespace std;
23
QuineGroup(unsigned int nb,QuineGroup * n,QuineGroup * p)24 QuineGroup::QuineGroup(unsigned int nb, QuineGroup* n, QuineGroup* p)
25 {
26 head = tail = NULL;
27 next = n;
28 prev = p;
29 diffBits = NULL;
30 numBits = nb;
31 numDiffBits = 0;
32 numItems = 0;
33 primeImplicant = 0;
34 hasCombined = false;
35 repeatCount = 0;
36 }
37
~QuineGroup()38 QuineGroup::~QuineGroup()
39 {
40 QuineNode* nd = head;
41 QuineNode* trash;
42 while(nd != NULL)
43 {
44 trash = nd;
45 nd = nd->GetNext();
46 delete trash;
47 }
48
49 head = tail = NULL;
50 next = prev = NULL;
51 numItems = 0;
52 primeImplicant = 0;
53 hasCombined = false;
54 repeatCount = 0;
55 }
56
GetDiffBits(unsigned int & numElements) const57 unum* QuineGroup::GetDiffBits(unsigned int& numElements) const
58 {
59 numElements = numDiffBits;
60 return diffBits;
61 }
62
Insert(unum value)63 void QuineGroup::Insert(unum value)
64 {
65 QuineNode* ndBefore = FindGreaterThan(value);
66 QuineNode* nd;
67
68 if (!numItems) // empty list
69 {
70 nd = new QuineNode(value, numBits);
71 head = tail = nd;
72 }
73 else if (ndBefore == head) // insert at beginning of list
74 {
75 nd = new QuineNode(value, numBits, head, NULL);
76 head->SetPrev(nd);
77 head = nd;
78 }
79 else if (ndBefore == NULL) // insert at end of list
80 {
81 nd = new QuineNode(value, numBits, NULL, tail);
82 tail->SetNext(nd);
83 tail = nd;
84 }
85 else // general case
86 {
87 nd = new QuineNode(value, numBits, ndBefore, ndBefore->GetPrev());
88 (ndBefore->GetPrev())->SetNext(nd);
89 ndBefore->SetPrev(nd);
90 }
91 numItems++;
92 }
93
CalculateDiffBits()94 bool QuineGroup::CalculateDiffBits()
95 {
96 if (!numItems)
97 return false;
98
99 // numItems = 2^n
100 // log(numItems) = n*log(2)
101 // n = log(numItems) / log(2)
102 // ^^^ doesn't work with integers well
103 // factor out by 2 and count the # of 2's
104 unsigned int i;
105 for (i=1; i<numItems; i*=2)
106 { numDiffBits++; }
107
108 diffBits = new unsigned int[numDiffBits];
109 assert(diffBits);
110
111 unsigned int headData = head->GetData();
112 for (i=0; i<numDiffBits; i++)
113 {
114 unsigned int numToSkip = (unsigned int)pow(2.0,(int)i);
115 diffBits[i] = ValueAt(numToSkip) - headData;
116 }
117
118 return true;
119 }
120
ValueAt(unsigned int index) const121 unum QuineGroup::ValueAt(unsigned int index) const
122 {
123 if (index > numItems)
124 return (unum)-1;
125
126 QuineNode* nd = head;
127 for (unsigned int i=0; i<index; i++)
128 nd = nd->GetNext();
129
130 return nd->GetData();
131 }
132
FindGreaterThan(unum n)133 QuineNode* QuineGroup::FindGreaterThan(unum n)
134 {
135 QuineNode* nd = head;
136
137 if (!numItems)
138 return NULL;
139
140 while (nd != NULL && nd->GetData() < n)
141 {
142 nd = nd->GetNext();
143 }
144
145 return nd;
146 }
147
operator <<(ostream & outs,const QuineGroup & qg)148 ostream& operator<<(ostream& outs, const QuineGroup& qg)
149 {
150 if (!qg.numItems)
151 return outs;
152
153 QuineNode* nd = qg.head;
154 for(unsigned int i=0; i<qg.numItems; i++)
155 {
156 outs << nd->GetData();
157 if (i != qg.numItems-1)
158 outs << ",";
159 nd = nd->GetNext();
160 }
161
162 if (qg.diffBits)
163 {
164 outs << " (";
165 for (unsigned int i=0; i<qg.numDiffBits; i++)
166 {
167 outs << qg.diffBits[i];
168 if (i != qg.numDiffBits-1)
169 outs << ",";
170 }
171 outs << ")";
172 }
173
174 if (qg.hasCombined)
175 {
176 outs << " *";
177 }
178 else if (qg.primeImplicant != 0)
179 {
180 outs << " PI#" << qg.primeImplicant;
181 }
182
183 return outs;
184 }