--- projects/cms/source/util/uk/org/iscream/cms/util/Queue.java	2001/02/25 23:29:06	1.13
+++ projects/cms/source/util/uk/org/iscream/cms/util/Queue.java	2001/03/01 01:05:49	1.14
@@ -4,6 +4,7 @@ package uk.ac.ukc.iscream.util;
 //---IMPORTS---
 import java.util.LinkedList;
 import java.util.NoSuchElementException;
+import java.util.Random;
 import uk.ac.ukc.iscream.util.*;
 
 /**
@@ -13,7 +14,7 @@ import uk.ac.ukc.iscream.util.*;
  * actually contains some elements.
  *
  * @author  $Author: tdb $
- * @version $Id: Queue.java,v 1.13 2001/02/25 23:29:06 tdb Exp $
+ * @version $Id: Queue.java,v 1.14 2001/03/01 01:05:49 tdb Exp $
  */
 public class Queue {
 
@@ -22,11 +23,59 @@ public class Queue {
     /**
      * The current CVS revision of this class
      */
-    public static final String REVISION = "$Revision: 1.13 $";
+    public static final String REVISION = "$Revision: 1.14 $";
     
+    /**
+     * Pass to constructor to remove a RANDOM item from
+     * the Queue upon reaching the maximum limit.
+     */
+    public static final int RANDOM = 0;
+    
+    /**
+     * Pass to constructor to remove the FIRST item from
+     * the Queue upon reaching the maximum limit.
+     */
+    public static final int FIRST = 1;
+    
+    /**
+     * Pass to constructor to remove the LAST item from
+     * the Queue upon reaching the maximum limit.
+     */
+    public static final int LAST = 2;
+    
+    /**
+     * Pass to constructor to drop the new item upon reaching
+     * the maximum Queue limit.
+     */
+    public static final int DROP = 3;
+    
 //---STATIC METHODS---
 
 //---CONSTRUCTORS---  
+    
+    /**
+     * Constructs a new Queue with a maximum size limit on
+     * any individual queue. This should be used to stop
+     * conditions where the Queue cannot be guaranteed to
+     * be emptied as quick as it's filled.
+     *
+     * An algorithm will be used to remove data when new data
+     * arrives. There may be choices of algorithms later on.
+     *
+     * @param maxSize the upper limit for a queue
+     * @param removeAlgorithm the remove algorithm to use upon reaching the maxSize
+     */
+    public Queue(int maxSize, int removeAlgorithm) {
+        _maxSize = maxSize;
+        _removeAlgorithm = removeAlgorithm;
+    }
+    
+    /**
+     * Constructs a Queue with no maximum size.
+     */
+    public Queue() {
+        _maxSize = -1;
+    }
 
 //---PUBLIC METHODS---
     
@@ -40,11 +89,21 @@ public class Queue {
         for(int i=0; i < _lists.size(); i++) {
             // skip over any gaps left in the list
             if(_lists.get(i) != null) {
+                // get size before adding to the Queue
                 int s = ((LinkedList) _lists.get(i)).size();
-                synchronized(this) {
-                    // add() does the same thing, but this ensures behaviour
-                    ((LinkedList) _lists.get(i)).addLast(o);
+                // check whether we need to remove an item from the current Queue
+                if(_maxSize!=-1 && s==_maxSize && _removeAlgorithm!=DROP) {
+                    // we need to remove an item
+                    removeQueueItem((LinkedList) _lists.get(i));
                 }
+                // check if we should add (not if Queue full, and using DROP algorithm)
+                if(!(s==_maxSize && _removeAlgorithm==DROP)) {
+                    // add the next item, ensuring we lock
+                    synchronized(this) {
+                        // LinkedList.add() does the same thing, but this ensures behaviour
+                        ((LinkedList) _lists.get(i)).addLast(o);
+                    }
+                }
                 // if the queue was empty before the add it is possible
                 // that a consumer is waiting... so we notify them
                 if (s == 0) {
@@ -138,7 +197,11 @@ public class Queue {
                 status += "queue"+i+"=\"[deleted]\" ";
             }
         }
-        status += "total=\""+_count+"\"></queue>";
+        status += "total=\""+_count+"\"";
+        if(_maxSize != -1) {
+            status += " maxSize=\""+_maxSize+"\"";
+        }
+        status += "</queue>";
         return status;
     }
     
@@ -277,7 +340,38 @@ public class Queue {
     }
 
 //---PRIVATE METHODS---
-
+    
+    /**
+     * This method removes an item from a Queue, using a method
+     * requested at construction.
+     *
+     * @param list The LinkedList from which to remove an item.
+     */
+    private void removeQueueItem(LinkedList list) {
+        // look at our algorithm
+        // remove a random item from the list
+        if(_removeAlgorithm==RANDOM) {
+            // new Random, with a good seed
+            Random rand = new Random(System.currentTimeMillis());
+            int i = rand.nextInt(_maxSize);
+            synchronized(this) {
+                list.remove(i);
+            }
+        }
+        // remove the first item from the list
+        else if(_removeAlgorithm==FIRST) {
+            synchronized(this) {
+                list.removeFirst();
+            }
+        }
+        // remove the last item from the list
+        else if(_removeAlgorithm==LAST) {
+            synchronized(this) {
+                list.removeLast();
+            }
+        }
+    }
+    
 //---ACCESSOR/MUTATOR METHODS---
 
 //---ATTRIBUTES---
@@ -297,6 +391,17 @@ public class Queue {
      * A reference to our QueueMonitor, if we have one.
      */
     private QueueMonitor _queueMon = null;
+    
+    /**
+     * The maximum size of any Queue.
+     */
+    private int _maxSize = -1;
+    
+    /**
+     * The remove algorithm to use upon a Queue reaching
+     * it's maximum size.
+     */
+    private int _removeAlgorithm = -1;
     
     /**
      * This is the friendly identifier of the