hmbdc
simplify-high-performance-messaging-programming
StringTrieSet.hpp
1 #include "hmbdc/Copyright.hpp"
2 #pragma once
3 
4 #include <ext/pb_ds/assoc_container.hpp>
5 #include <ext/pb_ds/trie_policy.hpp>
6 #include <string>
7 #include <unistd.h>
8 #include <string.h>
9 
10 
11 namespace hmbdc { namespace text {
12 
13 using namespace std;
14 
16  using size_type = size_t;
17  using key_type = std::string;
18  using __rebind_k = std::allocator<char>::template rebind<key_type>;
19  using key_const_reference = typename __rebind_k::other::const_reference;
20  enum { reverse = false };
21  using const_iterator = const char*;
22  using e_type = const char;
23 
24  enum {
25  min_e_val = __gnu_pbds::detail::__numeric_traits<char>::__min,
26  max_e_val = __gnu_pbds::detail::__numeric_traits<char>::__max,
27  max_size = max_e_val - min_e_val + 1
28  };
29 
30  /// Returns a const_iterator to the first element of
31  /// key_const_reference agumnet.
32  inline static const_iterator
33  begin(key_const_reference ck) { return ck.c_str(); }
34 
35  /// Returns a const_iterator to the after-last element of
36  /// key_const_reference argument.
37  inline static const_iterator
38  end(key_const_reference ck) { return ck.c_str() + ck.size(); }
39 
40  /// Maps an element to a position.
41  inline static size_type
42  e_pos(e_type e) { return static_cast<size_type>(e - min_e_val); }
43 
44 };
45 
46 template<typename Node_CItr,
47  typename Node_Itr,
48  typename _ATraits,
49  typename _Alloc
50 >
51 struct
53 : __gnu_pbds::detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc> {
54 private:
55  using base_type = __gnu_pbds::detail::trie_policy_base<Node_CItr, Node_Itr, _ATraits, _Alloc>;
56  using node_iterator = typename base_type::node_iterator;
57  using node_const_iterator = typename base_type::node_const_iterator;
58  using access_traits = typename base_type::access_traits;
59  using size_type = typename base_type::size_type;
60 
61  bool
62  search_recursive(Node_Itr nd_it, Node_Itr end_nd_it
63  , typename access_traits::const_iterator b
64  , typename access_traits::const_iterator e
65  , size_t len) {
66  if (nd_it == end_nd_it) {
67  return false;
68  }
69  auto r = nd_it.valid_prefix();
70  auto pref_b = r.first + len;
71  auto pref_e = r.second;
72 
73  while (pref_b != pref_e && b != e) {
74  if (*pref_b != *b) {
75  return false;
76  }
77  pref_b++;
78  b++;
79  }
80  if (pref_b != pref_e) { //already seeing mismatching
81  return false;
82  }
83 
84  if (b == e && nd_it.m_p_nd->m_type == 1) { //perfect match a leaf?
85  return true;
86  }
87 
88  if (b != e && nd_it.m_p_nd->m_type == 1 && (*nd_it)->second) { //wildcard match?
89  return true;
90  }
91 
92  const size_type num_children = nd_it.num_children();
93  len = pref_b - r.first;
94  for (size_type i = 0; i < num_children; ++i) {
95  if (search_recursive(nd_it.get_child(i), end_nd_it, b, e, len)) {
96  return true;
97  }
98  }
99  return false;
100  }
101 
102 public:
103  bool
104  search_wildcardly(typename access_traits::const_iterator b
105  , typename access_traits::const_iterator e) {
106  Node_Itr nd_it = this->node_begin();
107  Node_Itr end_nd_it = this->node_end();
108  return search_recursive(nd_it, end_nd_it, b, e, 0);
109  }
110  void operator()(node_iterator /*nd_it*/, node_const_iterator /*end_nd_it*/) const{}
111 };
112 
114 : private __gnu_pbds::trie<std::string, bool, stringAccessTraits, __gnu_pbds::pat_trie_tag,
115  string_wildcard_trie_search, std::allocator<char>> {
116  using Base = __gnu_pbds::trie<std::string, bool, stringAccessTraits, __gnu_pbds::pat_trie_tag,
117  string_wildcard_trie_search, std::allocator<char>>;
118 
119  using Base::begin;
120  using Base::end;
121 
122  void add(std::string const& s) {
123  if (s[s.size() - 1] == '*') {
124  (*this)[s.substr(0, s.size() - 1)] = true;
125  } else {
126  (*this)[s];
127  }
128  }
129 
130  auto erase(std::string const& s) {
131  if (s[s.size() - 1] == '*') {
132  return Base::erase(s.substr(0, s.size() - 1));
133  } else {
134  return Base::erase(s);
135  }
136  }
137 
138  bool check(char const*b, size_t len) const {
139  return const_cast<StringTrieSet*>(this)->search_wildcardly(b, b + len);
140  }
141 
142  bool check(std::pair<char const*, char const*> const& str) const {
143  return const_cast<StringTrieSet*>(this)->search_wildcardly(str.first, str.second);
144  }
145 
146 };
147 
148 }}
Definition: StringTrieSet.hpp:51
Definition: StringTrieSet.hpp:15
Definition: StringTrieSet.hpp:113
Definition: TypedString.hpp:74
static size_type e_pos(e_type e)
Maps an element to a position.
Definition: StringTrieSet.hpp:42
static const_iterator begin(key_const_reference ck)
Definition: StringTrieSet.hpp:33
static const_iterator end(key_const_reference ck)
Definition: StringTrieSet.hpp:38
Definition: Client.hpp:11