Home Manual Reference Source

Function

Static Public Summary
public

Split(k: number, xBegin: number, xEnd: number, distanceLeft: number, distance: number)

Split.
public

StackEntry(D: number, li: number, lj: number, ri: number, rj: number)

StackEntry.
public

ArrayAlloc.
public

ArrayRealloc.
public

arrayType(maxValue: number): Int8ArrayConstructor | Int16ArrayConstructor | Int32ArrayConstructor

ArrayType.
public

backwardExtend(cMin: number, cMax: number, cx: number, V: {[x: number]}, eq: Function, lj: number, rj: number)

Diagonal backward extension subroutine.
public

backwardStep(V: {[x: number]}, cMin: number, cMax: number, cmD: number)

Diagonal backward step.
public

boundAlloc(MAX: number, li: number, lj: number): number

BoundAlloc.
public

diff(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): IterableIterator

Yields diff rectangles.
public

diff32(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): IterableIterator

Yields diff rectangles.
public

forwardExtend(cMin: number, cMax: number, cx: number, V: {[x: number]}, eq: Function, lj: number, rj: number)

Diagonal forward extension subroutine.
public

forwardStep(V: {[x: number]}, cMin: number, cMax: number, cpD: number)

Diagonal forward step.
public

int32(x: any): number

Int32.
public

Computes a lower bound for the signed distance.
public

longestCommonPrefix(eq: Function, ai: number, aj: number, bi: number, bj: number): *

LongestCommonPrefix.
public

longestCommonSuffix(eq: Function, aj: number, ai: number, bj: number, bi: number): *

LongestCommonSuffix.
public

MakeScan.
public

MakeScan.
public

oneWay(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): Split

Scan from begin to end.
public

oneWayAlloc(MAX: number, li: number, lj: number, ri: number, rj: number, init: number): {"array": *, "center": *}

DiagonalAlloc.
public

recurse(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): IterableIterator

Recurse.
public

recurseDeep(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): IterableIterator

RecurseDeep.
public

RecurseDeeper.
public

twoWay(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): *

Scan from begin to middle and end to middle.
public

twoWayAlloc(MAX: number, li: number, lj: number, ri: number, rj: number): {"V": *, "centerF": *, "centerB": *}

TwoWayAlloc.
public

twoWayRealloc(B: Int8Array | Int16Array | Int32Array, MAX: number, li: number, lj: number, ri: number, rj: number): {"V": *, "centerF": *, "centerB": *}

TwoWayRealloc.
public

twoWayScan(MAX: number, V: {[x: number], length: number}, centerF: number, centerB: number, eq: Function, li: number, lj: number, ri: number, rj: number): Split

Scan from begin to middle and end to middle.
public

Computes an upper bound for the signed distance.

Static Public

public Split(k: number, xBegin: number, xEnd: number, distanceLeft: number, distance: number) source 

import Split from '@edit-distance/myers-1986/src/Split.js'

Split.

Params:

NameTypeAttributeDescription
k number
xBegin number
xEnd number
distanceLeft number
distance number

public StackEntry(D: number, li: number, lj: number, ri: number, rj: number) source 

import StackEntry from '@edit-distance/myers-1986/src/StackEntry.js'

StackEntry.

Params:

NameTypeAttributeDescription
D number
li number
lj number
ri number
rj number

public arrayAlloc(maxValue: number, length: number): Int8Array | Int16Array | Int32Array source 

import arrayAlloc from '@edit-distance/myers-1986/src/arrayAlloc.js'

ArrayAlloc.

Params:

NameTypeAttributeDescription
maxValue number
length number

Return:

Int8Array | Int16Array | Int32Array

public arrayRealloc(maxValue: number, B: Int8Array | Int16Array | Int32Array): Int8Array | Int16Array | Int32Array source 

import arrayRealloc from '@edit-distance/myers-1986/src/arrayRealloc.js'

ArrayRealloc.

Params:

NameTypeAttributeDescription
maxValue number
B Int8Array | Int16Array | Int32Array

Return:

Int8Array | Int16Array | Int32Array

public arrayType(maxValue: number): Int8ArrayConstructor | Int16ArrayConstructor | Int32ArrayConstructor source 

import arrayType from '@edit-distance/myers-1986/src/arrayType.js'

ArrayType.

