/**************************************************************************/ /* test_list.cpp */ /**************************************************************************/ /* This file is part of: */ /* GODOT ENGINE */ /* https://godotengine.org */ /**************************************************************************/ /* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */ /* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ /* */ /* Permission is hereby granted, free of charge, to any person obtaining */ /* a copy of this software and associated documentation files (the */ /* "Software"), to deal in the Software without restriction, including */ /* without limitation the rights to use, copy, modify, merge, publish, */ /* distribute, sublicense, and/or sell copies of the Software, and to */ /* permit persons to whom the Software is furnished to do so, subject to */ /* the following conditions: */ /* */ /* The above copyright notice and this permission notice shall be */ /* included in all copies or substantial portions of the Software. */ /* */ /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */ /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /**************************************************************************/ #include "tests/test_macros.h" TEST_FORCE_LINK(test_list) #include "core/templates/list.h" namespace TestList { static void populate_integers(List &p_list, List::Element *r_elements[], int num_elements) { p_list.clear(); for (int i = 0; i < num_elements; ++i) { List::Element *n = p_list.push_back(i); r_elements[i] = n; } } TEST_CASE("[List] List initialization") { List list{ 0, 1, 2, 3, 4 }; CHECK(list.size() == 5); CHECK(list.get(0) == 0); CHECK(list.get(1) == 1); CHECK(list.get(2) == 2); CHECK(list.get(3) == 3); CHECK(list.get(4) == 4); } TEST_CASE("[List] Push/pop back") { List list; List::Element *n; n = list.push_back("A"); CHECK(n->get() == "A"); n = list.push_back("B"); CHECK(n->get() == "B"); n = list.push_back("C"); CHECK(n->get() == "C"); CHECK(list.size() == 3); CHECK(!list.is_empty()); String v; v = list.back()->get(); list.pop_back(); CHECK(v == "C"); v = list.back()->get(); list.pop_back(); CHECK(v == "B"); v = list.back()->get(); list.pop_back(); CHECK(v == "A"); CHECK(list.size() == 0); CHECK(list.is_empty()); CHECK(list.back() == nullptr); CHECK(list.front() == nullptr); } TEST_CASE("[List] Push/pop front") { List list; List::Element *n; n = list.push_front("A"); CHECK(n->get() == "A"); n = list.push_front("B"); CHECK(n->get() == "B"); n = list.push_front("C"); CHECK(n->get() == "C"); CHECK(list.size() == 3); CHECK(!list.is_empty()); String v; v = list.front()->get(); list.pop_front(); CHECK(v == "C"); v = list.front()->get(); list.pop_front(); CHECK(v == "B"); v = list.front()->get(); list.pop_front(); CHECK(v == "A"); CHECK(list.size() == 0); CHECK(list.is_empty()); CHECK(list.back() == nullptr); CHECK(list.front() == nullptr); } TEST_CASE("[List] Set and get") { List list; list.push_back("A"); List::Element *n = list.front(); CHECK(n->get() == "A"); n->set("X"); CHECK(n->get() == "X"); } TEST_CASE("[List] Insert before") { List list; List::Element *a = list.push_back("A"); List::Element *b = list.push_back("B"); List::Element *c = list.push_back("C"); list.insert_before(b, "I"); CHECK(a->next()->get() == "I"); CHECK(c->prev()->prev()->get() == "I"); CHECK(list.front()->next()->get() == "I"); CHECK(list.back()->prev()->prev()->get() == "I"); } TEST_CASE("[List] Insert after") { List list; List::Element *a = list.push_back("A"); List::Element *b = list.push_back("B"); List::Element *c = list.push_back("C"); list.insert_after(b, "I"); CHECK(a->next()->next()->get() == "I"); CHECK(c->prev()->get() == "I"); CHECK(list.front()->next()->next()->get() == "I"); CHECK(list.back()->prev()->get() == "I"); } TEST_CASE("[List] Insert before null") { List list; List::Element *a = list.push_back("A"); List::Element *b = list.push_back("B"); List::Element *c = list.push_back("C"); list.insert_before(nullptr, "I"); CHECK(a->next()->get() == "B"); CHECK(b->get() == "B"); CHECK(c->prev()->prev()->get() == "A"); CHECK(list.front()->next()->get() == "B"); CHECK(list.back()->prev()->prev()->get() == "B"); CHECK(list.back()->get() == "I"); } TEST_CASE("[List] Insert after null") { List list; List::Element *a = list.push_back("A"); List::Element *b = list.push_back("B"); List::Element *c = list.push_back("C"); list.insert_after(nullptr, "I"); CHECK(a->next()->get() == "B"); CHECK(b->get() == "B"); CHECK(c->prev()->prev()->get() == "A"); CHECK(list.front()->next()->get() == "B"); CHECK(list.back()->prev()->prev()->get() == "B"); CHECK(list.back()->get() == "I"); } TEST_CASE("[List] Find") { List list; List::Element *n[10]; // Indices match values. populate_integers(list, n, 10); for (int i = 0; i < 10; ++i) { CHECK(n[i]->get() == list.find(i)->get()); } } TEST_CASE("[List] Erase (by value)") { List list; List::Element *n[4]; // Indices match values. populate_integers(list, n, 4); CHECK(list.front()->next()->next()->get() == 2); bool erased = list.erase(2); // 0, 1, 3. CHECK(erased); CHECK(list.size() == 3); // The pointer n[2] points to the freed memory which is not reset to zero, // so the below assertion may pass, but this relies on undefined behavior. // CHECK(n[2]->get() == 2); CHECK(list.front()->get() == 0); CHECK(list.front()->next()->next()->get() == 3); CHECK(list.back()->get() == 3); CHECK(list.back()->prev()->get() == 1); CHECK(n[1]->next()->get() == 3); CHECK(n[3]->prev()->get() == 1); erased = list.erase(9000); // Doesn't exist. CHECK(!erased); } TEST_CASE("[List] Erase (by element)") { List list; List::Element *n[4]; // Indices match values. populate_integers(list, n, 4); bool erased = list.erase(n[2]); CHECK(erased); CHECK(list.size() == 3); CHECK(n[1]->next()->get() == 3); CHECK(n[3]->prev()->get() == 1); } TEST_CASE("[List] Element erase") { List list; List::Element *n[4]; // Indices match values. populate_integers(list, n, 4); n[2]->erase(); CHECK(list.size() == 3); CHECK(n[1]->next()->get() == 3); CHECK(n[3]->prev()->get() == 1); } TEST_CASE("[List] Clear") { List list; List::Element *n[100]; populate_integers(list, n, 100); list.clear(); CHECK(list.size() == 0); CHECK(list.is_empty()); } TEST_CASE("[List] Invert") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.reverse(); CHECK(list.front()->get() == 3); CHECK(list.front()->next()->get() == 2); CHECK(list.back()->prev()->get() == 1); CHECK(list.back()->get() == 0); } TEST_CASE("[List] Move to front") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.move_to_front(n[3]); CHECK(list.front()->get() == 3); CHECK(list.back()->get() == 2); } TEST_CASE("[List] Move to back") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.move_to_back(n[0]); CHECK(list.back()->get() == 0); CHECK(list.front()->get() == 1); } TEST_CASE("[List] Move before") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.move_before(n[3], n[1]); CHECK(list.front()->next()->get() == n[3]->get()); } template static void compare_lists(const List &p_result, const List &p_expected) { CHECK_EQ(p_result.size(), p_expected.size()); const typename List::Element *result_it = p_result.front(); const typename List::Element *expected_it = p_expected.front(); for (int i = 0; i < p_result.size(); i++) { CHECK(result_it); CHECK(expected_it); CHECK_EQ(result_it->get(), expected_it->get()); result_it = result_it->next(); expected_it = expected_it->next(); } CHECK(!result_it); CHECK(!expected_it); result_it = p_result.back(); expected_it = p_expected.back(); for (int i = 0; i < p_result.size(); i++) { CHECK(result_it); CHECK(expected_it); CHECK_EQ(result_it->get(), expected_it->get()); result_it = result_it->prev(); expected_it = expected_it->prev(); } CHECK(!result_it); CHECK(!expected_it); } TEST_CASE("[List] Sort") { List result{ "D", "B", "A", "C" }; result.sort(); List expected{ "A", "B", "C", "D" }; compare_lists(result, expected); List empty_result{}; empty_result.sort(); List empty_expected{}; compare_lists(empty_result, empty_expected); List one_result{ 1 }; one_result.sort(); List one_expected{ 1 }; compare_lists(one_result, one_expected); List reversed_result{ 2.0, 1.5, 1.0 }; reversed_result.sort(); List reversed_expected{ 1.0, 1.5, 2.0 }; compare_lists(reversed_result, reversed_expected); List already_sorted_result{ 1, 2, 3, 4, 5 }; already_sorted_result.sort(); List already_sorted_expected{ 1, 2, 3, 4, 5 }; compare_lists(already_sorted_result, already_sorted_expected); List with_duplicates_result{ 1, 2, 3, 1, 2, 3 }; with_duplicates_result.sort(); List with_duplicates_expected{ 1, 1, 2, 2, 3, 3 }; compare_lists(with_duplicates_result, with_duplicates_expected); } TEST_CASE("[List] Swap adjacent front and back") { List list; List::Element *n[2]; populate_integers(list, n, 2); list.swap(list.front(), list.back()); CHECK(list.front()->prev() == nullptr); CHECK(list.front() != list.front()->next()); CHECK(list.front() == n[1]); CHECK(list.back() == n[0]); CHECK(list.back()->next() == nullptr); CHECK(list.back() != list.back()->prev()); } TEST_CASE("[List] Swap first adjacent pair") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.swap(n[0], n[1]); CHECK(list.front()->prev() == nullptr); CHECK(list.front() != list.front()->next()); CHECK(list.front() == n[1]); CHECK(list.front()->next() == n[0]); CHECK(list.back()->prev() == n[2]); CHECK(list.back() == n[3]); CHECK(list.back()->next() == nullptr); CHECK(list.back() != list.back()->prev()); } TEST_CASE("[List] Swap middle adjacent pair") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.swap(n[1], n[2]); CHECK(list.front()->prev() == nullptr); CHECK(list.front() == n[0]); CHECK(list.front()->next() == n[2]); CHECK(list.back()->prev() == n[1]); CHECK(list.back() == n[3]); CHECK(list.back()->next() == nullptr); } TEST_CASE("[List] Swap last adjacent pair") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.swap(n[2], n[3]); CHECK(list.front()->prev() == nullptr); CHECK(list.front() == n[0]); CHECK(list.front()->next() == n[1]); CHECK(list.back()->prev() == n[3]); CHECK(list.back() == n[2]); CHECK(list.back()->next() == nullptr); } TEST_CASE("[List] Swap first cross pair") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.swap(n[0], n[2]); CHECK(list.front()->prev() == nullptr); CHECK(list.front() == n[2]); CHECK(list.front()->next() == n[1]); CHECK(list.back()->prev() == n[0]); CHECK(list.back() == n[3]); CHECK(list.back()->next() == nullptr); } TEST_CASE("[List] Swap last cross pair") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.swap(n[1], n[3]); CHECK(list.front()->prev() == nullptr); CHECK(list.front() == n[0]); CHECK(list.front()->next() == n[3]); CHECK(list.back()->prev() == n[2]); CHECK(list.back() == n[1]); CHECK(list.back()->next() == nullptr); } TEST_CASE("[List] Swap edges") { List list; List::Element *n[4]; populate_integers(list, n, 4); list.swap(n[1], n[3]); CHECK(list.front()->prev() == nullptr); CHECK(list.front() == n[0]); CHECK(list.front()->next() == n[3]); CHECK(list.back()->prev() == n[2]); CHECK(list.back() == n[1]); CHECK(list.back()->next() == nullptr); } TEST_CASE("[List] Swap middle (values check)") { List list; List::Element *n_str1 = list.push_back("Still"); List::Element *n_str2 = list.push_back("waiting"); List::Element *n_str3 = list.push_back("for"); List::Element *n_str4 = list.push_back("Godot."); CHECK(n_str1->get() == "Still"); CHECK(n_str4->get() == "Godot."); CHECK(list.front()->get() == "Still"); CHECK(list.front()->next()->get() == "waiting"); CHECK(list.back()->prev()->get() == "for"); CHECK(list.back()->get() == "Godot."); list.swap(n_str2, n_str3); CHECK(list.front()->next()->get() == "for"); CHECK(list.back()->prev()->get() == "waiting"); } TEST_CASE("[List] Swap front and back (values check)") { List list; Variant str = "Godot"; List::Element *n_str = list.push_back(str); Variant color = Color(0, 0, 1); List::Element *n_color = list.push_back(color); CHECK(list.front()->get() == "Godot"); CHECK(list.back()->get() == Color(0, 0, 1)); list.swap(n_str, n_color); CHECK(list.front()->get() == Color(0, 0, 1)); CHECK(list.back()->get() == "Godot"); } TEST_CASE("[List] Swap adjacent back and front (reverse order of elements)") { List list; List::Element *n[2]; populate_integers(list, n, 2); list.swap(n[1], n[0]); List::Element *it = list.front(); while (it) { List::Element *prev_it = it; it = it->next(); if (it == prev_it) { FAIL_CHECK("Infinite loop detected."); break; } } } } // namespace TestList