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) {
74               if (!block) return null;
75               try {
76                   wait();
77               } catch (InterruptedException e) {
78               } catch (Exception e) {
79                   if (Log.on) Log.info(this, "exception in Queue.wait(); this should never happen");
80                   if (Log.on) Log.info(this, e);
81               }
82           }
83           
84           Object ret = vec[first];
85           first++;
86           size--;
87           if (first >= vec.length) first = 0;
88           return ret;
89       }
90   
91       /** Returns the top element in the queue without removing it */
92       public synchronized Object peek() {
93           if (size == 0) return null;
94           return vec[first];
95       }
96   
97   }
98