-
Notifications
You must be signed in to change notification settings - Fork 0
/
ShowTransformations.h
150 lines (133 loc) · 7.21 KB
/
ShowTransformations.h
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/*
* Copyright (C) 2010 University of Tartu
* Authors: Reina Käärik, Siim Orasmaa, Kristo Tammeoja, Jaak Vilo
* Contact: siim . orasmaa {at} ut . ee
*
* This file is part of Generalized Edit Distance Tool.
*
* Generalized Edit Distance Tool 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 3 of the
* License, or (at your option) any later version.
*
* Generalized Edit Distance Tool 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.
*
* You should have received a copy of the GNU General Public License
* along with Generalized Edit Distance Tool.
* If not, see <http://www.gnu.org/licenses/>.
*
*/
#ifndef SHOWTRANSFORMATIONS_H
#define SHOWTRANSFORMATIONS_H
#include <stdio.h>
#include <string.h>
#include "Trie.h"
#include "ARTrie.h"
#include "FileToTrie.h"
#include "Transformation.h"
#include <float.h>
#include <locale.h>
// Default values for add, replace and remove operations
extern double rep;
extern double rem;
extern double add;
// -----------------------------------------------------------------------------
// Util(s)
// -----------------------------------------------------------------------------
/**
* Compares given floats and determines, whether these are approximately equal
* (with the difference being smaller than 0.000001);
* This method is to be used instead of the regular comparison \a a \c == \a b ,
* which may not work correctly ...
* http://www.cygnus-software.com/papers/comparingfloats/Comparing%20floating%20point%20numbers.htm
*/
int equalWeights(double a, double b);
// -----------------------------------------------------------------------------
// Backtracing transformations over generalised edit distance operations
// -----------------------------------------------------------------------------
/**
* Searches for transformations in "remove" trie, which can be applied
* for reaching the \a table position \c [i][j] .
* Found transformations are inserted into the \a *transF : if \a first==0
* then transformations are added to the first/root position of \a *transF , or
* to the positions parallel to the root; otherwise transformatons are added
* as neighbours of the given transformation \a *transForm .
*/
double searchPathFromRemTrie(int cols, double table[][cols], Transformation *transForm, double value, wchar_t* string, int i, int j, int first, Transformations *transF, ARTrie *remTrie);
/**
* Searches for transformations in "add" trie, which can be applied
* for reaching the \a table position \c [i][j] .
* Found transformations are inserted into the \a *transF : if \a first==0
* then transformations are added to the first/root position of \a *transF , or
* to the positions parallel to the root; otherwise transformatons are added
* as neighbours of the given transformation \a *transForm .
*/
double searchPathFromAddTrie(int cols, double table[][cols], Transformation *transForm, double value, wchar_t* string, int i, int j, int first, Transformations *transF, ARTrie *addTrie);
/**
* Searches for transformations in "replace" trie, which can be applied
* for reaching the \a table position \c [i][j] .
* Found transformations are inserted into the \a *transF : if \a first==0
* then transformations are added to the first/root position of \a *transF , or
* to the positions parallel to the root; otherwise transformatons are added
* as neighbours of the given transformation \a *transForm .
*/
double searchPathFromRepTrie(int cols, double table[][cols], double value, Transformation *transForm, wchar_t *string1, wchar_t *string2, int i, int j, int first, Transformations *transF, Trie *repTrie);
/**
* Searches a replacement from list \a *n , which matches a prefix of
* \a *string2 , and can be applied for reaching the \a table position
* \c [i][j] .
* For each found suitable replacement, inserts the transformation into
* the \a *transF : if \a first==0 then transformations are added to the
* first/root position of \a *transF , or to the positions parallel to
* the root; otherwise transformatons are added as neighbours of the given
* transformation \a *transForm .
*/
double findReplacementPath(int cols, double table[][cols], double value, Transformation *transForm, wchar_t *string2, wchar_t *left, int leftLen, EndNode *n, int i_start, int i, int j, int first, Transformations *transF);
// -----------------------------------------------------------------------------
// Backtracing the (generalized) edit distance table for transformations
// made on the best paths
// -----------------------------------------------------------------------------
/**
* Given two strings \a a and \a b , and the prefilled edit distance
* \a table , backtraces the (generalized) edit distance operations and
* constructs best paths ( series of transformations from string \a a to
* string \a b ). Transformations are inserted into \a *transF ;
*
* \param table prefilled edit distance table
* \param cols number of columns in the table
* \param a search string
* \param b text
* \param aLen length of a
* \param bLen length of b
* \param transF object for storing series of transformations
* \param remTrie trie with generalized edit distance remove operations
* \param addTrie trie with generalized edit distance add operations
* \param repTrie trie with generalized edit distance replace operations
*/
int findBestPaths(int cols, double table[][cols], wchar_t *a, wchar_t *b, int aLen, int bLen, Transformations *transF, ARTrie *remTrie, ARTrie *addTrie, Trie *repTrie);
// -----------------------------------------------------------------------------
// Printing transformations / alignments
// -----------------------------------------------------------------------------
/**
* Given two strings \a a and \a b , and the series of transformations
* between these strings \a *transF , outputs all the transformations from
* one string to another, aligned by character positions.
*
* \param a search string
* \param b text
* \param transF object storing the series of transformations from a to b
* \param caseInsensitiveMode whether the program was executed in the case insensitive mode
* \param printAlignments whether to print transformations aligned by character positions
* \param printTransWeights whether to print weights of corresponding transformations
* \param printPretty whether alignments should be outputted in a pretty-print mode
*/
int printTransformations(wchar_t *a, wchar_t *b, Transformations *transF, int caseInsensitiveMode, int printAlignments, int printTransWeights, int printPretty);
/**
* Prints \a *thisStr in a pretty-print manner, padding it with spaces if it is
* shorter than \a *otherStr .
*/
int prettyPrint(wchar_t *thisStr, wchar_t *otherStr);
#endif