tclbdd

Check-in [d66431592d]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Removed abuse of the word 'minterm': the terms being discussed were not minimal
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:d66431592d77b1a634c2e24c74cbd12c79922e9a
User & Date: kbk 2013-12-17 18:42:54
Context
2013-12-18
16:06
Added 'replace' method to bdd::system in support of relational algebra. Fixed a typo in '===' method that caused it to fail always check-in: db99db21ba user: kbk tags: trunk
2013-12-17
18:42
Removed abuse of the word 'minterm': the terms being discussed were not minimal check-in: d66431592d user: kbk tags: trunk
16:16
Add test cases for low-level 'project' and fixed the bugs that were exposed check-in: 74ad4ed7f0 user: kbk tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to generic/tclBdd.c.

  1330   1330   }
  1331   1331   
  1332   1332   /*
  1333   1333    *-----------------------------------------------------------------------------
  1334   1334    *
  1335   1335    * BDDSystemLoadMethod --
  1336   1336    *
  1337         - *	OR's a minterm representing a tuple in a finite domain into a
         1337  + *	OR's a term representing a tuple in a finite domain into a
  1338   1338    *	BDD representing a relation.
  1339   1339    *
  1340   1340    * Usage:
  1341   1341    *	$system load relation description value ?value ...?
  1342   1342    *
  1343   1343    * Parameters:
  1344   1344    *	system - System of BDD's
................................................................................
  1386   1386       Tcl_Obj* name;		/* Name of the named relation */
  1387   1387       int paramc = objc-skipped-2;
  1388   1388   				/* Number of supplied parameters */
  1389   1389       Tcl_WideInt* paramv;	/* Vector of integer parameters */
  1390   1390       int descc;			/* Count of elements in the description list */
  1391   1391       Tcl_Obj** descv;		/* Description list */
  1392   1392       int i;
  1393         -    BDD_BeadIndex minterm;	/* Minterm under construction */
         1393  +    BDD_BeadIndex term;		/* Term under construction */
  1394   1394       BDD_BeadIndex relation;	/* Relation under construction */
  1395   1395       BDD_BeadIndex temp;
  1396   1396       int lastVarIndex = INT_MAX;	/* Variable index from the last trip */
  1397   1397       int varIndex;		/* Variable index */
  1398   1398       int paramIndex;		/* Parameter index */
  1399   1399       int bitPos;			/* Bit position within the value */
  1400   1400       Tcl_HashEntry* entryPtr;	/* Hash entry holding the named relation */
