1 #ifndef SEQUENCE_MATCHER_HPP 2 #define SEQUENCE_MATCHER_HPP 3 /* 4 Copyright © 2011-13 Qtrac Ltd. All rights reserved. 5 This program or module is free software: you can redistribute it 6 and/or modify it under the terms of the GNU General Public License 7 as published by the Free Software Foundation, either version 2 of 8 the License, or (at your option) any later version. This program is 9 distributed in the hope that it will be useful, but WITHOUT ANY 10 WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 for more details. 13 */ 14 15 #include "generic.hpp" 16 #include <QHash> 17 #include <QList> 18 #include <QString> 19 #include <QStringList> 20 21 typedef QStringList Sequence; 22 typedef QString Element; 23 24 class SequenceMatcher; 25 26 RangesPair computeRanges(SequenceMatcher *matcher); 27 RangesPair invertRanges(const Ranges &ranges1, int length1, 28 const Ranges &ranges2, int length2); 29 30 struct Match 31 { MatchMatch32 Match(int i_=0, int j_=0, int size_=0) : i(i_), j(j_), size(size_) {} 33 34 int i; 35 int j; 36 int size; 37 }; 38 39 40 // A simplified C++ implementation of Python's difflib's SequenceMatcher 41 class SequenceMatcher 42 { 43 public: 44 SequenceMatcher(const Sequence &a_=Sequence(), 45 const Sequence &b_=Sequence()); 46 set_sequences(const Sequence & a,const Sequence & b)47 void set_sequences(const Sequence &a, const Sequence &b) 48 { set_sequence1(a); set_sequence2(b); } 49 void set_sequence1(const Sequence &sequence); 50 void set_sequence2(const Sequence &sequence); 51 52 QList<Match> get_matching_blocks(); 53 Match find_longest_match(int a_low, int a_high, int b_low, int b_high); 54 55 private: 56 void chain_b(); 57 58 Sequence a; 59 Sequence b; 60 QHash<Element, QList<int> > b2j; 61 QList<Match> matching_blocks; 62 }; 63 64 #endif // SEQUENCE_MATCHER_HPP 65