Patience-diff NPM

patience-diff

Linear Diff algorithm for Arrays. Uses statically allocated memory for predictable performance between runs. Supported by all browsers.

Usage

var PatienceDiff = require('patience-diff')

var current = [ 'a', 'b', 'c' ]
var desired = [ 'a', 'c', 'b', 'c' ]

var differ = new PatienceDiff()
differ.diff(current, desired)

console.log(differ.instructions)
// => [ 0x0002, 0x001, 0x001, 0x000 ]

Bytecode

Patience diff operates on two arrays: one that contains a desired state, and the other that contains the current state. It then proceeds to calculate the optimal diff between the two, and stores it in a Uint16Array.

Because Patience Diff is intended to run in memory sensitive environments, the instructions are stored as binary inside a Uint16Array. This allows for up to 65535 instructions to be returned, which should be more than enough for any reasonable application.

The Uint16Array is allocated statically and allows up to 512 commands (of max 2 arguments). If more instructions are needed in a single run, then the array will keep doubling in size until it's large enough to contain the amount of instructions needed.

Each instruction has its own unique code, and is optionally followed by of arguments. Each list of instructions is terminated by a NUL instruction (0x0000) to indicate that there are no more commands. Explicit termination is needed because the instruction list is reused between calls.

The table below shows all supported instructions. The examples are written in hex notation using 4 bits, because that's how data is represented in a Uint16Array. The Node REPL supports converting hex to regular (base10) numbers, which can be helpful to understand the examples better.

Instruction	Code	Arguments	Example	Example Description
NUL	`0x0000`	0	`[0x0000]`	Required. All instructions have been executed, ignore the rest of the array.
NOOP	`0x0001`	2	`[0x0001,0x0003,0x0003,0x0000]`	The element from array A at index 3 is equivalent to the element from array B at index 3.
MOVE	`0x0002`	2	`[0x0002,0x0000,0x0001,0x0000]`	Move the element from array A at index 0 into array B before index 1.
DELETE	`0x0003`	1	`[0x0003,0x0005,0x0000]`	Delete the element from array B at index 5.
REPLACE	`0x0004`	0	`[0x0004,0x0010,0x00fe,0x0000]`	Replace the element from array B at index 254 with the element from array A at index 16.