/*
 * Default Queue Implementation
 *
 * Developed for "Rethinking CS101", a project of Lynn Andrea Stein's AP Group.
 * For more information, see <a href="http://www.ai.mit.edu/projects/cs101/">the
 * CS101 homepage</a> or email <las@ai.mit.edu>.
 *
 * Copyright (C) 1998 Massachusetts Institute of Technology.
 * Please do not redistribute without obtaining permission.
 */

package cs101.util.queue;

import java.util.Enumeration;
import java.util.NoSuchElementException;

/** 
 * Default Queue class.  Allows insertion/deletion at either end.
 * Throws EmptyQueueException in some situations, but
 * EmptyQueueException is a subclass of RuntimeException, so you don't
 * have to protect Queue access with try/catch blocks.
 * <p> 
 * Copyright (c) 1998 Massachusetts Institute of Technology
 *
 * @author Todd C. Parnell, tparnell@ai.mit.edu
 * @version $Id: DefaultQueue.java,v 1.2 2003/09/23 14:46:57 gus Exp $
 *
 * @see cs101.util.queue.EmptyQueueException 
 */
public class DefaultQueue implements Queue {

  private Link first, last;
  private int count;

  /** Creates a new, empty Queue */
  public DefaultQueue () {}

  /** Creates a new Queue contining obj as the only element */
  public DefaultQueue (Object obj) {
    this.first = this.last = new Link (obj);
    this.count = 1;
  }

  /** Returns the number of elements in this. */
  public synchronized int size() { return this.count; }

  /** 
   * Gets the tail object from the queue </B>without</B> removing
   * it. 
   */
  public synchronized Object peek() {
    return this.peek(Queue.BACK);
  }

  /** 
   * Gets the object from the specified end of the queue
   * </B>without</B> removing it. 
   */
  public synchronized Object peek(int end) {
    if (this.isEmpty()) throw new EmptyQueueException();
    if (end == Queue.FRONT)
      return this.first.contents();
    else
      return this.last.contents();
  }

  /** Puts obj into the front the queue. */
  public synchronized void enqueue(Object obj) {
    this.enqueue(obj, Queue.FRONT);
  }

  /** Puts obj into the specified end of the queue. */
  public synchronized void enqueue(Object obj, int end) {
    if (this.isEmpty()) {
      this.first = this.last = new Link(obj);
    } else {
      if (end == Queue.FRONT) {
	Link tmp = new Link(obj);
	tmp.setNext(this.first);
	this.first.setPrevious(tmp);
	this.first = tmp;
      }
      else /* end == Queue.BACK */ {
	Link tmp = new Link(obj);
	tmp.setPrevious(this.last);
	this.last.setNext(tmp);
	this.last = tmp;
      }
    }
    this.count++;
  }

  /** Removes and returns the Object at the tail of the queue. */
  public synchronized Object dequeue() {
    return this.dequeue(Queue.BACK);
  }

  /** Removes and returns the Object at the specified end of the queue. */
  public synchronized Object dequeue(int end) {
    if (this.isEmpty()) throw new EmptyQueueException();
    this.count--;
    if (end == Queue.FRONT) {
      Object tmp = this.first.contents();
      Link l_tmp = this.first.next();
      this.first.setNext(null);    // remove reference
      this.first = l_tmp;
      if (this.first == null) {
	this.last = null;
      }
      else {
	// remove dangling reference for gc
	this.first.setPrevious(null);
      }
      return tmp;
    }
    else /* end == Queue.BACK */ {
      Object tmp = this.last.contents();
      Link l_tmp = this.last.previous();
      this.last.setPrevious(null);
      this.last = l_tmp;
      if (this.last == null) {
	this.first = null;
      }
      else {
	this.last.setNext(null);
      }
      return tmp;
    }
  }

  /** Tests whether the queue is empty. */
  public synchronized boolean isEmpty () {
    return (this.first == null);
  }

  /** 
   * Returns an Enumeration of the Objects in the queue.<p> 
   *
   * <I>Note: Do not modify the queue while enumerating--unpredictable
   * behavior may result.</I>
   *
   * @see java.util.Enumeration
   */
  public Enumeration elements() { 
    return new QueueEnumeration(this.first); 
  }

  public synchronized String toString() {
    StringBuffer sb = new StringBuffer("cs101.util.Queue: [");
    Enumeration enum = this.elements();
    while (enum.hasMoreElements()) {
      sb.append(enum.nextElement());
      if (enum.hasMoreElements()) sb.append(", ");
    }
    sb.append("]");
    return sb.toString();
  }
      
  /** Inner class to make Queue.elements() happen. */
  private class QueueEnumeration implements Enumeration {
    private Link current;
    
    public QueueEnumeration(Link l) {
      current = l;
    }

    public boolean hasMoreElements() {
      return (current != null);
    }

    public Object nextElement() {
      if (current == null) throw new NoSuchElementException();
      Object tmp = current.contents();
      current = current.next();
      return tmp;
    }
  } // class QueueEnumeration
  

  /** 
   * Links form the building blocks for Queues. 
   *
   * @see Queue
   */
  class Link {

    private Link previous = null;
    private Link next = null;
    private Object contents;

    protected Link(Object obj) {
      this.contents = obj;
    }

    public Object contents() {
      return this.contents;
    }

    public Link next() {
      return this.next;
    }
    
    public Link previous() {
      return this.previous;
    }

    protected synchronized void setPrevious(Link link) {
      this.previous = link;
    }

    protected synchronized void setNext(Link link) {
      this.next = link;
    }

    public synchronized String toString() {
      StringBuffer sb = new StringBuffer("cs101.util.Link: [previous:");
      if (this.previous != null)
	sb.append("linked");
      else sb.append("null");
      sb.append("] [contents:" + this.contents + "] [next:");
      if (this.next != null)
	sb.append("linked]");
      else sb.append("null]");
      return sb.toString();
    }
  } // class Link
}

/*
 * $Log: DefaultQueue.java,v $
 * Revision 1.2  2003/09/23 14:46:57  gus
 * javadoc fix
 *
 * Revision 1.1.1.1  2002/06/05 21:56:32  root
 * CS101 comes to Olin finally.
 *
 * Revision 1.1  2000/04/24 22:17:18  nathanw
 * Bulk reorganization
 *
 * Revision 1.3  1999/07/27 18:59:33  jsmthng
 * Changed *all* instances of 'peak' to 'peek' this time. Really. (I
 * hope.)
 *
 * Revision 1.2  1999/07/27 18:51:12  jsmthng
 * Instances of 'peak' changed to the new spelling, 'peek', in compliance
 * with the new version of cs101.util.Queue.
 *
 * Revision 1.1  1999/01/21 20:49:18  tparnell
 * Made Queue.java an interface and added DefaultQueue.java as an implementation.
 *
 */