src/org/xwt/util/Queue.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.util;
   3
   4 /** A simple synchronized queue, implemented as an array */
   5 public class Queue {
   6
   7     public Queue(int initiallength) { vec = new Object[initiallength]; }
   8
   9     /** The store */
  10     private Object[] vec;
  11
  12     /** The index of the first node in the queue */
  13     private int first = 0;
  14
  15     /** The number of elements in the queue; INVARAINT: size <= vec.length */
  16     private int size = 0;
  17
  18     /** Grow the queue, if needed */
  19     private void grow(int newlength) {
  20         Object[] newvec = new Object[newlength];
  21         if (first + size > vec.length) {
  22             System.arraycopy(vec, first, newvec, 0, vec.length - first);
  23             System.arraycopy(vec, 0, newvec, vec.length - first, size - (vec.length - first));
  24         } else {
  25             System.arraycopy(vec, first, newvec, 0, size);
  26         }
  27         first = 0;
  28         vec = newvec;
  29     }
  30
  31     /** The number of elements in the queue */
  32     public int size() { return size; }
  33
  34     /** Empties the queue */
  35     public synchronized void flush() {
  36         first = 0;
  37         size = 0;
  38         for(int i=0; i<vec.length; i++) vec[i] = null;
  39     }
  40
  41     /** Add an element to the front of the queue */
  42     public synchronized void prepend(Object o) {
  43         if (size == vec.length) grow(vec.length * 2);
  44         first--;
  45         if (first < 0) first += vec.length;
  46         vec[first] = o;
  47         size++;
  48         if (size == 1) notify();
  49     }
  50
  51     /** Add an element to the back of the queue */
  52     public synchronized void append(Object o) {
  53         if (size == vec.length) grow(vec.length * 2);
  54         if (first + size >= vec.length) vec[first + size - vec.length] = o;
  55         else vec[first + size] = o;
  56         size++;
  57         if (size == 1) notify();
  58     }
  59
  60     /** Remove and return and element from the queue, blocking if empty. */
  61     public Object remove() { return remove(true); }
  62
  63     /** Remove and return an element from the queue, blocking if
  64         <tt>block</tt> is true and the queue is empty. */
  65     public synchronized Object remove(boolean block) {
  66
  67         while (size == 0) {
  68             if (!block) return null;
  69             try {
  70                 wait();
  71             } catch (InterruptedException e) {
  72             } catch (Exception e) {
  73                 if (Log.on) Log.log(this, "exception in Queue.wait(); this should never happen");
  74                 if (Log.on) Log.log(this, e);
  75             }
  76         }
  77
  78         Object ret = vec[first];
  79         first++;
  80         size--;
  81         if (first >= vec.length) first = 0;
  82         return ret;
  83     }
  84
  85     /** Returns the top element in the queue without removing it */
  86     public synchronized Object peek() {
  87         if (size == 0) return null;
  88         return vec[first];
  89     }
  90
  91 }