src/main/gov/nasa/jpf/util/ArrayObjectQueue.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19 package gov.nasa.jpf.util;
  20
  21 import java.util.Iterator;
  22 import java.util.NoSuchElementException;
  23
  24 /**
  25  * dynamically growing, cyclic array buffer queue for object references
  26  */
  27 public class ArrayObjectQueue<E> implements ObjectQueue<E> {
  28
  29   static final int DEFAULT_CAPACITY = 256;
  30
  31   int size = 0;
  32   int first;  // next index we will remove
  33   int last;   // last index we did add
  34
  35   Object[] buffer = null;
  36
  37   class FIFOIterator implements Iterator<E> {
  38     int next = first;
  39     int remaining = size;
  40
  41     @Override
  42         public boolean hasNext() {
  43       return (remaining > 0);
  44     }
  45
  46     @Override
  47         public E next() {
  48       if (remaining == 0){
  49         throw new NoSuchElementException();
  50       } else {
  51         E e = (E) buffer[next];
  52         next = (next+1) % buffer.length;
  53         remaining--;
  54         return e;
  55       }
  56     }
  57
  58     @Override
  59         public void remove() { // its a queue
  60       throw new UnsupportedOperationException();
  61     }
  62   }
  63
  64   // just for debugging purposes
  65   class StorageIterator implements Iterator<E> {
  66     int next = 0;
  67
  68     @Override
  69         public boolean hasNext(){
  70       return (next < buffer.length);
  71     }
  72
  73     @Override
  74         public E next(){
  75       if (next == buffer.length){
  76         throw new NoSuchElementException();
  77       }
  78
  79       E e = (E) buffer[next];
  80       next++;
  81       return e;
  82     }
  83
  84     @Override
  85         public void remove() { // its a queue
  86       throw new UnsupportedOperationException();
  87     }
  88   }
  89
  90   public ArrayObjectQueue (){
  91     buffer = new Object[DEFAULT_CAPACITY];
  92   }
  93
  94   public ArrayObjectQueue (int initialCapacity){
  95     buffer = new Object[initialCapacity];
  96   }
  97
  98   protected void grow(){
  99     Object[] newBuffer = new Object[buffer.length * 3 / 2];
 100
 101     if (first < last){
 102       System.arraycopy(buffer, first, newBuffer, 0, last - first +1);
 103     } else if (first > last){
 104       int nRight = buffer.length - first;
 105       System.arraycopy(buffer, first, newBuffer, 0, nRight);
 106       System.arraycopy(buffer, 0, newBuffer, nRight, last+1);
 107     } else { // just 1 element
 108       newBuffer[0] = buffer[first];
 109     }
 110
 111     first = 0;
 112     last = size-1;
 113     buffer = newBuffer;
 114   }
 115
 116   @Override
 117   public boolean isEmpty() {
 118     return (size == 0);
 119   }
 120
 121   public int getCurrentCapacity(){
 122     return buffer.length;
 123   }
 124
 125   @Override
 126   public int size() {
 127     return size;
 128   }
 129
 130   @Override
 131   public boolean offer (E e){
 132     return add(e);
 133   }
 134
 135   @Override
 136   public boolean add (E e){
 137     if (size == 0){  // first element
 138       first = last = 0;
 139       buffer[0] = e;
 140       size = 1;
 141
 142     } else {
 143       int i = (last + 1) % buffer.length;
 144       if (i == first) {
 145         grow();
 146         i = size;
 147       }
 148
 149       last = i;
 150       buffer[i] = e;
 151       size++;
 152     }
 153
 154     return true; // this is a dynamic queue, we never run out of space
 155   }
 156
 157   @Override
 158   public E poll (){
 159     if (size == 0){
 160       return null;
 161
 162     } else {
 163       int i = first;
 164
 165       first = (first+1) % buffer.length;
 166       size--;
 167
 168       E e = (E) buffer[i];
 169       buffer[i] = null; // avoid memory leaks
 170       return e;
 171     }
 172
 173   }
 174
 175   @Override
 176   public E remove () throws NoSuchElementException {
 177     if (size == 0){
 178       throw new NoSuchElementException();
 179     } else {
 180       return poll();
 181     }
 182   }
 183
 184   @Override
 185   public E peek () {
 186     if (size == 0){
 187       return null;
 188     } else {
 189       return (E)buffer[first];
 190     }
 191   }
 192
 193   @Override
 194   public Iterator<E> iterator() {
 195     return new FIFOIterator();
 196   }
 197
 198   public Iterator<E> storageIterator(){
 199     return new StorageIterator();
 200   }
 201
 202
 203   @Override
 204   public void clear(){
 205     buffer = new Object[buffer.length]; // cheaper than iterating over the old one
 206     size = 0;
 207     first = last = -1;
 208   }
 209
 210   /**
 211    * call Processor.process(e) on each queued object
 212    *
 213    * This method does not return before the queue is empty, which makes it
 214    * suitable for graph traversal. It also avoids iterator objects, allows
 215    * adding new objects while processing the queue, and enables to keep
 216    * processing state in the processor
 217    */
 218   @Override
 219   public void process (Processor<E> processor){
 220     while (size > 0){
 221       E e = remove();
 222       processor.process(e);
 223     }
 224   }
 225 }