Debian Codegraph @

src/perfect-hashing/frozen/algorithm.h

raw
1 /*
2 * Frozen
3 * Copyright 2016 QuarksLab
4 *
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 */
22
23 #ifndef FROZEN_LETITGO_ALGORITHM_H
24 #define FROZEN_LETITGO_ALGORITHM_H
25
26 #include "frozen/bits/basic_types.h"
27 #include "frozen/bits/version.h"
28 #include "frozen/string.h"
29
30 namespace frozen {
31
32 // 'search' implementation if C++17 is not available
33 // https://en.cppreference.com/w/cpp/algorithm/search
34 template <class ForwardIterator, class Searcher>
35 ForwardIterator
36 search(ForwardIterator first, ForwardIterator last, const Searcher &searcher) {
37 return searcher(first, last).first;
38 }
39
40 // text book implementation from
41 // https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
42
43 template <std::size_t size> class knuth_morris_pratt_searcher {
44 bits::carray<std::ptrdiff_t, size> step_;
45 bits::carray<char, size> needle_;
46
47 static constexpr bits::carray<std::ptrdiff_t, size>
48 build_kmp_cache(char const (&needle)[size + 1]) {
49 std::ptrdiff_t cnd = 0;
50 bits::carray<std::ptrdiff_t, size> cache;
51
52 cache.fill(-1);
53 for (std::size_t pos = 1; pos < size; ++pos) {
54 if (needle[pos] == needle[cnd]) {
55 cache[pos] = cache[cnd];
56 cnd += 1;
57 } else {
58 cache[pos] = cnd;
59 cnd = cache[cnd];
60 while (cnd >= 0 && needle[pos] != needle[cnd]) cnd = cache[cnd];
61 cnd += 1;
62 }
63 }
64 return cache;
65 }
66
67 public:
68 constexpr knuth_morris_pratt_searcher(char const (&needle)[size + 1]) : step_{build_kmp_cache(needle)}, needle_(needle) {}
69
70 template <class ForwardIterator>
71 constexpr std::pair<ForwardIterator, ForwardIterator>
72 operator()(ForwardIterator first, ForwardIterator last) const {
73 std::size_t i = 0;
74 ForwardIterator iter = first;
75 while (iter != last) {
76 if (needle_[i] == *iter) {
77 if (i == (size - 1)) return {iter - i, iter - i + size};
78 ++i;
79 ++iter;
80 } else {
81 if (step_[i] > -1) {
82 i = step_[i];
83 } else {
84 ++iter;
85 i = 0;
86 }
87 }
88 }
89 return {last, last};
90 }
91 };
92
93 template <std::size_t N>
94 constexpr knuth_morris_pratt_searcher<N - 1>
95 make_knuth_morris_pratt_searcher(char const (&needle)[N]) {
96 return {needle};
97 }
98
99 // text book implementation from
100 // https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
101
102 template <std::size_t size> class boyer_moore_searcher {
103 using skip_table_type = bits::carray<std::ptrdiff_t, sizeof(char) << 8>;
104 using suffix_table_type = bits::carray<std::ptrdiff_t, size>;
105
106 skip_table_type skip_table_;
107 suffix_table_type suffix_table_;
108 bits::carray<char, size> needle_;
109
110 constexpr auto
111 build_skip_table(char const (&needle)[size + 1]) {
112 skip_table_type skip_table;
113
114 skip_table.fill(size);
115 for (std::size_t i = 0; i < size - 1; ++i) skip_table[needle[i]] -= i + 1;
116 return skip_table;
117 }
118
119 constexpr bool
120 is_prefix(char const (&needle)[size + 1], std::size_t pos) {
121 std::size_t suffixlen = size - pos;
122
123 for (std::size_t i = 0; i < suffixlen; i++) {
124 if (needle[i] != needle[pos + i]) return false;
125 }
126 return true;
127 }
128
129 constexpr std::size_t
130 suffix_length(char const (&needle)[size + 1], std::size_t pos) {
131 // increment suffix length slen to the first mismatch or beginning
132 // of the word
133 for (std::size_t slen = 0; slen < pos; slen++)
134 if (needle[pos - slen] != needle[size - 1 - slen]) return slen;
135
136 return pos;
137 }
138
139 constexpr auto
140 build_suffix_table(char const (&needle)[size + 1]) {
141 suffix_table_type suffix;
142 std::ptrdiff_t last_prefix_index = size - 1;
143
144 // first loop
145 for (std::ptrdiff_t p = size - 1; p >= 0; p--) {
146 if (is_prefix(needle, p + 1)) last_prefix_index = p + 1;
147
148 suffix[p] = last_prefix_index + (size - 1 - p);
149 }
150
151 // second loop
152 for (std::size_t p = 0; p < size - 1; p++) {
153 auto slen = suffix_length(needle, p);
154 if (needle[p - slen] != needle[size - 1 - slen]) suffix[size - 1 - slen] = size - 1 - p + slen;
155 }
156 return suffix;
157 }
158
159 public:
160 constexpr boyer_moore_searcher(char const (&needle)[size + 1])
161 : skip_table_{build_skip_table(needle)}, suffix_table_{build_suffix_table(needle)}, needle_(needle) {}
162
163 template <class ForwardIterator>
164 constexpr std::pair<ForwardIterator, ForwardIterator>
165 operator()(ForwardIterator first, ForwardIterator last) const {
166 if (size == 0) return {first, first + size};
167
168 ForwardIterator iter = first + size - 1;
169 while (iter < last) {
170 std::ptrdiff_t j = size - 1;
171 while (j > 0 && (*iter == needle_[j])) {
172 --iter;
173 --j;
174 }
175 if (*iter == needle_[0]) return {iter, iter + size};
176
177 iter += std::max(skip_table_[*iter], suffix_table_[j]);
178 }
179 return {last, last + size};
180 }
181 };
182
183 template <std::size_t N>
184 constexpr boyer_moore_searcher<N - 1>
185 make_boyer_moore_searcher(char const (&needle)[N]) {
186 return {needle};
187 }
188
189 } // namespace frozen
190
191 #endif