lib/mlton/queue/singly-linked.fun

   1 (* Copyright (C) 1999-2005 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 (*                           SinglyLinked                            *)
   9 (*-------------------------------------------------------------------*)
  10
  11 functor SinglyLinkedQueue(): UNBOUNDED_EPHEMERAL_QUEUE =
  12 struct
  13
  14 structure P = Pointer
  15 structure E = SimpleSinglyLinkedElement
  16
  17 datatype 'a t = T of {head: 'a E.t P.t,
  18                       tail: 'a E.t P.t}
  19
  20 fun empty() = T{head = P.null(), tail = P.null()}
  21
  22 fun isEmpty(T{head, ...}) = P.isNull head
  23
  24 fun enque(q as T{head, tail}, x) =
  25    let val e = E.new x
  26    in if isEmpty q then P.:=(head, e) else E.setNext(P.! tail, e) ;
  27       P.:=(tail, e)
  28    end
  29
  30 fun deque(T{head, tail}) =
  31    let val (v, p) = E.destruct(P.! head)
  32    in P.copy(head, p) ;
  33       if P.isNull p then P.clear tail else () ;
  34       v
  35    end
  36
  37 end
  38
  39 structure SinglyLinkedQueue = SinglyLinkedQueue()