For diffing ordered trees
A single diffTrees function is exported:
declare function diffTrees<TValue>(
treeA: TreeNode<{ value: TValue }>,
treeB: TreeNode<{ value: TValue }>
): DiffTree<TValue>;It takes two trees of type TreeNode:
type TreeNode<TValues> = {
id: string;
children: TreeNode<TValues>[];
} & TValues;And produces a single tree of type DiffTree which is an array containing one or two DiffTreeNodes. The second DiffTreeNode is included if the root of the tree was deleted.
type DiffTree<TValue> =
| [DiffTreeNode<TValue>]
| [DiffTreeNode<TValue>, DiffTreeNode<TValue>];type DiffTreeNode<TValue> = Omit<TreeNode<{ value: TValue }>, 'children'> & {
change: Change;
children: DiffTreeNode<TValue>[];
};Where a Change is:
type Change =
| [ChangeType.Unchanged]
| [ChangeType.Inserted]
| [ChangeType.Deleted]
| [ChangeType.Updated]
| [ChangeType.Moved]
| [ChangeType.Moved, ChangeType.Updated];ChangeType.Unchangeddenotes unchanged nodes.ChangeType.Inserteddenotes new nodes.ChangeType.Deleteddenotes deleted nodes.ChangeType.Updateddenotes nodes where thevaluechanged.ChangeType.Moveddenotes nodes that moved to another subtree or changed place within the same subtree.
The value in a TreeNode can is generic. If the value has changed, the DiffTreeNode is annotated with ChangeType.Updated. By default, values are compared using strict equality (===). To change how values are compared, add a custom valueEquality function to the optional options object:
declare function diffTrees<TValue>(
treeA: TreeNode<{ value: TValue }>,
treeB: TreeNode<{ value: TValue }>,
options?: {
valueEquality: (a: TValue, b: TValue) => boolean;
}
): DiffTreeNode<TValue>;diffTrees(
{ id: '1', value: 'a', children: [] },
{ id: '1', value: 'a', children: [] }
);
// =>
[
{
id: '1',
value: 'a',
children: [],
change: [ChangeType.Unchanged],
},
];diffTrees(
{ id: '1', value: 'a', children: [] },
{ id: '2', value: 'b', children: [] }
);
// =>
[
{
id: '2',
value: 'b',
children: [],
change: [ChangeType.Inserted],
},
{
id: '1',
value: '1',
children: [],
change: [ChangeType.Deleted],
},
];diffTrees(
{ id: '1', value: 'a', children: [] },
{ id: '1', value: 'a', children: [{ id: '2', value: 'b', children: [] }] }
);
// =>
[
{
id: '1',
value: 'a',
change: [ChangeType.Unchanged],
children: [
{ id: '2', value: 'b', change: [ChangeType.Inserted], children: [] },
],
},
];diffTrees(
{
id: '1',
value: 'a',
children: [
{ id: '2', value: 'b', children: [] },
{ id: '3', value: 'c', children: [] },
],
},
{
id: '1',
value: 'a',
children: [
{ id: '3', value: 'c2', children: [] },
{ id: '2', value: 'b', children: [] },
],
}
);
// =>
[
{
id: '1',
value: 'a',
change: [ChangeType.Unchanged],
children: [
{
id: '3',
value: 'c2',
change: [ChangeType.Moved, ChangeType.Updated],
children: [],
},
{
id: '2',
value: 'b',
change: [ChangeType.Moved],
children: [],
},
],
},
];