diff-trees
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 DiffTreeNode
s. 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.Unchanged
denotes unchanged nodes. -
ChangeType.Inserted
denotes new nodes. -
ChangeType.Deleted
denotes deleted nodes. -
ChangeType.Updated
denotes nodes where thevalue
changed. -
ChangeType.Moved
denotes 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>;
Examples
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: [],
},
],
},
];