/usr/include/blasr/algorithms/anchoring/LongestIncreasingSubsequenceImpl.hpp is in libblasr-dev 0~20151014+gitbe5d1bf-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | #ifndef _BLASR_LONGEST_INCREASING_SUBSEQUENCE_IMPL_HPP_
#define _BLASR_LONGEST_INCREASING_SUBSEQUENCE_IMPL_HPP_
using namespace std;
template<typename T, typename F_IntValue>
int BinarySearch(T *x, vector<int> &m, int i, int lenM, F_IntValue IntValue) {
//
// Binary search for the largest
// j ≤ L such that X[M[j]] < X[i]
// (or set j = 0 if no such value exists)
//
//
// In English: Find the longest subsequence ending
// at some value less than X[i]. That
// way, X[i] can increase this subsequence by 1.
//
int low = 0, high = lenM, cur;
cur = (high + low) / 2;
assert(cur < m.size());
while (low < high) {
if (high == 1) {
assert(cur == 0);
return cur;
}
// The highest value is between cur and high.
if (IntValue(x[m[cur]]) < IntValue(x[i])) {
low = cur + 1;
}
else {
// x[m[cur]] is above x[i], so the highest valid value is
// strictly below cur
high = cur;
}
cur = (low + high) / 2;
}
// cur is either the last spot where x[m[cur]] < x[i], or
// the first spot where x[m[cur]] > x[i];
// Typically x[m[cur]] must be less than x[i], except on the first
// call to this, in which case x[m[cur]] == x[i] == the first element
// in the array.
if (cur == 0) {
return cur;
}
else {
return cur - 1;
}
}
template<typename T, typename F_IntValue >
int LongestIncreasingSubset(T *x, int xLength, vector<int> &subsetIndices,
vector<int> &m, vector<int> &p, F_IntValue IntValue,
int start, int end) {
//
// m[i] is the index of the LIS of length i+1
//
m.resize(xLength+1);
if (xLength == 0)
return 0;
m[0] = -1;
p.resize(xLength);
int i;
int maxM;
// On the first iteration m[0] should be set to 0.
int lenM = 1;
int mi;
for (i = 0; i < xLength; i++) {
//
// Find the index of the longest increasing subsequence ending
// before x[i]
//
maxM = BinarySearch<T,F_IntValue>(x, m, i, lenM);
//
// p is the list of back pointers.
// Create a reference for where the previous longest increasing
// subsequence that x[i] is part of.
//
p[i] = m[maxM];
//
// If this creates a LIS longer than any previously known one,
// add this to maxM.
//
if (maxM + 1 >= lenM) {
assert(maxM+1 < m.size());
m[maxM+1] = i;
if (maxM + 1>= lenM) {
// assume that lenM is never more than 2 greater than maxM.
lenM++;
}
}
//
// Otherwise, x[i] cannot create a longer LIS, BUT, if
// it is less than the current element that ends a LIS of length maxM,
// it bumps that element out from the slot of ending the LIS with
// length maxM.
//
else if (IntValue(x[i]) < IntValue(x[m[maxM+1]])) {
m[maxM+1] = i;
}
}
//
// Trace back;
//
int lisLen = lenM-1;
int lisCur = m[lisLen];
for (i = 0 ; i < lisLen and lisCur != -1; i++) {
subsetIndices.push_back(lisCur);
lisCur = p[lisCur];
}
std::reverse(subsetIndices.begin(), subsetIndices.end());
return lenM - 1;
}
template<typename T, typename F_IntValue>
int LongestIncreasingSubset(T*x, int& xLength, vector<int> &subsetIndices) {
vector<int> p;
vector<int> m;
return LongestIncreasingSubset(x, xLength, subsetIndices, m, p);
}
#endif
|