Robust/src/Benchmarks/SingleTM/Bayes/Data.java

   1 /* =============================================================================
   2  *
   3  * data.java
   4  *
   5  * =============================================================================
   6  *
   7  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   8  * Author: Chi Cao Minh
   9  * Ported to Java June 2009 Alokika Dash
  10  * University of California, Irvine
  11  *
  12  * =============================================================================
  13  *
  14  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  15  * of the files.
  16  *
  17  * ------------------------------------------------------------------------
  18  *
  19  * Unless otherwise noted, the following license applies to STAMP files:
  20  *
  21  * Copyright (c) 2007, Stanford University
  22  * All rights reserved.
  23  *
  24  * Redistribution and use in source and binary forms, with or without
  25  * modification, are permitted provided that the following conditions are
  26  * met:
  27  *
  28  *     * Redistributions of source code must retain the above copyright
  29  *       notice, this list of conditions and the following disclaimer.
  30  *
  31  *     * Redistributions in binary form must reproduce the above copyright
  32  *       notice, this list of conditions and the following disclaimer in
  33  *       the documentation and/or other materials provided with the
  34  *       distribution.
  35  *
  36  *     * Neither the name of Stanford University nor the names of its
  37  *       contributors may be used to endorse or promote products derived
  38  *       from this software without specific prior written permission.
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  41  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  43  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  45  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  46  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  47  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  48  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  49  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  50  * THE POSSIBILITY OF SUCH DAMAGE.
  51  *
  52  * =============================================================================
  53  */
  54
  55 #define DATA_PRECISION    100
  56 #define DATA_INIT         2 /* not 0 or 1 */
  57
  58 public class Data {
  59   int numVar;
  60   int numRecord;
  61   byte[] records; /* coordination of all records */
  62   Random randomPtr;
  63   Sort sort;
  64
  65   /* =============================================================================
  66    * data_alloc
  67    * =============================================================================
  68    */
  69   public Data(int numVar, int numRecord, Random randomPtr)
  70   {
  71     int numDatum = numVar * numRecord;
  72     records = new byte[numDatum];
  73     for(int i = 0; i<numDatum; i++)
  74       this.records[i] = (byte)DATA_INIT;
  75
  76     this.numVar = numVar;
  77     this.numRecord = numRecord;
  78     this.randomPtr = randomPtr;
  79     this.sort=new Sort();
  80   }
  81
  82   public void data_free() {
  83     records=null;
  84     randomPtr=null;
  85   }
  86
  87   /* =============================================================================
  88    * data_generate
  89    * -- Binary variables of random PDFs
  90    * -- If seed is <0, do not reseed
  91    * -- Returns random network
  92    * =============================================================================
  93    */
  94   public Net data_generate (int seed, int maxNumParent, int percentParent)
  95   {
  96     if (seed >= 0) {
  97       randomPtr.random_seed(seed);
  98     }
  99
 100     /*
 101      * Generate random Bayesian network
 102      */
 103
 104     Net netPtr = new Net(numVar);
 105     netPtr.net_generateRandomEdges(maxNumParent, percentParent, randomPtr);
 106
 107     /*
 108      * Create a threshold for each of the possible permutation of variable
 109      * value instances
 110      */
 111
 112     int[][] thresholdsTable = new int[numVar][];
 113     int v;
 114     for (v = 0; v < numVar; v++) {
 115       IntList parentIdListPtr = netPtr.net_getParentIdListPtr(v);
 116       int numThreshold = 1 << parentIdListPtr.list_getSize();
 117       int[] thresholds = new int[numThreshold];
 118       for (int t = 0; t < numThreshold; t++) {
 119         int threshold = (int) (randomPtr.random_generate() % (DATA_PRECISION + 1));
 120         thresholds[t] = threshold;
 121       }
 122       thresholdsTable[v] = thresholds;
 123     }
 124
 125     /*
 126      * Create variable dependency ordering for record generation
 127      */
 128
 129     int[] order = new int[numVar];
 130     int numOrder = 0;
 131
 132     Queue workQueuePtr = Queue.queue_alloc(-1);
 133
 134     IntVector dependencyVectorPtr = IntVector.vector_alloc(1);
 135
 136     BitMap orderedBitmapPtr = BitMap.bitmap_alloc(numVar);
 137     orderedBitmapPtr.bitmap_clearAll();
 138
 139     BitMap doneBitmapPtr = BitMap.bitmap_alloc(numVar);
 140     doneBitmapPtr.bitmap_clearAll();
 141
 142     v = -1;
 143     while ((v = doneBitmapPtr.bitmap_findClear(v + 1)) >= 0) {
 144       IntList childIdListPtr = netPtr.net_getChildIdListPtr(v);
 145       int numChild = childIdListPtr.list_getSize();
 146
 147       if (numChild == 0) {
 148
 149         boolean status;
 150
 151         /*
 152          * Use breadth-first search to find net connected to this leaf
 153          */
 154
 155         workQueuePtr.queue_clear();
 156         if((status = workQueuePtr.queue_push(v)) != true) {
 157           System.out.println("Assert failed: status= "+ status + "should be true");
 158           System.exit(0);
 159         }
 160
 161         while (!(workQueuePtr.queue_isEmpty())) {
 162           int id = workQueuePtr.queue_pop();
 163           if((status = doneBitmapPtr.bitmap_set(id)) != true) {
 164             System.out.println("Assert failed: status= "+ status + "should be true");
 165             System.exit(0);
 166           }
 167
 168           if((status = dependencyVectorPtr.vector_pushBack(id)) == false) {
 169             System.out.println("Assert failed: status= "+ status + "should be true");
 170             System.exit(0);
 171           }
 172
 173           IntList parentIdListPtr = netPtr.net_getParentIdListPtr(id);
 174           IntListNode it = parentIdListPtr.head;
 175
 176           while (it.nextPtr!=null) {
 177             it = it.nextPtr;
 178             int parentId = it.dataPtr;
 179             if((status = workQueuePtr.queue_push(parentId)) == false) {
 180               System.out.println("Assert failed: status= "+ status + "should be true");
 181               System.exit(0);
 182             }
 183           }
 184         }
 185
 186         /*
 187          * Create ordering
 188          */
 189
 190         int n = dependencyVectorPtr.vector_getSize();
 191         for (int i = 0; i < n; i++) {
 192           int id = dependencyVectorPtr.vector_popBack();
 193           if (!(orderedBitmapPtr.bitmap_isSet(id))) {
 194             orderedBitmapPtr.bitmap_set(id);
 195             order[numOrder++] = id;
 196           }
 197         }
 198       }
 199     }
 200
 201     if(numOrder != numVar) {
 202       System.out.println("Assert failed: numVar should be equal to numOrder");
 203       System.exit(0);
 204     }
 205
 206     /*
 207      * Create records
 208      */
 209
 210     int startindex = 0;
 211     for (int r = 0; r < numRecord; r++) {
 212       for (int o = 0; o < numOrder; o++) {
 213         v = order[o];
 214         IntList parentIdListPtr = netPtr.net_getParentIdListPtr(v);
 215         int index = 0;
 216         IntListNode it = parentIdListPtr.head;
 217
 218         while (it.nextPtr!=null) {
 219           it = it.nextPtr;
 220           int parentId = it.dataPtr;
 221           int value = records[startindex + parentId];
 222           if(value == DATA_INIT) {
 223             System.out.println("Assert failed value should be != DATA_INIT");
 224             System.exit(0);
 225           }
 226
 227           index = (index << 1) + value;
 228         }
 229         int rnd = (int) (randomPtr.random_generate() % DATA_PRECISION);
 230         int threshold = thresholdsTable[v][index];
 231         records[startindex + v] = (byte) ((rnd < threshold) ? 1 : 0);
 232       }
 233       startindex += numVar;
 234       if(startindex > numRecord * numVar) {
 235         System.out.println("Assert failed: value should be != DATA_INIT in data_generate()");
 236         System.exit(0);
 237       }
 238     }
 239
 240     return netPtr;
 241   }
 242
 243
 244   /* =============================================================================
 245    * data_copy
 246    * -- Returns false on failure
 247    * =============================================================================
 248    */
 249   public static boolean
 250     data_copy (Data dstPtr, Data srcPtr)
 251     {
 252       int numDstDatum = dstPtr.numVar * dstPtr.numRecord;
 253       int numSrcDatum = srcPtr.numVar * srcPtr.numRecord;
 254       if (numDstDatum != numSrcDatum) {
 255         dstPtr.records = new byte[numSrcDatum];
 256       }
 257
 258       dstPtr.numVar    = srcPtr.numVar;
 259       dstPtr.numRecord = srcPtr.numRecord;
 260       for(int i=0; i<numSrcDatum; i++)
 261         dstPtr.records[i] = srcPtr.records[i];
 262
 263       return true;
 264     }
 265
 266   /* =============================================================================
 267    * data_sort
 268    * -- In place
 269    * =============================================================================
 270    */
 271   public void
 272     data_sort (int start,
 273         int num,
 274         int offset)
 275     {
 276       if((start < 0) || (start > numRecord)) {
 277         System.out.println("start: Assert failed in data_sort");
 278         System.exit(0);
 279       }
 280       if((num < 0) || (num > numRecord)) {
 281         System.out.println("num: Assert failed in data_sort");
 282         System.exit(0);
 283       }
 284       if((start + num < 0) || (start + num > numRecord)) {
 285         System.out.println("start + num: Assert failed in data_sort");
 286         System.exit(0);
 287       }
 288
 289       sort.sort(records,
 290           start * numVar,
 291           num,
 292           numVar,
 293           numVar,
 294           offset);
 295
 296     }
 297
 298
 299   /* =============================================================================
 300    * data_findSplit
 301    * -- Call data_sort first with proper start, num, offset
 302    * -- Returns number of zeros in offset column
 303    * =============================================================================
 304    */
 305   public int
 306     data_findSplit (int start, int num, int offset)
 307     {
 308       int low = start;
 309       int high = start + num - 1;
 310
 311       while (low <= high) {
 312         int mid = (low + high) / 2;
 313         if (records[numVar * mid + offset] == 0) {
 314           low = mid + 1;
 315         } else {
 316           high = mid - 1;
 317         }
 318       }
 319
 320       return (low - start);
 321     }
 322 }
 323
 324 /* =============================================================================
 325  *
 326  * End of data.java
 327  *
 328  * =============================================================================
 329  */