Below is the file 'q.ml' from this revision. You can also download the file.

type 'a t = 'a list * 'a list

let norm f r =
  if f = []
  then List.rev r, []
  else f, r

let empty = [], []

let pop = function
  | ([], r) ->
      assert (r = []) ;
      None
  | (x :: f, r) ->
      Some (x, norm f r)

let push (f, r) x =
  norm f (x :: r)

let push_list q l =
  match q with
  | ([], r) ->
      assert (r = []) ;
      (l, [])
  | (f, r) ->
      (f, List.rev_append l r)

let concat (f1, r1) (f2, r2) =
  (List.append f1 (List.rev_append r1 f2), r2)

let to_list (f, r) =
  List.append f (List.rev r)

let of_list l =
  (l, [])

let list_fold g l =
  to_list (List.fold_left g empty l)