Line data Source code
1 : /**
2 : Copyright (c) 2017-2022 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : #include "SPSearchDistance.h"
25 :
26 : namespace STAPPLER_VERSIONIZED stappler::search {
27 :
28 2697800 : void Distance::Storage::Struct::set(uint8_t idx, Value value) {
29 2697800 : switch (idx) {
30 674625 : case 0: v1 = toInt(value); break;
31 674475 : case 1: v2 = toInt(value); break;
32 674425 : case 2: v3 = toInt(value); break;
33 674275 : case 3: v4 = toInt(value); break;
34 0 : default: break;
35 : }
36 2697800 : }
37 :
38 2214975 : Distance::Value Distance::Storage::Struct::get(uint8_t idx) const {
39 2214975 : switch (idx) {
40 554550 : case 0: return Value(v1); break;
41 554250 : case 1: return Value(v2); break;
42 553225 : case 2: return Value(v3); break;
43 552950 : case 3: return Value(v4); break;
44 0 : default: break;
45 : }
46 0 : return Value::Match;
47 : }
48 :
49 25 : Distance::Storage Distance::Storage::merge(const Storage &first, const Storage &last) {
50 25 : Distance::Storage ret(first);
51 25 : ret.reserve(first.size() + last.size());
52 57350 : for (size_t i = 0; i < last.size(); ++ i) {
53 57325 : ret.emplace_back(last.at(i));
54 : }
55 :
56 25 : return ret;
57 0 : }
58 :
59 650 : Distance::Storage::Storage() noexcept : _size({0, 0}) {
60 650 : new (&_array) Array();
61 650 : }
62 1100 : Distance::Storage::~Storage() noexcept {
63 1100 : if (isVecStorage()) {
64 325 : _bytes.~vector();
65 : } else {
66 775 : _array.~array();
67 : }
68 1100 : }
69 :
70 125 : Distance::Storage::Storage(const Storage &other) noexcept {
71 125 : _size = other._size;
72 125 : if (other.isVecStorage()) {
73 125 : new (&_bytes) Vec(other._bytes);
74 : } else {
75 0 : new (&_array) Array(other._array);
76 : }
77 125 : }
78 325 : Distance::Storage::Storage(Storage &&other) noexcept {
79 325 : _size = other._size;
80 325 : if (other.isVecStorage()) {
81 200 : new (&_bytes) Vec(move(other._bytes));
82 : } else {
83 125 : new (&_array) Array(other._array);
84 : }
85 325 : other.clear();
86 325 : }
87 :
88 50 : Distance::Storage &Distance::Storage::operator=(const Storage &other) noexcept {
89 50 : clear();
90 50 : if (other.isVecStorage()) {
91 50 : _array.~array();
92 50 : new (&_bytes) Vec(other._bytes);
93 : } else {
94 0 : _array = other._array;
95 : }
96 50 : _size = other._size;
97 50 : return *this;
98 : }
99 :
100 150 : Distance::Storage &Distance::Storage::operator=(Storage &&other) noexcept {
101 150 : clear();
102 150 : if (other.isVecStorage()) {
103 125 : _array.~array();
104 125 : new (&_bytes) Vec(move(other._bytes));
105 : } else {
106 25 : _array = other._array;
107 : }
108 150 : _size = other._size;
109 150 : other.clear();
110 150 : return *this;
111 : }
112 :
113 4375 : bool Distance::Storage::empty() const {
114 4375 : return _size.size == 0;
115 : }
116 :
117 61375 : size_t Distance::Storage::size() const {
118 61375 : return _size.size;
119 : }
120 :
121 25 : size_t Distance::Storage::capacity() const {
122 25 : if (isVecStorage()) {
123 25 : return _bytes.size() * 4;
124 : } else {
125 0 : return _array.size() * 4;
126 : }
127 : }
128 :
129 525 : void Distance::Storage::reserve(size_t s) {
130 525 : if (isVecStorage() && isVecStorage(s)) {
131 25 : _bytes.resize((s + 3) / 4);
132 500 : } else if (isVecStorage(s)) {
133 225 : auto tmp = _array;
134 225 : _array.~array();
135 225 : new (&_bytes) Vec();
136 225 : _bytes.resize((s + 3) / 4);
137 225 : memcpy(_bytes.data(), tmp.data(), tmp.size());
138 225 : _size.vec = 1;
139 : }
140 525 : }
141 :
142 2683525 : void Distance::Storage::emplace_back(Value val) {
143 2683525 : (isVecStorage() ? _bytes.data() : _array.data())[_size.size / 4].set(_size.size % 4, val);
144 2683525 : ++ _size.size;
145 2683525 : }
146 :
147 25 : void Distance::Storage::reverse() {
148 7150 : for (size_t i = 0; i < _size.size / 2; ++ i) {
149 7125 : auto b = at(_size.size - i - 1);
150 7125 : set(_size.size - i - 1, at(i));
151 7125 : set(i, b);
152 : }
153 25 : }
154 :
155 2214975 : Distance::Value Distance::Storage::at(size_t idx) const {
156 2214975 : return (isVecStorage() ? _bytes.data() : _array.data())[idx / 4].get(idx % 4);
157 : }
158 :
159 14275 : void Distance::Storage::set(size_t idx, Value val) {
160 14275 : (isVecStorage() ? _bytes.data() : _array.data())[idx / 4].set(idx % 4, val);
161 14275 : }
162 :
163 700 : void Distance::Storage::clear() {
164 700 : if (isVecStorage()) {
165 400 : _bytes.~vector();
166 400 : new (&_array) Array();
167 400 : _size.vec = 0;
168 : } else {
169 300 : memset(_array.data(), 0, _array.size());
170 : }
171 700 : _size.size = 0;
172 700 : }
173 :
174 4915775 : bool Distance::Storage::isVecStorage() const {
175 4915775 : return _size.vec;
176 : }
177 :
178 525 : bool Distance::Storage::isVecStorage(size_t s) const {
179 525 : return (s + 3) / 4 > sizeof(Bytes);
180 : }
181 :
182 :
183 125 : Distance::Distance() noexcept { }
184 :
185 25 : Distance::Distance(const Distance &dist) noexcept : _storage(dist._storage) { }
186 300 : Distance::Distance(Distance &&dist) noexcept : _storage(move(dist._storage)) { }
187 :
188 25 : Distance &Distance::operator=(const Distance &dist) noexcept {
189 25 : _storage = dist._storage;
190 25 : return *this;
191 : }
192 125 : Distance &Distance::operator=(Distance &&dist) noexcept {
193 125 : _storage = move(dist._storage);
194 125 : return *this;
195 : }
196 :
197 4375 : bool Distance::empty() const {
198 4375 : return _storage.empty() && _distance == 0;
199 : }
200 :
201 3925 : size_t Distance::size() const {
202 3925 : return _storage.size();
203 : }
204 :
205 2550 : int32_t Distance::diff_original(size_t pos, bool forward) const {
206 2550 : if (empty()) {
207 0 : return pos;
208 : }
209 :
210 2550 : int32_t ret = 0;
211 2550 : size_t i = 0;
212 2550 : pos = min(pos, size());
213 1950550 : for (; i < pos; ++ i) {
214 1948000 : switch (_storage.at(i)) {
215 1783550 : case Value::Match:
216 : case Value::Replace:
217 : // do nothing
218 1783550 : break;
219 1250 : case Value::Delete:
220 1250 : ++ ret;
221 1250 : break;
222 163200 : case Value::Insert:
223 163200 : -- ret;
224 163200 : break;
225 : }
226 : }
227 2550 : if (forward) {
228 1275 : while (i < size() && _storage.at(i) == Value::Delete) {
229 0 : ++ ret;
230 0 : ++ i;
231 : }
232 : }
233 2550 : return ret;
234 : }
235 :
236 50 : int32_t Distance::diff_canonical(size_t pos, bool forward) const {
237 50 : if (empty()) {
238 0 : return pos;
239 : }
240 :
241 50 : int32_t ret = 0;
242 50 : size_t i = 0;
243 50 : pos = min(pos, size());
244 107800 : for (; i < pos; ++ i) {
245 107750 : switch (_storage.at(i)) {
246 102900 : case Value::Match:
247 : case Value::Replace:
248 : // do nothing
249 102900 : break;
250 1250 : case Value::Delete:
251 1250 : -- ret;
252 1250 : break;
253 3600 : case Value::Insert:
254 3600 : ++ ret;
255 3600 : break;
256 : }
257 : }
258 50 : if (forward) {
259 25 : while (i < size() && _storage.at(i) == Value::Insert) {
260 0 : ++ ret;
261 0 : ++ i;
262 : }
263 : }
264 50 : return ret;
265 : }
266 :
267 25 : size_t Distance::nmatch() const {
268 25 : size_t ret = 0;
269 25 : size_t storageSize = _storage.size();
270 57350 : for (size_t i = 0; i < storageSize; ++ i) {
271 57325 : switch (_storage.at(i)) {
272 53875 : case Value::Match:
273 53875 : ++ ret;
274 53875 : break;
275 3450 : default:
276 3450 : break;
277 : }
278 : }
279 25 : return ret;
280 : }
281 :
282 25 : memory::string Distance::info() const {
283 25 : const auto s = _storage.size();
284 25 : memory::string ret; ret.reserve(s);
285 :
286 25 : char moveCodeToChar[] = {'=', '+', '-', 'X'};
287 :
288 25 : char lastMove = 0; // Char of last move. 0 if there was no previous move.
289 25 : int numOfSameMoves = 0;
290 14300 : for (size_t i = 0; i <= s; i++) {
291 : // if new sequence of same moves started
292 14275 : if (i == s || (moveCodeToChar[toInt(_storage.at(i))] != lastMove && lastMove != 0)) {
293 : // Write number of moves to cigar string.
294 550 : int numDigits = 0;
295 1375 : for (; numOfSameMoves; numOfSameMoves /= 10) {
296 825 : ret.push_back('0' + numOfSameMoves % 10);
297 825 : numDigits++;
298 : }
299 550 : std::reverse(ret.end() - numDigits, ret.end());
300 : // Write code of move to cigar string.
301 550 : ret.push_back(lastMove);
302 : // If not at the end, start new sequence of moves.
303 550 : if (i < s) {
304 : // Check if alignment has valid values.
305 525 : if (toInt(_storage.at(i)) > 3) {
306 0 : return memory::string();
307 : }
308 525 : numOfSameMoves = 0;
309 : }
310 : }
311 14275 : if (i < s) {
312 14250 : lastMove = moveCodeToChar[toInt(_storage.at(i))];
313 14250 : numOfSameMoves++;
314 : }
315 : }
316 :
317 25 : return ret;
318 25 : }
319 :
320 50 : Distance::Storage Distance::storage() const {
321 50 : return _storage;
322 : }
323 :
324 : }
|
