1# -*- perl -*-
2
3use strict;
4use Set::IntSpan 1.17;
5
6my $N = 1;
7sub Not { print "not " }
8sub OK  { print "ok ", $N++, "\n" }
9
10my @tests =
11(
12 [ []   , 0, 0 ],
13
14 [ [ 1 ], 0, 0 ],
15 [ [ 1 ], 1, 0 ],
16 [ [ 1 ], 2, 1 ],
17
18 [ [ 1, 2 ], 0, 0 ],
19 [ [ 1, 2 ], 1, 0 ],
20 [ [ 1, 2 ], 2, 1 ],
21 [ [ 1, 2 ], 3, 2 ],
22
23 [ [ 1, 3 ], 0, 0 ],
24 [ [ 1, 3 ], 1, 0 ],
25 [ [ 1, 3 ], 2, 1 ],
26 [ [ 1, 3 ], 3, 1 ],
27 [ [ 1, 3 ], 4, 2 ],
28
29 [ [ 1, 3, 5 ], 0, 0 ],
30 [ [ 1, 3, 5 ], 1, 0 ],
31 [ [ 1, 3, 5 ], 2, 1 ],
32 [ [ 1, 3, 5 ], 3, 1 ],
33 [ [ 1, 3, 5 ], 4, 2 ],
34 [ [ 1, 3, 5 ], 5, 2 ],
35 [ [ 1, 3, 5 ], 6, 3 ],
36
37 [ [ 1, 3, 5, 7 ], 0, 0 ],
38 [ [ 1, 3, 5, 7 ], 1, 0 ],
39 [ [ 1, 3, 5, 7 ], 2, 1 ],
40 [ [ 1, 3, 5, 7 ], 3, 1 ],
41 [ [ 1, 3, 5, 7 ], 4, 2 ],
42 [ [ 1, 3, 5, 7 ], 5, 2 ],
43 [ [ 1, 3, 5, 7 ], 6, 3 ],
44 [ [ 1, 3, 5, 7 ], 7, 3 ],
45 [ [ 1, 3, 5, 7 ], 8, 4 ],
46
47 [ [ 1, 3, 5, 7, 9 ],  0, 0 ],
48 [ [ 1, 3, 5, 7, 9 ],  1, 0 ],
49 [ [ 1, 3, 5, 7, 9 ],  2, 1 ],
50 [ [ 1, 3, 5, 7, 9 ],  3, 1 ],
51 [ [ 1, 3, 5, 7, 9 ],  4, 2 ],
52 [ [ 1, 3, 5, 7, 9 ],  5, 2 ],
53 [ [ 1, 3, 5, 7, 9 ],  6, 3 ],
54 [ [ 1, 3, 5, 7, 9 ],  7, 3 ],
55 [ [ 1, 3, 5, 7, 9 ],  8, 4 ],
56 [ [ 1, 3, 5, 7, 9 ],  9, 4 ],
57 [ [ 1, 3, 5, 7, 9 ], 10, 5 ],
58
59 [ [ 1, 3, 5, 7, 9, 11 ],  0, 0 ],
60 [ [ 1, 3, 5, 7, 9, 11 ],  1, 0 ],
61 [ [ 1, 3, 5, 7, 9, 11 ],  2, 1 ],
62 [ [ 1, 3, 5, 7, 9, 11 ],  3, 1 ],
63 [ [ 1, 3, 5, 7, 9, 11 ],  4, 2 ],
64 [ [ 1, 3, 5, 7, 9, 11 ],  5, 2 ],
65 [ [ 1, 3, 5, 7, 9, 11 ],  6, 3 ],
66 [ [ 1, 3, 5, 7, 9, 11 ],  7, 3 ],
67 [ [ 1, 3, 5, 7, 9, 11 ],  8, 4 ],
68 [ [ 1, 3, 5, 7, 9, 11 ],  9, 4 ],
69 [ [ 1, 3, 5, 7, 9, 11 ], 10, 5 ],
70 [ [ 1, 3, 5, 7, 9, 11 ], 11, 5 ],
71 [ [ 1, 3, 5, 7, 9, 11 ], 12, 6 ],
72
73 [ [ 1, 3, 5, 7, 9, 11, 13 ],  0, 0 ],
74 [ [ 1, 3, 5, 7, 9, 11, 13 ],  1, 0 ],
75 [ [ 1, 3, 5, 7, 9, 11, 13 ],  2, 1 ],
76 [ [ 1, 3, 5, 7, 9, 11, 13 ],  3, 1 ],
77 [ [ 1, 3, 5, 7, 9, 11, 13 ],  4, 2 ],
78 [ [ 1, 3, 5, 7, 9, 11, 13 ],  5, 2 ],
79 [ [ 1, 3, 5, 7, 9, 11, 13 ],  6, 3 ],
80 [ [ 1, 3, 5, 7, 9, 11, 13 ],  7, 3 ],
81 [ [ 1, 3, 5, 7, 9, 11, 13 ],  8, 4 ],
82 [ [ 1, 3, 5, 7, 9, 11, 13 ],  9, 4 ],
83 [ [ 1, 3, 5, 7, 9, 11, 13 ], 10, 5 ],
84 [ [ 1, 3, 5, 7, 9, 11, 13 ], 11, 5 ],
85 [ [ 1, 3, 5, 7, 9, 11, 13 ], 12, 6 ],
86 [ [ 1, 3, 5, 7, 9, 11, 13 ], 13, 6 ],
87 [ [ 1, 3, 5, 7, 9, 11, 13 ], 14, 7 ],
88
89 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  0, 0 ],
90 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  1, 0 ],
91 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  2, 1 ],
92 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  3, 1 ],
93 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  4, 2 ],
94 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  5, 2 ],
95 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  6, 3 ],
96 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  7, 3 ],
97 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  8, 4 ],
98 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ],  9, 4 ],
99 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ], 10, 5 ],
100 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ], 11, 5 ],
101 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ], 12, 6 ],
102 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ], 13, 6 ],
103 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ], 14, 7 ],
104 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ], 15, 7 ],
105 [ [ 1, 3, 5, 7, 9, 11, 13, 15 ], 16, 8 ],
106
107 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  0, 0 ],
108 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  1, 0 ],
109 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  2, 1 ],
110 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  3, 1 ],
111 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  4, 2 ],
112 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  5, 2 ],
113 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  6, 3 ],
114 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  7, 3 ],
115 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  8, 4 ],
116 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ],  9, 4 ],
117 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 10, 5 ],
118 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 11, 5 ],
119 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 12, 6 ],
120 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 13, 6 ],
121 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 14, 7 ],
122 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 15, 7 ],
123 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 16, 8 ],
124 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 17, 8 ],
125 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17 ], 18, 9 ],
126
127 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  0,  0 ],
128 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  1,  0 ],
129 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  2,  1 ],
130 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  3,  1 ],
131 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  4,  2 ],
132 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  5,  2 ],
133 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  6,  3 ],
134 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  7,  3 ],
135 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  8,  4 ],
136 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ],  9,  4 ],
137 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 10,  5 ],
138 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 11,  5 ],
139 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 12,  6 ],
140 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 13,  6 ],
141 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 14,  7 ],
142 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 15,  7 ],
143 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 16,  8 ],
144 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 17,  8 ],
145 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 18,  9 ],
146 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 19,  9 ],
147 [ [ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 ], 20, 10 ],
148);
149
150
151print "1..", scalar @tests, "\n";
152
153for my $test (@tests)
154{
155    my($edges, $target, $expected) = @$test;
156    my $actual = Set::IntSpan::_bsearch($edges, $target);
157    $expected==$actual or Not; OK;
158}
159