File: fqueue.ml

package info (click to toggle)
planets 0.1.13-19
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 512 kB
  • sloc: ml: 4,541; makefile: 207; ansic: 38
file content (95 lines) | stat: -rw-r--r-- 2,219 bytes parent folder | download | duplicates (9)
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
(* Simple implementation of a polymorphic functional queue *)

(* 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 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 remove queue = 
  let (el,new_q) = pop queue in
    new_q
      
(*****************************************)

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

(*****************************************)    
  
let length queue = queue.length