diff options
Diffstat (limited to 'archived/projt-launcher/tests/SeparatorPrefixTree_test.cpp')
| -rw-r--r-- | archived/projt-launcher/tests/SeparatorPrefixTree_test.cpp | 168 |
1 files changed, 168 insertions, 0 deletions
diff --git a/archived/projt-launcher/tests/SeparatorPrefixTree_test.cpp b/archived/projt-launcher/tests/SeparatorPrefixTree_test.cpp new file mode 100644 index 0000000000..3207079e37 --- /dev/null +++ b/archived/projt-launcher/tests/SeparatorPrefixTree_test.cpp @@ -0,0 +1,168 @@ +// SPDX-License-Identifier: GPL-3.0-only +// SPDX-FileCopyrightText: 2026 Project Tick +// SPDX-FileContributor: Project Tick Team +/* + * ProjT Launcher - Minecraft Launcher + * Copyright (C) 2026 Project Tick + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, version 3. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include <QByteArray> +#include <QRandomGenerator> +#include <QSet> +#include <QStringList> +#include <QTest> + +#include <SeparatorPrefixTree.h> + +namespace { +QString randomPath(QRandomGenerator& rng) +{ + static const char kAlphabet[] = "abcdefghijklmnopqrstuvwxyz0123456789-_."; + const int alphabet_len = static_cast<int>(sizeof(kAlphabet) - 1); + + const int segments = rng.bounded(1, 5); + QStringList parts; + parts.reserve(segments); + + for (int i = 0; i < segments; ++i) { + const int length = rng.bounded(1, 9); + QByteArray bytes; + bytes.reserve(length); + for (int j = 0; j < length; ++j) { + bytes.append(kAlphabet[rng.bounded(alphabet_len)]); + } + parts.append(QString::fromLatin1(bytes)); + } + + return parts.join('/'); +} + +QString shortestContainedPrefix(const SeparatorPrefixTree<'/'> &tree, const QString& path) +{ + const auto parts = path.split('/'); + QString prefix; + for (int i = 0; i < parts.size(); ++i) { + if (i == 0) + prefix = parts.at(i); + else + prefix = prefix + '/' + parts.at(i); + if (tree.contains(prefix)) + return prefix; + } + return QString(); +} +} // namespace + +class SeparatorPrefixTreeTest : public QObject +{ + Q_OBJECT + + private slots: + void test_basicInsertAndCovers() + { + SeparatorPrefixTree<'/'> tree; + tree.insert("a/b"); + tree.insert("a/c"); + tree.insert("d"); + + QVERIFY(tree.contains("a/b")); + QVERIFY(tree.contains("a/c")); + QVERIFY(tree.contains("d")); + QVERIFY(!tree.contains("a")); + + QVERIFY(tree.covers("a/b/c")); + QCOMPARE(tree.cover("a/b/c"), QString("a/b")); + QVERIFY(tree.covers("d/x")); + QCOMPARE(tree.cover("d/x"), QString("d")); + QVERIFY(!tree.covers("x")); + QVERIFY(tree.cover("x").isNull()); + } + + void test_removeKeepsDescendants() + { + SeparatorPrefixTree<'/'> tree; + tree.insert("a/b"); + tree.insert("a/b/c"); + tree.insert("x/y"); + + QVERIFY(tree.remove("a/b")); + QVERIFY(!tree.contains("a/b")); + QVERIFY(tree.contains("a/b/c")); + QVERIFY(tree.covers("a/b/c")); + QCOMPARE(tree.cover("a/b/c"), QString("a/b/c")); + QVERIFY(tree.contains("x/y")); + } + + void test_toStringListMatchesContainment() + { + SeparatorPrefixTree<'/'> tree; + QSet<QString> expected{ "alpha/bravo", "alpha/charlie", "delta" }; + for (const auto& path : expected) + tree.insert(path); + + const auto list = tree.toStringList(); + QSet<QString> actual(list.cbegin(), list.cend()); + QCOMPARE(actual, expected); + + for (const auto& path : list) + QVERIFY(tree.contains(path)); + } + + void test_randomizedStability() + { + SeparatorPrefixTree<'/'> tree; + QSet<QString> inserted; + QRandomGenerator rng(0xC0FFEEu); + + for (int i = 0; i < 250; ++i) { + const auto path = randomPath(rng); + inserted.insert(path); + tree.insert(path); + QVERIFY(tree.contains(path)); + QVERIFY(tree.covers(path)); + QCOMPARE(tree.cover(path), shortestContainedPrefix(tree, path)); + } + + for (int i = 0; i < 200; ++i) { + const auto probe = randomPath(rng); + const auto cover = tree.cover(probe); + const auto expected = shortestContainedPrefix(tree, probe); + if (expected.isNull()) { + QVERIFY(!tree.covers(probe)); + QVERIFY(cover.isNull()); + } else { + QVERIFY(tree.covers(probe)); + QCOMPARE(cover, expected); + } + } + + QStringList list = tree.toStringList(); + for (const auto& path : list) + QVERIFY(tree.contains(path)); + + const auto values = inserted.values(); + for (int i = 0; i < 80 && !inserted.isEmpty(); ++i) { + const auto& path = values.at(rng.bounded(values.size())); + if (tree.remove(path)) + inserted.remove(path); + QVERIFY(!tree.contains(path)); + } + } +}; + +QTEST_GUILESS_MAIN(SeparatorPrefixTreeTest) + +#include "SeparatorPrefixTree_test.moc" |