/src/serenity/AK/Trie.h

Source (jump to first uncovered line)
/*
 * Copyright (c) 2020, the SerenityOS developers.
 *
 * SPDX-License-Identifier: BSD-2-Clause
 */

#pragma once

#include <AK/Concepts.h>
#include <AK/Forward.h>
#include <AK/HashMap.h>
#include <AK/OwnPtr.h>
#include <AK/Types.h>

namespace AK {

namespace Detail {

template<typename TypeA, typename Default>
struct SubstituteIfVoid {
    using Type = TypeA;
};

template<typename Default>
struct SubstituteIfVoid<void, Default> {
    using Type = Default;
};

template<typename DeclaredBaseType, typename DefaultBaseType, typename ValueType, typename MetadataT, typename ValueTraits, template<typename, typename, typename> typename MapType>
class Trie {
    using BaseType = typename SubstituteIfVoid<DeclaredBaseType, DefaultBaseType>::Type;

public:
    using MetadataType = MetadataT;

    Trie(ValueType value, Optional<MetadataType> metadata)
        : m_value(move(value))
        , m_metadata(move(metadata))
    {
    }

    template<typename It>
    BaseType& traverse_until_last_accessible_node(It& it, It const& end)
    {
        Trie* node = this;
        for (; it < end; ++it) {
            auto next_it = node->m_children.find(*it);
            if (next_it == node->m_children.end())
                return static_cast<BaseType&>(*node);
            node = &*(*next_it).value;
        }
        return static_cast<BaseType&>(*node);
    }

    template<typename It>
    BaseType const& traverse_until_last_accessible_node(It& it, It const& end) const { return const_cast<Trie*>(this)->traverse_until_last_accessible_node(it, end); }

    template<typename It>
    BaseType& traverse_until_last_accessible_node(It const& begin, It const& end)
    {
        auto it = begin;
        return const_cast<Trie*>(this)->traverse_until_last_accessible_node(it, end);
    }

    template<typename It>
    BaseType const& traverse_until_last_accessible_node(It const& begin, It const& end) const
    {
        auto it = begin;
        return const_cast<Trie*>(this)->traverse_until_last_accessible_node(it, end);
    }

    bool has_metadata() const { return m_metadata.has_value(); }

    Optional<MetadataType> metadata() const
    requires(!IsNullPointer<MetadataType>)
    {
        return m_metadata;
    }
    void set_metadata(MetadataType metadata)
    requires(!IsNullPointer<MetadataType>)
    {
        m_metadata = move(metadata);
    }
    MetadataType const& metadata_value() const
    requires(!IsNullPointer<MetadataType>)
    {
        return m_metadata.value();
    }
    MetadataType& metadata_value()
    requires(!IsNullPointer<MetadataType>)
    {
        return m_metadata.value();
    }

    ValueType const& value() const { return m_value; }
    ValueType& value() { return m_value; }

