source: vis_dev/vis-2.3/src/tbl/tblSweep.c @ 99

Last change on this file since 99 was 14, checked in by cecile, 14 years ago

vis2.3
File size: 15.6 KB
RevLine 
[14]1/**CFile***********************************************************************
2
3  FileName    [ tblSweep.c ]
4
5  PackageName [ tbl ]
6
7  Synopsis    [Functions to support network sweeping.]
8
9  SeeAlso     [ tbl.h, tblEntryUtil.c ]
10
11  Author      [ Gitanjali M. Swamy ]
12
13  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
14  All rights reserved.
15
16  Permission is hereby granted, without written agreement and without license
17  or royalty fees, to use, copy, modify, and distribute this software and its
18  documentation for any purpose, provided that the above copyright notice and
19  the following two paragraphs appear in all copies of this software.
20
21  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
22  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
23  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
24  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
26  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
27  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
28  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
29  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
30  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
31
32******************************************************************************/
33#include "tblInt.h"
34
35static char rcsid[] UNUSED = "$Id: tblSweep.c,v 1.12 2009/04/11 18:26:45 fabio Exp $";
36
37/**AutomaticStart*************************************************************/
38
39/*---------------------------------------------------------------------------*/
40/* Static function prototypes                                                */
41/*---------------------------------------------------------------------------*/
42
43static void SetAdjustedEntry(Tbl_Table_t *table, Tbl_Entry_t *entry, int index, int rownum, int colnum, boolean flag);
44static void SetEntry(Tbl_Table_t *newTable, Tbl_Entry_t *entry1, Tbl_Entry_t *entry2, int rownum, int colnum, int index, boolean flag);
45
46/**AutomaticEnd***************************************************************/
47
48
49/*---------------------------------------------------------------------------*/
50/* Definition of exported functions                                          */
51/*---------------------------------------------------------------------------*/
52/**Function********************************************************************
53
54  Synopsis    [return the result of collapsing table2 into table1]
55
56  Description [Given two Tbl_Table_t table1 and table2, this function
57               will collapse table2 into the table1. It will remove
58               the column corresponding to the var associated with the
59               first table. Currently, the second table must a
60               constant table. This function checks every row to
61               confirm that the entry corresponding to the variable of
62               table2 does indeed take the constant value. If this
63               condition is satisfied it copies the entire row (minus
64               the column corresponding to the constant variable) into
65               a new resultant table. This condition can be easily
66               checked if the corresponding entry is of type
67               Tbl_EntryNormal_c, using
68               Tbl_EntryTestIntersectEntry. Otherwise its an involved
69               process that entails tracing the entire sequence of
70               equal entries until we encounter a Tbl_EntryNormal_c
71               entry.]
72
73  SideEffects  [required]
74
75  SeeAlso      [optional]
76
77******************************************************************************/
78Tbl_Table_t*
79Tbl_TableCollapse(Tbl_Table_t* table1, Tbl_Table_t* table2,int index)
80{
81  int rownum, realRowNum, colnum,eqcolnum,count,check;
82  Var_Variable_t *var;
83  Tbl_Table_t *newTable;
84  Tbl_Entry_t *entry1, *entry2;
85  Tbl_Entry_t *testEntry;
86
87  if (Tbl_TableReadNumOutputs(table2)==1){
88    newTable = Tbl_TableAlloc();
89
90    if (Tbl_TableReadNumRows(table2) !=0) {
91      entry2 = Tbl_TableReadEntry(table2,0,0,1);
92    }
93    else {
94      entry2 = Tbl_TableDefaultReadEntry(table2,0);
95    }
96    /* add every input column except collapsing input */
97    for(colnum=0;colnum < Tbl_TableReadNumInputs(table1); colnum++) {
98      if (colnum != index) {
99        var = Tbl_TableReadIndexVar(table1,colnum,0);
100        Tbl_TableAddColumn(newTable,var,0);
101      }
102    }
103    for(colnum=0;colnum < Tbl_TableReadNumOutputs(table1); colnum++) {
104      var = Tbl_TableReadIndexVar(table1,colnum,1);
105      Tbl_TableAddColumn(newTable,var,1);
106    }
107    /*     (void) Tbl_TableAddRow(newTable); */
108
109
110    realRowNum =0;
111    eqcolnum = index;
112
113    /* row by row, check if var has given constant value */
114    for(rownum=0; rownum< Tbl_TableReadNumRows(table1); rownum++) {
115      testEntry = Tbl_TableReadEntry(table1,rownum,index,0);
116      assert(entry2->type == Tbl_EntryNormal_c);
117
118      /* input column by column */
119      if (testEntry->type == Tbl_EntryNormal_c){
120        if (Tbl_EntryTestIntersectEntry(testEntry,entry2)){
121          (void) Tbl_TableAddRow(newTable);
122
123          for(colnum=0;colnum < Tbl_TableReadNumInputs(table1); colnum++) {
124            entry1= Tbl_TableReadEntry(table1,rownum,colnum,0);
125            SetEntry(newTable,entry1,entry2,realRowNum,colnum,index,0);
126          }
127
128          /* do outputs */
129          for(colnum=0;colnum < Tbl_TableReadNumOutputs(table1); colnum++) {
130            entry1= Tbl_TableReadEntry(table1,rownum,colnum,1);
131            SetEntry(newTable,entry1,entry2,realRowNum,colnum,index,1);
132          }
133          realRowNum++;
134        }
135      }
136      else if (testEntry->type == Tbl_EntryEqual_c){
137        count = 0;
138        check = 0;
139        while(count<= Tbl_TableReadNumInputs(table1)){
140
141          /* Find out the column the entry equal to
142           * and set that column entry to constant value if
143           * its is of type Equal. This gets propagated by the while count
144           * loop until you find a non-equal entry, and then it checks
145           * for an intersection. If no intersection, then it
146           * nullifies the row. Alas, there was no easier way */
147          if (testEntry->type == Tbl_EntryNormal_c){
148            if (Tbl_EntryTestIntersectEntry(testEntry,entry2)){
149              check = 1;
150            }
151            count = Tbl_TableReadNumInputs(table1)+1;
152          }
153          else {
154            eqcolnum = Tbl_EntryReadVarIndex(testEntry);
155            testEntry = Tbl_TableReadEntry(table1,rownum,eqcolnum,0);
156          }
157          if (count == Tbl_TableReadNumInputs(table1)){
158            check = 1;
159          }
160          count ++;
161        }
162
163        if (check == 1) {
164          (void) Tbl_TableAddRow(newTable);
165          count = 0;
166          eqcolnum = index;
167          testEntry = Tbl_TableReadEntry(table1,rownum,index,0);
168          while(count<= Tbl_TableReadNumInputs(table1)){
169            if (testEntry->type == Tbl_EntryNormal_c){
170              SetEntry(newTable,entry2,entry2,realRowNum,eqcolnum,index,0);
171              count = Tbl_TableReadNumInputs(table1)+1 ;
172            }
173            else {
174            eqcolnum = Tbl_EntryReadVarIndex(testEntry);
175            testEntry = Tbl_TableReadEntry(table1,rownum,eqcolnum,0);
176            count ++;
177          }
178          }
179          /* end of while */
180          /* fill in zero entries */
181          for(colnum=0;colnum < Tbl_TableReadNumInputs(table1); colnum++) {
182            entry1= Tbl_TableReadEntry(table1,rownum,colnum,0);
183            SetAdjustedEntry(newTable,Tbl_EntryDup(entry1),index,rownum,colnum,0);
184          }
185          /* do outputs */
186          for(colnum=0;colnum < Tbl_TableReadNumOutputs(table1); colnum++) {
187            entry1= Tbl_TableReadEntry(table1,rownum,colnum,1);
188            SetEntry(newTable,entry1,entry2,realRowNum,colnum,index,1);
189
190          }
191        }
192          realRowNum++;
193      }
194    }
195    Tbl_TableForEachDefaultEntry(table1,entry1,colnum) {
196      entry2 = NIL(Tbl_Entry_t);
197
198      if (entry1 != NIL(Tbl_Entry_t)) {
199        if (entry1->type != Tbl_EntryEqual_c) {
200          entry2 = Tbl_EntryDup(entry1);
201        }
202        else{
203          eqcolnum = Tbl_EntryReadVarIndex(entry1);
204          if ( eqcolnum < index) {
205            entry2 = Tbl_EntryDup(entry1);
206          }
207          else {
208            if ( eqcolnum > index) {
209              entry2 = Tbl_EntryDup(entry1);
210              Tbl_EntrySetEqual(entry2, eqcolnum -1);
211            }
212            else {
213              entry2 = Tbl_EntryDup(Tbl_TableReadEntry(table2,0,0,1));
214            }
215          }
216        }
217      }
218      (void) Tbl_TableDefaultSetEntry(newTable,entry2,colnum);
219    }
220    return newTable;
221  }
222  else {
223    fail("The table is not constant\n");
224    return NIL(Tbl_Table_t);  /* not reached */
225  }
226}
227
228
229/**Function********************************************************************
230
231  Synopsis    [Inverts a binary input column in a table.]
232
233  Description [Inverts a binary input column in a table.  It has no
234  effect if the variable associated to the given index is not binary
235  or is symbolic.  In some uncommon cases that are tricky to handle,
236  it goves up ad returns a NULL pointer.  Otherwise it returns a
237  modified table.]
238
239  SideEffects [none]
240
241  SeeAlso     [Tbl_TableIsInverter]
242
243******************************************************************************/
244Tbl_Table_t *
245Tbl_TableInvertBinaryInputColumn(
246  Tbl_Table_t *table,
247  int index
248  )
249{
250  int rowNum, colNum;
251  Tbl_Entry_t *entry;
252  Tbl_Table_t *newTable;
253  Var_Variable_t *var;
254
255  var = Tbl_TableReadIndexVar(table, index, 0);
256  if (Var_VariableReadNumValues(var) != 2 ||
257      Var_VariableTestIsSymbolic(var)) return NIL(Tbl_Table_t);
258
259  /* Check default entries.  We give up if any variable points to the column
260   * to be complemented, because it's a rare case and it does not seem worth
261   * the effort.
262   */
263  Tbl_TableForEachDefaultEntry(table, entry, colNum) {
264    if (entry != NIL(Tbl_Entry_t) && Tbl_EntryIsEqual(entry)) {
265      int eqColNum = Tbl_EntryReadVarIndex(entry);
266      if (eqColNum == index) {
267        return NIL(Tbl_Table_t);
268      }
269    }
270  }
271
272  newTable = Tbl_TableHardDup(table);
273
274  Tbl_TableForEachInputVar(table, colNum, var) {
275    Tbl_TableSetVar(newTable, colNum, var, 0);
276  }
277
278  Tbl_TableForEachOutputVar(table, colNum, var) {
279    Tbl_TableSetVar(newTable, colNum, var, 1);
280  }
281
282  /* Get rid of equal entries in the output part that point to the
283   * column to be negated.  We do not currently deal with equal
284   * entries in the input part.  If we find one, we give up.
285   */
286  Tbl_TableForEachOutputEntry(newTable, rowNum, colNum, entry) {
287    if (Tbl_EntryIsEqual(entry)) {
288      int eqColNum = Tbl_EntryReadVarIndex(entry);
289      if (eqColNum == index) {
290        Tbl_Entry_t *eqEntry = Tbl_TableReadEntry(newTable, rowNum, index, 0);
291        if (Tbl_EntryIsEqual(eqEntry) ||
292            Tbl_EntryReadNumValues(eqEntry) == 0) {
293          /* Tricky case: we give up. */
294          Tbl_TableFree(newTable);
295          return NIL(Tbl_Table_t);
296        } else if (Tbl_EntryReadNumValues(eqEntry) == 1) {
297          /* Downgrade the equality to a constant value. */
298          Tbl_Entry_t *entry2 = Tbl_EntryDup(eqEntry);
299          Tbl_TableSetEntry(newTable, entry2, rowNum, colNum, 1);
300        } else {
301          int i, j;
302          Tbl_Entry_t *entry2;
303          i = Tbl_TableAddRow(newTable);
304          Tbl_RowForEachInputEntry(newTable, rowNum, entry2, j) {
305            if (j == index) {
306              Tbl_Entry_t *entry3 = Tbl_EntryAlloc(Tbl_EntryNormal_c);
307              Tbl_Entry_t *entry4 = Tbl_EntryAlloc(Tbl_EntryNormal_c);
308              Tbl_EntrySetValue(entry3, 0, 0);
309              Tbl_EntrySetValue(entry4, 1, 1);
310              Tbl_TableSetEntry(newTable, entry3, rowNum, j, 0);
311              Tbl_TableSetEntry(newTable, entry4, i, j, 0);
312            } else {
313              Tbl_TableSetEntry(newTable, Tbl_EntryDup(entry2), i, j, 0);
314            }
315          }
316          Tbl_RowForEachOutputEntry(newTable, rowNum, entry2, j) {
317            if (Tbl_EntryIsEqual(entry2) &&
318                Tbl_EntryReadVarIndex(entry) == index) {
319              Tbl_Entry_t *entry3 = Tbl_EntryAlloc(Tbl_EntryNormal_c);
320              Tbl_Entry_t *entry4 = Tbl_EntryAlloc(Tbl_EntryNormal_c);
321              Tbl_EntrySetValue(entry3, 0, 0);
322              Tbl_EntrySetValue(entry4, 1, 1);
323              Tbl_TableSetEntry(newTable, entry3, rowNum, j, 1);
324              Tbl_TableSetEntry(newTable, entry4, i, j, 1);
325            } else {
326              Tbl_TableSetEntry(newTable, Tbl_EntryDup(entry2), i, j, 1);
327            }
328          }
329          continue;
330        }
331      }
332    }
333  }
334
335  Tbl_TableForEachInputEntry(newTable, rowNum, colNum, entry) {
336    if (Tbl_EntryIsEqual(entry)) {
337      if (colNum == index) {
338        Tbl_TableFree(newTable);
339        return NIL(Tbl_Table_t);
340      } else {
341        int eqColNum = Tbl_EntryReadVarIndex(entry);
342        if (eqColNum == index) {
343          Tbl_TableFree(newTable);
344          return NIL(Tbl_Table_t);
345        }
346      }
347    } else if (colNum == index) {
348      if (Tbl_EntryReadNumValues(entry) == 1) {
349        Tbl_EntryComplement(entry, 0, 1);
350      }
351    }
352  }
353
354  return newTable;
355
356} /* Tbl_TableInvertBinaryInputColumn */
357
358
359/*---------------------------------------------------------------------------*/
360/* Definition of internal functions                                          */
361/*---------------------------------------------------------------------------*/
362
363/**Function********************************************************************
364
365  Synopsis           [Remove last row from table]
366
367  Description        [optional]
368
369  SideEffects        [required]
370
371  SeeAlso            [optional]
372
373******************************************************************************/
374boolean
375TblTableDeleteLastRow(
376  Tbl_Table_t* table)
377{
378  array_t *dataArray;
379  Tbl_Row_t *row;
380  int rowNum;
381
382  dataArray = array_dup(TblTableReadData(table));
383  array_free(TblTableReadData(table));
384  TblTableReadData(table)= array_alloc(Tbl_Row_t*,0);
385  for(rowNum=0; rowNum < (array_n(dataArray)-1); rowNum++) {
386    row = array_fetch(Tbl_Row_t*,dataArray,rowNum);
387    array_insert_last(Tbl_Row_t*,TblTableReadData(table),row);
388  }
389  return TRUE;
390}
391
392/*---------------------------------------------------------------------------*/
393/* Definition of static functions                                            */
394/*---------------------------------------------------------------------------*/
395
396
397/**Function********************************************************************
398
399  Synopsis           [Set entry correctly]
400
401  Description        [optional]
402
403  SideEffects        [required]
404
405  SeeAlso            [optional]
406
407
408******************************************************************************/
409static void SetAdjustedEntry(
410  Tbl_Table_t *table,
411  Tbl_Entry_t *entry,
412  int index,
413  int rownum,
414  int colnum,
415  boolean flag)
416{
417  Tbl_Entry_t *newEntry;
418
419  if (flag ==0) {
420    if (colnum < index) {
421      /* should free if necessary */
422      newEntry = Tbl_TableReadEntry(table,rownum,colnum,0);
423      if (newEntry==NIL(Tbl_Entry_t)) {
424        Tbl_TableSetEntry(table,entry,rownum,colnum,0);
425      }
426      else {
427        Tbl_EntryFree(entry);
428      }
429    }
430    else if (colnum > index) {
431      /* should free if necessary */
432      newEntry = Tbl_TableReadEntry(table,rownum,colnum-1,0);
433      if (newEntry==NIL(Tbl_Entry_t)) {
434        Tbl_TableSetEntry(table,entry,rownum,colnum-1,0);
435      }
436      else {
437        Tbl_EntryFree(entry);
438      }
439    }
440    else {
441      Tbl_EntryFree(entry);
442    }
443  }
444  else {
445    newEntry = Tbl_TableReadEntry(table,rownum,colnum,1);
446    if (newEntry== NIL(Tbl_Entry_t)) {
447      Tbl_TableSetEntry(table,entry,rownum,colnum,1);
448    }
449    else {
450      Tbl_EntryFree(newEntry);
451      Tbl_TableSetEntry(table,entry,rownum,colnum,1);
452
453      }
454    }
455}
456
457/**Function********************************************************************
458
459  Synopsis           [Set entry correctly]
460
461  Description        [optional]
462
463  SideEffects        [required]
464
465  SeeAlso            [optional]
466
467
468******************************************************************************/
469static void SetEntry(
470Tbl_Table_t *newTable,
471Tbl_Entry_t *entry1,
472Tbl_Entry_t *entry2,
473int rownum,
474int colnum,
475int index,
476boolean flag)
477{
478  int varcolnum;
479  Tbl_Entry_t *newEntry;
480
481
482  if (entry1->type == Tbl_EntryNormal_c) {
483    SetAdjustedEntry(newTable,Tbl_EntryDup(entry1),index,rownum,colnum, flag);
484  }
485  else {
486    /* its of type equal */
487    varcolnum = Tbl_EntryReadVarIndex(entry1);
488    if (varcolnum < index) {
489      SetAdjustedEntry(newTable,Tbl_EntryDup(entry1),index,rownum,colnum, flag);
490    }
491    else {
492      if (varcolnum > index) {
493        newEntry = Tbl_EntryDup(entry1);
494        Tbl_EntrySetEqual(newEntry,varcolnum-1);
495        SetAdjustedEntry(newTable,newEntry,index,rownum,colnum,flag);
496
497      }
498      else {
499        SetAdjustedEntry(newTable,Tbl_EntryDup(entry2),index,rownum,colnum, flag);
500      }
501    }
502  }
503}
Note: See TracBrowser for help on using the repository browser.