Robust/src/ClassLibrary/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
  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 public class Queue {
  53   int pop; /* points before element to pop */
  54   int push;
  55   int capacity;
  56   int size;
  57   int QUEUE_GROWTH_FACTOR;
  58   Object[] elements;
  59
  60   public Queue() {
  61     Queue(10);
  62   }
  63
  64   /* =============================================================================
  65    * queue_alloc
  66    * =============================================================================
  67    */
  68   public Queue (int initCapacity) {
  69     QUEUE_GROWTH_FACTOR = 2;
  70     capacity = ((initCapacity < 2)?2:initCapacity);
  71
  72     elements = new Object[capacity];
  73     size = 0;
  74     pop      = capacity - 1;
  75     push     = 0;
  76     capacity = capacity;
  77   }
  78
  79   /* =============================================================================
  80    * queue_isEmpty
  81    * =============================================================================
  82    */
  83   public boolean
  84   isEmpty() {
  85     return (((pop + 1) % capacity == push)?true:false);
  86   }
  87
  88
  89   /* =============================================================================
  90    * queue_clear
  91    * =============================================================================
  92    */
  93   public void
  94   queue_clear() {
  95     pop  = capacity - 1;
  96     push = 0;
  97   }
  98
  99   /* =============================================================================
 100    * queue_push
 101    * =============================================================================
 102    */
 103   public boolean
 104   push(Object dataPtr) {
 105     if(pop == push) {
 106 //        System.out.println("push == pop in Queue.java");
 107       return false;
 108     }
 109
 110     /* Need to resize */
 111     int newPush = (push + 1) % capacity;
 112     if (newPush == pop) {
 113
 114       int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
 115       Object[] newElements = new Object[newCapacity];
 116
 117       if (newElements == null) {
 118         return false;
 119       }
 120
 121       int dst = 0;
 122       Object[] tmpelements = elements;
 123       if (pop < push) {
 124         int src;
 125         for (src = (pop + 1); src < push; src++, dst++) {
 126           newElements[dst] = elements[src];
 127         }
 128       } else {
 129         int src;
 130         for (src = (pop + 1); src < capacity; src++, dst++) {
 131           newElements[dst] = elements[src];
 132         }
 133         for (src = 0; src < push; src++, dst++) {
 134           newElements[dst] = elements[src];
 135         }
 136       }
 137
 138       //elements = null;
 139       elements = newElements;
 140       pop      = newCapacity - 1;
 141       capacity = newCapacity;
 142       push = dst;
 143       newPush = push + 1;   /* no need modulo */
 144     }
 145     size++;
 146     elements[push] = dataPtr;
 147     push = newPush;
 148
 149     return true;
 150   }
 151
 152
 153   /* =============================================================================
 154    * queue_pop
 155    * =============================================================================
 156    */
 157   public Object
 158   pop() {
 159     int newPop = (pop + 1) % capacity;
 160     if (newPop == push) {
 161       return null;
 162     }
 163
 164     //Object dataPtr = queuePtr.elements[newPop];
 165     //queuePtr.pop = newPop;
 166     Object dataPtr = elements[newPop];
 167     pop = newPop;
 168     size--;
 169     return dataPtr;
 170   }
 171   public int size() {
 172     return size;
 173   }
 174
 175 }
 176 /* =============================================================================
 177  *
 178  * End of queue.java
 179  *
 180  * =============================================================================
 181  */