//	Object queue
//
//	Author	Matthew Caryl
//
//  Although under copywrite to the author (Matthew Caryl) this code can be copied and modified for non-commercial
//  purposes as long as any derivatives contain this condition.



final public class Queue {
    int         number = 0;
    QueueItem   front = null;
    QueueItem   back = null;
    Random random = new Random();

    public Queue() {
        }

    public Queue(Queue q) {
    	try {
    		for (int i = q.size(); i > 0; i--)
    			enqueue(q.requeue());
    		}
    	catch (QueueEmpty e) {
    		}
    	}

    public void finalise() {
        clear();
        }

    public void enqueue(Object o) {
        if (empty()) {
            front = back = new QueueItem(o);
            number = 1;
            }
        else {
            back.next = new QueueItem(o);
            back = back.next;
            number++;
            }
        }

    public Object dequeue() throws QueueEmpty {
        QueueItem   i;

        if (empty())
            throw new QueueEmpty();
        i = front;
        front = front.next;
        i.next = null;
        if (back == i)
        	back = null;
        number--;
        return i.item;
        }

    // returns the item from the front of the queue
    public Object peekqueue() throws QueueEmpty {
        if (empty())
            throw new QueueEmpty();
        return front.item;
        }

    // dequeue then enqueue
    // returns the object which has been moved
    public Object requeue() throws QueueEmpty {
        if (empty())
            throw new QueueEmpty();
        back.next = front;
        back = front;
        front = front.next;
        back.next = null;
        return back.item;
        }

    // object to remove should be in queue
    public void remove(Object o) throws QueueItemAbsent {
        QueueItem   p0, p, q;

        p = front;
        p0 = null;
        q = null;
        while (p != q)
            if (p.item == o)
                q = p;
            else
                {p0 = p; p = p.next;};
        if (p == null)
            throw new QueueItemAbsent();
        if (p == front)
            front = front.next;
        if (p == back)
            back = p0;
        if (p0 != null)
            p0.next = p.next;
        number--;
        }

    public boolean membership(Object o) {
        QueueItem p, q;

        p = front;
        q = null;
        while (p != q)
            if (p.item == o)
                q = p;
            else
                p = p.next;
        return p != null;
        }

    public int size() {
        return number;
        }

    public boolean empty() {
        return number == 0;
        }

    private void clear() {
        try {
            while (!empty())
                dequeue();
            }
        catch (QueueEmpty e) {
            }
        }
    //this useful routine was added by Bill Harms    

    public Object[] getObjectList(){
        int newNumObjects = size();
        Object[] objectList = new Object[newNumObjects];
        try {
          synchronized (this) {
               for (int i = size(); i > 0; i--)
                 objectList[i-1] = requeue();
          }
        }
        catch (QueueEmpty e) {}
        return objectList;
    }
    
}

class QueueItem extends Object {
    Object      item = null;
    QueueItem   next = null;

    public QueueItem(Object o) {
        item = o;
        }
    }