Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Queue_t.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
  11  * Author:Alokika Dash
  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_t {
  55         private static int QUEUE_GROWTH_FACTOR;
  56
  57   int pop; /* points before element to pop */
  58   int push;
  59   int capacity;
  60   Object[] elements;
  61
  62   public Queue_t() {
  63           QUEUE_GROWTH_FACTOR = 2;
  64   }
  65
  66   /* =============================================================================
  67    * queue_alloc
  68    * =============================================================================
  69    */
  70   public Queue_t queue_alloc (int initCapacity)
  71   {
  72     Queue_t queuePtr = new Queue_t();
  73
  74     int capacity = ((initCapacity < 2) ? 2 : initCapacity);
  75     queuePtr.elements = new Object[capacity];
  76     if (queuePtr.elements == null) {
  77       queuePtr = null;
  78       return null;
  79     }
  80     queuePtr.pop      = capacity - 1;
  81     queuePtr.push     = 0;
  82     queuePtr.capacity = capacity;
  83
  84     return queuePtr;
  85   }
  86
  87
  88   /* =============================================================================
  89    * Pqueue_alloc
  90    * =============================================================================
  91    */
  92   public Queue_t
  93     Pqueue_alloc (int initCapacity)
  94     {
  95       Queue_t queuePtr = new Queue_t();
  96
  97       int capacity = ((initCapacity < 2) ? 2 : initCapacity);
  98       queuePtr.elements = new Object[capacity];
  99       if (queuePtr.elements == null) {
 100         queuePtr = null;
 101         return null;
 102       }
 103       queuePtr.pop      = capacity - 1;
 104       queuePtr.push     = 0;
 105       queuePtr.capacity = capacity;
 106
 107       return queuePtr;
 108     }
 109
 110   /* =============================================================================
 111    * queue_free
 112    * =============================================================================
 113    */
 114   public void
 115     queue_free (Queue_t queuePtr)
 116     {
 117       queuePtr.elements = null;
 118       queuePtr = null;
 119     }
 120
 121
 122   /* =============================================================================
 123    * Pqueue_free
 124    * =============================================================================
 125    */
 126   public void
 127     Pqueue_free (Queue_t queuePtr)
 128     {
 129       queuePtr.elements = null;
 130       queuePtr = null;
 131     }
 132
 133
 134   /* =============================================================================
 135    * TMqueue_free
 136    * =============================================================================
 137    *
 138   public void
 139     TMqueue_free (TM_ARGDECL  Queue* queuePtr)
 140     {
 141       queuePtr.elements = null;
 142       queuePtr = null;
 143     }
 144
 145 */
 146   /* =============================================================================
 147    * queue_isEmpty
 148    * =============================================================================
 149    */
 150   public boolean
 151     queue_isEmpty ()
 152     {
 153       //int pop      = queuePtr.pop;
 154       //int push     = queuePtr.push;
 155       //int capacity = queuePtr.capacity;
 156
 157       return (((pop + 1) % capacity == push) ? true : false);
 158     }
 159
 160
 161   /* =============================================================================
 162    * queue_clear
 163    * =============================================================================
 164    */
 165   public void
 166     queue_clear ()
 167     {
 168       pop  = capacity - 1;
 169       push = 0;
 170     }
 171
 172
 173   /* =============================================================================
 174    * TMqueue_isEmpty
 175    * =============================================================================
 176    */
 177
 178
 179
 180   /* =============================================================================
 181    * queue_push
 182    * =============================================================================
 183    */
 184   public boolean
 185     queue_push (Object dataPtr)
 186     {
 187
 188       if(pop == push) {
 189
 190         System.out.println("push == pop in Queue.java");
 191         return false;
 192       }
 193
 194
 195       /* Need to resize */
 196       int newPush = (push + 1) % capacity;
 197       if (newPush == pop) {
 198
 199         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 200         Object[] newElements = new Object[newCapacity];
 201         if (newElements == null) {
 202           return false;
 203         }
 204
 205         int dst = 0;
 206         Object[] tmpelements = elements;
 207         if (pop < push) {
 208           int src;
 209           for (src = (pop + 1); src < push; src++, dst++) {
 210             newElements[dst] = elements[src];
 211           }
 212         } else {
 213           int src;
 214           for (src = (pop + 1); src < capacity; src++, dst++) {
 215             newElements[dst] = elements[src];
 216           }
 217           for (src = 0; src < push; src++, dst++) {
 218             newElements[dst] = elements[src];
 219           }
 220         }
 221
 222         //elements = null;
 223         elements = newElements;
 224         pop      = newCapacity - 1;
 225         capacity = newCapacity;
 226         push = dst;
 227         newPush = push + 1; /* no need modulo */
 228       }
 229
 230       elements[push] = dataPtr;
 231       push = newPush;
 232
 233       return true;
 234     }
 235
 236
 237   /* =============================================================================
 238    * Pqueue_push
 239    * =============================================================================
 240    */
 241   public boolean
 242     Pqueue_push (Queue_t queuePtr, Object dataPtr)
 243     {
 244       int pop      = queuePtr.pop;
 245       int push     = queuePtr.push;
 246       int capacity = queuePtr.capacity;
 247
 248       if(pop == push) {
 249         System.out.println("push == pop in Queue.java");
 250         return false;
 251       }
 252
 253       /* Need to resize */
 254       int newPush = (push + 1) % capacity;
 255       if (newPush == pop) {
 256
 257         int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 258         Object[] newElements = new Object[newCapacity];
 259         if (newElements == null) {
 260           return false;
 261         }
 262
 263         int dst = 0;
 264         Object[] elements = queuePtr.elements;
 265         if (pop < push) {
 266           int src;
 267           for (src = (pop + 1); src < push; src++, dst++) {
 268             newElements[dst] = elements[src];
 269           }
 270         } else {
 271           int src;
 272           for (src = (pop + 1); src < capacity; src++, dst++) {
 273             newElements[dst] = elements[src];
 274           }
 275           for (src = 0; src < push; src++, dst++) {
 276             newElements[dst] = elements[src];
 277           }
 278         }
 279
 280         elements = null;
 281         queuePtr.elements = newElements;
 282         queuePtr.pop      = newCapacity - 1;
 283         queuePtr.capacity = newCapacity;
 284         push = dst;
 285         newPush = push + 1; /* no need modulo */
 286
 287       }
 288
 289       queuePtr.elements[push] = dataPtr;
 290       queuePtr.push = newPush;
 291
 292       return true;
 293     }
 294
 295   /* =============================================================================
 296    * queue_pop
 297    * =============================================================================
 298    */
 299   public Object
 300     //queue_pop (Queue queuePtr)
 301     queue_pop ()
 302     {
 303       //int pop      = queuePtr.pop;
 304       //int push     = queuePtr.push;
 305       //int capacity = queuePtr.capacity;
 306
 307       int newPop = (pop + 1) % capacity;
 308       if (newPop == push) {
 309         return null;
 310       }
 311
 312       //Object dataPtr = queuePtr.elements[newPop];
 313       //queuePtr.pop = newPop;
 314       Object dataPtr = elements[newPop];
 315       pop = newPop;
 316
 317       return dataPtr;
 318     }
 319
 320   /* =============================================================================
 321    * pop a certain amount
 322    * =============================================================================
 323    */
 324
 325   //TODO optimize by taking advantage of underlying data structure
 326   public Queue_t get(int n, Queue_t original)
 327   {
 328           Queue_t subset = original.queue_alloc(n);
 329
 330           for(int i = 0; i < n; i++)
 331           {
 332                   Object o = original.queue_pop();
 333                   subset.queue_push(o);
 334           }
 335
 336           return subset;
 337   }
 338
 339 }
 340 /* =============================================================================
 341  *
 342  * End of queue.java
 343  *
 344  * =============================================================================
 345  */