(*
 * priority_queue.sml - An extremely naive implementation of 
 *  a priority queue.
 *     Ronald Garcia
 * $Id: priority_queue.sml,v 1.2 2003/05/02 20:03:40 jewillco Exp $
 *)

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

use "concepts.sml";

(* This queue is mutable.  It depends on stored elements being unique *)

functor MakePQ(Cmp : StrictWeakOrderingSig) =
struct

  type value_t = Cmp.arg_t
  type queue_t = Cmp.data_t * value_t list ref
  type data_t = queue_t

  exception BadInsert

  fun check v [] = ()
    | check v (u::xs) =
      if u = v then
	  raise BadInsert
      else
	  check v xs

  fun insert v (cmp,queue) = (
      check v (!queue);
      queue := v::(!queue))

  fun create(cmp:Cmp.data_t):queue_t =
      (cmp,ref ([]))

  exception Empty

  fun remove (cmp,(ref [])) = raise Empty
    | remove ((cmp,queue as ref (u::qs)):queue_t) =
      let
	  fun loop [] v rest = (
	      queue := rest;
	      v)
	    | loop (nv::xs) v rest =
	      if not (Cmp.go cmp nv v) then
		  loop xs v (nv::rest)
	      else
		  loop xs nv (v::rest)
      in
	  loop qs u []
      end

(* match BufferSig signature *)
    fun push q v = insert v q
    fun pop  q = remove q
    fun empty (cmp,(ref [])) = true
      | empty x = false

end (* struct *)