patience-diff
v0.0.2
Published
Linear Diff algorithm for Arrays.
Downloads
21
Maintainers
yoshuawuytsReadme
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-diffSee Also
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