lib/mlton/queue/linked-list.fun

   1 (* Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   2  *    Jagannathan, and Stephen Weeks.
   3  *
   4  * MLton is released under a BSD-style license.
   5  * See the file MLton-LICENSE for details.
   6  *)
   7 (*-------------------------------------------------------------------*)
   8 (*                          QueueLinkedList                          *)
   9 (*-------------------------------------------------------------------*)
  10
  11 functor QueueLinkedList(): QUEUE_EPHEMERAL_UNBOUNDED =
  12 struct
  13
  14 val {error, ...} = Error.errors("queue", "linked-list")
  15
  16 structure L = MutableList
  17
  18 datatype 'a t = T of {head: 'a L.t ref,
  19                       tail: 'a L.t ref}
  20
  21 fun empty() = T{head = ref(L.empty()), tail = ref(L.empty())}
  22
  23 fun isEmpty(T{head = ref l, ...}) = L.isEmpty l
  24
  25 fun enque(q as T{head, tail}, x) =
  26    let val cell = L.single x
  27    in (if isEmpty q then head := cell
  28        else L.setTail(!tail, cell) ;
  29        tail := cell)
  30    end
  31
  32 fun deque(q as T{head, tail}) =
  33    case L.destruct(!head) of
  34       NONE => error "deque"
  35     | SOME(x, _) => (if L.eq(!head, !tail)
  36                        then (head := L.empty() ; tail := L.empty())
  37                     else head := L.tail(!head) ;
  38                     x)
  39
  40 end