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

   1 /* =============================================================================
   2  *
   3  * queue.java
   4  *
   5  * =============================================================================
   6  *
   7  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   8  * Author: Chi Cao Minh
   9  *
  10  * Ported to Java June 2009 Alokika Dash
  11  * adash@uci.edu
  12  * University of California, Irvine
  13  *
  14  * =============================================================================
  15  *
  16  * Unless otherwise noted, the following license applies to STAMP files:
  17  *
  18  * Copyright (c) 2007, Stanford University
  19  * All rights reserved.
  20  *
  21  * Redistribution and use in source and binary forms, with or without
  22  * modification, are permitted provided that the following conditions are
  23  * met:
  24  *
  25  *     * Redistributions of source code must retain the above copyright
  26  *       notice, this list of conditions and the following disclaimer.
  27  *
  28  *     * Redistributions in binary form must reproduce the above copyright
  29  *       notice, this list of conditions and the following disclaimer in
  30  *       the documentation and/or other materials provided with the
  31  *       distribution.
  32  *
  33  *     * Neither the name of Stanford University nor the names of its
  34  *       contributors may be used to endorse or promote products derived
  35  *       from this software without specific prior written permission.
  36  *
  37  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  38  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  40  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  41  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  42  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  43  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  44  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  45  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  47  * THE POSSIBILITY OF SUCH DAMAGE.
  48  *
  49  * =============================================================================
  50  */
  51
  52 #define QUEUE_GROWTH_FACTOR 2
  53
  54 public class Queue {
  55   int pop; /* points before element to pop */
  56   int push;
  57   int capacity;
  58   int[] elements;
  59
  60   public Queue() {
  61   }
  62
  63   /* =============================================================================
  64    * queue_alloc
  65    * =============================================================================
  66    */
  67   public static Queue queue_alloc (int initCapacity)
  68   {
  69     Queue queuePtr = new Queue();
  70
  71     int capacity = ((initCapacity < 2) ? 2 : initCapacity);
  72     queuePtr.elements = new int[capacity];
  73     if (queuePtr.elements == null) {
  74       queuePtr = null;
  75       return null;
  76     }
  77     queuePtr.pop      = capacity - 1;
  78     queuePtr.push     = 0;
  79     queuePtr.capacity = capacity;
  80
  81     return queuePtr;
  82   }
  83
  84
  85   /* =============================================================================
  86    * Pqueue_alloc
  87    * =============================================================================
  88    */
  89   public Queue
  90     Pqueue_alloc (int initCapacity)
  91     {
  92       Queue queuePtr = new Queue();
  93
  94       int capacity = ((initCapacity < 2) ? 2 : initCapacity);
  95       queuePtr.elements = new int[capacity];
  96       if (queuePtr.elements == null) {
  97         queuePtr = null;
  98         return null;
  99       }
 100       queuePtr.pop      = capacity - 1;
 101       queuePtr.push     = 0;
 102       queuePtr.capacity = capacity;
 103
 104       return queuePtr;
 105     }
 106
 107
 108   /* =============================================================================
 109    * TMqueue_alloc
 110    * =============================================================================
 111    */
 112   public Queue TMqueue_alloc (int initCapacity)
 113   {
 114     Queue queuePtr = new Queue();
 115
 116     int capacity = ((initCapacity < 2) ? 2 : initCapacity);
 117     queuePtr.elements = new int[capacity];
 118     if (queuePtr.elements == null) {
 119       queuePtr = null;
 120       return null;
 121     }
 122     queuePtr.pop      = capacity - 1;
 123     queuePtr.push     = 0;
 124     queuePtr.capacity = capacity;
 125
 126     return queuePtr;
 127   }
 128
 129
 130   /* =============================================================================
 131    * queue_free
 132    * =============================================================================
 133    */
 134   public void
 135     queue_free ()
 136     {
 137       elements = null;
 138     }
 139
 140
 141   /* =============================================================================
 142    * Pqueue_free
 143    * =============================================================================
 144    */
 145   public void
 146     Pqueue_free ()
 147     {
 148       elements = null;
 149     }
 150
 151
 152   /* =============================================================================
 153    * TMqueue_free
 154    * =============================================================================
 155    */
 156   public void
 157     TMqueue_free ()
 158     {
 159       elements = null;
 160     }
 161
 162
 163   /* =============================================================================
 164    * queue_isEmpty
 165    * =============================================================================
 166    */
 167   public boolean
 168     queue_isEmpty ()
 169     {
 170       return (((pop + 1) % capacity == push) ? true : false);
 171     }
 172
 173
 174   /* =============================================================================
 175    * queue_clear
 176    * =============================================================================
 177    */
 178   public void
 179     queue_clear ()
 180     {
 181       pop  = capacity - 1;
 182       push = 0;
 183     }
 184
 185
 186   /* =============================================================================
 187    * TMqueue_isEmpty
 188    * =============================================================================
 189    */
 190   public boolean
 191     TMqueue_isEmpty (Queue queuePtr)
 192     {
 193       int pop      = queuePtr.pop;
 194       int push     = queuePtr.push;
 195       int capacity = queuePtr.capacity;
 196
 197       return (((pop + 1) % capacity == push) ? true : false);
 198     }
 199
 200
 201   /* =============================================================================
 202    * queue_shuffle
 203    * =============================================================================
 204    */
 205   public void
 206     queue_shuffle (Queue queuePtr, Random randomPtr)
 207     {
 208       int pop      = queuePtr.pop;
 209       int push     = queuePtr.push;
 210       int capacity = queuePtr.capacity;
 211
 212       int numElement;
 213       if (pop < push) {
 214         numElement = push - (pop + 1);
 215       } else {
 216         numElement = capacity - (pop - push + 1);
 217       }
 218
 219       int[] elements = queuePtr.elements;
 220       int i;
 221       int base = pop + 1;
 222       for (i = 0; i < numElement; i++) {
 223         int r1 = (int) (randomPtr.random_generate() % numElement);
 224         int r2 = (int) (randomPtr.random_generate() % numElement);
 225         int i1 = (base + r1) % capacity;
 226         int i2 = (base + r2) % capacity;
 227         int tmp = elements[i1];
 228         elements[i1] = elements[i2];
 229         elements[i2] = tmp;
 230       }
 231     }
 232
 233
 234   /* =============================================================================
 235    * queue_push
 236    * =============================================================================
 237    */
 238   public boolean
 239     queue_push (int dataPtr)
 240     {
 241       if(pop == push) {
 242         System.out.println("push == pop in Queue.java");
 243         return false;
 244       }
 245
 246       /* Need to resize */
 247       int newPush = (push + 1) % capacity;
 248       if (newPush == pop) {
 249
 250         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 251         int[] newElements = new int[newCapacity];
 252         if (newElements == null) {
 253           return false;
 254         }
 255
 256         int dst = 0;
 257         int[] tmpelements = elements;
 258         if (pop < push) {
 259           int src;
 260           for (src = (pop + 1); src < push; src++, dst++) {
 261             newElements[dst] = elements[src];
 262           }
 263         } else {
 264           int src;
 265           for (src = (pop + 1); src < capacity; src++, dst++) {
 266             newElements[dst] = elements[src];
 267           }
 268           for (src = 0; src < push; src++, dst++) {
 269             newElements[dst] = elements[src];
 270           }
 271         }
 272
 273         elements = newElements;
 274         pop      = newCapacity - 1;
 275         capacity = newCapacity;
 276         push = dst;
 277         newPush = push + 1; /* no need modulo */
 278       }
 279
 280       elements[push] = dataPtr;
 281       push = newPush;
 282
 283       return true;
 284     }
 285
 286
 287   /* =============================================================================
 288    * Pqueue_push
 289    * =============================================================================
 290    */
 291   public boolean
 292     Pqueue_push (Queue queuePtr, int dataPtr)
 293     {
 294       int pop      = queuePtr.pop;
 295       int push     = queuePtr.push;
 296       int capacity = queuePtr.capacity;
 297
 298       if(pop == push) {
 299         System.out.println("push == pop in Queue.java");
 300         return false;
 301       }
 302
 303       /* Need to resize */
 304       int newPush = (push + 1) % capacity;
 305       if (newPush == pop) {
 306
 307         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 308         int[] newElements = new int[newCapacity];
 309         if (newElements == null) {
 310           return false;
 311         }
 312
 313         int dst = 0;
 314         int[] elements = queuePtr.elements;
 315         if (pop < push) {
 316           int src;
 317           for (src = (pop + 1); src < push; src++, dst++) {
 318             newElements[dst] = elements[src];
 319           }
 320         } else {
 321           int src;
 322           for (src = (pop + 1); src < capacity; src++, dst++) {
 323             newElements[dst] = elements[src];
 324           }
 325           for (src = 0; src < push; src++, dst++) {
 326             newElements[dst] = elements[src];
 327           }
 328         }
 329
 330         elements = null;
 331         queuePtr.elements = newElements;
 332         queuePtr.pop      = newCapacity - 1;
 333         queuePtr.capacity = newCapacity;
 334         push = dst;
 335         newPush = push + 1; /* no need modulo */
 336
 337       }
 338
 339       queuePtr.elements[push] = dataPtr;
 340       queuePtr.push = newPush;
 341
 342       return true;
 343     }
 344
 345
 346   /* =============================================================================
 347    * TMqueue_push
 348    * =============================================================================
 349    */
 350   public boolean
 351     TMqueue_push (Queue queuePtr, int dataPtr)
 352     {
 353       int pop      = (queuePtr.pop);
 354       int push     = (queuePtr.push);
 355       int capacity = (queuePtr.capacity);
 356
 357       if(pop == push) {
 358         System.out.println("push == pop in Queue.java");
 359         return false;
 360       }
 361
 362       /* Need to resize */
 363       int newPush = (push + 1) % capacity;
 364       if (newPush == pop) {
 365         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 366         int[] newElements = new int[newCapacity];
 367         if (newElements == null) {
 368           return false;
 369         }
 370
 371         int dst = 0;
 372         int[] elements = queuePtr.elements;
 373         if (pop < push) {
 374           int src;
 375           for (src = (pop + 1); src < push; src++, dst++) {
 376             newElements[dst] = (elements[src]);
 377           }
 378         } else {
 379           int src;
 380           for (src = (pop + 1); src < capacity; src++, dst++) {
 381             newElements[dst] = (elements[src]);
 382           }
 383           for (src = 0; src < push; src++, dst++) {
 384             newElements[dst] = (elements[src]);
 385           }
 386         }
 387
 388         elements = null;
 389         queuePtr.elements = newElements;
 390         queuePtr.pop      = newCapacity - 1;
 391         queuePtr.capacity = newCapacity;
 392         push = dst;
 393         newPush = push + 1; /* no need modulo */
 394
 395       }
 396
 397       int[] elements = queuePtr.elements;
 398       elements[push] = dataPtr;
 399       queuePtr.push = newPush;
 400
 401       return true;
 402     }
 403
 404
 405   /* =============================================================================
 406    * queue_pop
 407    * =============================================================================
 408    */
 409   public int
 410     queue_pop ()
 411     {
 412       int newPop = (pop + 1) % capacity;
 413       if (newPop == push) {
 414         return 0;
 415       }
 416
 417       int dataPtr = elements[newPop];
 418       pop = newPop;
 419
 420       return dataPtr;
 421     }
 422
 423
 424   /* =============================================================================
 425    * TMqueue_pop
 426    * =============================================================================
 427    */
 428   public int
 429     TMqueue_pop (Queue queuePtr)
 430     {
 431       int pop      = queuePtr.pop;
 432       int push     = queuePtr.push;
 433       int capacity = queuePtr.capacity;
 434
 435       int newPop = (pop + 1) % capacity;
 436       if (newPop == push) {
 437         return 0;
 438       }
 439
 440       int[] elements = queuePtr.elements;
 441       int dataPtr = elements[newPop];
 442       queuePtr.pop = newPop;
 443
 444       return dataPtr;
 445     }
 446
 447   /****
 448    * main method for testing
 449    **/
 450   /*
 451      public static void main(String[] args) {
 452      testQueue queuePtr = testQueue.queue_alloc(-1);
 453      int numData = 4;
 454      if(queuePtr.queue_isEmpty())
 455      System.out.println("Queue is empty");
 456
 457      for(int i = 0; i<numData; i++) {
 458      System.out.println("Inserting " + i);
 459      queuePtr.queue_push(i);
 460      }
 461
 462      for(int i = 0; i<numData; i++) {
 463      int val = queuePtr.queue_pop();
 464      System.out.println("Removing " + val);
 465      }
 466
 467      if(queuePtr.queue_isEmpty())
 468      System.out.println("Queue is empty");
 469      }
 470      */
 471 }
 472 /* =============================================================================
 473  *
 474  * End of queue.java
 475  *
 476  * =============================================================================
 477  */