/**********************************************************************
 * LeechCraft - modular cross-platform feature rich internet client.
 * Copyright (C) 2006-2014  Georg Rudoy
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE or copy at https://www.boost.org/LICENSE_1_0.txt)
 **********************************************************************/

#pragma once

#include <optional>
#include <type_traits>
#include <QHash>
#include <QString>
#include <QStringView>
#include <QtDebug>

namespace LC::Util
{
	template<typename Cont>
	concept StringViewContainer = std::is_same_v<typename std::decay_t<Cont>::value_type, QStringView>;

	template<typename V>
	class StringPathTrie
	{
		std::optional<V> Value_;

		// TODO C++20 use transparent hashes and unordered_map
		QHash<QString, StringPathTrie> Children_;
	public:
		const std::optional<V>& GetValue () const
		{
			return Value_;
		}

		const StringPathTrie* GetChild (QStringView view) const
		{
			const auto pos = Children_.find (view.toString ());
			if (pos == Children_.end ())
				return nullptr;

			return &*pos;
		}

		template<StringViewContainer Cont>
		void Add (Cont&& path, V value)
		{
			Add (path.begin (), path.end (), std::move (value));
		}

		template<typename It, typename End>
		void Add (It begin, End end, V value)
		{
			if (begin == end)
			{
				Value_ = std::move (value);
				return;
			}

			const auto& strRef = (*begin).toString ();
			auto pos = Children_.find (strRef);
			if (pos == Children_.end ())
				pos = Children_.insert (strRef, {});
			pos->Add (std::next (begin), end, std::move (value));
		}

		struct FindResult
		{
			std::optional<V> Value_;
			std::ptrdiff_t Remaining_ = 0;

			inline const static StringPathTrie NullTrie {};
			const StringPathTrie *Rest_ = &NullTrie;

			bool operator== (const FindResult& other) const
			{
				return Value_ == other.Value_ && Remaining_ == other.Remaining_;
			}
		};

		FindResult Find (QStringView single) const
		{
			std::initializer_list<QStringView> dummy { single };
			return Find (dummy.begin (), dummy.end ());
		}

		template<StringViewContainer Cont>
		FindResult Find (Cont&& path) const
		{
			return Find (path.begin (), path.end ());
		}

		template<typename It, typename End>
		FindResult Find (It begin, End end) const
		{
			return Find (begin, end, { Value_, end - begin, this });
		}
	private:
		template<typename It, typename End>
		FindResult Find (It begin, End end, FindResult lastGood) const
		{
			if (Value_)
				lastGood = { Value_, end - begin, this };

			if (begin == end)
				return lastGood;

			const auto& strRef = (*begin).toString ();
			const auto pos = Children_.find (strRef);
			if (pos == Children_.end ())
				return lastGood;

			return pos->Find (std::next (begin), end, lastGood);
		}
	};
}
