bag_fifo.mz

(* Data type definitions. *)

data mutable cell a =
  Cell { value_: a; next: dynamic }

data mutable bag a =
  Empty { head: (); tail: () }
| NonEmpty { head: dynamic; tail: dynamic }
adopts cell a

(* The real functions. *)

val create [a] (): bag a =
  Empty { head = (); tail = () }

val insert [a] (consumes x: a, b: bag a): () =
  let c = Cell {
    value_ = x; next = ()
  } in
  c.next <- c;
  give c to b;
  match b with
  | Empty ->
      tag of b <- NonEmpty;
      b.head <- c;
      b.tail <- c
  | NonEmpty { tail } ->
      take tail from b;
      tail.next <- c;
      give tail to b;
      b.tail <- c
  end

val retrieve [a] (b: bag a): option a =
  match b with
  | Empty ->
      none
  | NonEmpty { head; tail } ->
      take head from b;
      if head == tail then begin
        tag of b <- Empty;
        b.head <- ();
        b.tail <- ()
      end else begin
        b.head <- head.next
      end;
      let x = head.value_ in
      some x
  end