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
|
#ifndef SEQUENCE_MATCHER_HPP
#define SEQUENCE_MATCHER_HPP
/*
Copyright © 2011-13 Qtrac Ltd. All rights reserved.
This program or module is free software: you can redistribute it
and/or modify it under the terms of the GNU General Public License
as published by the Free Software Foundation, either version 2 of
the License, or (at your option) any later version. This program is
distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
*/
#include "generic.hpp"
#include <QHash>
#include <QList>
#include <QString>
#include <QStringList>
typedef QStringList Sequence;
typedef QString Element;
class SequenceMatcher;
RangesPair computeRanges(SequenceMatcher *matcher);
RangesPair invertRanges(const Ranges &ranges1, int length1,
const Ranges &ranges2, int length2);
struct Match
{
Match(int i_=0, int j_=0, int size_=0) : i(i_), j(j_), size(size_) {}
int i;
int j;
int size;
};
// A simplified C++ implementation of Python's difflib's SequenceMatcher
class SequenceMatcher
{
public:
SequenceMatcher(const Sequence &a_=Sequence(),
const Sequence &b_=Sequence());
void set_sequences(const Sequence &a, const Sequence &b)
{ set_sequence1(a); set_sequence2(b); }
void set_sequence1(const Sequence &sequence);
void set_sequence2(const Sequence &sequence);
QList<Match> get_matching_blocks();
Match find_longest_match(int a_low, int a_high, int b_low, int b_high);
private:
void chain_b();
Sequence a;
Sequence b;
QHash<Element, QList<int> > b2j;
QList<Match> matching_blocks;
};
#endif // SEQUENCE_MATCHER_HPP
|
