1 #include "obt/unittest_base.h"
3 #include "obt/bsearch.h"
14 /* Search in an empty array. */
15 BSEARCH(int, array, 0, array_size, 10);
16 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
17 EXPECT_UINT_EQ(0, BSEARCH_AT());
19 /* Search in an empty array with a non-zero starting position. */
20 BSEARCH(int, array, 10, array_size, -10);
21 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
22 EXPECT_UINT_EQ(10, BSEARCH_AT());
27 static void single_element() {
34 /* Search for something smaller than the only element. */
36 BSEARCH(int, array, 0, array_size, -10);
37 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
38 EXPECT_UINT_EQ(0, BSEARCH_AT());
39 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
41 /* Search for something bigger than the only element. */
43 BSEARCH(int, array, 0, array_size, 30);
44 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
45 EXPECT_UINT_EQ(0, BSEARCH_AT());
46 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
48 /* Search for something smaller than the only element. */
50 BSEARCH(int, array, 0, array_size, -30);
51 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
52 EXPECT_UINT_EQ(0, BSEARCH_AT());
53 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
55 /* Search for something bigger than the only element. */
57 BSEARCH(int, array, 0, array_size, 10);
58 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
59 EXPECT_UINT_EQ(0, BSEARCH_AT());
60 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
62 /* Search for the only element that exists. */
64 BSEARCH(int, array, 0, array_size, -20);
65 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
66 EXPECT_UINT_EQ(0, BSEARCH_AT());
67 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
72 static void single_element_nonzero_start() {
77 guint array_start = 9;
80 /* Search for something smaller than the only element. */
81 array[array_start] = 20;
82 BSEARCH(int, array, array_start, array_size, -10);
83 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
84 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
85 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
87 /* Search for something bigger than the only element. */
88 array[array_start] = 20;
89 BSEARCH(int, array, array_start, array_size, 30);
90 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
91 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
92 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
94 /* Search for something smaller than the only element. */
95 array[array_start] = -20;
96 BSEARCH(int, array, array_start, array_size, -30);
97 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
98 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
99 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
101 /* Search for something bigger than the only element. */
102 array[array_start] = -20;
103 BSEARCH(int, array, array_start, array_size, 10);
104 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
105 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
106 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
108 /* Search for the only element that exists. */
109 array[array_start] = -20;
110 BSEARCH(int, array, array_start, array_size, -20);
111 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
112 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
113 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
118 static void present() {
123 guint array_start = 0;
124 guint array_size = 5;
132 /* Search for something that is in the array. */
134 BSEARCH(int, array, array_start, array_size, 10);
135 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
136 EXPECT_UINT_EQ(0, BSEARCH_AT());
137 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
139 BSEARCH(int, array, array_start, array_size, 12);
140 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
141 EXPECT_UINT_EQ(1, BSEARCH_AT());
142 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
144 BSEARCH(int, array, array_start, array_size, 14);
145 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
146 EXPECT_UINT_EQ(2, BSEARCH_AT());
147 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
149 BSEARCH(int, array, array_start, array_size, 16);
150 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
151 EXPECT_UINT_EQ(3, BSEARCH_AT());
152 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
154 BSEARCH(int, array, array_start, array_size, 18);
155 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
156 EXPECT_UINT_EQ(4, BSEARCH_AT());
157 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
162 static void present_nonzero_start() {
167 guint array_start = 2;
168 guint array_size = 3;
176 /* Search for something that is in the array. */
178 BSEARCH(int, array, array_start, array_size, 10);
179 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
180 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
181 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
183 BSEARCH(int, array, array_start, array_size, 12);
184 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
185 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
186 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
188 BSEARCH(int, array, array_start, array_size, 14);
189 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
190 EXPECT_UINT_EQ(2, BSEARCH_AT());
191 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
193 BSEARCH(int, array, array_start, array_size, 16);
194 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
195 EXPECT_UINT_EQ(3, BSEARCH_AT());
196 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
198 BSEARCH(int, array, array_start, array_size, 18);
199 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND());
200 EXPECT_UINT_EQ(4, BSEARCH_AT());
201 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
206 static void missing() {
211 guint array_start = 0;
212 guint array_size = 5;
220 /* Search for something that is _not_ in the array. */
222 BSEARCH(int, array, array_start, array_size, 9);
223 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
224 EXPECT_UINT_EQ(0, BSEARCH_AT());
225 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
227 BSEARCH(int, array, array_start, array_size, 11);
228 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
229 EXPECT_UINT_EQ(0, BSEARCH_AT());
230 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
232 BSEARCH(int, array, array_start, array_size, 13);
233 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
234 EXPECT_UINT_EQ(1, BSEARCH_AT());
235 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
237 BSEARCH(int, array, array_start, array_size, 15);
238 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
239 EXPECT_UINT_EQ(2, BSEARCH_AT());
240 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
242 BSEARCH(int, array, array_start, array_size, 17);
243 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
244 EXPECT_UINT_EQ(3, BSEARCH_AT());
245 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
247 BSEARCH(int, array, array_start, array_size, 19);
248 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
249 EXPECT_UINT_EQ(4, BSEARCH_AT());
250 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
255 static void missing_nonzero_start() {
260 guint array_start = 2;
261 guint array_size = 3;
269 /* Search for something that is _not_ in the array. */
271 BSEARCH(int, array, array_start, array_size, 9);
272 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
273 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
274 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
276 BSEARCH(int, array, array_start, array_size, 11);
277 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
278 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
279 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
281 BSEARCH(int, array, array_start, array_size, 13);
282 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
283 EXPECT_UINT_EQ(array_start, BSEARCH_AT());
284 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND_NEAREST_SMALLER());
286 BSEARCH(int, array, array_start, array_size, 15);
287 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
288 EXPECT_UINT_EQ(2, BSEARCH_AT());
289 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
291 BSEARCH(int, array, array_start, array_size, 17);
292 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
293 EXPECT_UINT_EQ(3, BSEARCH_AT());
294 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
296 BSEARCH(int, array, array_start, array_size, 19);
297 EXPECT_BOOL_EQ(FALSE, BSEARCH_FOUND());
298 EXPECT_UINT_EQ(4, BSEARCH_AT());
299 EXPECT_BOOL_EQ(TRUE, BSEARCH_FOUND_NEAREST_SMALLER());
304 void run_bsearch_unittest() {
305 unittest_start_suite("bsearch");
309 single_element_nonzero_start();
311 present_nonzero_start();
313 missing_nonzero_start();
315 unittest_end_suite();