| 109 | * ``` |
| 110 | */ |
| 111 | export function backTrace<T>( |
| 112 | A: T[], |
| 113 | B: T[], |
| 114 | current: FarthestPoint, |
| 115 | swapped: boolean, |
| 116 | routes: Uint32Array, |
| 117 | diffTypesPtrOffset: number, |
| 118 | ): Array<{ |
| 119 | type: DiffType; |
| 120 | value: T; |
| 121 | }> { |
| 122 | const M = A.length; |
| 123 | const N = B.length; |
| 124 | const result: { type: DiffType; value: T }[] = []; |
| 125 | let a = M - 1; |
| 126 | let b = N - 1; |
| 127 | let j = routes[current.id]; |
| 128 | let type = routes[current.id + diffTypesPtrOffset]; |
| 129 | while (true) { |
| 130 | if (!j && !type) break; |
| 131 | const prev = j!; |
| 132 | if (type === REMOVED) { |
| 133 | result.push({ |
| 134 | type: swapped ? "removed" : "added", |
| 135 | value: B[b]!, |
| 136 | }); |
| 137 | b -= 1; |
| 138 | } else if (type === ADDED) { |
| 139 | result.push({ |
| 140 | type: swapped ? "added" : "removed", |
| 141 | value: A[a]!, |
| 142 | }); |
| 143 | a -= 1; |
| 144 | } else { |
| 145 | result.push({ type: "common", value: A[a]! }); |
| 146 | a -= 1; |
| 147 | b -= 1; |
| 148 | } |
| 149 | j = routes[prev]; |
| 150 | type = routes[prev + diffTypesPtrOffset]; |
| 151 | } |
| 152 | result.reverse(); |
| 153 | return result; |
| 154 | } |
| 155 | |
| 156 | /** |
| 157 | * Creates a {@linkcode FarthestPoint}. |