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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
/**CFile****************************************************************
FileName [mvcContain.c]
PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]
Synopsis [Making the cover single-cube containment ABC_FREE.]
Author [MVSIS Group]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - February 1, 2003.]
Revision [$Id: mvcContain.c,v 1.4 2003/04/03 23:25:42 alanmi Exp $]
***********************************************************************/
#include "mvc.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
static void Mvc_CoverRemoveDuplicates( Mvc_Cover_t * pCover );
static void Mvc_CoverRemoveContained( Mvc_Cover_t * pCover );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Removes the contained cubes.]
Description [Returns 1 if the cover has been changed.]
SideEffects []
SeeAlso []
***********************************************************************/
int Mvc_CoverContain( Mvc_Cover_t * pCover )
{
int nCubes;
nCubes = Mvc_CoverReadCubeNum( pCover );
if ( nCubes < 2 )
return 0;
Mvc_CoverSetCubeSizes(pCover);
Mvc_CoverSort( pCover, NULL, Mvc_CubeCompareSizeAndInt );
Mvc_CoverRemoveDuplicates( pCover );
if ( nCubes > 1 )
Mvc_CoverRemoveContained( pCover );
return (nCubes != Mvc_CoverReadCubeNum(pCover));
}
/**Function*************************************************************
Synopsis [Removes adjacent duplicated cubes from the cube list.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Mvc_CoverRemoveDuplicates( Mvc_Cover_t * pCover )
{
Mvc_Cube_t * pPrev, * pCube, * pCube2;
int fEqual;
// set the first cube of the cover
pPrev = Mvc_CoverReadCubeHead(pCover);
// go through all the cubes after this one
Mvc_CoverForEachCubeStartSafe( Mvc_CubeReadNext(pPrev), pCube, pCube2 )
{
// compare the current cube with the prev cube
Mvc_CubeBitEqual( fEqual, pPrev, pCube );
if ( fEqual )
{ // they are equal - remove the current cube
Mvc_CoverDeleteCube( pCover, pPrev, pCube );
Mvc_CubeFree( pCover, pCube );
// don't change the previous cube cube
}
else
{ // they are not equal - update the previous cube
pPrev = pCube;
}
}
}
/**Function*************************************************************
Synopsis [Removes contained cubes from the sorted cube list.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Mvc_CoverRemoveContained( Mvc_Cover_t * pCover )
{
Mvc_Cube_t * pCubeBeg, * pCubeEnd, * pCubeLarge;
Mvc_Cube_t * pCube, * pCube2, * pPrev;
unsigned sizeCur;
int Result;
// since the cubes are sorted by size, it is sufficient
// to compare each cube with other cubes that have larger sizes
// if the given cube implies a larger cube, the larger cube is removed
pCubeBeg = Mvc_CoverReadCubeHead(pCover);
do
{
// get the current cube size
sizeCur = Mvc_CubeReadSize(pCubeBeg);
// initialize the end of the given size group
pCubeEnd = pCubeBeg;
// find the beginning of the next size group
Mvc_CoverForEachCubeStart( Mvc_CubeReadNext(pCubeBeg), pCube )
{
if ( sizeCur == Mvc_CubeReadSize(pCube) )
pCubeEnd = pCube;
else // pCube is the first cube in the new size group
break;
}
// if we could not find the next size group
// the containment check is finished
if ( pCube == NULL )
break;
// otherwise, pCubeBeg/pCubeEnd are the first/last cubes of the group
// go through all the cubes between pCubeBeg and pCubeEnd, inclusive,
// and for each of them, try removing cubes after pCubeEnd
Mvc_CoverForEachCubeStart( pCubeBeg, pCubeLarge )
{
pPrev = pCubeEnd;
Mvc_CoverForEachCubeStartSafe( Mvc_CubeReadNext(pCubeEnd), pCube, pCube2 )
{
// check containment
Mvc_CubeBitNotImpl( Result, pCube, pCubeLarge );
if ( !Result )
{ // pCubeLarge implies pCube - remove pCube
Mvc_CoverDeleteCube( pCover, pPrev, pCube );
Mvc_CubeFree( pCover, pCube );
// don't update the previous cube
}
else
{ // update the previous cube
pPrev = pCube;
}
}
// quit, if the main cube was the last one of this size
if ( pCubeLarge == pCubeEnd )
break;
}
// set the beginning of the next group
pCubeBeg = Mvc_CubeReadNext(pCubeEnd);
}
while ( pCubeBeg );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END
|
