Add include of cairo.h when using librsvg
[dana/openbox.git] / obt / bsearch_unittest.c
1 #include "obt/unittest_base.h"
2
3 #include "obt/bsearch.h"
4
5 #include <glib.h>
6
7 static void empty() {
8     TEST_START();
9
10     BSEARCH_SETUP();
11     int* array = NULL;
12     guint array_size = 0;
13
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());
18
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());
23
24     TEST_END();
25 }
26
27 static void single_element() {
28     TEST_START();
29
30     BSEARCH_SETUP();
31     int array[1];
32     guint array_size = 1;
33
34     /* Search for something smaller than the only element. */
35     array[0] = 20;
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());
40
41     /* Search for something bigger than the only element. */
42     array[0] = 20;
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());
47
48     /* Search for something smaller than the only element. */
49     array[0] = -20;
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());
54
55     /* Search for something bigger than the only element. */
56     array[0] = -20;
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());
61
62     /* Search for the only element that exists. */
63     array[0] = -20;
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());
68
69     TEST_END();
70 }
71
72 static void single_element_nonzero_start() {
73     TEST_START();
74
75     BSEARCH_SETUP();
76     int array[10];
77     guint array_start = 9;
78     guint array_size = 1;
79
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());
86
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());
93
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());
100
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());
107
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());
114
115     TEST_END();
116 }
117
118 static void present() {
119     TEST_START();
120
121     BSEARCH_SETUP();
122     int array[5];
123     guint array_start = 0;
124     guint array_size = 5;
125
126     array[0] = 10;
127     array[1] = 12;
128     array[2] = 14;
129     array[3] = 16;
130     array[4] = 18;
131
132     /* Search for something that is in the array. */
133
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());
138
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());
143
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());
148
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());
153
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());
158
159     TEST_END();
160 }
161
162 static void present_nonzero_start() {
163     TEST_START();
164
165     BSEARCH_SETUP();
166     int array[5];
167     guint array_start = 2;
168     guint array_size = 3;
169
170     array[0] = 10;
171     array[1] = 12;
172     array[2] = 14;
173     array[3] = 16;
174     array[4] = 18;
175
176     /* Search for something that is in the array. */
177
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());
182
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());
187
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());
192
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());
197
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());
202
203     TEST_END();
204 }
205
206 static void missing() {
207     TEST_START();
208
209     BSEARCH_SETUP();
210     int array[5];
211     guint array_start = 0;
212     guint array_size = 5;
213
214     array[0] = 10;
215     array[1] = 12;
216     array[2] = 14;
217     array[3] = 16;
218     array[4] = 18;
219
220     /* Search for something that is _not_ in the array. */
221
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());
226
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());
231
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());
236
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());
241
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());
246
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());
251
252     TEST_END();
253 }
254
255 static void missing_nonzero_start() {
256     TEST_START();
257
258     BSEARCH_SETUP();
259     int array[5];
260     guint array_start = 2;
261     guint array_size = 3;
262
263     array[0] = 10;
264     array[1] = 12;
265     array[2] = 14;
266     array[3] = 16;
267     array[4] = 18;
268
269     /* Search for something that is _not_ in the array. */
270
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());
275
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());
280
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());
285
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());
290
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());
295
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());
300
301     TEST_END();
302 }
303
304 void run_bsearch_unittest() {
305     unittest_start_suite("bsearch");
306
307     empty();
308     single_element();
309     single_element_nonzero_start();
310     present();
311     present_nonzero_start();
312     missing();
313     missing_nonzero_start();
314
315     unittest_end_suite();
316 }