    ErrorOr<Trie*> ensure_child(ValueType value, Optional<MetadataType> metadata = {})
    {
        auto it = m_children.find(value);
        if (it == m_children.end()) {
            OwnPtr<Trie> node;
            if constexpr (requires { { value->try_clone() } -> SpecializationOf<ErrorOr>; })
                node = TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(TRY(value->try_clone()), move(metadata))));
            else
                node = TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(value, move(metadata))));
            auto& node_ref = *node;
            TRY(m_children.try_set(move(value), node.release_nonnull()));
            return &static_cast<BaseType&>(node_ref);
        }

        auto& node_ref = *it->value;
        if (metadata.has_value())
            node_ref.m_metadata = move(metadata);
        return &static_cast<BaseType&>(node_ref);
    }

    template<typename It, typename ProvideMetadataFunction>
    ErrorOr<BaseType*> insert(
        It& it, It const& end, MetadataType metadata, ProvideMetadataFunction provide_missing_metadata)
    requires(!IsNullPointer<MetadataType>)
    {
        Trie* last_root_node = &traverse_until_last_accessible_node(it, end);
        auto invoke_provide_missing_metadata = [&]<typename... Ts>(Ts&&... args) -> ErrorOr<Optional<MetadataType>> {
            if constexpr (SameAs<MetadataType, decltype(provide_missing_metadata(forward<Ts>(args)...))>)
                return Optional<MetadataType>(provide_missing_metadata(forward<Ts>(args)...));
            else
                return provide_missing_metadata(forward<Ts>(args)...);
        };
        for (; it != end; ++it) {
            if constexpr (requires { { ValueType::ElementType::try_create(*it) } -> SpecializationOf<ErrorOr>; })
                last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(TRY(ValueType::ElementType::try_create(*it)), TRY(invoke_provide_missing_metadata(static_cast<BaseType&>(*last_root_node), it)))));
            else
                last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(*it, TRY(invoke_provide_missing_metadata(static_cast<BaseType&>(*last_root_node), it)))));
        }
        last_root_node->set_metadata(move(metadata));
        return static_cast<BaseType*>(last_root_node);
    }

    template<typename It>
    ErrorOr<BaseType*> insert(It& it, It const& end)
    requires(IsNullPointer<MetadataType>)
    {
        Trie* last_root_node = &traverse_until_last_accessible_node(it, end);
        for (; it != end; ++it) {
            if constexpr (requires { { ValueType::ElementType::try_create(*it) } -> SpecializationOf<ErrorOr>; })
                last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(TRY(ValueType::ElementType::try_create(*it)), {})));
            else
                last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(*it, {})));
        }
        return static_cast<BaseType*>(last_root_node);
    }

    template<typename It, typename ProvideMetadataFunction>
    ErrorOr<BaseType*> insert(
        It const& begin, It const& end, MetadataType metadata, ProvideMetadataFunction provide_missing_metadata)
    requires(!IsNullPointer<MetadataType>)
    {
        auto it = begin;
        return insert(it, end, move(metadata), move(provide_missing_metadata));
    }

    template<typename It>
    ErrorOr<BaseType*> insert(It const& begin, It const& end)
    requires(IsNullPointer<MetadataType>)
    {
        auto it = begin;
        return insert(it, end);
    }

    MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits>& children() { return m_children; }
    MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits> const& children() const { return m_children; }

    template<typename Fn>
    ErrorOr<void> for_each_node_in_tree_order(Fn callback) const
    {
        struct State {
            bool did_generate_root { false };
            typename MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits>::ConstIteratorType it;
            typename MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits>::ConstIteratorType end;
        };
        Vector<State> state;
        TRY(state.try_empend(false, m_children.begin(), m_children.end()));

        auto invoke = [&](auto& current_node) -> ErrorOr<IterationDecision> {
            if constexpr (VoidFunction<Fn, BaseType const&>) {
                callback(static_cast<BaseType const&>(current_node));
                return IterationDecision::Continue;
            } else if constexpr (IsSpecializationOf<decltype(callback(declval<BaseType const&>())), ErrorOr>) {
                return callback(static_cast<BaseType const&>(current_node));
            } else if constexpr (IteratorFunction<Fn, BaseType const&>) {
                return callback(static_cast<BaseType const&>(current_node));
            } else {
                static_assert(DependentFalse<Fn>, "Invalid iterator function type signature");
            }
            return IterationDecision::Continue;
        };

        for (auto* current_node = this; current_node != nullptr;) {
            if (TRY(invoke(*current_node)) == IterationDecision::Break)
                break;
            TRY(skip_to_next_iterator(state, current_node));
        }
        return {};
    }

    [[nodiscard]] bool is_empty() const { return m_children.is_empty(); }
    void clear() { m_children.clear(); }

    ErrorOr<BaseType> deep_copy()
    requires(requires(ValueType value) { { value->try_clone() } -> SpecializationOf<ErrorOr>; })
    {
        Trie root(TRY(m_value->try_clone()), TRY(copy_metadata(m_metadata)));
        for (auto& it : m_children)
            TRY(root.m_children.try_set(TRY(it.key->try_clone()), TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(TRY(it.value->deep_copy()))))));
        return static_cast<BaseType&&>(move(root));
    }

    ErrorOr<BaseType> deep_copy()
    {
        Trie root(m_value, TRY(copy_metadata(m_metadata)));
        for (auto& it : m_children)
            TRY(root.m_children.try_set(it.key, TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(TRY(it.value->deep_copy()))))));
        return static_cast<BaseType&&>(move(root));
    }

