align-arr

Find the minimal edit path between two generic arrays.

Installation

npm i align-arr

or

yarn add align-arr

Usage

Find the difference between two arrays of number.

import { align } from 'align-arr';

const source = [1, 3, 3];
const target = [1, 2, 3];

const alignment: Edit<number>[] = align(source, target);

console.log(alignment);

[
  {
    operation: 'equal',
    source: { position: 0, data: 1 },
    target: { position: 0, data: 1 },
    cost: 0
  },
  {
    operation: 'substitute',
    source: { position: 1, data: 3 },
    target: { position: 1, data: 2 },
    cost: 1
  },
  {
    operation: 'equal',
    source: { position: 2, data: 3 },
    target: { position: 2, data: 3 },
    cost: 0
  }
]

The console logs an array of Edit objects describing the difference between source and target.

export type Edit<S = any, T = S> = {
  operation: Operation;
  source: Chunk<S>;
  target: Chunk<T>;
  cost: number;
};

export type Operation = 'equal' | 'insert' | 'delete' | 'substitute';

export type Chunk<T = any> = {
  position: number;
  data?: T;
};

Customizing The Aligner

By default, the algorithm compares two elements as a === b, and has a fixed cost of 1 for each operation.

In this example, we override the equals method to compare between a number and a string, and assign a fixed cost of 10 to the substitute operation, which causes the algorithm to favour insert and delete instead.

const source = [1, 3, 3];
const target = ['1', '2', '3'];

const alignment = align(source, target, {
  equals: (a, b) => a === Number.parseFloat(b),
  insCost: (a) => 1,
  delCost: (a) => 1,
  subCost: (a, b) => 10,
});

console.log(alignment);

[
  {
    operation: 'equal',
    source: { position: 0, data: 1 },
    target: { position: 0, data: '1' },
    cost: 0
  },
  {
    operation: 'insert',
    source: { position: 1, data: undefined },
    target: { position: 1, data: '2' },
    cost: 1
  },
  {
    operation: 'delete',
    source: { position: 1, data: 3 },
    target: { position: 2, data: undefined },
    cost: 1
  },
  {
    operation: 'equal',
    source: { position: 2, data: 3 },
    target: { position: 2, data: '3' },
    cost: 0
  }
]

Contributions

To contribute to align-arr, follow these steps:

1. Fork this repository.
2. Create a branch: git checkout -b <branch_name>.
3. Make your changes and commit them: git commit -m '<commit_message>'
4. Push to the original branch: git push origin <project_name>/<location>
5. Create the pull request.

Alternatively see the GitHub documentation on creating a pull request.

Contributors

Thanks to the following people who have contributed to this project:

• @manzurola 🐈

Contact

If you want to contact me you can reach me at [email protected].

License

This project uses the following license: MIT.