1// Copyright 2022 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package lcs
6
7import (
8 "log"
9 "sort"
10)
11
12// lcs is a longest common sequence
13type lcs []diag
14
15// A diag is a piece of the edit graph where A[X+i] == B[Y+i], for 0<=i<Len.
16// All computed diagonals are parts of a longest common subsequence.
17type diag struct {
18 X, Y int
19 Len int
20}
21
22// sort sorts in place, by lowest X, and if tied, inversely by Len
23func (l lcs) sort() lcs {
24 sort.Slice(l, func(i, j int) bool {
25 if l[i].X != l[j].X {
26 return l[i].X < l[j].X
27 }
28 return l[i].Len > l[j].Len
29 })
30 return l
31}
32
33// validate that the elements of the lcs do not overlap
34// (can only happen when the two-sided algorithm ends early)
35// expects the lcs to be sorted
36func (l lcs) valid() bool {
37 for i := 1; i < len(l); i++ {
38 if l[i-1].X+l[i-1].Len > l[i].X {
39 return false
40 }
41 if l[i-1].Y+l[i-1].Len > l[i].Y {
42 return false
43 }
44 }
45 return true
46}
47
48// repair overlapping lcs
49// only called if two-sided stops early
50func (l lcs) fix() lcs {
51 // from the set of diagonals in l, find a maximal non-conflicting set
52 // this problem may be NP-complete, but we use a greedy heuristic,
53 // which is quadratic, but with a better data structure, could be D log D.
54 // independent is not enough: {0,3,1} and {3,0,2} can't both occur in an lcs
55 // which has to have monotone x and y
56 if len(l) == 0 {
57 return nil
58 }
59 sort.Slice(l, func(i, j int) bool { return l[i].Len > l[j].Len })
60 tmp := make(lcs, 0, len(l))
61 tmp = append(tmp, l[0])
62 for i := 1; i < len(l); i++ {
63 var dir direction
64 nxt := l[i]
65 for _, in := range tmp {
66 if dir, nxt = overlap(in, nxt); dir == empty || dir == bad {
67 break
68 }
69 }
70 if nxt.Len > 0 && dir != bad {
71 tmp = append(tmp, nxt)
72 }
73 }
74 tmp.sort()
75 if false && !tmp.valid() { // debug checking
76 log.Fatalf("here %d", len(tmp))
77 }
78 return tmp
79}
80
81type direction int
82
83const (
84 empty direction = iota // diag is empty (so not in lcs)
85 leftdown // proposed acceptably to the left and below
86 rightup // proposed diag is acceptably to the right and above
87 bad // proposed diag is inconsistent with the lcs so far
88)
89
90// overlap trims the proposed diag prop so it doesn't overlap with
91// the existing diag that has already been added to the lcs.
92func overlap(exist, prop diag) (direction, diag) {
93 if prop.X <= exist.X && exist.X < prop.X+prop.Len {
94 // remove the end of prop where it overlaps with the X end of exist
95 delta := prop.X + prop.Len - exist.X
96 prop.Len -= delta
97 if prop.Len <= 0 {
98 return empty, prop
99 }
100 }
101 if exist.X <= prop.X && prop.X < exist.X+exist.Len {
102 // remove the beginning of prop where overlaps with exist
103 delta := exist.X + exist.Len - prop.X
104 prop.Len -= delta
105 if prop.Len <= 0 {
106 return empty, prop
107 }
108 prop.X += delta
109 prop.Y += delta
110 }
111 if prop.Y <= exist.Y && exist.Y < prop.Y+prop.Len {
112 // remove the end of prop that overlaps (in Y) with exist
113 delta := prop.Y + prop.Len - exist.Y
114 prop.Len -= delta
115 if prop.Len <= 0 {
116 return empty, prop
117 }
118 }
119 if exist.Y <= prop.Y && prop.Y < exist.Y+exist.Len {
120 // remove the beginning of peop that overlaps with exist
121 delta := exist.Y + exist.Len - prop.Y
122 prop.Len -= delta
123 if prop.Len <= 0 {
124 return empty, prop
125 }
126 prop.X += delta // no test reaches this code
127 prop.Y += delta
128 }
129 if prop.X+prop.Len <= exist.X && prop.Y+prop.Len <= exist.Y {
130 return leftdown, prop
131 }
132 if exist.X+exist.Len <= prop.X && exist.Y+exist.Len <= prop.Y {
133 return rightup, prop
134 }
135 // prop can't be in an lcs that contains exist
136 return bad, prop
137}
138
139// manipulating Diag and lcs
140
141// prepend a diagonal (x,y)-(x+1,y+1) segment either to an empty lcs
142// or to its first Diag. prepend is only called to extend diagonals
143// the backward direction.
144func (lcs lcs) prepend(x, y int) lcs {
145 if len(lcs) > 0 {
146 d := &lcs[0]
147 if int(d.X) == x+1 && int(d.Y) == y+1 {
148 // extend the diagonal down and to the left
149 d.X, d.Y = int(x), int(y)
150 d.Len++
151 return lcs
152 }
153 }
154
155 r := diag{X: int(x), Y: int(y), Len: 1}
156 lcs = append([]diag{r}, lcs...)
157 return lcs
158}
159
160// append appends a diagonal, or extends the existing one.
161// by adding the edge (x,y)-(x+1.y+1). append is only called
162// to extend diagonals in the forward direction.
163func (lcs lcs) append(x, y int) lcs {
164 if len(lcs) > 0 {
165 last := &lcs[len(lcs)-1]
166 // Expand last element if adjoining.
167 if last.X+last.Len == x && last.Y+last.Len == y {
168 last.Len++
169 return lcs
170 }
171 }
172
173 return append(lcs, diag{X: x, Y: y, Len: 1})
174}
175
176// enforce constraint on d, k
177func ok(d, k int) bool {
178 return d >= 0 && -d <= k && k <= d
179}