private:
    static ErrorOr<Optional<MetadataType>> copy_metadata(Optional<MetadataType> const& metadata)
    {
        if (!metadata.has_value())
            return Optional<MetadataType> {};

        if constexpr (requires(MetadataType t) { { t.copy() } -> SpecializationOf<ErrorOr>; })
            return Optional<MetadataType> { TRY(metadata->copy()) };
#ifndef KERNEL
        else
            return Optional<MetadataType> { MetadataType(metadata.value()) };
#endif
    }

    static ErrorOr<void> skip_to_next_iterator(auto& state, auto& current_node)
    {
        auto& current_state = state.last();
        if (current_state.did_generate_root)
            ++current_state.it;
        else
            current_state.did_generate_root = true;

        if (current_state.it == current_state.end)
            return pop_and_get_next_iterator(state, current_node);

        current_node = &*(*current_state.it).value;

        TRY(state.try_empend(false, current_node->m_children.begin(), current_node->m_children.end()));
        return {};
    }

    static ErrorOr<void> pop_and_get_next_iterator(auto& state, auto& current_node)
    {
        state.take_last();
        if (state.is_empty()) {
            current_node = nullptr;
            return {};
        }
        return skip_to_next_iterator(state, current_node);
    }

    ValueType m_value;
    Optional<MetadataType> m_metadata;
    MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits> m_children;
};

template<typename BaseType, typename DefaultBaseType, typename ValueType, typename ValueTraits, template<typename, typename, typename> typename MapType>
class Trie<BaseType, DefaultBaseType, ValueType, void, ValueTraits, MapType> : public Trie<BaseType, DefaultBaseType, ValueType, decltype(nullptr), ValueTraits, MapType> {
    using Trie<BaseType, DefaultBaseType, ValueType, decltype(nullptr), ValueTraits, MapType>::Trie;
};

template<typename K, typename V, typename T>
using HashMapForTrie = HashMap<K, V, T>;

}

template<typename ValueType, typename MetadataT = void, typename ValueTraits = Traits<ValueType>, typename BaseT = void, template<typename, typename, typename> typename MapType = Detail::HashMapForTrie>
class Trie : public Detail::Trie<BaseT, Trie<ValueType, MetadataT, ValueTraits, void, MapType>, ValueType, MetadataT, ValueTraits, MapType> {
public:
    using DetailTrie = Detail::Trie<BaseT, Trie<ValueType, MetadataT, ValueTraits, void, MapType>, ValueType, MetadataT, ValueTraits, MapType>;
    using MetadataType = typename DetailTrie::MetadataType;

    Trie(ValueType value, MetadataType metadata)
    requires(!IsVoid<MetadataType> && !IsNullPointer<MetadataType>)
        : DetailTrie(move(value), move(metadata))
    {
    }

    explicit Trie(ValueType value)
        : DetailTrie(move(value), Optional<MetadataType> {})
    {
    }
};

}

#if USING_AK_GLOBALLY
using AK::Trie;
#endif

Coverage Report

