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
|
// Copyright 2016 Martin C. Frith
#include "SubsetMinimizerFinder.hh"
#include "CyclicSubsetSeed.hh"
namespace cbrc {
void SubsetMinimizerFinder::init(const CyclicSubsetSeed &seed,
const uchar *text,
size_t beg,
size_t end) {
const uchar *m = seed.firstMap();
while (beg < end && m[text[beg]] == CyclicSubsetSeed::DELIMITER) ++beg;
minima.assign(1, beg);
}
bool SubsetMinimizerFinder::isMinimizer(const CyclicSubsetSeed &seed,
const uchar *text,
size_t pos,
size_t end,
size_t window) {
const uchar *subsetMap = seed.firstMap();
while (true) {
size_t currentMinimum = minima[0];
if (currentMinimum > pos) return false;
if (currentMinimum == pos) return true;
size_t newPos = minima.back() + 1;
if (newPos == end) return false;
const uchar *newText = text + newPos;
if (subsetMap[*newText] == CyclicSubsetSeed::DELIMITER) {
init(seed, text, newPos + 1, end);
continue;
}
size_t stop = (newPos - currentMinimum >= window);
size_t i = minima.size();
while (i > stop) {
size_t oldPos = minima[i - 1];
const uchar *oldText = text + oldPos;
if (!seed.isLess(newText, oldText, subsetMap)) break;
--i;
}
minima.resize(i);
if (stop) minima.erase(minima.begin());
minima.push_back(newPos);
}
}
}
|
