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

class LINKLIST_MUT_QUEUE[VERTEX,
                           COMPARE->STRICT_WEAK_ORDERING[VERTEX]]

inherit MUTABLE_QUEUE[VERTEX]
      redefine out
         end
         
create make

feature --{NONE}
   q: LINKED_LIST[VERTEX]
   comp: COMPARE
feature

   out : STRING is
      do
         Result := "Mutable queue [ "
         from q.start until q.off
         loop
            Result := Result + q.item.out + " "
            q.forth
         end
         Result := Result + "]"
      end
   
   make (c: COMPARE) is
      do
         create q.make
         comp := c
      end
   
   push(v: VERTEX) is
      local
         break : BOOLEAN
      do
         from q.start; break := false
         until q.off or break
         loop
            if comp.less(v, q.item) then
               q.put_left(v)
               break := true
            end
            q.forth
         end
         if not break then
            q.extend(v)
         end
      end

   update(v: VERTEX) is
      do
         q.start
         q.search(v)
         q.remove
         push(v)
      end

feature
   
   item : VERTEX is
      require else not empty
      do
         Result := q.first
      end

   pop is
      require else not empty
      do
         q.start
         q.remove
      end
   
   empty : BOOLEAN is
      do
         Result := q.is_empty
      end
end -- LINKLIST_MUT_QUEUE