-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

--DOC Queues are implemented as special interfaces to mutable lists.

-- since we can add at either end efficiently, but can only remove efficiently
-- from the front, we use add_last to implement enqueue and remove_first to
-- implement dequeue

template object queue[T];
private extend queue[`T] isa m_list[T];

  method collection_name(t@:queue[`T]):string { "queue" }

  method enqueue(t@:queue[`T], x:T):void { t.add_last(x) }

  method dequeue(t@:queue[`T]):T {
      dequeue(t, { error("dequeuing from an empty queue") }) }
  method dequeue(t@:queue[`T], if_empty:&():T):T { t.remove_first(if_empty) }

  method copy(q@:queue[`T]):queue[T] {
      let new:queue[T] := new_queue[T]();
      q.do(&(x:T){
	  new.add_last(x);
      });
      new }

  method new_queue[T]():queue[T] { concrete object isa queue[T] }