File: fqueue.ml

package info (click to toggle)
sks 1.1.6-14
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 2,296 kB
  • sloc: ml: 15,228; ansic: 1,069; sh: 358; makefile: 347
file content (124 lines) | stat: -rw-r--r-- 4,026 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
(***********************************************************************)
(* fqueue.ml - Simple implementation of a polymorphic functional queue *)
(*                                                                     *)
(* Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, *)
(*               2011, 2012, 2013  Yaron Minsky and Contributors       *)
(*                                                                     *)
(* This file is part of SKS.  SKS is free software; you can            *)
(* redistribute it and/or modify it under the terms of the GNU General *)
(* Public License as published by the Free Software Foundation; either *)
(* version 2 of the License, or (at your option) any later version.    *)
(*                                                                     *)
(* This program is distributed in the hope that it will be useful, but *)
(* WITHOUT ANY WARRANTY; without even the implied warranty of          *)
(* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU   *)
(* General Public License for more details.                            *)
(*                                                                     *)
(* You should have received a copy of the GNU General Public License   *)
(* along with this program; if not, write to the Free Software         *)
(* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 *)
(* USA or see <http://www.gnu.org/licenses/>.                          *)
(***********************************************************************)

open StdLabels
open MoreLabels
module Unix=UnixLabels


(** push and top are O(1).
   pop and take are O(1) amortized.
   to_list and length are O(n).
*)

(* Invariant:
   if queue is not empty, outlist is not empty
   queue.length = List.length(queue.outlist) + List.length(queue.inlist)*)

exception Empty

type 'a t = { inlist: 'a list;
              outlist: 'a list;
              length: int;
            }

(*****************************************)

(*
let test_invariants queue =
  assert
    begin
      queue.length = (List.length queue.outlist) + (List.length queue.inlist)
    end;
  assert
    begin
      (queue.length = 0) || List.length queue.outlist > 0
    end
*)

let empty = { inlist = [];
              outlist = [];
              length = 0;
            }

(*****************************************)

let push el queue =
  if queue.outlist = [] then
    let outlist = List.rev (el::queue.inlist)
    in { inlist = [];
         outlist = outlist;
         length = queue.length + 1;
       }
  else
    { inlist = el::queue.inlist;
      outlist = queue.outlist;
      length = queue.length + 1;
    }

let enq = push
(*****************************************)

let top queue =
  match queue.outlist with
      [] -> (if queue.inlist != []
             then failwith "FQueue.top: BUG. inlist should be empty but isn't"
             else raise Empty)
    | hd::tl -> hd

(*****************************************)

let pop queue = match queue.outlist with
    hd::[] -> (hd, { inlist = [];
                     outlist = (List.rev queue.inlist);
                     length = queue.length - 1})
  | hd::tl -> (hd, { inlist = queue.inlist;
                     outlist = tl;
                     length = queue.length - 1;})
  | [] ->
      if queue.inlist = []
      then raise Empty
      else (match List.rev queue.inlist with
                [] -> failwith "FQueue.top: BUG.  inlist should not be empty here"
              | hd::tl -> (hd, { inlist=[];
                                 outlist=tl;
                                 length = queue.length - 1;
                               }))

(*****************************************)

let discard queue =
  let (el,new_q) = pop queue in
    new_q

let deq = pop

(*****************************************)

let to_list queue =
  queue.inlist @ (List.rev (queue.outlist))

(*****************************************)

let length queue = queue.length

let is_empty queue = queue.length = 0