2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
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
10 * http://www.apache.org/licenses/LICENSE-2.0.
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.
19 package gov.nasa.jpf.util;
21 import java.util.Iterator;
22 import java.util.NoSuchElementException;
25 * dynamically growing, cyclic array buffer queue for object references
27 public class ArrayObjectQueue<E> implements ObjectQueue<E> {
29 static final int DEFAULT_CAPACITY = 256;
32 int first; // next index we will remove
33 int last; // last index we did add
35 Object[] buffer = null;
37 class FIFOIterator implements Iterator<E> {
42 public boolean hasNext() {
43 return (remaining > 0);
49 throw new NoSuchElementException();
51 E e = (E) buffer[next];
52 next = (next+1) % buffer.length;
59 public void remove() { // its a queue
60 throw new UnsupportedOperationException();
64 // just for debugging purposes
65 class StorageIterator implements Iterator<E> {
69 public boolean hasNext(){
70 return (next < buffer.length);
75 if (next == buffer.length){
76 throw new NoSuchElementException();
79 E e = (E) buffer[next];
85 public void remove() { // its a queue
86 throw new UnsupportedOperationException();
90 public ArrayObjectQueue (){
91 buffer = new Object[DEFAULT_CAPACITY];
94 public ArrayObjectQueue (int initialCapacity){
95 buffer = new Object[initialCapacity];
98 protected void grow(){
99 Object[] newBuffer = new Object[buffer.length * 3 / 2];
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];
117 public boolean isEmpty() {
121 public int getCurrentCapacity(){
122 return buffer.length;
131 public boolean offer (E e){
136 public boolean add (E e){
137 if (size == 0){ // first element
143 int i = (last + 1) % buffer.length;
154 return true; // this is a dynamic queue, we never run out of space
165 first = (first+1) % buffer.length;
169 buffer[i] = null; // avoid memory leaks
176 public E remove () throws NoSuchElementException {
178 throw new NoSuchElementException();
189 return (E)buffer[first];
194 public Iterator<E> iterator() {
195 return new FIFOIterator();
198 public Iterator<E> storageIterator(){
199 return new StorageIterator();
205 buffer = new Object[buffer.length]; // cheaper than iterating over the old one
211 * call Processor.process(e) on each queued object
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
219 public void process (Processor<E> processor){
222 processor.process(e);