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.

API

differ = new PatienceDiff()

Create a new differ instance.

differ.diff(current, desired)

Create a diff between the current array and the desired array. Each element in both arrays should be of type String.

instructions = differ.instructions

Read out the diff instructions for the last call to differ.diff(). The returned value is in instance of Uint16Array.

Installation

$ npm install patience-diff

See Also

• kpdecker/jsdiff
• jhchen/fast-diff

Further Reading

• Jcoglan: The Myers Diff Algorithm Part 1
• Jcoglan: The Myers Diff Algorithm Part 2
• Jcoglan: The Myers Diff Algorithm Part 3
• Jcoglan: Myers Diff in Linear Space: Theory
• Jcoglan: Myers Diff in Linear Space: Implementation
• Jcoglan: The Patience Diff Algorithm
• Jcoglan: Implementing Patience Diff
• Myers Diff Algorithm - Code & Interactive Visualization
• An O(ND) Difference Algorithm and Its Variations
• Prefix Matching

License

Apache-2.0