................................................................................
  1436   1436   						  "elements", -1));
  1437   1437   	Tcl_SetErrorCode(interp, "BDD", "DescNotMultipleOf3", NULL);
  1438   1438   	ckfree(paramv);
  1439   1439   	return TCL_ERROR;
  1440   1440       }
  1441   1441   
  1442   1442       /*
  1443         -     * Convert the given integer values to a minterm
         1443  +     * Convert the given integer values to a term
  1444   1444        */
  1445         -    minterm = 1;
  1446         -    BDD_IncrBeadRefCount(sdata->system, minterm);
         1445  +    term = 1;
         1446  +    BDD_IncrBeadRefCount(sdata->system, term);
  1447   1447       for (i = descc; i > 0; ) {
  1448   1448   	i -= 3;
  1449   1449   	/*
  1450   1450   	 * Unpack the description for the current bit
  1451   1451   	 */
  1452   1452   	if (Tcl_GetIntFromObj(interp, descv[i], &varIndex) != TCL_OK
  1453   1453   	    || Tcl_GetIntFromObj(interp, descv[i+1], &paramIndex) != TCL_OK
  1454   1454   	    || Tcl_GetIntFromObj(interp, descv[i+2], &bitPos) != TCL_OK) {
  1455         -	    BDD_UnrefBead(sdata->system, minterm);
         1455  +	    BDD_UnrefBead(sdata->system, term);
  1456   1456   	    ckfree(paramv);
  1457   1457   	    return TCL_ERROR;
  1458   1458   	}
  1459   1459   	if (varIndex >= lastVarIndex || varIndex < 0) {
  1460   1460   	    Tcl_SetObjResult(interp, Tcl_NewStringObj("variables are not in "
  1461   1461   						      "increasing order", -1));
  1462   1462   	    Tcl_SetErrorCode(interp, "BDD", "VarsOutOfOrder", NULL);
  1463         -	    BDD_UnrefBead(sdata->system, minterm);
         1463  +	    BDD_UnrefBead(sdata->system, term);
  1464   1464   	    ckfree(paramv);
  1465   1465   	    return TCL_ERROR;
  1466   1466   	}
  1467   1467   	lastVarIndex = varIndex;
  1468   1468   	if (paramIndex >= paramc || paramIndex < 0) {
  1469   1469   	    Tcl_SetObjResult(interp, Tcl_NewStringObj("description refers to a "
  1470   1470   						      "nonexistent "
  1471   1471   						      "parameter", -1));
  1472   1472   	    Tcl_SetErrorCode(interp, "BDD", "NonexistentParam", NULL);
  1473         -	    BDD_UnrefBead(sdata->system, minterm);
         1473  +	    BDD_UnrefBead(sdata->system, term);
  1474   1474   	    ckfree(paramv);
  1475   1475   	    return TCL_ERROR;
  1476   1476   	}
  1477   1477   	if (bitPos >= CHAR_BIT * sizeof(Tcl_WideInt) || bitPos < 0) {
  1478   1478   	    Tcl_SetObjResult(interp, Tcl_NewStringObj("bad bit index in "
  1479   1479   						      "description", -1));
  1480   1480   	    Tcl_SetErrorCode(interp, "BDD", "BadBitIndex", NULL);
  1481         -	    BDD_UnrefBead(sdata->system, minterm);
         1481  +	    BDD_UnrefBead(sdata->system, term);
  1482   1482   	    ckfree(paramv);
  1483   1483   	    return TCL_ERROR;
  1484   1484   	}
  1485   1485   
  1486   1486   	/*
  1487         -	 * Make a literal for the current bit and AND it with the minterm
         1487  +	 * Make a literal for the current bit and AND it with the term
  1488   1488   	 * under construction.
  1489   1489   	 */
  1490   1490   	if ((paramv[paramIndex] >> bitPos) & 1) {
  1491   1491   	    temp = BDD_MakeBead(sdata->system, (BDD_VariableIndex) varIndex,
  1492         -				(BDD_BeadIndex) 0, minterm);
         1492  +				(BDD_BeadIndex) 0, term);
  1493   1493   	} else {
  1494   1494   	    temp = BDD_MakeBead(sdata->system, (BDD_VariableIndex) varIndex,
  1495         -				minterm, 0);
         1495  +				term, 0);
  1496   1496   	}
  1497         -	BDD_UnrefBead(sdata->system, minterm);
  1498         -	minterm = temp;
         1497  +	BDD_UnrefBead(sdata->system, term);
         1498  +	term = temp;
  1499   1499       }
  1500   1500       ckfree(paramv);
  1501   1501   
  1502   1502       /*
  1503         -     * OR the minterm into the named relation, creating the empty
         1503  +     * OR the term into the named relation, creating the empty
  1504   1504        * relation if necessary.
  1505   1505        */
  1506   1506       entryPtr = Tcl_CreateHashEntry(sdata->expressions, name, &newFlag);
  1507   1507       if (newFlag) {
  1508   1508   	relation = 0;
  1509   1509   	BDD_IncrBeadRefCount(sdata->system, relation);
  1510   1510       } else {
  1511   1511   	relation = (BDD_BeadIndex) Tcl_GetHashValue(entryPtr);
  1512   1512       }
  1513   1513       temp = relation;
  1514         -    relation = BDD_Apply(sdata->system, BDD_BINOP_OR, relation, minterm);
         1514  +    relation = BDD_Apply(sdata->system, BDD_BINOP_OR, relation, term);
  1515   1515       BDD_UnrefBead(sdata->system, temp);
  1516         -    BDD_UnrefBead(sdata->system, minterm);
         1516  +    BDD_UnrefBead(sdata->system, term);
  1517   1517       Tcl_SetHashValue(entryPtr, relation);
  1518   1518   
  1519   1519       return TCL_OK;
  1520   1520       
  1521   1521   }
  1522   1522   
  1523   1523   /*

Changes to library/tclfddd.tcl.

   153    153   	lappend chain {*}$b
   154    154       }
   155    155       return [list $names $chain]
   156    156   }
   157    157   
   158    158   # bdd::fddd::reader --
   159    159   #
   160         -#	Makes a call to the BDD engine to construct a minterm corresponding
          160  +#	Makes a call to the BDD engine to construct a term corresponding
   161    161   #	to a tuple in a finite domain.
   162    162   #
   163    163   # Usage:
   164    164   #	bdd::fddd::reader sysName termName layout domain ?domain...?
   165    165   #
   166    166   # Parameters:
   167    167   #	sysName - Name of the system of BDD's
................................................................................
   192    192   #    {var 2 var 1 var 0 stmt 0 stmt2 0 stmt 1 stmt2 1 stmt 2 stmt2 2 
   193    193   #     stmt 3 stmt2 3 stmt 4 stmt2 4}
   194    194   #
   195    195   # and r set to:
   196    196   #   sys load reads {0 1 2 1 1 1 2 1 0 3 0 0 5 0 1 7 0 2 9 0 3 11 0 4}
   197    197   #
   198    198   # which (when two additional args are catenated on the end), asks the BDD
   199         -# system "construct a minterm named 'reads', where variable zero is set from
          199  +# system "construct a term named 'reads', where variable zero is set from
   200    200   # parameter 1, the 2**2 bit, variable 1 from parameter 1 the 2**1 bit,
   201    201   # variable 2 from parameter 1 the 2**0 bit, variable 3 from parameter 0 the
   202    202   # 2**0 bit, variable 5 from parameter 0 the 2**1 bit ... variable 11 from
   203    203   # parameter 0 the 2**4 bit."
   204    204   
   205    205   proc bdd::fddd::reader {sysName termName layout args} {
   206    206       set i 0

Changes to tests/fddd.test.

     2      2   #
     3      3   #       Tests for Finite Domain Decision Diagrams (FDDD's)
     4      4   #
     5      5   # Copyright (c) 2013 by Kevin B. Kenny.
     6      6   
     7      7   package require tclbdd::fddd
     8      8   
     9         -test fddd-1.1 {load minterm - wrong # args} {*}{
            9  +test fddd-1.1 {load term - wrong # args} {*}{
    10     10       -setup {
    11     11   	bdd::system create sys
    12     12       }
    13     13       -body {
    14     14   	sys load
    15     15       }
    16     16       -cleanup {
................................................................................
    17     17   	rename sys {}
    18     18       }
    19     19       -result {wrong # args: *}
    20     20       -match glob
    21     21       -returnCodes error
    22     22   }
    23     23   
    24         -test fddd-1.2 {load minterm - bad integer} {*}{
           24  +test fddd-1.2 {load term - bad integer} {*}{
    25     25       -setup {
    26     26   	bdd::system create sys
    27     27       } 
    28     28       -body {
    29     29   	sys load x {} garbage
    30     30       } 
    31     31       -cleanup {
    32     32   	rename sys {}
    33     33       }
    34     34       -result {expected integer but got "garbage"}
    35     35       -returnCodes error
    36     36   }
    37     37   
    38         -test fddd-1.3 {load minterm - ill-formed list} {
           38  +test fddd-1.3 {load term - ill-formed list} {
    39     39       -setup {
    40     40   	bdd::system create sys
    41     41       }
    42     42       -body {
    43     43   	sys load x \{ 
    44     44       }
    45     45       -cleanup {
    46     46   	rename sys {}
    47     47       }
    48     48       -result {unmatched open brace in list}
    49     49       -returnCodes error
    50     50   }
    51     51   
    52         -test fddd-1.4 {load minterm - wrong list size} {
           52  +test fddd-1.4 {load term - wrong list size} {
    53     53       -setup {
    54     54   	bdd::system create sys
    55     55       }
    56     56       -body {
    57     57   	list [catch {sys load x {1 2}} result] $result $::errorCode
    58     58       }
    59     59       -cleanup {
................................................................................
   171    171       }
   172    172       -cleanup {
   173    173   	sys destroy
   174    174       }
   175    175       -result {1 {} 2}
   176    176   }
   177    177   
   178         -test fddd-1.12 {load multiple minterms} {*}{
          178  +test fddd-1.12 {load multiple terms} {*}{
   179    179       -setup {
   180    180   	bdd::system create sys
   181    181       }
   182    182       -body {
   183    183   	set result {}
   184    184   	for {set i 0} {$i < 3} {incr i} {
   185    185   	    set j [expr {($i + 1) % 4}]