1 #include "hmbdc/Copyright.hpp" 4 #include <ext/pb_ds/assoc_container.hpp> 5 #include <ext/pb_ds/trie_policy.hpp> 11 namespace hmbdc {
namespace text {
14 namespace stringtrieset_detail {
18 using size_type = size_t;
19 using key_type = std::string;
20 using __rebind_k = std::allocator<char>::template rebind<key_type>;
21 using key_const_reference =
typename __rebind_k::other::const_reference;
22 enum { reverse =
false };
23 using const_iterator =
const char*;
24 using e_type =
const char;
27 min_e_val = __gnu_pbds::detail::__numeric_traits<char>::__min,
28 max_e_val = __gnu_pbds::detail::__numeric_traits<char>::__max,
29 max_size = max_e_val - min_e_val + 1
34 inline static const_iterator
35 begin(key_const_reference ck) {
return ck.c_str(); }
39 inline static const_iterator
40 end(key_const_reference ck) {
return ck.c_str() + ck.size(); }
43 inline static size_type
44 e_pos(e_type e) {
return static_cast<size_type
>(e - min_e_val); }
48 template<
typename Node_CItr,
55 : __gnu_pbds::detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc> {
57 using base_type = __gnu_pbds::detail::trie_policy_base<Node_CItr, Node_Itr, _ATraits, _Alloc>;
58 using node_iterator =
typename base_type::node_iterator;
59 using node_const_iterator =
typename base_type::node_const_iterator;
60 using access_traits =
typename base_type::access_traits;
61 using size_type =
typename base_type::size_type;
64 search_recursive(Node_Itr nd_it, Node_Itr end_nd_it
65 ,
typename access_traits::const_iterator b
66 ,
typename access_traits::const_iterator e
68 if (nd_it == end_nd_it) {
71 auto r = nd_it.valid_prefix();
72 auto pref_b = r.first + len;
73 auto pref_e = r.second;
75 while (pref_b != pref_e && b != e) {
82 if (pref_b != pref_e) {
86 if (b == e && nd_it.m_p_nd->m_type == 1) {
90 if (b != e && nd_it.m_p_nd->m_type == 1 && (*nd_it)->second) {
94 const size_type num_children = nd_it.num_children();
95 len = pref_b - r.first;
96 for (size_type i = 0; i < num_children; ++i) {
97 if (search_recursive(nd_it.get_child(i), end_nd_it, b, e, len)) {
106 search_wildcardly(
typename access_traits::const_iterator b
107 ,
typename access_traits::const_iterator e) {
108 Node_Itr nd_it = this->node_begin();
109 Node_Itr end_nd_it = this->node_end();
110 return search_recursive(nd_it, end_nd_it, b, e, 0);
112 void operator()(node_iterator , node_const_iterator )
const{}
116 :
private __gnu_pbds::trie<std::string, bool, stringAccessTraits, __gnu_pbds::pat_trie_tag,
117 string_wildcard_trie_search, std::allocator<char>> {
118 using Base = __gnu_pbds::trie<std::string, bool,
stringAccessTraits, __gnu_pbds::pat_trie_tag,
125 void add(std::string
const& s) {
126 if (s[s.size() - 1] ==
'*') {
127 (*this)[s.substr(0, s.size() - 1)] =
true;
133 void erase(std::string
const& s) {
134 if (s[s.size() - 1] ==
'*') {
135 Base::erase(s.substr(0, s.size() - 1));
141 bool check(
char const*b,
size_t len)
const {
142 return const_cast<StringTrieSet*
>(
this)->search_wildcardly(b, b + len);
145 bool check(std::pair<char const*, char const*>
const& str)
const {
146 return const_cast<StringTrieSet*
>(
this)->search_wildcardly(str.first, str.second);
static size_type e_pos(e_type e)
Maps an element to a position.
Definition: StringTrieSetDetail.hpp:44
Definition: TypedString.hpp:74
static const_iterator end(key_const_reference ck)
Definition: StringTrieSetDetail.hpp:40
Definition: StringTrieSetDetail.hpp:17
static const_iterator begin(key_const_reference ck)
Definition: StringTrieSetDetail.hpp:35
Definition: StringTrieSetDetail.hpp:115
Definition: StringTrieSetDetail.hpp:53