Params:

NameTypeAttributeDescription
maxValue number

Return:

Int8ArrayConstructor | Int16ArrayConstructor | Int32ArrayConstructor

public backwardExtend(cMin: number, cMax: number, cx: number, V: {[x: number]}, eq: Function, lj: number, rj: number) source 

import backwardExtend from '@edit-distance/myers-1986/src/backwardExtend.js'

Diagonal backward extension subroutine.

Params:

NameTypeAttributeDescription
cMin number
cMax number
cx number
V {[x: number]}
eq Function
lj number
rj number

public backwardStep(V: {[x: number]}, cMin: number, cMax: number, cmD: number) source 

import backwardStep from '@edit-distance/myers-1986/src/backwardStep.js'

Diagonal backward step.

Params:

NameTypeAttributeDescription
V {[x: number]}
cMin number
cMax number
cmD number

public boundAlloc(MAX: number, li: number, lj: number): number source 

import boundAlloc from '@edit-distance/myers-1986/src/boundAlloc.js'

BoundAlloc.

Params:

NameTypeAttributeDescription
MAX number
li number
lj number

Return:

number

public diff(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): IterableIterator source 

import diff from '@edit-distance/myers-1986/src/diff.js'

Yields diff rectangles. Throws if indices are not int32.

Params:

NameTypeAttributeDescription
MAX number
eq Function
li number
lj number
ri number
rj number

Return:

IterableIterator

public diff32(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): IterableIterator source 

import diff32 from '@edit-distance/myers-1986/src/diff32.js'

Yields diff rectangles. Undefined behavior if indices are not int32.

Params:

NameTypeAttributeDescription
MAX number
eq Function
li number
lj number
ri number
rj number

Return:

IterableIterator

public forwardExtend(cMin: number, cMax: number, cx: number, V: {[x: number]}, eq: Function, lj: number, rj: number) source 

import forwardExtend from '@edit-distance/myers-1986/src/forwardExtend.js'

Diagonal forward extension subroutine.

Params:

NameTypeAttributeDescription
cMin number
cMax number
cx number
V {[x: number]}
eq Function
lj number
rj number

public forwardStep(V: {[x: number]}, cMin: number, cMax: number, cpD: number) source 

import forwardStep from '@edit-distance/myers-1986/src/forwardStep.js'

Diagonal forward step.

Params:

NameTypeAttributeDescription
V {[x: number]}
cMin number
cMax number
cpD number

public int32(x: any): number source 

import int32 from '@edit-distance/myers-1986/src/int32.js'

Int32.

Params:

NameTypeAttributeDescription
x any

Return:

number

A signed 32-bit integer.

public lBound(D: number, N: number): number source 

import lBound from '@edit-distance/myers-1986/src/lBound.js'

Computes a lower bound for the signed distance.

Params:

NameTypeAttributeDescription
D number

= 1
N number

= 1

Return:

number

A number -N <= k < D.

See:

  • uBound for more details on usage and invariants.

public longestCommonPrefix(eq: Function, ai: number, aj: number, bi: number, bj: number): * source 

import longestCommonPrefix from '@edit-distance/myers-1986/src/longestCommonPrefix.js'

LongestCommonPrefix.

Params:

NameTypeAttributeDescription
eq Function
ai number
aj number
bi number
bj number

Return:

*

public longestCommonSuffix(eq: Function, aj: number, ai: number, bj: number, bi: number): * source 

import longestCommonSuffix from '@edit-distance/myers-1986/src/longestCommonSuffix.js'

LongestCommonSuffix.

Params:

NameTypeAttributeDescription
eq Function
aj number
ai number
bj number
bi number

Return:

*

public makeScan(method: Function): Function source 

import makeScan from '@edit-distance/myers-1986/src/makeScan.js'

MakeScan.

Params:

NameTypeAttributeDescription
method Function

Return:

Function

public makeScan32(method: Function): Function source 

import makeScan32 from '@edit-distance/myers-1986/src/makeScan32.js'

MakeScan.

Params:

NameTypeAttributeDescription
method Function

Return:

Function

public oneWay(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): Split source 

import oneWay from '@edit-distance/myers-1986/src/oneWay.js'

Scan from begin to end.

Params:

NameTypeAttributeDescription
MAX number
eq Function
li number
lj number
ri number
rj number

