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>;
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: [],
},
],
},
];