1 /* =============================================================================
5 * =============================================================================
7 * Copyright (C) Stanford University, 2006. All Rights Reserved.
9 * Ported to Java June 2009 Alokika Dash
10 * University of California, Irvine
12 * =============================================================================
14 * For the license of bayes/sort.h and bayes/sort.c, please see the header
17 * ------------------------------------------------------------------------
19 * Unless otherwise noted, the following license applies to STAMP files:
21 * Copyright (c) 2007, Stanford University
22 * All rights reserved.
24 * Redistribution and use in source and binary forms, with or without
25 * modification, are permitted provided that the following conditions are
28 * * Redistributions of source code must retain the above copyright
29 * notice, this list of conditions and the following disclaimer.
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
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.
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.
52 * =============================================================================
55 #define DATA_PRECISION 100
56 #define DATA_INIT 2 /* not 0 or 1 */
61 byte[] records; /* coordination of all records */
65 /* =============================================================================
67 * =============================================================================
69 public Data(int numVar, int numRecord, Random randomPtr)
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;
77 this.numRecord = numRecord;
78 this.randomPtr = randomPtr;
82 public void data_free() {
87 /* =============================================================================
89 * -- Binary variables of random PDFs
90 * -- If seed is <0, do not reseed
91 * -- Returns random network
92 * =============================================================================
94 public Net data_generate (int seed, int maxNumParent, int percentParent)
97 randomPtr.random_seed(seed);
101 * Generate random Bayesian network
104 Net netPtr = new Net(numVar);
105 netPtr.net_generateRandomEdges(maxNumParent, percentParent, randomPtr);
108 * Create a threshold for each of the possible permutation of variable
112 int[][] thresholdsTable = new int[numVar][];
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;
122 thresholdsTable[v] = thresholds;
126 * Create variable dependency ordering for record generation
129 int[] order = new int[numVar];
132 Queue workQueuePtr = Queue.queue_alloc(-1);
134 IntVector dependencyVectorPtr = IntVector.vector_alloc(1);
136 BitMap orderedBitmapPtr = BitMap.bitmap_alloc(numVar);
137 orderedBitmapPtr.bitmap_clearAll();
139 BitMap doneBitmapPtr = BitMap.bitmap_alloc(numVar);
140 doneBitmapPtr.bitmap_clearAll();
143 while ((v = doneBitmapPtr.bitmap_findClear(v + 1)) >= 0) {
144 IntList childIdListPtr = netPtr.net_getChildIdListPtr(v);
145 int numChild = childIdListPtr.list_getSize();
152 * Use breadth-first search to find net connected to this leaf
155 workQueuePtr.queue_clear();
156 if((status = workQueuePtr.queue_push(v)) != true) {
157 System.out.println("Assert failed: status= "+ status + "should be true");
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");
168 if((status = dependencyVectorPtr.vector_pushBack(id)) == false) {
169 System.out.println("Assert failed: status= "+ status + "should be true");
173 IntList parentIdListPtr = netPtr.net_getParentIdListPtr(id);
174 IntListNode it = parentIdListPtr.head;
176 while (it.nextPtr!=null) {
178 int parentId = it.dataPtr;
179 if((status = workQueuePtr.queue_push(parentId)) == false) {
180 System.out.println("Assert failed: status= "+ status + "should be true");
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;
201 if(numOrder != numVar) {
202 System.out.println("Assert failed: numVar should be equal to numOrder");
211 for (int r = 0; r < numRecord; r++) {
212 for (int o = 0; o < numOrder; o++) {
214 IntList parentIdListPtr = netPtr.net_getParentIdListPtr(v);
216 IntListNode it = parentIdListPtr.head;
218 while (it.nextPtr!=null) {
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");
227 index = (index << 1) + value;
229 int rnd = (int) (randomPtr.random_generate() % DATA_PRECISION);
230 int threshold = thresholdsTable[v][index];
231 records[startindex + v] = (byte) ((rnd < threshold) ? 1 : 0);
233 startindex += numVar;
234 if(startindex > numRecord * numVar) {
235 System.out.println("Assert failed: value should be != DATA_INIT in data_generate()");
244 /* =============================================================================
246 * -- Returns false on failure
247 * =============================================================================
249 public static boolean
250 data_copy (Data dstPtr, Data srcPtr)
252 int numDstDatum = dstPtr.numVar * dstPtr.numRecord;
253 int numSrcDatum = srcPtr.numVar * srcPtr.numRecord;
254 if (numDstDatum != numSrcDatum) {
255 dstPtr.records = new byte[numSrcDatum];
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];
266 /* =============================================================================
269 * =============================================================================
272 data_sort (int start,
276 if((start < 0) || (start > numRecord)) {
277 System.out.println("start: Assert failed in data_sort");
280 if((num < 0) || (num > numRecord)) {
281 System.out.println("num: Assert failed in data_sort");
284 if((start + num < 0) || (start + num > numRecord)) {
285 System.out.println("start + num: Assert failed in data_sort");
299 /* =============================================================================
301 * -- Call data_sort first with proper start, num, offset
302 * -- Returns number of zeros in offset column
303 * =============================================================================
306 data_findSplit (int start, int num, int offset)
309 int high = start + num - 1;
311 while (low <= high) {
312 int mid = (low + high) / 2;
313 if (records[numVar * mid + offset] == 0) {
320 return (low - start);
324 /* =============================================================================
328 * =============================================================================