Return:

Split

public oneWayAlloc(MAX: number, li: number, lj: number, ri: number, rj: number, init: number): {"array": *, "center": *} source 

import oneWayAlloc from '@edit-distance/myers-1986/src/oneWayAlloc.js'

DiagonalAlloc.

Params:

NameTypeAttributeDescription
MAX number
li number
lj number
ri number
rj number
init number

Return:

{"array": *, "center": *}

public recurse(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): IterableIterator source 

import recurse from '@edit-distance/myers-1986/src/recurse.js'

Recurse.

Params:

NameTypeAttributeDescription
MAX number
eq Function
li number
lj number
ri number
rj number

Return:

IterableIterator

public recurseDeep(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): IterableIterator source 

import recurseDeep from '@edit-distance/myers-1986/src/recurseDeep.js'

RecurseDeep.

Params:

NameTypeAttributeDescription
MAX number
eq Function
li number
lj number
ri number
rj number

Return:

IterableIterator

public recurseDeeperStep(B: Int8Array | Int16Array | Int32Array, stack: StackEntry[], eq: Function): number[] source 

import recurseDeeperStep from '@edit-distance/myers-1986/src/recurseDeeperStep.js'

RecurseDeeper.

/!\ The entries in this stack should have a value D = MAX that is exactly the distance on the input range [li, lj, ri, rj].

Params:

NameTypeAttributeDescription
B Int8Array | Int16Array | Int32Array
stack StackEntry[]
eq Function

Return:

number[]

public twoWay(MAX: number, eq: Function, li: number, lj: number, ri: number, rj: number): * source 

import twoWay from '@edit-distance/myers-1986/src/twoWay.js'

Scan from begin to middle and end to middle.

Params:

NameTypeAttributeDescription
MAX number
eq Function
li number
lj number
ri number
rj number

Return:

*

public twoWayAlloc(MAX: number, li: number, lj: number, ri: number, rj: number): {"V": *, "centerF": *, "centerB": *} source 

import twoWayAlloc from '@edit-distance/myers-1986/src/twoWayAlloc.js'

TwoWayAlloc.

Params:

NameTypeAttributeDescription
MAX number
li number
lj number
ri number
rj number

Return:

{"V": *, "centerF": *, "centerB": *}

public twoWayRealloc(B: Int8Array | Int16Array | Int32Array, MAX: number, li: number, lj: number, ri: number, rj: number): {"V": *, "centerF": *, "centerB": *} source 

import twoWayRealloc from '@edit-distance/myers-1986/src/twoWayRealloc.js'

TwoWayRealloc.

Params:

NameTypeAttributeDescription
B Int8Array | Int16Array | Int32Array
MAX number
li number
lj number
ri number
rj number

Return:

{"V": *, "centerF": *, "centerB": *}

public twoWayScan(MAX: number, V: {[x: number], length: number}, centerF: number, centerB: number, eq: Function, li: number, lj: number, ri: number, rj: number): Split source 

import twoWayScan from '@edit-distance/myers-1986/src/twoWayScan.js'

Scan from begin to middle and end to middle.

Params:

NameTypeAttributeDescription
MAX number
V {[x: number], length: number}
centerF number
centerB number
eq Function
li number
lj number
ri number
rj number

Return:

Split

public uBound(D: number, N: number): number source 

import uBound from '@edit-distance/myers-1986/src/uBound.js'

Computes an upper bound for the signed distance.

Note that lBound(D, N) = uBound(D, M) is possible if and only if we have D = N + M and N >= 1 and M >= 1. Case analysis:

  • D = -D NOT POSSIBLE SINCE D >= 1
  • D = D - M * 2 NOT POSSIBLE SINCE M >= 1
  • -D = N * 2 - D NOT POSSIBLE SINCE N >= 1

  • D - M 2 = N 2 - D POSSIBLE ONLY IF D = N + M, D >= N + 1, and D >= M + 1.

    Note that we only use lBound and uBound when this special case does not happen. This required some refactoring in oneWay to pull-out the case D = N

  • M. None was required in twoWayScan since we have the assertions 2 * D <= MAX + parityDelta and MAX <= N + M.

Params:

NameTypeAttributeDescription
D number

= 1
N number

= 1

Return:

number

A number -D < k <= N.

See: