HCoop / hcoop / debian / mlton.git / blame
| Commit | Line | Data |
|---|---|---|
| 7f918cf1 CE |
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 | (* EarlyQueue *) | |
| 9 | (*-------------------------------------------------------------------*) | |
| 10 | ||
| 11 | (* Error. on Okasaki93, Okasaki96 *) | |
| 12 | ||
| 13 | (* reverses tail before it is needed *) | |
| 14 | ||
| 15 | functor EarlyQueue(AR: APPEND_REVERSE): BASIC_PERSISTENT_QUEUE = | |
| 16 | struct | |
| 17 | ||
| 18 | structure L = AR.L | |
| 19 | open L.I | |
| 20 | ||
| 21 | datatype 'a t = T of 'a AR.t * 'a L.t | |
| 22 | ||
| 23 | fun queue(l, r) = | |
| 24 | if AR.length l >= L.length r then T(l, r) | |
| 25 | else T(AR.appendReverse(l, r), L.empty()) | |
| 26 | ||
| 27 | fun empty() = T(AR.empty(), L.empty()) | |
| 28 | ||
| 29 | fun isEmpty(T(l, _)) = AR.isEmpty l | |
| 30 | ||
| 31 | fun destruct(T(l, r)) = | |
| 32 | case AR.destruct l of | |
| 33 | NONE => NONE | |
| 34 | | SOME(x, l) => SOME(x, queue(l, r)) | |
| 35 | ||
| 36 | fun enque(T(l, r), x) = queue(l, L.cons(x, r)) | |
| 37 | ||
| 38 | end |