jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Idan Horowitz <idan.horowitz@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/BinaryHeap.h>
10#include <AK/DeprecatedString.h>
11
12TEST_CASE(construct)
13{
14 BinaryHeap<int, int, 5> empty;
15 EXPECT(empty.is_empty());
16 EXPECT(empty.size() == 0);
17}
18
19TEST_CASE(construct_from_existing)
20{
21 int keys[] = { 3, 2, 1 };
22 char values[] = { 'c', 'b', 'a' };
23 BinaryHeap<int, char, 5> from_existing(keys, values, 3);
24 EXPECT(from_existing.size() == 3);
25 EXPECT_EQ(from_existing.pop_min(), 'a');
26 EXPECT_EQ(from_existing.pop_min(), 'b');
27 EXPECT_EQ(from_existing.pop_min(), 'c');
28}
29
30TEST_CASE(populate_int)
31{
32 BinaryHeap<int, int, 5> ints;
33 ints.insert(1, 10);
34 ints.insert(3, 20);
35 ints.insert(2, 30);
36 EXPECT_EQ(ints.size(), 3u);
37 EXPECT_EQ(ints.pop_min(), 10);
38 EXPECT_EQ(ints.size(), 2u);
39 EXPECT_EQ(ints.pop_min(), 30);
40 EXPECT_EQ(ints.size(), 1u);
41 EXPECT_EQ(ints.pop_min(), 20);
42 EXPECT_EQ(ints.size(), 0u);
43}
44
45TEST_CASE(populate_string)
46{
47 BinaryHeap<int, DeprecatedString, 5> strings;
48 strings.insert(1, "ABC");
49 strings.insert(2, "DEF");
50 EXPECT_EQ(strings.size(), 2u);
51 EXPECT_EQ(strings.pop_min(), "ABC");
52 EXPECT_EQ(strings.pop_min(), "DEF");
53 EXPECT(strings.is_empty());
54}
55
56TEST_CASE(large_populate_reverse)
57{
58 BinaryHeap<int, int, 1024> ints;
59 for (int i = 1023; i >= 0; i--) {
60 ints.insert(i, i);
61 }
62 EXPECT_EQ(ints.size(), 1024u);
63 for (int i = 0; i < 1024; i++) {
64 EXPECT_EQ(ints.peek_min(), i);
65 EXPECT_EQ(ints.pop_min(), i);
66 }
67}