src/main/gov/nasa/jpf/util/ArrayByteQueue.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 package gov.nasa.jpf.util;
  19
  20 import java.util.Iterator;
  21 import java.util.NoSuchElementException;
  22
  23 /**
  24  * It is a dynamically growing, cyclic array buffer queue for bytes. It has
  25  * the similar implementation as ArrayObjectQueue.
  26  *
  27  * Suitable buffer for storing data transmitted and received as a continuous
  28  * stream of bytes, e.g. buffers for socket based communications
  29  */
  30 public class ArrayByteQueue  implements ObjectQueue<Byte>, Cloneable {
  31
  32   static final int DEFAULT_CAPACITY = 256;
  33
  34   int size = 0;
  35   int first;  // next index we will remove
  36   int last;   // last index we did add
  37
  38   byte[] buffer = null;
  39
  40   class FIFOIterator implements Iterator<Byte> {
  41     int next = first;
  42     int remaining = size;
  43
  44     @Override
  45         public boolean hasNext() {
  46       return (remaining > 0);
  47     }
  48
  49     @Override
  50         public Byte next() {
  51       if (remaining == 0){
  52         throw new NoSuchElementException();
  53       } else {
  54         Byte e = buffer[next];
  55         next = (next+1) % buffer.length;
  56         remaining--;
  57         return e;
  58       }
  59     }
  60
  61     @Override
  62         public void remove() { // its a queue
  63       throw new UnsupportedOperationException();
  64     }
  65   }
  66
  67   // just for debugging purposes
  68   class StorageIterator implements Iterator<Byte> {
  69     int next = 0;
  70
  71     @Override
  72         public boolean hasNext(){
  73       return (next < buffer.length);
  74     }
  75
  76     @Override
  77         public Byte next(){
  78       if (next == buffer.length){
  79         throw new NoSuchElementException();
  80       }
  81
  82       Byte e = buffer[next];
  83       next++;
  84       return e;
  85     }
  86
  87     @Override
  88         public void remove() { // its a queue
  89       throw new UnsupportedOperationException();
  90     }
  91   }
  92
  93   public ArrayByteQueue (){
  94     buffer = new byte[DEFAULT_CAPACITY];
  95   }
  96
  97   public ArrayByteQueue (int initialCapacity){
  98     buffer = new byte[initialCapacity];
  99   }
 100
 101   protected void grow(){
 102     byte[] newBuffer = new byte[buffer.length * 3 / 2];
 103
 104     if (first < last){
 105       System.arraycopy(buffer, first, newBuffer, 0, last - first +1);
 106     } else if (first > last){
 107       int nRight = buffer.length - first;
 108       System.arraycopy(buffer, first, newBuffer, 0, nRight);
 109       System.arraycopy(buffer, 0, newBuffer, nRight, last+1);
 110     } else { // just 1 element
 111       newBuffer[0] = buffer[first];
 112     }
 113
 114     first = 0;
 115     last = size-1;
 116     buffer = newBuffer;
 117   }
 118
 119   @Override
 120   public boolean isEmpty() {
 121     return (size == 0);
 122   }
 123
 124   public int getCurrentCapacity(){
 125     return buffer.length;
 126   }
 127
 128   @Override
 129   public int size() {
 130     return size;
 131   }
 132
 133   @Override
 134   public boolean offer (Byte e){
 135     return add(e);
 136   }
 137
 138   @Override
 139   public boolean add (Byte e){
 140     if (size == 0){  // first element
 141       first = last = 0;
 142       buffer[0] = e;
 143       size = 1;
 144
 145     } else {
 146       int i = (last + 1) % buffer.length;
 147       if (i == first) {
 148         grow();
 149         i = size;
 150       }
 151
 152       last = i;
 153       buffer[i] = e;
 154       size++;
 155     }
 156
 157     return true; // this is a dynamic queue, we never run out of space
 158   }
 159
 160   @Override
 161   public Byte poll (){
 162     if (size == 0){
 163       return null;
 164     } else {
 165       int i = first;
 166
 167       first = (first+1) % buffer.length;
 168       size--;
 169
 170       Byte e = buffer[i];
 171       //buffer[i] = null; // avoid memory leaks
 172       return e;
 173     }
 174   }
 175
 176   @Override
 177   public Byte remove () throws NoSuchElementException {
 178     if (size == 0){
 179       throw new NoSuchElementException();
 180     } else {
 181       return poll();
 182     }
 183   }
 184
 185   @Override
 186   public Byte peek () {
 187     if (size == 0){
 188       return null;
 189     } else {
 190       return buffer[first];
 191     }
 192   }
 193
 194   @Override
 195   public Iterator<Byte> iterator() {
 196     return new FIFOIterator();
 197   }
 198
 199   public Iterator<Byte> storageIterator(){
 200     return new StorageIterator();
 201   }
 202
 203
 204   @Override
 205   public void clear(){
 206     buffer = new byte[buffer.length]; // cheaper than iterating over the old one
 207     size = 0;
 208     first = last = -1;
 209   }
 210
 211   /**
 212    * call Processor.process(e) on each queued object
 213    *
 214    * This method does not return before the queue is empty, which makes it
 215    * suitable for graph traversal. It also avoids iterator objects, allows
 216    * adding new objects while processing the queue, and enables to keep
 217    * processing state in the processor
 218    */
 219   @Override
 220   public void process (Processor<Byte> processor){
 221     while (size > 0){
 222         Byte e = remove();
 223       processor.process(e);
 224     }
 225   }
 226
 227   @Override
 228   public Object clone() {
 229     try {
 230       ArrayByteQueue clone = (ArrayByteQueue)super.clone();
 231       clone.buffer = this.buffer.clone();
 232       return clone;
 233     } catch (CloneNotSupportedException cnx) {
 234       return null;
 235     }
 236   }
 237
 238   @Override
 239   public String toString() {
 240     Iterator<Byte> itr = iterator();
 241     String result = "[";
 242     while(itr.hasNext()) {
 243       if(result.length()>1) {
 244         result = result + ", ";
 245       }
 246       byte b = itr.next();
 247       result = result + b;
 248     }
 249     result = result + "]";
 250     return result;
 251   }
 252 }