//	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.

package ADT;

final public class Queue {
    int         number = 0;
    QueueItem   front = null;
    QueueItem   back = null;

    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) {
            }
        }
    }

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

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