hmbdc
simplify-high-performance-messaging-programming
StringTrieSetDetail.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 
14 namespace stringtrieset_detail {
15 using namespace std;
16 
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;
25 
26  enum {
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
30  };
31 
32  /// Returns a const_iterator to the first element of
33  /// key_const_reference agumnet.
34  inline static const_iterator
35  begin(key_const_reference ck) { return ck.c_str(); }
36 
37  /// Returns a const_iterator to the after-last element of
38  /// key_const_reference argument.
39  inline static const_iterator
40  end(key_const_reference ck) { return ck.c_str() + ck.size(); }
41 
42  /// Maps an element to a position.
43  inline static size_type
44  e_pos(e_type e) { return static_cast<size_type>(e - min_e_val); }
45 
46 };
47 
48 template<typename Node_CItr,
49  typename Node_Itr,
50  typename _ATraits,
51  typename _Alloc
52 >
53 struct
55 : __gnu_pbds::detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc> {
56 private:
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;
62 
63  bool
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
67  , size_t len) {
68  if (nd_it == end_nd_it) {
69  return false;
70  }
71  auto r = nd_it.valid_prefix();
72  auto pref_b = r.first + len;
73  auto pref_e = r.second;
74 
75  while (pref_b != pref_e && b != e) {
76  if (*pref_b != *b) {
77  return false;
78  }
79  pref_b++;
80  b++;
81  }
82  if (pref_b != pref_e) { //already seeing mismatching
83  return false;
84  }
85 
86  if (b == e && nd_it.m_p_nd->m_type == 1) { //perfect match a leaf?
87  return true;
88  }
89 
90  if (b != e && nd_it.m_p_nd->m_type == 1 && (*nd_it)->second) { //wildcard match?
91  return true;
92  }
93 
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)) {
98  return true;
99  }
100  }
101  return false;
102  }
103 
104 public:
105  bool
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);
111  }
112  void operator()(node_iterator /*nd_it*/, node_const_iterator /*end_nd_it*/) const{}
113 };
114 
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,
119  string_wildcard_trie_search, std::allocator<char>>;
120 
121  using Base::begin;
122  using Base::end;
123  using Base::size;
124 
125  void add(std::string const& s) {
126  if (s[s.size() - 1] == '*') {
127  (*this)[s.substr(0, s.size() - 1)] = true;
128  } else {
129  (*this)[s];
130  }
131  }
132 
133  void erase(std::string const& s) {
134  if (s[s.size() - 1] == '*') {
135  Base::erase(s.substr(0, s.size() - 1));
136  } else {
137  Base::erase(s);
138  }
139  }
140 
141  bool check(char const*b, size_t len) const {
142  return const_cast<StringTrieSet*>(this)->search_wildcardly(b, b + len);
143  }
144 
145  bool check(std::pair<char const*, char const*> const& str) const {
146  return const_cast<StringTrieSet*>(this)->search_wildcardly(str.first, str.second);
147  }
148 
149 };
150 
151 } //stringtrieset_detail
152 }}
153 
154 
155 
156 
static size_type e_pos(e_type e)
Maps an element to a position.
Definition: StringTrieSetDetail.hpp:44
Definition: Topic.hpp:44
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: Base.hpp:13