// Copyright 2003, Trustees of Indiana University
// Please see the license in the file ../LICENSE

using GCollections;

public class queue<T>: Buffer<T> {
  private LinkedList<T> data;

  public queue() {
    data = new LinkedList<T>();
  }

  public void push(T v) {
    data.AddLast(v);
  }

  public T pop() {
    return data.RemoveFirst();
  }

  public bool empty() {
    return data.Count == 0;
  }
}

public class mutable_queue<
	      Vertex,
	      Compare>
    : MutableQueue<Vertex>
  where Compare: StrictWeakOrdering<Vertex> {

  private ArrayList<Vertex> vertices_;
  private Compare compare_;

  public void push(Vertex v) {
    vertices_.AddLast(v);
  }

  public Vertex pop() {
    // if (empty()) throw new 
    Vertex best = vertices_[0];
    int best_idx = 0;
    for (int i = 1; i < vertices_.Count; ++i)
      if (compare_.less(vertices_[i], best)) {
	best = vertices_[i];
	best_idx = i;
      }
    vertices_.Remove(best_idx);
    return best;
  }

  public bool empty() {
    return vertices_.Count == 0;
  }

  public void update(Vertex v) {}

  public mutable_queue(Compare compare) {
    compare_ = compare;
    vertices_ = new ArrayList<Vertex>();
  }
}