/* SPDX-FileCopyrightText: 2026 Project Tick
 * SPDX-FileContributor: Project Tick
 * SPDX-License-Identifier: GPL-3.0-or-later
 *
 *   MeshMC - A Custom Launcher for Minecraft
 *   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, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   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, see <https://www.gnu.org/licenses/>.
 */

#pragma once
#include <QString>
#include <QMap>
#include <QStringList>

template <char Tseparator> class SeparatorPrefixTree
{
  public:
	SeparatorPrefixTree(QStringList paths)
	{
		insert(paths);
	}

	SeparatorPrefixTree(bool contained = false)
	{
		m_contained = contained;
	}

	void insert(QStringList paths)
	{
		for (auto& path : paths) {
			insert(path);
		}
	}

	/// insert an exact path into the tree
	SeparatorPrefixTree& insert(QString path)
	{
		auto sepIndex = path.indexOf(Tseparator);
		if (sepIndex == -1) {
			children[path] = SeparatorPrefixTree(true);
			return children[path];
		} else {
			auto prefix = path.left(sepIndex);
			if (!children.contains(prefix)) {
				children[prefix] = SeparatorPrefixTree(false);
			}
			return children[prefix].insert(path.mid(sepIndex + 1));
		}
	}

	/// is the path fully contained in the tree?
	bool contains(QString path) const
	{
		auto node = find(path);
		return node != nullptr;
	}

	/// does the tree cover a path? That means the prefix of the path is
	/// contained in the tree
	bool covers(QString path) const
	{
		// if we found some valid node, it's good enough. the tree covers the
		// path
		if (m_contained) {
			return true;
		}
		auto sepIndex = path.indexOf(Tseparator);
		if (sepIndex == -1) {
			auto found = children.find(path);
			if (found == children.end()) {
				return false;
			}
			return (*found).covers(QString());
		} else {
			auto prefix = path.left(sepIndex);
			auto found = children.find(prefix);
			if (found == children.end()) {
				return false;
			}
			return (*found).covers(path.mid(sepIndex + 1));
		}
	}

	/// return the contained path that covers the path specified
	QString cover(QString path) const
	{
		// if we found some valid node, it's good enough. the tree covers the
		// path
		if (m_contained) {
			return QString("");
		}
		auto sepIndex = path.indexOf(Tseparator);
		if (sepIndex == -1) {
			auto found = children.find(path);
			if (found == children.end()) {
				return QString();
			}
			auto nested = (*found).cover(QString());
			if (nested.isNull()) {
				return nested;
			}
			if (nested.isEmpty())
				return path;
			return path + Tseparator + nested;
		} else {
			auto prefix = path.left(sepIndex);
			auto found = children.find(prefix);
			if (found == children.end()) {
				return QString();
			}
			auto nested = (*found).cover(path.mid(sepIndex + 1));
			if (nested.isNull()) {
				return nested;
			}
			if (nested.isEmpty())
				return prefix;
			return prefix + Tseparator + nested;
		}
	}

	/// Does the path-specified node exist in the tree? It does not have to be
	/// contained.
	bool exists(QString path) const
	{
		auto sepIndex = path.indexOf(Tseparator);
		if (sepIndex == -1) {
			auto found = children.find(path);
			if (found == children.end()) {
				return false;
			}
			return true;
		} else {
			auto prefix = path.left(sepIndex);
			auto found = children.find(prefix);
			if (found == children.end()) {
				return false;
			}
			return (*found).exists(path.mid(sepIndex + 1));
		}
	}

	/// find a node in the tree by name
	const SeparatorPrefixTree* find(QString path) const
	{
		auto sepIndex = path.indexOf(Tseparator);
		if (sepIndex == -1) {
			auto found = children.find(path);
			if (found == children.end()) {
				return nullptr;
			}
			return &(*found);
		} else {
			auto prefix = path.left(sepIndex);
			auto found = children.find(prefix);
			if (found == children.end()) {
				return nullptr;
			}
			return (*found).find(path.mid(sepIndex + 1));
		}
	}

	/// is this a leaf node?
	bool leaf() const
	{
		return children.isEmpty();
	}

	/// is this node actually contained in the tree, or is it purely structural?
	bool contained() const
	{
		return m_contained;
	}

	/// Remove a path from the tree
	bool remove(QString path)
	{
		return removeInternal(path) != Failed;
	}

	/// Clear all children of this node tree node
	void clear()
	{
		children.clear();
	}

	QStringList toStringList() const
	{
		QStringList collected;
		// collecting these is more expensive.
		auto iter = children.begin();
		while (iter != children.end()) {
			QStringList list = iter.value().toStringList();
			for (int i = 0; i < list.size(); i++) {
				list[i] = iter.key() + Tseparator + list[i];
			}
			collected.append(list);
			if ((*iter).m_contained) {
				collected.append(iter.key());
			}
			iter++;
		}
		return collected;
	}

  private:
	enum Removal { Failed, Succeeded, HasChildren };
	Removal removeInternal(QString path = QString())
	{
		if (path.isEmpty()) {
			if (!m_contained) {
				// remove all children - we are removing a prefix
				clear();
				return Succeeded;
			}
			m_contained = false;
			if (children.size()) {
				return HasChildren;
			}
			return Succeeded;
		}
		Removal remStatus = Failed;
		QString childToRemove;
		auto sepIndex = path.indexOf(Tseparator);
		if (sepIndex == -1) {
			childToRemove = path;
			auto found = children.find(childToRemove);
			if (found == children.end()) {
				return Failed;
			}
			remStatus = (*found).removeInternal();
		} else {
			childToRemove = path.left(sepIndex);
			auto found = children.find(childToRemove);
			if (found == children.end()) {
				return Failed;
			}
			remStatus = (*found).removeInternal(path.mid(sepIndex + 1));
		}
		switch (remStatus) {
			case Failed:
			case HasChildren: {
				return remStatus;
			}
			case Succeeded: {
				children.remove(childToRemove);
				if (m_contained) {
					return HasChildren;
				}
				if (children.size()) {
					return HasChildren;
				}
				return Succeeded;
			}
		}
		return Failed;
	}

  private:
	QMap<QString, SeparatorPrefixTree<Tseparator>> children;
	bool m_contained = false;
};