src/org/xwt/util/Queue.java

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