| 1 | #ifndef __LCS_HH__␊ |
| 2 | #define __LCS_HH__␊ |
| 3 | ␊ |
| 4 | /* ␊ |
| 5 | ␊ |
| 6 | this is a pretty direct translation (with only vague understanding,␊ |
| 7 | unfortunately) of aubrey jaffer's most recent O(NP) edit-script␊ |
| 8 | calculation algorithm, which performs quite a bit better than myers,␊ |
| 9 | manber and miller's O(NP) simple edit *distance* algorithm. this one␊ |
| 10 | builds the entire *script* that fast.␊ |
| 11 | ␊ |
| 12 | the following is jaffer's copyright and license statement. it probably␊ |
| 13 | still has some legal relevance here, as this is a highly derivative␊ |
| 14 | work. if not, the portions of this file which are "mine" (if any exist)␊ |
| 15 | are subject to copyright (C) 2003 graydon hoare, licensed to the public␊ |
| 16 | under the GPL v2+. see the file COPYING for details. if you want to see␊ |
| 17 | more of the original file jaffer's work came from, see the SLIB␊ |
| 18 | repository on savannah.nongnu.org, or look in the journal of␊ |
| 19 | computational biology. apparantly it's submitted for publication there␊ |
| 20 | too.␊ |
| 21 | ␊ |
| 22 | --- ␊ |
| 23 | ␊ |
| 24 | "differ.scm" O(NP) Sequence Comparison Algorithm.␊ |
| 25 | Copyright (C) 2001, 2002, 2003 Aubrey Jaffer␊ |
| 26 | ␊ |
| 27 | Permission to copy this software, to modify it, to redistribute it, to␊ |
| 28 | distribute modified versions, and to use it for any purpose is granted,␊ |
| 29 | subject to the following restrictions and understandings.␊ |
| 30 | ␊ |
| 31 | 1. Any copy made of this software must include this copyright notice␊ |
| 32 | in full.␊ |
| 33 | ␊ |
| 34 | 2. I have made no warrantee or representation that the operation of␊ |
| 35 | this software will be error-free, and I am under no obligation to␊ |
| 36 | provide any services, by way of maintenance, update, or otherwise.␊ |
| 37 | ␊ |
| 38 | 3. In conjunction with products arising from the use of this material,␊ |
| 39 | there shall be no use of my name in any advertising, promotional, or␊ |
| 40 | sales literature without prior written consent in each case.␊ |
| 41 | ␊ |
| 42 | */␊ |
| 43 | ␊ |
| 44 | #include <vector>␊ |
| 45 | #include <algorithm>␊ |
| 46 | #include <iostream>␊ |
| 47 | #include "sanity.hh"␊ |
| 48 | ␊ |
| 49 | template <typename A,␊ |
| 50 | ␉ typename B,␊ |
| 51 | ␉ typename LCS>␉␊ |
| 52 | struct jaffer_edit_calculator␊ |
| 53 | {␊ |
| 54 | ␊ |
| 55 | typedef std::vector<long> cost_vec;␊ |
| 56 | typedef std::vector<long> edit_vec;␊ |
| 57 | ␊ |
| 58 | template <typename T>␊ |
| 59 | struct subarray␊ |
| 60 | {␊ |
| 61 | typedef typename std::iterator_traits<T>::value_type vt;␊ |
| 62 | ␊ |
| 63 | T base; // underlying representation␊ |
| 64 | long start; // current extent␊ |
| 65 | long end; // current extent␊ |
| 66 | ␊ |
| 67 | subarray(T b, long s, long e) : ␊ |
| 68 | base(b), start(s), end(e) {}␊ |
| 69 | ␊ |
| 70 | long size() const␊ |
| 71 | {␊ |
| 72 | if (end < start)␊ |
| 73 | ␉return start - end;␊ |
| 74 | else␊ |
| 75 | ␉return end - start;␊ |
| 76 | }␊ |
| 77 | ␊ |
| 78 | subarray subset(long s, long e) const␊ |
| 79 | {␊ |
| 80 | return subarray(base + std::min(start, end), s, e);␊ |
| 81 | }␊ |
| 82 | ␊ |
| 83 | vt const & operator[](size_t idx) const␊ |
| 84 | {␊ |
| 85 | if (end < start)␊ |
| 86 | ␉ return *(base + (start - (idx + 1)));␊ |
| 87 | else␊ |
| 88 | ␉ return *(base + (start + idx));␊ |
| 89 | }␊ |
| 90 | };␊ |
| 91 | ␊ |
| 92 | struct work_vec␊ |
| 93 | {␊ |
| 94 | long lo;␊ |
| 95 | long hi;␊ |
| 96 | std::vector<long> vec;␊ |
| 97 | work_vec(long lo, long hi) : ␊ |
| 98 | lo(lo), hi(hi), vec((hi - lo) + 1, -1) ␊ |
| 99 | {}␊ |
| 100 | long & operator[](long t) ␊ |
| 101 | {␊ |
| 102 | I(t >= lo);␊ |
| 103 | I(t <= hi);␊ |
| 104 | I((t-lo) <= static_cast<long>(vec.size()));␊ |
| 105 | return vec[t-lo]; ␊ |
| 106 | }␊ |
| 107 | };␊ |
| 108 | ␊ |
| 109 | ␊ |
| 110 | static long run(work_vec & fp, long k, ␊ |
| 111 | ␉␉ subarray<A> const & a, long m,␊ |
| 112 | ␉␉ subarray<B> const & b, long n,␊ |
| 113 | ␉␉ cost_vec & CC, long p)␊ |
| 114 | {␊ |
| 115 | long cost = k + 2*p;␊ |
| 116 | ␊ |
| 117 | // do the run␊ |
| 118 | long y = std::max(fp[k-1]+1, fp[k+1]);␊ |
| 119 | long x = y - k;␊ |
| 120 | ␊ |
| 121 | I(y >= 0);␊ |
| 122 | I(x >= 0);␊ |
| 123 | ␊ |
| 124 | while (true)␊ |
| 125 | {␉␊ |
| 126 | ␉// record costs along the way␊ |
| 127 | ␉long xcst = m - x;␊ |
| 128 | ␉if (y < static_cast<long>(CC.size()) && xcst >= 0)␊ |
| 129 | ␉ {␊ |
| 130 | ␉ CC[y] = std::min(xcst + cost, CC[y]); ␊ |
| 131 | ␉ }␉␊ |
| 132 | ␉if (x < m && y < n && a[x] == b[y])␊ |
| 133 | ␉ {␊ |
| 134 | ␉ ++x; ++y;␊ |
| 135 | ␉ }␊ |
| 136 | ␉else␊ |
| 137 | ␉ break;␊ |
| 138 | }␊ |
| 139 | ␊ |
| 140 | fp[k] = y;␊ |
| 141 | return y;␊ |
| 142 | }␊ |
| 143 | ␊ |
| 144 | // 'compare' here is the core myers, manber and miller algorithm.␊ |
| 145 | static long compare(cost_vec & costs, ␊ |
| 146 | ␉␉ subarray<A> const & a, long m,␊ |
| 147 | ␉␉ subarray<B> const & b, long n,␊ |
| 148 | ␉␉ long p_lim,␊ |
| 149 | ␉␉ bool full_scan = true)␊ |
| 150 | {␊ |
| 151 | long lo = -(m+1), hi = (1+n);␊ |
| 152 | if (full_scan)␊ |
| 153 | {␊ |
| 154 | ␉lo = -(p_lim + 1);␊ |
| 155 | ␉hi = p_lim + 1 + (n-m);␊ |
| 156 | }␊ |
| 157 | work_vec fp(lo, hi);␊ |
| 158 | ␊ |
| 159 | long p = 0;␊ |
| 160 | long delta = n - m;␊ |
| 161 | ␊ |
| 162 | for (; p <= p_lim; ++p)␊ |
| 163 | {␊ |
| 164 | ␊ |
| 165 | ␉// lower sweep␊ |
| 166 | ␉for (long k = -p; k < delta; ++k)␊ |
| 167 | ␉ run(fp, k, a, m, b, n, costs, p);␊ |
| 168 | ␊ |
| 169 | ␉// upper sweep␊ |
| 170 | ␉for (long k = delta + p; k > delta; --k)␊ |
| 171 | ␉ run(fp, k, a, m, b, n, costs, p);␊ |
| 172 | ␊ |
| 173 | ␉// middle␊ |
| 174 | ␉long fpval = run(fp, delta, a, m, b, n, costs, p);␊ |
| 175 | ␊ |
| 176 | ␉// we can bail early if not doing a full scan␊ |
| 177 | ␉if (!full_scan && n <= fpval)␊ |
| 178 | ␉ break;␊ |
| 179 | }␊ |
| 180 | ␊ |
| 181 | return delta + 2*p;␊ |
| 182 | }␊ |
| 183 | ␊ |
| 184 | static long divide_and_conquer(subarray<A> const & a, long start_a, long end_a,␊ |
| 185 | ␉␉␉␉ subarray<B> const & b, long start_b, long end_b,␊ |
| 186 | ␉␉␉␉ edit_vec & edits,␊ |
| 187 | ␉␉␉␉ unsigned long edx, ␊ |
| 188 | ␉␉␉␉ long polarity,␊ |
| 189 | ␉␉␉␉ long p_lim)␊ |
| 190 | {␊ |
| 191 | long mid_a = (start_a + end_a) / 2;␊ |
| 192 | long len_b = end_b - start_b;␊ |
| 193 | long len_a = end_a - start_a;␊ |
| 194 | long tcst = (2 * p_lim) + (len_b - len_a);␊ |
| 195 | ␊ |
| 196 | I(start_a >= 0);␊ |
| 197 | I(start_a <= a.size());␊ |
| 198 | I(start_b >= 0);␊ |
| 199 | I(start_b <= b.size());␊ |
| 200 | I(end_a >= 0);␊ |
| 201 | I(end_a <= a.size());␊ |
| 202 | I(end_b >= 0);␊ |
| 203 | I(end_b <= b.size());␊ |
| 204 | ␊ |
| 205 | cost_vec cc(len_b + 1, len_a + len_b);␊ |
| 206 | cost_vec rr(len_b + 1, len_a + len_b);␊ |
| 207 | ␊ |
| 208 | compare (cc, ␊ |
| 209 | ␉ a.subset(start_a, mid_a), (mid_a - start_a),␊ |
| 210 | ␉ b.subset(start_b, end_b), len_b, std::min(p_lim, len_a));␊ |
| 211 | ␊ |
| 212 | compare (rr, ␊ |
| 213 | ␉ a.subset(end_a, mid_a), (end_a - mid_a),␊ |
| 214 | ␉ b.subset(end_b, start_b), len_b, std::min(p_lim, len_a));␊ |
| 215 | ␊ |
| 216 | long b_split = mid_split(len_a, len_b, rr, cc, tcst);␊ |
| 217 | ␊ |
| 218 | long est_c = cc[b_split];␊ |
| 219 | long est_r = rr[len_b - b_split];␊ |
| 220 | ␊ |
| 221 | long cost_c = diff_to_et (a, start_a, mid_a,␊ |
| 222 | ␉␉␉ b, start_b, start_b + b_split,␊ |
| 223 | ␉␉␉ edits, edx, polarity, ␊ |
| 224 | ␉␉␉ (est_c - (b_split - (mid_a - start_a))) / 2);␊ |
| 225 | ␊ |
| 226 | I(cost_c == est_c);␊ |
| 227 | ␊ |
| 228 | long cost_r = diff_to_et (a, mid_a, end_a,␊ |
| 229 | ␉␉␉ b, start_b + b_split, end_b,␊ |
| 230 | ␉␉␉ edits, est_c + edx, polarity,␊ |
| 231 | ␉␉␉ (est_r - ((len_b - b_split) - (end_a - mid_a))) / 2);␊ |
| 232 | ␊ |
| 233 | I(cost_r == est_r);␊ |
| 234 | ␊ |
| 235 | return est_r + est_c;␊ |
| 236 | }␊ |
| 237 | ␊ |
| 238 | static long mid_split(long m, long n, ␊ |
| 239 | ␉␉␉cost_vec const & rr,␊ |
| 240 | ␉␉␉cost_vec const & cc,␊ |
| 241 | ␉␉␉long cost)␊ |
| 242 | {␊ |
| 243 | long cdx = 1 + n/2;␊ |
| 244 | long rdx = n/2;␊ |
| 245 | while (true)␊ |
| 246 | {␊ |
| 247 | ␉I (rdx >= 0);␊ |
| 248 | ␊ |
| 249 | ␉if (cost == (cc[rdx] + rr[n-rdx])) ␊ |
| 250 | ␉ return rdx;␊ |
| 251 | ␉if (cost == (cc[cdx] + rr[n-cdx]))␊ |
| 252 | ␉ return cdx;␉ ␊ |
| 253 | ␉--rdx;␊ |
| 254 | ␉++cdx;␊ |
| 255 | }␊ |
| 256 | }␊ |
| 257 | ␊ |
| 258 | ␊ |
| 259 | static void order_edits(edit_vec const & edits,␊ |
| 260 | ␉␉␉ long sign,␊ |
| 261 | ␉␉␉ edit_vec & nedits)␊ |
| 262 | {␊ |
| 263 | nedits.clear();␊ |
| 264 | nedits.resize(edits.size());␊ |
| 265 | long cost = edits.size();␊ |
| 266 | ␊ |
| 267 | if (cost == 0)␊ |
| 268 | {␊ |
| 269 | ␉nedits = edits;␊ |
| 270 | ␉return;␊ |
| 271 | }␊ |
| 272 | ␊ |
| 273 | edit_vec sedits = edits;␊ |
| 274 | std::sort(sedits.begin(), sedits.end());␊ |
| 275 | ␊ |
| 276 | long idx0;␊ |
| 277 | for (idx0 = 0; idx0 < cost && sedits[idx0] < 0; ++idx0);␊ |
| 278 | long len_a = std::max(0L, -sedits[0]);␊ |
| 279 | long len_b = sedits[cost-1];␊ |
| 280 | ␊ |
| 281 | long ddx = idx0 - 1;␊ |
| 282 | long idx = idx0;␊ |
| 283 | long ndx = 0;␊ |
| 284 | long adx = 0;␊ |
| 285 | long bdx = 0;␊ |
| 286 | ␊ |
| 287 | while (bdx < len_b || adx < len_a)␊ |
| 288 | {␊ |
| 289 | ␊ |
| 290 | ␉long del = (ddx < 0) ? 0 : sedits[ddx];␊ |
| 291 | ␉long ins = (idx >= cost) ? 0 : sedits[idx];␊ |
| 292 | ␉␊ |
| 293 | ␉if (del < 0 && adx >= (-1 - del) &&␊ |
| 294 | ␉ ins > 0 && bdx >= (-1 + ins))␊ |
| 295 | ␉ {␊ |
| 296 | ␉ nedits[ndx] = del;␊ |
| 297 | ␉ nedits[ndx+1] = ins;␊ |
| 298 | ␉ --ddx; ++idx; ndx += 2; ++adx; ++bdx;␉ ␊ |
| 299 | ␉ }␊ |
| 300 | ␉else if (del < 0 && adx >= (-1 - del))␊ |
| 301 | ␉ {␊ |
| 302 | ␉ nedits[ndx] = del;␊ |
| 303 | ␉ --ddx; ++ndx; ++adx;␊ |
| 304 | ␉ }␊ |
| 305 | ␉else if (ins > 0 && bdx >= (-1 + ins))␊ |
| 306 | ␉ {␊ |
| 307 | ␉ nedits[ndx] = ins;␊ |
| 308 | ␉ ++idx; ++ndx; ++bdx;␊ |
| 309 | ␉ }␊ |
| 310 | ␉else␊ |
| 311 | ␉ {␊ |
| 312 | ␉ ++adx; ++bdx;␊ |
| 313 | ␉ }␊ |
| 314 | }␊ |
| 315 | }␊ |
| 316 | ␊ |
| 317 | // trims and calls diff_to_ez␊ |
| 318 | static long diff_to_et(subarray<A> const & a, long start_a, long end_a,␊ |
| 319 | ␉␉␉ subarray<B> const & b, long start_b, long end_b,␊ |
| 320 | ␉␉␉ std::vector<long> & edits,␊ |
| 321 | ␉␉␉ long edx,␊ |
| 322 | ␉␉␉ long polarity,␊ |
| 323 | ␉␉␉ long p_lim)␊ |
| 324 | {␊ |
| 325 | ␊ |
| 326 | I(start_a >= 0);␊ |
| 327 | I(start_a <= a.size());␊ |
| 328 | I(start_b >= 0);␊ |
| 329 | I(start_b <= b.size());␊ |
| 330 | I(end_a >= 0);␊ |
| 331 | I(end_a <= a.size());␊ |
| 332 | I(end_b >= 0);␊ |
| 333 | I(end_b <= b.size());␊ |
| 334 | ␊ |
| 335 | I(end_a - start_a >= p_lim);␊ |
| 336 | ␊ |
| 337 | long bsx, bdx, asx, adx;␊ |
| 338 | ␊ |
| 339 | for (bdx = end_b - 1, adx = end_a - 1;␊ |
| 340 | ␉ (start_b <= bdx) && (start_a <= adx) && (a[adx] == b[bdx]);␉ ␊ |
| 341 | ␉ --bdx, --adx);␊ |
| 342 | ␊ |
| 343 | for (bsx = start_b, asx = start_a;␊ |
| 344 | ␉ (bsx < bdx) && (asx < adx) && (a[asx] == b[bsx]);␊ |
| 345 | ␉ ++bsx, ++asx);␊ |
| 346 | ␊ |
| 347 | // we've trimmed; now call diff_to_ez.␊ |
| 348 | ␊ |
| 349 | long delta = (bdx - bsx) - (adx - asx);␊ |
| 350 | if (delta < 0)␊ |
| 351 | return diff_to_ez (b, bsx, bdx+1, ␊ |
| 352 | ␉␉␉ a, asx, adx+1,␊ |
| 353 | ␉␉␉ edits, edx, -polarity, delta + p_lim);␊ |
| 354 | else␊ |
| 355 | return diff_to_ez (a, asx, adx+1,␊ |
| 356 | ␉␉␉ b, bsx, bdx+1, ␊ |
| 357 | ␉␉␉ edits, edx, polarity, p_lim);␉ ␊ |
| 358 | }␊ |
| 359 | ␊ |
| 360 | static long diff_to_ez(subarray<A> const & a, long start_a, long end_a,␊ |
| 361 | ␉␉␉ subarray<B> const & b, long start_b, long end_b,␊ |
| 362 | ␉␉␉ std::vector<long> & edits,␊ |
| 363 | ␉␉␉ long edx1,␊ |
| 364 | ␉␉␉ long polarity,␊ |
| 365 | ␉␉␉ long p_lim)␊ |
| 366 | {␊ |
| 367 | ␊ |
| 368 | I(start_a >= 0);␊ |
| 369 | I(start_a <= a.size());␊ |
| 370 | I(start_b >= 0);␊ |
| 371 | I(start_b <= b.size());␊ |
| 372 | I(end_a >= 0);␊ |
| 373 | I(end_a <= a.size());␊ |
| 374 | I(end_b >= 0);␊ |
| 375 | I(end_b <= b.size());␊ |
| 376 | ␊ |
| 377 | long len_a = end_a - start_a;␊ |
| 378 | long len_b = end_b - start_b;␊ |
| 379 | ␊ |
| 380 | I(len_a <= len_b);␊ |
| 381 | ␊ |
| 382 | // easy case #1: B inserts only␊ |
| 383 | if (p_lim == 0)␊ |
| 384 | {␊ |
| 385 | ␉// A == B, no edits␊ |
| 386 | ␉if (len_a == len_b)␊ |
| 387 | ␉ return 0;␊ |
| 388 | ␉␊ |
| 389 | ␉long adx = start_a;␊ |
| 390 | ␉long bdx = start_b;␊ |
| 391 | ␉long edx0 = edx1;␊ |
| 392 | ␉␊ |
| 393 | ␉while (true)␊ |
| 394 | ␉ {␉ ␊ |
| 395 | ␉ if (bdx >= end_b)␊ |
| 396 | ␉ return len_b - len_a;␊ |
| 397 | ␉ ␊ |
| 398 | ␉ if (adx >= end_a)␊ |
| 399 | ␉ {␊ |
| 400 | ␉␉for (long idx = bdx, edx = edx0; ␊ |
| 401 | ␉␉ idx < end_b; ␊ |
| 402 | ␉␉ ++idx, ++edx)␊ |
| 403 | ␉␉ edits[edx] = polarity * (idx+1);␊ |
| 404 | ␉␉␊ |
| 405 | ␉␉return len_b - len_a;␉␉ ␊ |
| 406 | ␉ }␊ |
| 407 | ␉ ␊ |
| 408 | ␉ if (a[adx] == b[bdx])␊ |
| 409 | ␉ {␊ |
| 410 | ␉␉++adx; ++bdx;␊ |
| 411 | ␉ }␊ |
| 412 | ␉ else␊ |
| 413 | ␉ {␊ |
| 414 | ␉␉edits[edx0] = polarity * (bdx+1);␊ |
| 415 | ␉␉++bdx; ++edx0;␊ |
| 416 | ␉ }␊ |
| 417 | ␉ }␊ |
| 418 | }␊ |
| 419 | ␊ |
| 420 | // easy case #2: delete all A, insert all B␊ |
| 421 | else if (len_a <= p_lim) ␊ |
| 422 | {␊ |
| 423 | ␉I(len_a == p_lim);␊ |
| 424 | ␊ |
| 425 | ␉long edx0 = edx1;␊ |
| 426 | ␉for (long idx = start_a; idx < end_a; ++idx, ++edx0)␊ |
| 427 | ␉ edits[edx0] = polarity * (-1 - idx);␊ |
| 428 | ␉␊ |
| 429 | ␉for (long jdx = start_b; jdx < end_b; ++jdx, ++edx0)␊ |
| 430 | ␉ edits[edx0] = polarity * (jdx + 1);␊ |
| 431 | ␉␊ |
| 432 | ␉return len_a + len_b;␊ |
| 433 | }␊ |
| 434 | ␊ |
| 435 | // hard case: recurse on subproblems␊ |
| 436 | else␊ |
| 437 | {␊ |
| 438 | ␉return divide_and_conquer (a, start_a, end_a,␊ |
| 439 | ␉␉␉␉ b, start_b, end_b,␊ |
| 440 | ␉␉␉␉ edits, edx1, polarity, p_lim);␊ |
| 441 | }␊ |
| 442 | }␊ |
| 443 | ␊ |
| 444 | static void diff_to_edits(subarray<A> const & a, long m,␊ |
| 445 | ␉␉␉ subarray<B> const & b, long n,␊ |
| 446 | ␉␉␉ std::vector<long> & edits,␊ |
| 447 | ␉␉␉ long p_lim)␊ |
| 448 | {␊ |
| 449 | I(m <= n);␊ |
| 450 | cost_vec costs(m+n); // scratch array, ignored␊ |
| 451 | long edit_distance = compare(costs, a, m, b, n, p_lim, false);␊ |
| 452 | ␊ |
| 453 | edits.clear();␊ |
| 454 | edits.resize(edit_distance, 0);␊ |
| 455 | long cost = diff_to_et(a, 0, m, ␊ |
| 456 | ␉␉␉ b, 0, n, ␊ |
| 457 | ␉␉␉ edits, 0, 1, (edit_distance - (n-m)) / 2);␊ |
| 458 | I(cost == edit_distance);␊ |
| 459 | }␊ |
| 460 | ␊ |
| 461 | static void edits_to_lcs (std::vector<long> const & edits, ␊ |
| 462 | ␉␉␉ subarray<A> const a, long m, long n,␊ |
| 463 | ␉␉␉ LCS output)␊ |
| 464 | {␊ |
| 465 | long edx = 0, sdx = 0, adx = 0;␊ |
| 466 | typedef typename std::iterator_traits<A>::value_type vt;␊ |
| 467 | std::vector<vt> lcs(((m + n) - edits.size()) / 2);␊ |
| 468 | while (true)␊ |
| 469 | {␊ |
| 470 | ␉long edit = (edx < static_cast<long>(edits.size())) ? edits[edx] : 0;␊ |
| 471 | ␉␊ |
| 472 | ␉if (adx >= m)␊ |
| 473 | ␉ break;␊ |
| 474 | ␉else if (edit > 0)␊ |
| 475 | ␉ { ++edx; }␊ |
| 476 | ␉else if (edit == 0)␊ |
| 477 | ␉ { lcs[sdx++] = a[adx++]; }␊ |
| 478 | ␉else if (adx >= (-1 - edit))␊ |
| 479 | ␉ { ++edx; ++adx; }␊ |
| 480 | ␉else␊ |
| 481 | ␉ { lcs[sdx++] = a[adx++]; }␊ |
| 482 | }␊ |
| 483 | ␊ |
| 484 | std::copy(lcs.begin(), lcs.end(), output);␊ |
| 485 | }␊ |
| 486 | };␊ |
| 487 | ␊ |
| 488 | ␊ |
| 489 | template <typename A,␊ |
| 490 | ␉ typename B,␊ |
| 491 | ␉ typename LCS>␊ |
| 492 | ␊ |
| 493 | void edit_script(A begin_a, A end_a,␊ |
| 494 | ␉␉ B begin_b, B end_b,␊ |
| 495 | ␉␉ long p_lim,␊ |
| 496 | ␉␉ std::vector<long> & edits_out,␊ |
| 497 | ␉␉ LCS ignored_out)␊ |
| 498 | {␊ |
| 499 | typedef jaffer_edit_calculator<A,B,LCS> calc_t;␊ |
| 500 | long len_a = end_a - begin_a;␊ |
| 501 | long len_b = end_b - begin_b;␊ |
| 502 | typename calc_t::edit_vec edits, ordered;␊ |
| 503 | ␊ |
| 504 | typename calc_t::subarray<A> a(begin_a, 0, len_a);␊ |
| 505 | typename calc_t::subarray<B> b(begin_b, 0, len_b);␊ |
| 506 | ␊ |
| 507 | if (len_b < len_a)␊ |
| 508 | {␊ |
| 509 | calc_t::diff_to_edits (b, len_b, a, len_a, edits, p_lim);␊ |
| 510 | calc_t::order_edits (edits, -1, ordered);␊ |
| 511 | for (size_t i = 0; i < ordered.size(); ++i)␊ |
| 512 | ␉ordered[i] *= -1;␊ |
| 513 | }␊ |
| 514 | else␊ |
| 515 | {␊ |
| 516 | calc_t::diff_to_edits (a, len_a, b, len_b, edits, p_lim);␊ |
| 517 | calc_t::order_edits (edits, 1, ordered);␊ |
| 518 | }␊ |
| 519 | ␊ |
| 520 | edits_out.clear();␊ |
| 521 | edits_out.reserve(ordered.size());␊ |
| 522 | copy(ordered.begin(), ordered.end(), back_inserter(edits_out));␊ |
| 523 | }␊ |
| 524 | ␊ |
| 525 | ␊ |
| 526 | template <typename A,␊ |
| 527 | ␉ typename B,␊ |
| 528 | ␉ typename LCS>␊ |
| 529 | void longest_common_subsequence(A begin_a, A end_a,␊ |
| 530 | ␉␉␉␉B begin_b, B end_b,␊ |
| 531 | ␉␉␉␉long p_lim,␊ |
| 532 | ␉␉␉␉LCS out)␊ |
| 533 | {␊ |
| 534 | typedef jaffer_edit_calculator<A,B,LCS> calc_t;␊ |
| 535 | long len_a = end_a - begin_a;␊ |
| 536 | long len_b = end_b - begin_b;␊ |
| 537 | typename calc_t::edit_vec edits, ordered;␊ |
| 538 | ␊ |
| 539 | typename calc_t::subarray<A> a(begin_a, 0, len_a);␊ |
| 540 | typename calc_t::subarray<B> b(begin_b, 0, len_b);␊ |
| 541 | ␊ |
| 542 | if (len_b < len_a)␊ |
| 543 | {␊ |
| 544 | calc_t::diff_to_edits (b, len_b, a, len_a, edits, p_lim);␊ |
| 545 | calc_t::order_edits (edits, -1, ordered);␊ |
| 546 | calc_t::edits_to_lcs (ordered, b, len_b, len_a, out);␊ |
| 547 | }␊ |
| 548 | else␊ |
| 549 | {␊ |
| 550 | calc_t::diff_to_edits (a, len_a, b, len_b, edits, p_lim);␊ |
| 551 | calc_t::order_edits (edits, 1, ordered);␊ |
| 552 | calc_t::edits_to_lcs (ordered, a, len_a, len_b, out);␊ |
| 553 | }␊ |
| 554 | }␊ |
| 555 | ␊ |
| 556 | #endif // __LCS_HH__␊ |
