| 1 | (* Copyright (C) 1999-2005, 2008 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 | structure MutableQueue: |
| 9 | sig |
| 10 | type 'a t |
| 11 | |
| 12 | val new: unit -> 'a t |
| 13 | val enque: 'a t * 'a -> unit |
| 14 | val deque: 'a t -> 'a option |
| 15 | end = |
| 16 | struct |
| 17 | datatype 'a t = T of {front: 'a list ref, back: 'a list ref} |
| 18 | |
| 19 | fun new () = T {front = ref [], back = ref []} |
| 20 | |
| 21 | fun enque (T {back, ...}, x) = back := x :: !back |
| 22 | |
| 23 | fun deque (T {front, back}) = |
| 24 | case !front of |
| 25 | [] => (case !back of |
| 26 | [] => NONE |
| 27 | | l => let |
| 28 | val _ = back := [] |
| 29 | val l = rev l |
| 30 | in |
| 31 | case l of |
| 32 | [] => raise Fail "MutableQueue.deque" |
| 33 | | x :: l => (front := l; SOME x) |
| 34 | end) |
| 35 | | x :: l => (front := l; SOME x) |
| 36 | end |