Linear Diff algorithm for Arrays.
npm install patience-diffLinear Diff algorithm for Arrays. Uses statically allocated memory for
predictable performance between runs. Supported by all
browsers.
js
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 .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
$3
Create a new differ instance.$3
Create a diff between the current array and the desired array. Each element in
both arrays should be of type String.$3
Read out the diff instructions for the last call to differ.diff(). The
returned value is in instance of Uint16Array.Installation
`sh
$ npm install patience-diff
``[0]: https://img.shields.io/badge/stability-experimental-orange.svg?style=flat-square
[1]: https://nodejs.org/api/documentation.html#documentation_stability_index
[2]: https://img.shields.io/npm/v/patience-diff.svg?style=flat-square
[3]: https://npmjs.org/package/patience-diff
[4]: https://img.shields.io/travis/yoshuawuyts/patience-diff/master.svg?style=flat-square
[5]: https://travis-ci.org/yoshuawuyts/patience-diff
[6]: https://img.shields.io/codecov/c/github/yoshuawuyts/patience-diff/master.svg?style=flat-square
[7]: https://codecov.io/github/yoshuawuyts/patience-diff
[8]: http://img.shields.io/npm/dm/patience-diff.svg?style=flat-square
[9]: https://npmjs.org/package/patience-diff
[10]: https://img.shields.io/badge/code%20style-standard-brightgreen.svg?style=flat-square
[11]: https://github.com/feross/standard