Class LCS

Create a new instance of the LCS implementation.

Constructor

class LCS(a, b)

Arguments:

• a – The first sequence
• b – The second sequence

Methods

compute

LCS#compute(callback, T, limit)

Arguments:

• callback –

  A function(x, y) called for A[x] and B[y] for symbols

  taking part in the LCS.

• T –

  Context object bound to “this” when the callback is

  invoked.

• limit –

  A Limit instance constraining the window of operation to

  the given limit. If undefined the algorithm will iterate over the whole sequences a and b.

Compute longest common subsequence using myers divide & conquer linear space algorithm.

Call a callback for each snake which is part of the longest common subsequence.

This algorithm works with strings and arrays. In order to modify the equality-test, just override the equals(a, b) method on the LCS object.

defaultLimit

LCS#defaultLimit()

Return the default limit spanning the whole input

equals

LCS#equals(a, b)

Arguments:

• a –
• b –

Returns true if the sequence members a and b are equal. Override this method if your sequences contain special things.

forEachCommonSymbol

LCS#forEachCommonSymbol(callback, T)

Arguments:

• callback –

  A function(x, y) called for A[x] and B[y] for symbols

  taking part in the LCS.

• T –

  Context object bound to “this” when the callback is

  invoked.

Call a callback for each symbol which is part of the longest common subsequence between A and B.

Given that the two sequences A and B were supplied to the LCS constructor, invoke the callback for each pair A[x], B[y] which is part of the longest common subsequence of A and B.

This algorithm works with strings and arrays. In order to modify the equality-test, just override the equals(a, b) method on the LCS object.

Usage: <code> var lcs = []; var A = ‘abcabba’; var B = ‘cbabac’; var l = new LCS(A, B); l.forEachCommonSymbol(function(x, y) {

lcs.push(A[x]);

}); console.log(lcs); // -> [ ‘c’, ‘a’, ‘b’, ‘a’ ] </code>

forEachPositionInSnake

LCS#forEachPositionInSnake(left, right, callback, T)

Arguments:

• left – Left KPoint
• right – Right KPoint
• callback – Callback of the form function(x, y)
• T –

  Context object bound to “this” when the callback is

  invoked.

Invokes a function for each position in the snake between the left and the right snake head.

middleSnake

LCS#middleSnake(lefthead, righthead, limit)

Arguments:

• lefthead –

  (Output) A reference to a KPoint which will be

  populated with the values corresponding to the left end of the middle snake.

• righthead –

  (Output) A reference to a KPoint which will be

  populated with the values corresponding to the right end of the middle snake.

• limit – (In) Current lcs search limits (left, right, N, M, delta, dmax)

:returns :

d, number of edit script operations encountered within

the given limit

Internal use. Find the middle snake and set lefthead to the left end and righthead to the right end.

nextSnakeHeadBackward

LCS#nextSnakeHeadBackward(head, k, kmin, kmax, limit, V)

Arguments:

• head –

  (Output) Reference to a KPoint which will be populated

  with the new values

• k – (In) Current k-line
• kmin – (In) Lowest k-line in current d-round
• kmax – (In) Highest k-line in current d-round
• limit – (In) Current lcs search limits (left, right, N, M, delta, dmax)
• V –

  (In-/Out) Vector containing the results of previous

  calculations. This vector gets updated automatically by nextSnakeHeadForward method.

Internal use. Compute new values for the next head on the given k-line in reverse direction by examining the results of previous calculations in V in the neighborhood of the k-line k.

nextSnakeHeadForward

LCS#nextSnakeHeadForward(head, k, kmin, kmax, limit, V)

Arguments:

• head –

  (Output) Reference to a KPoint which will be populated

  with the new values

• k – (In) Current k-line
• kmin – (In) Lowest k-line in current d-round
• kmax – (In) Highest k-line in current d-round
• limit – (In) Current lcs search limits (left, right, N, M, delta, dmax)
• V –

  (In-/Out) Vector containing the results of previous

  calculations. This vector gets updated automatically by nextSnakeHeadForward method.

Internal use. Compute new values for the next head on the given k-line in forward direction by examining the results of previous calculations in V in the neighborhood of the k-line k.