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
  64   public Data() {
  65   }
  66
  67   /* =============================================================================
  68    * data_alloc
  69    * =============================================================================
  70    */
  71   public static Data data_alloc (int numVar, int numRecord, Random randomPtr)
  72   {
  73     Data dataPtr = new Data();
  74
  75     if (dataPtr != null) {
  76       int numDatum = numVar * numRecord;
  77       dataPtr.records = new byte[numDatum];
  78       for(int i = 0; i<numDatum; i++)
  79         dataPtr.records[i] = (byte)DATA_INIT;
  80
  81       dataPtr.numVar = numVar;
  82       dataPtr.numRecord = numRecord;
  83       dataPtr.randomPtr = randomPtr;
  84     }
  85
  86     return dataPtr;
  87   }
  88
  89
  90   /* =============================================================================
  91    * data_free
  92    * =============================================================================
  93    */
  94   void
  95     data_free ()
  96     {
  97       records = null;
  98     }
  99
 100   /* =============================================================================
 101    * data_generate
 102    * -- Binary variables of random PDFs
 103    * -- If seed is <0, do not reseed
 104    * -- Returns random network
 105    * =============================================================================
 106    */
 107   public Net data_generate (int seed, int maxNumParent, int percentParent)
 108   {
 109     if (seed >= 0) {
 110       randomPtr.random_seed(seed);
 111     }
 112
 113     /*
 114      * Generate random Bayesian network
 115      */
 116
 117     Net netPtr = Net.net_alloc(numVar);
 118     netPtr.net_generateRandomEdges(maxNumParent, percentParent, randomPtr);
 119
 120     /*
 121      * Create a threshold for each of the possible permutation of variable
 122      * value instances
 123      */
 124
 125     int[][] thresholdsTable = new int[numVar][];
 126     int v;
 127     for (v = 0; v < numVar; v++) {
 128       IntList parentIdListPtr = netPtr.net_getParentIdListPtr(v);
 129       int numThreshold = 1 << parentIdListPtr.list_getSize();
 130       int[] thresholds = new int[numThreshold];
 131       for (int t = 0; t < numThreshold; t++) {
 132         int threshold = (int) (randomPtr.random_generate() % (DATA_PRECISION + 1));
 133         thresholds[t] = threshold;
 134       }
 135       thresholdsTable[v] = thresholds;
 136     }
 137
 138     /*
 139      * Create variable dependency ordering for record generation
 140      */
 141
 142     int[] order = new int[numVar];
 143     int numOrder = 0;
 144
 145     Queue workQueuePtr = Queue.queue_alloc(-1);
 146
 147     IntVector dependencyVectorPtr = IntVector.vector_alloc(1);
 148
 149     BitMap orderedBitmapPtr = BitMap.bitmap_alloc(numVar);
 150     orderedBitmapPtr.bitmap_clearAll();
 151
 152     BitMap doneBitmapPtr = BitMap.bitmap_alloc(numVar);
 153     doneBitmapPtr.bitmap_clearAll();
 154
 155     v = -1;
 156     while ((v = doneBitmapPtr.bitmap_findClear(v + 1)) >= 0) {
 157       IntList childIdListPtr = netPtr.net_getChildIdListPtr(v);
 158       int numChild = childIdListPtr.list_getSize();
 159
 160       if (numChild == 0) {
 161
 162         boolean status;
 163
 164         /*
 165          * Use breadth-first search to find net connected to this leaf
 166          */
 167
 168         workQueuePtr.queue_clear();
 169         if((status = workQueuePtr.queue_push(v)) != true) {
 170           System.out.println("Assert failed: status= "+ status + "should be true");
 171           System.exit(0);
 172         }
 173
 174         while (!(workQueuePtr.queue_isEmpty())) {
 175           int id = workQueuePtr.queue_pop();
 176           if((status = doneBitmapPtr.bitmap_set(id)) != true) {
 177             System.out.println("Assert failed: status= "+ status + "should be true");
 178             System.exit(0);
 179           }
 180
 181           if((status = dependencyVectorPtr.vector_pushBack(id)) == false) {
 182             System.out.println("Assert failed: status= "+ status + "should be true");
 183             System.exit(0);
 184           }
 185
 186           IntList parentIdListPtr = netPtr.net_getParentIdListPtr(id);
 187           IntListNode it = parentIdListPtr.head;
 188
 189           while (it.nextPtr!=null) {
 190             it = it.nextPtr;
 191             int parentId = it.dataPtr;
 192             if((status = workQueuePtr.queue_push(parentId)) == false) {
 193               System.out.println("Assert failed: status= "+ status + "should be true");
 194               System.exit(0);
 195             }
 196           }
 197         }
 198
 199         /*
 200          * Create ordering
 201          */
 202
 203         int n = dependencyVectorPtr.vector_getSize();
 204         for (int i = 0; i < n; i++) {
 205           int id = dependencyVectorPtr.vector_popBack();
 206           if (!(orderedBitmapPtr.bitmap_isSet(id))) {
 207             orderedBitmapPtr.bitmap_set(id);
 208             order[numOrder++] = id;
 209           }
 210         }
 211       }
 212     }
 213
 214     if(numOrder != numVar) {
 215       System.out.println("Assert failed: numVar should be equal to numOrder");
 216       System.exit(0);
 217     }
 218
 219     /*
 220      * Create records
 221      */
 222
 223     int startindex = 0;
 224     for (int r = 0; r < numRecord; r++) {
 225       for (int o = 0; o < numOrder; o++) {
 226         v = order[o];
 227         IntList parentIdListPtr = netPtr.net_getParentIdListPtr(v);
 228         int index = 0;
 229         IntListNode it = parentIdListPtr.head;
 230
 231         while (it.nextPtr!=null) {
 232           it = it.nextPtr;
 233           int parentId = it.dataPtr;
 234           int value = records[startindex + parentId];
 235           if(value == DATA_INIT) {
 236             System.out.println("Assert failed value should be != DATA_INIT");
 237             System.exit(0);
 238           }
 239
 240           index = (index << 1) + value;
 241         }
 242         int rnd = (int) (randomPtr.random_generate() % DATA_PRECISION);
 243         int threshold = thresholdsTable[v][index];
 244         records[startindex + v] = (byte) ((rnd < threshold) ? 1 : 0);
 245       }
 246       startindex += numVar;
 247       if(startindex > numRecord * numVar) {
 248         System.out.println("Assert failed: value should be != DATA_INIT in data_generate()");
 249         System.exit(0);
 250       }
 251     }
 252
 253     /*
 254      * Clean up
 255      */
 256
 257     doneBitmapPtr.bitmap_free();
 258     orderedBitmapPtr.bitmap_free();
 259     dependencyVectorPtr.vector_free();
 260     workQueuePtr.queue_free();
 261     order = null;
 262
 263     for (v = 0; v < numVar; v++) {
 264       thresholdsTable[v] = null;
 265     }
 266
 267     thresholdsTable = null;
 268
 269     return netPtr;
 270   }
 271
 272
 273   /* =============================================================================
 274    * data_copy
 275    * -- Returns false on failure
 276    * =============================================================================
 277    */
 278   public static boolean
 279     data_copy (Data dstPtr, Data srcPtr)
 280     {
 281       int numDstDatum = dstPtr.numVar * dstPtr.numRecord;
 282       int numSrcDatum = srcPtr.numVar * srcPtr.numRecord;
 283       if (numDstDatum != numSrcDatum) {
 284         dstPtr.records = null;
 285         dstPtr.records = new byte[numSrcDatum];
 286         if (dstPtr.records == null) {
 287           return false;
 288         }
 289       }
 290
 291       dstPtr.numVar    = srcPtr.numVar;
 292       dstPtr.numRecord = srcPtr.numRecord;
 293       for(int i=0; i<numSrcDatum; i++)
 294         dstPtr.records[i] = srcPtr.records[i];
 295
 296       return true;
 297     }
 298
 299   /* =============================================================================
 300    * data_sort
 301    * -- In place
 302    * =============================================================================
 303    */
 304   public void
 305     data_sort (int start,
 306         int num,
 307         int offset)
 308     {
 309       if((start < 0) || (start > numRecord)) {
 310         System.out.println("start: Assert failed in data_sort");
 311         System.exit(0);
 312       }
 313       if((num < 0) || (num > numRecord)) {
 314         System.out.println("num: Assert failed in data_sort");
 315         System.exit(0);
 316       }
 317       if((start + num < 0) || (start + num > numRecord)) {
 318         System.out.println("start + num: Assert failed in data_sort");
 319         System.exit(0);
 320       }
 321
 322       Sort.sort(records,
 323           start * numVar,
 324           num,
 325           numVar,
 326           numVar,
 327           offset);
 328
 329     }
 330
 331
 332   /* =============================================================================
 333    * data_findSplit
 334    * -- Call data_sort first with proper start, num, offset
 335    * -- Returns number of zeros in offset column
 336    * =============================================================================
 337    */
 338   public int
 339     data_findSplit (int start, int num, int offset)
 340     {
 341       int low = start;
 342       int high = start + num - 1;
 343
 344       while (low <= high) {
 345         int mid = (low + high) / 2;
 346         if (records[numVar * mid + offset] == 0) {
 347           low = mid + 1;
 348         } else {
 349           high = mid - 1;
 350         }
 351       }
 352
 353       return (low - start);
 354     }
 355 }
 356
 357 /* =============================================================================
 358  *
 359  * End of data.java
 360  *
 361  * =============================================================================
 362  */