1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
/*
* Copyright (c) 2011-2013 Isode Limited.
* All rights reserved.
* See the COPYING file for more information.
*/
#pragma once
#include <vector>
#include <boost/numeric/conversion/cast.hpp>
namespace Swift {
using std::equal_to;
namespace Detail {
template<typename XIt, typename YIt, typename Length, typename Predicate>
void computeLeastCommonSubsequenceMatrix(XIt xBegin, XIt xEnd, YIt yBegin, YIt yEnd, std::vector<Length>& result) {
size_t width = static_cast<size_t>(std::distance(xBegin, xEnd) + 1);
size_t height = static_cast<size_t>(std::distance(yBegin, yEnd) + 1);
result.resize(width * height);
// Initialize first row & column
for (size_t i = 0; i < width; ++i) {
result[i] = 0;
}
for (size_t j = 0; j < height; ++j) {
result[j*width] = 0;
}
// Compute the LCS lengths for subsets
Predicate predicate;
for (size_t i = 1; i < width; ++i) {
for (size_t j = 1; j < height; ++j) {
result[i + j*width] = predicate(*(xBegin + boost::numeric_cast<long long>(i)-1), *(yBegin + boost::numeric_cast<long long >(j)-1)) ? result[(i-1) + (j-1)*width] + 1 : std::max(result[i + (j-1)*width], result[i-1 + (j*width)]);
}
}
}
}
template<typename X, typename InsertRemovePredicate, typename UpdatePredicate>
void computeIndexDiff(const std::vector<X>& x, const std::vector<X>& y, std::vector<size_t>& updates, std::vector<size_t>& postUpdates, std::vector<size_t>& removes, std::vector<size_t>& inserts) {
InsertRemovePredicate insertRemovePredicate;
UpdatePredicate updatePredicate;
// Find & handle common prefix (Optimization to reduce LCS matrix size)
typename std::vector<X>::const_iterator xBegin = x.begin();
typename std::vector<X>::const_iterator yBegin = y.begin();
while (xBegin < x.end() && yBegin < y.end() && insertRemovePredicate(*xBegin, *yBegin)) {
if (updatePredicate(*xBegin, *yBegin)) {
updates.push_back(static_cast<size_t>(std::distance(x.begin(), xBegin)));
postUpdates.push_back(static_cast<size_t>(std::distance(y.begin(), yBegin)));
}
++xBegin;
++yBegin;
}
size_t prefixLength = static_cast<size_t>(std::distance(x.begin(), xBegin));
// Find & handle common suffix (Optimization to reduce LCS matrix size)
typename std::vector<X>::const_reverse_iterator xEnd = x.rbegin();
typename std::vector<X>::const_reverse_iterator yEnd = y.rbegin();
while (xEnd.base() > xBegin && yEnd.base() > yBegin && insertRemovePredicate(*xEnd, *yEnd)) {
if (updatePredicate(*xEnd, *yEnd)) {
updates.push_back(static_cast<size_t>(std::distance(x.begin(), xEnd.base()) - 1));
postUpdates.push_back(static_cast<size_t>(std::distance(y.begin(), yEnd.base()) - 1));
}
++xEnd;
++yEnd;
}
// Compute lengths
size_t xLength = static_cast<size_t>(std::distance(xBegin, xEnd.base()));
size_t yLength = static_cast<size_t>(std::distance(yBegin, yEnd.base()));
// Compute LCS matrix
std::vector<unsigned int> lcs;
Detail::computeLeastCommonSubsequenceMatrix<typename std::vector<X>::const_iterator, typename std::vector<X>::const_iterator, unsigned int, InsertRemovePredicate>(xBegin, xEnd.base(), yBegin, yEnd.base(), lcs);
// Process LCS matrix
size_t i = xLength;
size_t j = yLength;
size_t width = xLength + 1;
while (true) {
if (i > 0 && j > 0 && insertRemovePredicate(x[prefixLength + i-1], y[prefixLength + j-1])) {
// x[i-1] same
if (updatePredicate(x[prefixLength + i - 1], y[prefixLength + j - 1])) {
updates.push_back(prefixLength + i-1);
postUpdates.push_back(prefixLength + j-1);
}
i -= 1;
j -= 1;
}
else if (j > 0 && (i == 0 || lcs[i + (j-1)*width] >= lcs[i-1 + j*width])) {
// y[j-1] added
inserts.push_back(prefixLength + j-1);
j -= 1;
}
else if (i > 0 && (j == 0 || lcs[i + (j-1)*width] < lcs[i-1 + j*width])) {
// x[i-1] removed
removes.push_back(prefixLength + i-1);
i -= 1;
}
else {
break;
}
}
}
}
|
Swift