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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
(******************************************************************************
* Core *
* *
* Copyright (C) 2008- Jane Street Holding, LLC *
* Contact: opensource@janestreet.com *
* WWW: http://www.janestreet.com/ocaml *
* *
* *
* This library is free software; you can redistribute it and/or *
* modify it under the terms of the GNU Lesser General Public *
* License as published by the Free Software Foundation; either *
* version 2 of the License, or (at your option) any later version. *
* *
* This library 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 *
* Lesser General Public License for more details. *
* *
* You should have received a copy of the GNU Lesser General Public *
* License along with this library; if not, write to the Free Software *
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
* *
******************************************************************************)
open OUnit;;
open Core.Std
let test =
"hash_queue" >:::
[
"basic" >:: (fun () ->
let module Hq_arg = struct
include String
let hash (x : t) = Hashtbl.hash x
let equal (x : t) (y : t) = x = y
let sexp_of_t = Sexplib.Conv.sexp_of_string
let t_of_sexp = Sexplib.Conv.string_of_sexp
end in
let module Hq = Hash_queue.Make (Hq_arg) in
let hq = Hq.create () in
let inv () = Hq.invariant hq in
(* tests over empty queue *)
inv ();
assert (Hq.is_empty hq);
assert (Hq.dequeue hq = None);
assert (try ignore (Hq.dequeue_exn hq); false with _ -> true);
assert (Hq.dequeue_with_key hq = None);
assert (try ignore (Hq.dequeue_with_key_exn hq); false with _ -> true);
Hq.dequeue_all hq ~f:(fun _ -> assert false);
assert (Hq.remove hq "foobar" = `No_such_key);
assert (try ignore (Hq.remove_exn hq "foobar"); false with | _ -> true);
assert (Hq.replace hq "foobar" 0 = `No_such_key);
assert (try ignore (Hq.replace_exn hq "foobar" 0); false with
| _ -> true);
assert
([] = Hq.foldi hq ~init:[] ~f:(fun ac ~key:_ ~data:_ -> () :: ac));
assert ([] = Hq.fold hq ~init:[] ~f:(fun ac _ -> () :: ac));
Hq.iteri hq ~f:(fun ~key:_ ~data:_ -> assert false);
(* test with 10 elems *)
let n = 10 in
for i = 1 to n do
assert (Hq.enqueue hq (string_of_int i) i = `Ok);
inv ();
done;
assert (Hq.length hq = n);
assert
(List.rev
(Hq.foldi hq ~init:[] ~f:(fun ac ~key ~data -> (key, data) :: ac))
= List.init n ~f:(fun i -> let i = i + 1 in (string_of_int i, i)));
assert
(List.rev (Hq.fold hq ~init:[] ~f:(fun ac data -> data :: ac))
= List.init n ~f:(fun i -> i + 1));
Hq.iteri hq ~f:(fun ~key ~data -> assert (key = string_of_int data));
(* test removing the first element from the queue *)
let sum = ref 0 in
Hq.iter hq ~f:(fun x -> sum := !sum + x);
assert (!sum = (n * (n + 1) / 2));
assert (Hq.mem hq "1");
ignore (Hq.dequeue hq);
inv ();
assert (not (Hq.mem hq "1"));
assert (Hq.length hq = n - 1);
(* remove the last *)
assert (Hq.remove hq (string_of_int n) = `Ok);
(* double remove *)
assert (Hq.remove hq (string_of_int n) = `No_such_key);
inv ();
assert (Hq.length hq = n - 2);
(* remove everything *)
let num = ref 0 in
Hq.dequeue_all hq ~f:(fun _ -> num := !num + 1);
inv ();
assert (!num = n - 2);
assert (Hq.is_empty hq);
inv ();
Hq.clear hq;
assert (Hq.is_empty hq);
(* add 100 *)
for i = 1 to 100 do
assert (Hq.enqueue hq (string_of_int i) i = `Ok);
done;
(* double booking *)
assert (Hq.enqueue hq "42" 42 = `Key_already_present);
assert (try
Hq.enqueue_exn hq "42" 42; false
with
| _ -> true);
assert (Hq.replace hq "1" 42 = `Ok);
assert (Hq.lookup hq "1" = Some 42);
assert (Hq.lookup_exn hq "1" = 42);
assert (Hq.dequeue_with_key hq = Some ("1", 42));
assert (Hq.replace hq "1" 42 = `No_such_key);
assert (try
Hq.replace_exn hq "1" 42; false
with
| _ -> true);
assert (Hq.lookup hq "1" = None);
assert (try ignore (Hq.lookup_exn hq "1"); false with
| Not_found -> true | _ -> false);
Hq.clear hq;
assert (Hq.is_empty hq);
let add i = Hq.enqueue_exn hq (Int.to_string i) i in
List.iter [1; 2; 3] ~f:add;
assert (["1"; "2"; "3" ] = Hq.keys hq);
begin
try Hq.iter hq ~f:(fun _ -> add 13); assert false
with _ -> ();
end;
begin
try Hq.iter hq ~f:(fun _ -> ignore (Hq.remove hq "foo")); assert false
with _ -> ();
end;
)
]
|
