Swiftdiff options
Diffstat (limited to 'Swift/Controllers/Roster/LeastCommonSubsequence.h')
| -rw-r--r-- | Swift/Controllers/Roster/LeastCommonSubsequence.h | 173 |
1 files changed, 87 insertions, 86 deletions
diff --git a/Swift/Controllers/Roster/LeastCommonSubsequence.h b/Swift/Controllers/Roster/LeastCommonSubsequence.h index 0b5aa0a..8daa20c 100644 --- a/Swift/Controllers/Roster/LeastCommonSubsequence.h +++ b/Swift/Controllers/Roster/LeastCommonSubsequence.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2011-2013 Isode Limited. + * Copyright (c) 2011-2016 Isode Limited. * All rights reserved. * See the COPYING file for more information. */ @@ -7,101 +7,102 @@ #pragma once #include <vector> + #include <boost/numeric/conversion/cast.hpp> namespace Swift { - using std::equal_to; + 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); + 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; - } + // 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)]); - } - } - } - } + // 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; + 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 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; - } + // 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 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); + // 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; - } - } - } + // 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; + } + } + } } |