jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
23 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <AK/TestSuite.h>
28
29#include <AK/BinarySearch.h>
30
31TEST_CASE(vector_ints)
32{
33 Vector<int> ints;
34 ints.append(1);
35 ints.append(2);
36 ints.append(3);
37
38 auto test1 = *binary_search(ints.data(), ints.size(), 1, AK::integral_compare<int>);
39 auto test2 = *binary_search(ints.data(), ints.size(), 2, AK::integral_compare<int>);
40 auto test3 = *binary_search(ints.data(), ints.size(), 3, AK::integral_compare<int>);
41 EXPECT_EQ(test1, 1);
42 EXPECT_EQ(test2, 2);
43 EXPECT_EQ(test3, 3);
44}
45
46TEST_CASE(array_doubles)
47{
48 double doubles[] = { 1.1, 9.9, 33.33 };
49
50 auto test1 = *binary_search(doubles, 3, 1.1, AK::integral_compare<double>);
51 auto test2 = *binary_search(doubles, 3, 9.9, AK::integral_compare<double>);
52 auto test3 = *binary_search(doubles, 3, 33.33, AK::integral_compare<double>);
53 EXPECT_EQ(test1, 1.1);
54 EXPECT_EQ(test2, 9.9);
55 EXPECT_EQ(test3, 33.33);
56}
57
58TEST_CASE(vector_strings)
59{
60 Vector<String> strings;
61 strings.append("bat");
62 strings.append("cat");
63 strings.append("dog");
64
65 auto string_compare = [](const String& a, const String& b) -> int {
66 return strcmp(a.characters(), b.characters());
67 };
68 auto test1 = *binary_search(strings.data(), strings.size(), String("bat"), string_compare);
69 auto test2 = *binary_search(strings.data(), strings.size(), String("cat"), string_compare);
70 auto test3 = *binary_search(strings.data(), strings.size(), String("dog"), string_compare);
71 EXPECT_EQ(test1, String("bat"));
72 EXPECT_EQ(test2, String("cat"));
73 EXPECT_EQ(test3, String("dog"));
74}
75
76TEST_CASE(single_element)
77{
78 Vector<int> ints;
79 ints.append(1);
80
81 auto test1 = *binary_search(ints.data(), ints.size(), 1, AK::integral_compare<int>);
82 EXPECT_EQ(test1, 1);
83}
84
85TEST_CASE(not_found)
86{
87 Vector<int> ints;
88 ints.append(1);
89 ints.append(2);
90 ints.append(3);
91
92 auto test1 = binary_search(ints.data(), ints.size(), -1, AK::integral_compare<int>);
93 auto test2 = binary_search(ints.data(), ints.size(), 0, AK::integral_compare<int>);
94 auto test3 = binary_search(ints.data(), ints.size(), 4, AK::integral_compare<int>);
95 EXPECT_EQ(test1, nullptr);
96 EXPECT_EQ(test2, nullptr);
97 EXPECT_EQ(test3, nullptr);
98}
99
100TEST_CASE(no_elements)
101{
102 Vector<int> ints;
103
104 auto test1 = binary_search(ints.data(), ints.size(), 1, AK::integral_compare<int>);
105 EXPECT_EQ(test1, nullptr);
106}
107
108TEST_MAIN(BinarySearch)