Created: 2025-08-28 06:26

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (c) 2020, the SerenityOS developers.
3		*
4		* SPDX-License-Identifier: BSD-2-Clause
5		*/
6
7		#pragma once
8
9		#include <AK/Concepts.h>
10		#include <AK/Forward.h>
11		#include <AK/HashMap.h>
12		#include <AK/OwnPtr.h>
13		#include <AK/Types.h>
14
15		namespace AK {
16
17		namespace Detail {
18
19		template<typename TypeA, typename Default>
20		struct SubstituteIfVoid {
21		using Type = TypeA;
22		};
23
24		template<typename Default>
25		struct SubstituteIfVoid<void, Default> {
26		using Type = Default;
27		};
28
29		template<typename DeclaredBaseType, typename DefaultBaseType, typename ValueType, typename MetadataT, typename ValueTraits, template<typename, typename, typename> typename MapType>
30		class Trie {
31		using BaseType = typename SubstituteIfVoid<DeclaredBaseType, DefaultBaseType>::Type;
32
33		public:
34		using MetadataType = MetadataT;
35
36		Trie(ValueType value, Optional<MetadataType> metadata)
37	9.34M	: m_value(move(value))
38	9.34M	, m_metadata(move(metadata))
39	9.34M	{
40	9.34M	}
41
42		template<typename It>
43		BaseType& traverse_until_last_accessible_node(It& it, It const& end)
44		{
45		Trie* node = this;
46		for (; it < end; ++it) {
47		auto next_it = node->m_children.find(*it);
48		if (next_it == node->m_children.end())
49		return static_cast<BaseType&>(*node);
50		node = &(next_it).value;
51		}
52		return static_cast<BaseType&>(*node);
53		}
54
55		template<typename It>
56		BaseType const& traverse_until_last_accessible_node(It& it, It const& end) const { return const_cast<Trie*>(this)->traverse_until_last_accessible_node(it, end); }
57
58		template<typename It>
59		BaseType& traverse_until_last_accessible_node(It const& begin, It const& end)
60		{
61		auto it = begin;
62		return const_cast<Trie*>(this)->traverse_until_last_accessible_node(it, end);
63		}
64
65		template<typename It>
66		BaseType const& traverse_until_last_accessible_node(It const& begin, It const& end) const
67		{
68		auto it = begin;
69		return const_cast<Trie*>(this)->traverse_until_last_accessible_node(it, end);
70		}
71
72	241M	bool has_metadata() const { return m_metadata.has_value(); }
73
74		Optional<MetadataType> metadata() const
75		requires(!IsNullPointer<MetadataType>)
76		{
77		return m_metadata;
78		}
79		void set_metadata(MetadataType metadata)
80		requires(!IsNullPointer<MetadataType>)
81	9.34M	{
82	9.34M	m_metadata = move(metadata);
83	9.34M	}
84		MetadataType const& metadata_value() const
85		requires(!IsNullPointer<MetadataType>)
86	231M	{
87	231M	return m_metadata.value();
88	231M	}
89		MetadataType& metadata_value()
90		requires(!IsNullPointer<MetadataType>)
91	1.03M	{
92	1.03M	return m_metadata.value();
93	1.03M	}
94
95	693k	ValueType const& value() const { return m_value; }
96		ValueType& value() { return m_value; }
97
98		ErrorOr<Trie*> ensure_child(ValueType value, Optional<MetadataType> metadata = {})
99	10.3M	{
100	10.3M	auto it = m_children.find(value);
101	10.3M	if (it == m_children.end()) {
102	9.34M	OwnPtr<Trie> node;
103		if constexpr (requires { { value->try_clone() } -> SpecializationOf<ErrorOr>; })
104		node = TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(TRY(value->try_clone()), move(metadata))));
105		else
106	9.34M	node = TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(value, move(metadata))));
107	0	auto& node_ref = *node;
108	9.34M	TRY(m_children.try_set(move(value), node.release_nonnull()));
109	0	return &static_cast<BaseType&>(node_ref);
110	9.34M	}
111
112	1.03M	auto& node_ref = *it->value;
113	1.03M	if (metadata.has_value())
114	0	node_ref.m_metadata = move(metadata);
115	1.03M	return &static_cast<BaseType&>(node_ref);
116	10.3M	}
117
118		template<typename It, typename ProvideMetadataFunction>
119		ErrorOr<BaseType*> insert(
120		It& it, It const& end, MetadataType metadata, ProvideMetadataFunction provide_missing_metadata)
121		requires(!IsNullPointer<MetadataType>)
122		{
123		Trie* last_root_node = &traverse_until_last_accessible_node(it, end);
124		auto invoke_provide_missing_metadata = [&]<typename... Ts>(Ts&&... args) -> ErrorOr<Optional<MetadataType>> {
125		if constexpr (SameAs<MetadataType, decltype(provide_missing_metadata(forward<Ts>(args)...))>)
126		return Optional<MetadataType>(provide_missing_metadata(forward<Ts>(args)...));
127		else
128		return provide_missing_metadata(forward<Ts>(args)...);
129		};
130		for (; it != end; ++it) {
131		if constexpr (requires { { ValueType::ElementType::try_create(*it) } -> SpecializationOf<ErrorOr>; })
132		last_root_node = static_cast<Trie>(TRY(last_root_node->ensure_child(TRY(ValueType::ElementType::try_create(it)), TRY(invoke_provide_missing_metadata(static_cast<BaseType&>(*last_root_node), it)))));
133		else
134		last_root_node = static_cast<Trie>(TRY(last_root_node->ensure_child(it, TRY(invoke_provide_missing_metadata(static_cast<BaseType&>(*last_root_node), it)))));
135		}
136		last_root_node->set_metadata(move(metadata));
137		return static_cast<BaseType*>(last_root_node);
138		}
139
140		template<typename It>
141		ErrorOr<BaseType*> insert(It& it, It const& end)
142		requires(IsNullPointer<MetadataType>)
143		{
144		Trie* last_root_node = &traverse_until_last_accessible_node(it, end);
145		for (; it != end; ++it) {
146		if constexpr (requires { { ValueType::ElementType::try_create(*it) } -> SpecializationOf<ErrorOr>; })
147		last_root_node = static_cast<Trie>(TRY(last_root_node->ensure_child(TRY(ValueType::ElementType::try_create(it)), {})));
148		else
149		last_root_node = static_cast<Trie>(TRY(last_root_node->ensure_child(it, {})));
150		}
151		return static_cast<BaseType*>(last_root_node);
152		}
153
154		template<typename It, typename ProvideMetadataFunction>
155		ErrorOr<BaseType*> insert(
156		It const& begin, It const& end, MetadataType metadata, ProvideMetadataFunction provide_missing_metadata)
157		requires(!IsNullPointer<MetadataType>)
158		{
159		auto it = begin;
160		return insert(it, end, move(metadata), move(provide_missing_metadata));
161		}
162
163		template<typename It>
164		ErrorOr<BaseType*> insert(It const& begin, It const& end)
165		requires(IsNullPointer<MetadataType>)
166		{
167		auto it = begin;
168		return insert(it, end);
169		}
170
171	0	MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits>& children() { return m_children; }
172	347k	MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits> const& children() const { return m_children; }
173
174		template<typename Fn>
175		ErrorOr<void> for_each_node_in_tree_order(Fn callback) const
176		{
177		struct State {
178		bool did_generate_root { false };
179		typename MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits>::ConstIteratorType it;
180		typename MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits>::ConstIteratorType end;
181		};
182		Vector<State> state;
183		TRY(state.try_empend(false, m_children.begin(), m_children.end()));
184
185		auto invoke = [&](auto& current_node) -> ErrorOr<IterationDecision> {
186		if constexpr (VoidFunction<Fn, BaseType const&>) {
187		callback(static_cast<BaseType const&>(current_node));
188		return IterationDecision::Continue;
189		} else if constexpr (IsSpecializationOf<decltype(callback(declval<BaseType const&>())), ErrorOr>) {
190		return callback(static_cast<BaseType const&>(current_node));
191		} else if constexpr (IteratorFunction<Fn, BaseType const&>) {
192		return callback(static_cast<BaseType const&>(current_node));
193		} else {
194		static_assert(DependentFalse<Fn>, "Invalid iterator function type signature");
195		}
196		return IterationDecision::Continue;
197		};
198
199		for (auto* current_node = this; current_node != nullptr;) {
200		if (TRY(invoke(*current_node)) == IterationDecision::Break)
201		break;
202		TRY(skip_to_next_iterator(state, current_node));
203		}
204		return {};
205		}
206
207		[[nodiscard]] bool is_empty() const { return m_children.is_empty(); }
208		void clear() { m_children.clear(); }
209
210		ErrorOr<BaseType> deep_copy()
211		requires(requires(ValueType value) { { value->try_clone() } -> SpecializationOf<ErrorOr>; })
212		{
213		Trie root(TRY(m_value->try_clone()), TRY(copy_metadata(m_metadata)));
214		for (auto& it : m_children)
215		TRY(root.m_children.try_set(TRY(it.key->try_clone()), TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(TRY(it.value->deep_copy()))))));
216		return static_cast<BaseType&&>(move(root));
217		}
218
219		ErrorOr<BaseType> deep_copy()
220		{
221		Trie root(m_value, TRY(copy_metadata(m_metadata)));
222		for (auto& it : m_children)
223		TRY(root.m_children.try_set(it.key, TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(TRY(it.value->deep_copy()))))));
224		return static_cast<BaseType&&>(move(root));
225		}
226
227		private:
228		static ErrorOr<Optional<MetadataType>> copy_metadata(Optional<MetadataType> const& metadata)
229		{
230		if (!metadata.has_value())
231		return Optional<MetadataType> {};
232
233		if constexpr (requires(MetadataType t) { { t.copy() } -> SpecializationOf<ErrorOr>; })
234		return Optional<MetadataType> { TRY(metadata->copy()) };
235		#ifndef KERNEL
236		else
237		return Optional<MetadataType> { MetadataType(metadata.value()) };
238		#endif
239		}
240
241		static ErrorOr<void> skip_to_next_iterator(auto& state, auto& current_node)
242		{
243		auto& current_state = state.last();
244		if (current_state.did_generate_root)
245		++current_state.it;
246		else
247		current_state.did_generate_root = true;
248
249		if (current_state.it == current_state.end)
250		return pop_and_get_next_iterator(state, current_node);
251
252		current_node = &(current_state.it).value;
253
254		TRY(state.try_empend(false, current_node->m_children.begin(), current_node->m_children.end()));
255		return {};
256		}
257
258		static ErrorOr<void> pop_and_get_next_iterator(auto& state, auto& current_node)
259		{
260		state.take_last();
261		if (state.is_empty()) {
262		current_node = nullptr;
263		return {};
264		}
265		return skip_to_next_iterator(state, current_node);
266		}
267
268		ValueType m_value;
269		Optional<MetadataType> m_metadata;
270		MapType<ValueType, NonnullOwnPtr<Trie>, ValueTraits> m_children;
271		};
272
273		template<typename BaseType, typename DefaultBaseType, typename ValueType, typename ValueTraits, template<typename, typename, typename> typename MapType>
274		class Trie<BaseType, DefaultBaseType, ValueType, void, ValueTraits, MapType> : public Trie<BaseType, DefaultBaseType, ValueType, decltype(nullptr), ValueTraits, MapType> {
275		using Trie<BaseType, DefaultBaseType, ValueType, decltype(nullptr), ValueTraits, MapType>::Trie;
276		};
277
278		template<typename K, typename V, typename T>
279		using HashMapForTrie = HashMap<K, V, T>;
280
281		}
282
283		template<typename ValueType, typename MetadataT = void, typename ValueTraits = Traits<ValueType>, typename BaseT = void, template<typename, typename, typename> typename MapType = Detail::HashMapForTrie>
284		class Trie : public Detail::Trie<BaseT, Trie<ValueType, MetadataT, ValueTraits, void, MapType>, ValueType, MetadataT, ValueTraits, MapType> {
285		public:
286		using DetailTrie = Detail::Trie<BaseT, Trie<ValueType, MetadataT, ValueTraits, void, MapType>, ValueType, MetadataT, ValueTraits, MapType>;
287		using MetadataType = typename DetailTrie::MetadataType;
288
289		Trie(ValueType value, MetadataType metadata)
290		requires(!IsVoid<MetadataType> && !IsNullPointer<MetadataType>)
291		: DetailTrie(move(value), move(metadata))
292		{
293		}
294
295		explicit Trie(ValueType value)
296	2.52k	: DetailTrie(move(value), Optional<MetadataType> {})
297	2.52k	{
298	2.52k	}
299		};
300
301		}
302
303		#if USING_AK_GLOBALLY
304		using AK::Trie;
305		#endif