jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/BinarySearch.h>
10#include <AK/Span.h>
11#include <AK/Vector.h>
12#include <cstring>
13#include <new>
14
15TEST_CASE(vector_ints)
16{
17 Vector<int> ints;
18 ints.append(1);
19 ints.append(2);
20 ints.append(3);
21
22 auto test1 = *binary_search(ints, 1);
23 auto test2 = *binary_search(ints, 2);
24 auto test3 = *binary_search(ints, 3);
25 EXPECT_EQ(test1, 1);
26 EXPECT_EQ(test2, 2);
27 EXPECT_EQ(test3, 3);
28}
29
30TEST_CASE(span_rvalue_reference)
31{
32 Array<long, 3> array { 1, 2, 3 };
33
34 size_t nearby_index = 0;
35 auto* pointer = binary_search(array.span(), 2, &nearby_index);
36
37 EXPECT_EQ(nearby_index, 1u);
38 EXPECT_EQ(pointer, &array[1]);
39}
40
41TEST_CASE(array_doubles)
42{
43 Array<double, 3> array { 1.1, 9.9, 33.33 };
44
45 EXPECT_EQ(binary_search(array, 1.1), &array[0]);
46 EXPECT_EQ(binary_search(array, 33.33), &array[2]);
47 EXPECT_EQ(binary_search(array, 9.9), &array[1]);
48}
49
50TEST_CASE(vector_strings)
51{
52 Vector<DeprecatedString> strings;
53 strings.append("bat");
54 strings.append("cat");
55 strings.append("dog");
56
57 auto string_compare = [](DeprecatedString const& a, DeprecatedString const& b) -> int {
58 return strcmp(a.characters(), b.characters());
59 };
60 auto test1 = *binary_search(strings, DeprecatedString("bat"), nullptr, string_compare);
61 auto test2 = *binary_search(strings, DeprecatedString("cat"), nullptr, string_compare);
62 auto test3 = *binary_search(strings, DeprecatedString("dog"), nullptr, string_compare);
63 EXPECT_EQ(test1, DeprecatedString("bat"));
64 EXPECT_EQ(test2, DeprecatedString("cat"));
65 EXPECT_EQ(test3, DeprecatedString("dog"));
66}
67
68TEST_CASE(single_element)
69{
70 Vector<int> ints;
71 ints.append(1);
72
73 auto test1 = *binary_search(ints, 1);
74 EXPECT_EQ(test1, 1);
75}
76
77TEST_CASE(not_found)
78{
79 Vector<int> ints;
80 ints.append(1);
81 ints.append(2);
82 ints.append(3);
83
84 auto test1 = binary_search(ints, -1);
85 auto test2 = binary_search(ints, 0);
86 auto test3 = binary_search(ints, 4);
87 EXPECT_EQ(test1, nullptr);
88 EXPECT_EQ(test2, nullptr);
89 EXPECT_EQ(test3, nullptr);
90}
91
92TEST_CASE(no_elements)
93{
94 Vector<int> ints;
95
96 auto test1 = binary_search(ints, 1);
97 EXPECT_EQ(test1, nullptr);
98}
99
100TEST_CASE(constexpr_array_search)
101{
102 constexpr Array<int, 3> array = { 1, 17, 42 };
103
104 static_assert(binary_search(array, 42) == &array[2]);
105 static_assert(binary_search(array, 17) == &array[1]);
106 static_assert(binary_search(array, 3) == nullptr);
107}
108
109TEST_CASE(unsigned_to_signed_regression)
110{
111 Array<u32, 5> const input { 0, 1, 2, 3, 4 };
112
113 // The algorithm computes 1 - input[2] = -1, and if this is (incorrectly) cast
114 // to an unsigned then it will look in the wrong direction and miss the 1.
115
116 size_t nearby_index = 1;
117 EXPECT_EQ(binary_search(input, 1u, &nearby_index), &input[1]);
118 EXPECT_EQ(nearby_index, 1u);
119}