Commit | Line | Data |
---|---|---|
7f918cf1 CE |
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 |