[hcoop/debian/mlton.git] / lib / mlton / basic / two-list-queue.sml

(* Copyright (C) 1999-2005 Henry Cejtin, Matthew Fluet, Suresh
 *    Jagannathan, and Stephen Weeks.
 *
 * MLton is released under a BSD-style license.
 * See the file MLton-LICENSE for details.
 *)

structure TwoListQueue:> QUEUE =
struct

datatype 'a t = T of 'a list * 'a list

fun foldAnyOrder (T (l, r), ac, f) =
   List.fold (r, List.fold (l, ac, f), f)

fun foldr (T (l, r), ac, f) =
   List.foldr (l, List.fold (r, ac, f), f)

fun toList q = foldr (q, [], op ::)

fun deque (T (l, r)) =
   let
      val (l, r) = (case l of
                       [] => (rev r, [])
                     | _ =>  (l, r))
   in
      case l of
         [] => NONE
       | x :: l => SOME (T (l, r), x)
   end

fun empty () = T ([], [])

val isEmpty =
   fn T ([], []) => true
    | _ => false

fun enque (T (l, r), x) = T (l, x :: r)

end

structure Queue = TwoListQueue
Commit	Line	Data
7f918cf1 CE	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	structure TwoListQueue:> QUEUE =
	9	struct
	10
	11	datatype 'a t = T of 'a list * 'a list
	12
	13	fun foldAnyOrder (T (l, r), ac, f) =
	14	List.fold (r, List.fold (l, ac, f), f)
	15
	16	fun foldr (T (l, r), ac, f) =
	17	List.foldr (l, List.fold (r, ac, f), f)
	18
	19	fun toList q = foldr (q, [], op ::)
	20
	21	fun deque (T (l, r)) =
	22	let
	23	val (l, r) = (case l of
	24	[] => (rev r, [])
	25	\| _ => (l, r))
	26	in
	27	case l of
	28	[] => NONE
	29	\| x :: l => SOME (T (l, r), x)
	30	end
	31
	32	fun empty () = T ([], [])
	33
	34	val isEmpty =
	35	fn T ([], []) => true
	36	\| _ => false
	37
	38	fun enque (T (l, r), x) = T (l, x :: r)
	39
	40	end
	41
	42	structure Queue = TwoListQueue