Class QueryTrie

SubtitleFontAutoLoaderDaemon/QueryService.cpp:13–205

{
	template <typename T, bool AllowDuplicate = true>
	class QueryTrie
	{
	private:
		struct TrieNode
		{
			std::vector<std::pair<std::wstring, std::unique_ptr<TrieNode>>> m_branch;
			std::vector<T*> m_data;

			void CollectData(std::vector<T*>& ret)
			{
				ret.insert(ret.end(), m_data.begin(), m_data.end());
				for (auto& branch : m_branch)
				{
					branch.second->CollectData(ret);
				}
			}

			void SortList()
			{
				std::sort(m_branch.begin(), m_branch.end());
			}

			std::pair<std::wstring, std::unique_ptr<TrieNode>>* SearchPrefix(wchar_t leading)
			{
				auto left = m_branch.begin();
				auto right = m_branch.end();
				auto mid = left + (right - left) / 2;
				auto result = right;
				while (left != right)
				{
					assert(!mid->first.empty());
					if (mid->first[0] == leading)
					{
						result = mid;
						break;
					}
					else if (mid->first[0] > leading)
					{
						right = mid;
					}
					else
					{
						left = mid + 1;
					}
					mid = left + (right - left) / 2;
				}
				if (result == m_branch.end())
					return nullptr;
				return &(*result);
			}
		};

		TrieNode m_rootNode;
	public:
		void AddEntry(const wchar_t* key, T* value)
		{
			const wchar_t* keyPointer = key;
			TrieNode* node = &m_rootNode;