Mercurial > hg > octave-kai > gnulib-hg
annotate lib/diffseq.h @ 12331:dfb465b19291
diffseq: reduce scope of variable 'best'.
author | Bruno Haible <bruno@clisp.org> |
---|---|
date | Sat, 21 Nov 2009 14:37:46 +0100 (2009-11-21) |
parents | de232f8c8d7f |
children | 911f28ebb9c4 |
rev | line source |
---|---|
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
1 /* Analyze differences between two vectors. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
2 |
12331
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
3 Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2009 Free |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
4 Software Foundation, Inc. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
5 |
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
9149
diff
changeset
|
6 This program is free software: you can redistribute it and/or modify |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
7 it under the terms of the GNU General Public License as published by |
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
9149
diff
changeset
|
8 the Free Software Foundation; either version 3 of the License, or |
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
9149
diff
changeset
|
9 (at your option) any later version. |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
10 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
11 This program is distributed in the hope that it will be useful, |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
12 but WITHOUT ANY WARRANTY; without even the implied warranty of |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
14 GNU General Public License for more details. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
15 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
16 You should have received a copy of the GNU General Public License |
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
9149
diff
changeset
|
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
18 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
19 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
20 /* The basic idea is to consider two vectors as similar if, when |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
21 transforming the first vector into the second vector through a |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
22 sequence of edits (inserts and deletes of one element each), |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
23 this sequence is short - or equivalently, if the ordered list |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
24 of elements that are untouched by these edits is long. For a |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
25 good introduction to the subject, read about the "Levenshtein |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
26 distance" in Wikipedia. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
27 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
28 The basic algorithm is described in: |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
29 "An O(ND) Difference Algorithm and its Variations", Eugene Myers, |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
30 Algorithmica Vol. 1 No. 2, 1986, pp. 251-266; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
31 see especially section 4.2, which describes the variation used below. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
32 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
33 The basic algorithm was independently discovered as described in: |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
34 "Algorithms for Approximate String Matching", E. Ukkonen, |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
35 Information and Control Vol. 64, 1985, pp. 100-118. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
36 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
37 Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
38 heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
39 at the price of producing suboptimal output for large inputs with |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
40 many differences. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
41 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
42 /* Before including this file, you need to define: |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
43 ELEMENT The element type of the vectors being compared. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
44 EQUAL A two-argument macro that tests two elements for |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
45 equality. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
46 OFFSET A signed integer type sufficient to hold the |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
47 difference between two indices. Usually |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
48 something like ssize_t. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
49 EXTRA_CONTEXT_FIELDS Declarations of fields for 'struct context'. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
50 NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff]. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
51 NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff]. |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
52 EARLY_ABORT(ctxt) (Optional) A boolean expression that triggers an |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
53 early abort of the computation. |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
54 USE_HEURISTIC (Optional) Define if you want to support the |
9669
8b484b0c3ae6
Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
55 heuristic for large vectors. |
8b484b0c3ae6
Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
56 Before including this file, you also need to include: |
8b484b0c3ae6
Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
57 #include <limits.h> |
8b484b0c3ae6
Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
58 #include <stdbool.h> |
8b484b0c3ae6
Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
59 #include "minmax.h" |
8b484b0c3ae6
Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
60 */ |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
61 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
62 /* Maximum value of type OFFSET. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
63 #define OFFSET_MAX \ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
64 ((((OFFSET)1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
65 |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
66 /* Default to no early abort. */ |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
67 #ifndef EARLY_ABORT |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
68 # define EARLY_ABORT(ctxt) false |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
69 #endif |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
70 |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
71 /* Use this to suppress gcc's `...may be used before initialized' warnings. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
72 #ifndef IF_LINT |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
73 # ifdef lint |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
74 # define IF_LINT(Code) Code |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
75 # else |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
76 # define IF_LINT(Code) /* empty */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
77 # endif |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
78 #endif |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
79 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
80 /* |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
81 * Context of comparison operation. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
82 */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
83 struct context |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
84 { |
9149 | 85 /* Vectors being compared. */ |
9685
2858c91c7452
Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents:
9669
diff
changeset
|
86 ELEMENT const *xvec; |
2858c91c7452
Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents:
9669
diff
changeset
|
87 ELEMENT const *yvec; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
88 |
9149 | 89 /* Extra fields. */ |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
90 EXTRA_CONTEXT_FIELDS |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
91 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
92 /* Vector, indexed by diagonal, containing 1 + the X coordinate of the point |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
93 furthest along the given diagonal in the forward search of the edit |
9149 | 94 matrix. */ |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
95 OFFSET *fdiag; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
96 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
97 /* Vector, indexed by diagonal, containing the X coordinate of the point |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
98 furthest along the given diagonal in the backward search of the edit |
9149 | 99 matrix. */ |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
100 OFFSET *bdiag; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
101 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
102 #ifdef USE_HEURISTIC |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
103 /* This corresponds to the diff -H flag. With this heuristic, for |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
104 vectors with a constant small density of changes, the algorithm is |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
105 linear in the vectors size. */ |
9149 | 106 bool heuristic; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
107 #endif |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
108 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
109 /* Edit scripts longer than this are too expensive to compute. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
110 OFFSET too_expensive; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
111 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
112 /* Snakes bigger than this are considered `big'. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
113 #define SNAKE_LIMIT 20 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
114 }; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
115 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
116 struct partition |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
117 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
118 /* Midpoints of this partition. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
119 OFFSET xmid; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
120 OFFSET ymid; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
121 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
122 /* True if low half will be analyzed minimally. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
123 bool lo_minimal; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
124 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
125 /* Likewise for high half. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
126 bool hi_minimal; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
127 }; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
128 |
9149 | 129 |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
130 /* Find the midpoint of the shortest edit script for a specified portion |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
131 of the two vectors. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
132 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
133 Scan from the beginnings of the vectors, and simultaneously from the ends, |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
134 doing a breadth-first search through the space of edit-sequence. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
135 When the two searches meet, we have found the midpoint of the shortest |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
136 edit sequence. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
137 |
9149 | 138 If FIND_MINIMAL is true, find the minimal edit script regardless of |
139 expense. Otherwise, if the search is too expensive, use heuristics to | |
140 stop the search and report a suboptimal answer. | |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
141 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
142 Set PART->(xmid,ymid) to the midpoint (XMID,YMID). The diagonal number |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
143 XMID - YMID equals the number of inserted elements minus the number |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
144 of deleted elements (counting only elements before the midpoint). |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
145 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
146 Set PART->lo_minimal to true iff the minimal edit script for the |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
147 left half of the partition is known; similarly for PART->hi_minimal. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
148 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
149 This function assumes that the first elements of the specified portions |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
150 of the two vectors do not match, and likewise that the last elements do not |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
151 match. The caller must trim matching elements from the beginning and end |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
152 of the portions it is going to specify. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
153 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
154 If we return the "wrong" partitions, the worst this can do is cause |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
155 suboptimal diff output. It cannot cause incorrect diff output. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
156 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
157 static void |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
158 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal, |
9149 | 159 struct partition *part, struct context *ctxt) |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
160 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
161 OFFSET *const fd = ctxt->fdiag; /* Give the compiler a chance. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
162 OFFSET *const bd = ctxt->bdiag; /* Additional help for the compiler. */ |
9685
2858c91c7452
Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents:
9669
diff
changeset
|
163 ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */ |
2858c91c7452
Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents:
9669
diff
changeset
|
164 ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */ |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
165 const OFFSET dmin = xoff - ylim; /* Minimum valid diagonal. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
166 const OFFSET dmax = xlim - yoff; /* Maximum valid diagonal. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
167 const OFFSET fmid = xoff - yoff; /* Center diagonal of top-down search. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
168 const OFFSET bmid = xlim - ylim; /* Center diagonal of bottom-up search. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
169 OFFSET fmin = fmid; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
170 OFFSET fmax = fmid; /* Limits of top-down search. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
171 OFFSET bmin = bmid; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
172 OFFSET bmax = bmid; /* Limits of bottom-up search. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
173 OFFSET c; /* Cost. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
174 bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
175 diagonal with respect to the northwest. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
176 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
177 fd[fmid] = xoff; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
178 bd[bmid] = xlim; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
179 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
180 for (c = 1;; ++c) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
181 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
182 OFFSET d; /* Active diagonal. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
183 bool big_snake = false; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
184 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
185 /* Extend the top-down search by an edit step in each diagonal. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
186 if (fmin > dmin) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
187 fd[--fmin - 1] = -1; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
188 else |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
189 ++fmin; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
190 if (fmax < dmax) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
191 fd[++fmax + 1] = -1; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
192 else |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
193 --fmax; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
194 for (d = fmax; d >= fmin; d -= 2) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
195 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
196 OFFSET x; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
197 OFFSET y; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
198 OFFSET tlo = fd[d - 1]; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
199 OFFSET thi = fd[d + 1]; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
200 OFFSET x0 = tlo < thi ? thi : tlo + 1; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
201 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
202 for (x = x0, y = x0 - d; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
203 x < xlim && y < ylim && EQUAL (xv[x], yv[y]); |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
204 x++, y++) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
205 continue; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
206 if (x - x0 > SNAKE_LIMIT) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
207 big_snake = true; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
208 fd[d] = x; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
209 if (odd && bmin <= d && d <= bmax && bd[d] <= x) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
210 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
211 part->xmid = x; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
212 part->ymid = y; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
213 part->lo_minimal = part->hi_minimal = true; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
214 return; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
215 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
216 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
217 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
218 /* Similarly extend the bottom-up search. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
219 if (bmin > dmin) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
220 bd[--bmin - 1] = OFFSET_MAX; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
221 else |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
222 ++bmin; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
223 if (bmax < dmax) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
224 bd[++bmax + 1] = OFFSET_MAX; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
225 else |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
226 --bmax; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
227 for (d = bmax; d >= bmin; d -= 2) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
228 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
229 OFFSET x; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
230 OFFSET y; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
231 OFFSET tlo = bd[d - 1]; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
232 OFFSET thi = bd[d + 1]; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
233 OFFSET x0 = tlo < thi ? tlo : thi - 1; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
234 |
9149 | 235 for (x = x0, y = x0 - d; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
236 xoff < x && yoff < y && EQUAL (xv[x - 1], yv[y - 1]); |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
237 x--, y--) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
238 continue; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
239 if (x0 - x > SNAKE_LIMIT) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
240 big_snake = true; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
241 bd[d] = x; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
242 if (!odd && fmin <= d && d <= fmax && x <= fd[d]) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
243 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
244 part->xmid = x; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
245 part->ymid = y; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
246 part->lo_minimal = part->hi_minimal = true; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
247 return; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
248 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
249 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
250 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
251 if (find_minimal) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
252 continue; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
253 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
254 #ifdef USE_HEURISTIC |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
255 /* Heuristic: check occasionally for a diagonal that has made lots |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
256 of progress compared with the edit distance. If we have any |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
257 such, find the one that has made the most progress and return it |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
258 as if it had succeeded. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
259 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
260 With this heuristic, for vectors with a constant small density |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
261 of changes, the algorithm is linear in the vector size. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
262 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
263 if (200 < c && big_snake && ctxt->heuristic) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
264 { |
12331
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
265 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
266 OFFSET best = 0; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
267 |
12331
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
268 for (d = fmax; d >= fmin; d -= 2) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
269 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
270 OFFSET dd = d - fmid; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
271 OFFSET x = fd[d]; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
272 OFFSET y = x - d; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
273 OFFSET v = (x - xoff) * 2 - dd; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
274 |
12331
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
275 if (v > 12 * (c + (dd < 0 ? -dd : dd))) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
276 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
277 if (v > best |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
278 && xoff + SNAKE_LIMIT <= x && x < xlim |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
279 && yoff + SNAKE_LIMIT <= y && y < ylim) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
280 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
281 /* We have a good enough best diagonal; now insist |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
282 that it end with a significant snake. */ |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
283 int k; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
284 |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
285 for (k = 1; EQUAL (xv[x - k], yv[y - k]); k++) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
286 if (k == SNAKE_LIMIT) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
287 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
288 best = v; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
289 part->xmid = x; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
290 part->ymid = y; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
291 break; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
292 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
293 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
294 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
295 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
296 if (best > 0) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
297 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
298 part->lo_minimal = true; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
299 part->hi_minimal = false; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
300 return; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
301 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
302 } |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
303 |
12331
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
304 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
305 OFFSET best = 0; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
306 |
12331
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
307 for (d = bmax; d >= bmin; d -= 2) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
308 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
309 OFFSET dd = d - bmid; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
310 OFFSET x = bd[d]; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
311 OFFSET y = x - d; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
312 OFFSET v = (xlim - x) * 2 + dd; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
313 |
12331
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
314 if (v > 12 * (c + (dd < 0 ? -dd : dd))) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
315 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
316 if (v > best |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
317 && xoff < x && x <= xlim - SNAKE_LIMIT |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
318 && yoff < y && y <= ylim - SNAKE_LIMIT) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
319 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
320 /* We have a good enough best diagonal; now insist |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
321 that it end with a significant snake. */ |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
322 int k; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
323 |
12331
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
324 for (k = 0; EQUAL (xv[x + k], yv[y + k]); k++) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
325 if (k == SNAKE_LIMIT - 1) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
326 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
327 best = v; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
328 part->xmid = x; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
329 part->ymid = y; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
330 break; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
331 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
332 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
333 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
334 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
335 if (best > 0) |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
336 { |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
337 part->lo_minimal = false; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
338 part->hi_minimal = true; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
339 return; |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
340 } |
dfb465b19291
diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents:
12330
diff
changeset
|
341 } |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
342 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
343 #endif /* USE_HEURISTIC */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
344 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
345 /* Heuristic: if we've gone well beyond the call of duty, give up |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
346 and report halfway between our best results so far. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
347 if (c >= ctxt->too_expensive) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
348 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
349 OFFSET fxybest; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
350 OFFSET fxbest IF_LINT (= 0); |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
351 OFFSET bxybest; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
352 OFFSET bxbest IF_LINT (= 0); |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
353 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
354 /* Find forward diagonal that maximizes X + Y. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
355 fxybest = -1; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
356 for (d = fmax; d >= fmin; d -= 2) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
357 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
358 OFFSET x = MIN (fd[d], xlim); |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
359 OFFSET y = x - d; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
360 if (ylim < y) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
361 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
362 x = ylim + d; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
363 y = ylim; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
364 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
365 if (fxybest < x + y) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
366 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
367 fxybest = x + y; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
368 fxbest = x; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
369 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
370 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
371 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
372 /* Find backward diagonal that minimizes X + Y. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
373 bxybest = OFFSET_MAX; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
374 for (d = bmax; d >= bmin; d -= 2) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
375 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
376 OFFSET x = MAX (xoff, bd[d]); |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
377 OFFSET y = x - d; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
378 if (y < yoff) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
379 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
380 x = yoff + d; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
381 y = yoff; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
382 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
383 if (x + y < bxybest) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
384 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
385 bxybest = x + y; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
386 bxbest = x; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
387 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
388 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
389 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
390 /* Use the better of the two diagonals. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
391 if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff)) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
392 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
393 part->xmid = fxbest; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
394 part->ymid = fxybest - fxbest; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
395 part->lo_minimal = true; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
396 part->hi_minimal = false; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
397 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
398 else |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
399 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
400 part->xmid = bxbest; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
401 part->ymid = bxybest - bxbest; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
402 part->lo_minimal = false; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
403 part->hi_minimal = true; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
404 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
405 return; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
406 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
407 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
408 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
409 |
9149 | 410 |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
411 /* Compare in detail contiguous subsequences of the two vectors |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
412 which are known, as a whole, to match each other. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
413 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
414 The subsequence of vector 0 is [XOFF, XLIM) and likewise for vector 1. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
415 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
416 Note that XLIM, YLIM are exclusive bounds. All indices into the vectors |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
417 are origin-0. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
418 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
419 If FIND_MINIMAL, find a minimal difference no matter how |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
420 expensive it is. |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
421 |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
422 The results are recorded by invoking NOTE_DELETE and NOTE_INSERT. |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
423 |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
424 Return false if terminated normally, or true if terminated through early |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
425 abort. */ |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
426 |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
427 static bool |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
428 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, |
9149 | 429 bool find_minimal, struct context *ctxt) |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
430 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
431 ELEMENT const *xv = ctxt->xvec; /* Help the compiler. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
432 ELEMENT const *yv = ctxt->yvec; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
433 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
434 /* Slide down the bottom initial diagonal. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
435 while (xoff < xlim && yoff < ylim && EQUAL (xv[xoff], yv[yoff])) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
436 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
437 xoff++; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
438 yoff++; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
439 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
440 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
441 /* Slide up the top initial diagonal. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
442 while (xoff < xlim && yoff < ylim && EQUAL (xv[xlim - 1], yv[ylim - 1])) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
443 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
444 xlim--; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
445 ylim--; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
446 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
447 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
448 /* Handle simple cases. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
449 if (xoff == xlim) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
450 while (yoff < ylim) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
451 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
452 NOTE_INSERT (ctxt, yoff); |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
453 if (EARLY_ABORT (ctxt)) |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
454 return true; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
455 yoff++; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
456 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
457 else if (yoff == ylim) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
458 while (xoff < xlim) |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
459 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
460 NOTE_DELETE (ctxt, xoff); |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
461 if (EARLY_ABORT (ctxt)) |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
462 return true; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
463 xoff++; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
464 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
465 else |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
466 { |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
467 struct partition part; |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
468 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
469 /* Find a point of correspondence in the middle of the vectors. */ |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
470 diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt); |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
471 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
472 /* Use the partitions to split this problem into subproblems. */ |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
473 if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt)) |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
474 return true; |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
475 if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt)) |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
476 return true; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
477 } |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
478 |
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
479 return false; |
9147
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
480 } |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
481 |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
482 #undef ELEMENT |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
483 #undef EQUAL |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
484 #undef OFFSET |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
485 #undef EXTRA_CONTEXT_FIELDS |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
486 #undef NOTE_DELETE |
d5c437e55b50
* MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff
changeset
|
487 #undef NOTE_INSERT |
10436
74c36e9e4884
Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents:
9685
diff
changeset
|
488 #undef EARLY_ABORT |
9149 | 489 #undef USE_HEURISTIC |
490 #undef OFFSET_MAX |