@dovyih/x-tree-diff

X-Tree Diff

A implementation for X-tree Diff: An Efficient Change Detection Algorithm for Tree-structured Data.

Paper link: https://link.springer.com/chapter/10.1007/3-540-45036-X_74.

install

npm install --save @dov/x-tree-diff
# or
yarn add @dov/x-tree-diff

Usage

import { XMLXTreeDiff } from '@dov/x-tree-diff'

const xmlStr = `<Meta>
  <Author>yidafu(dov yih)</Author>
  <Title>x-tree-diff</Title>
</Meta>`;

const xmlStr2 =  `<Meta>
<Author>yidafu(dov yih)</Author>
<Name>x-tree-diff</Name>
</Meta>`;

const xmlDiff = new XMLXTreeDiff(xmlStr, xmlStr2);
const { oldTree, newTree } = xmlDiff.diff();
/*
oldTree:
<Meta op="0">
  <Author op="0">yidafu(dov yih)</Author>
  <Title op="2">x-tree-diff</Title>
</Meta>

newTree:
<Meta op="0">
  <Author op="0">yidafu(dov yih)</Author>
  <Name op="1">x-tree-diff</Name>
</Meta>
*/

Advanced Usage

if you want to implement your own Tree Struct Diff，you should implement XTreeDiff class -- two method you need impl buildXTree dumpXTree.

abstract class XTreeDiff<T> {
  public abstract buildXTree(rawTree: T): XTree;

  public abstract dumpXTree(xTree: XTree): T;
}

see src/XMLXTreeDiff.ts for more detail.

API

Implement:

• XMLXTreeDiff xml impl
• HTMLXTreeDiff Dom impl

Othor:

• XTreeDiff abstract class. Implemetn core X-Tree Diff alogrithm
• XTree core data struct
• EditOption, five option: NOP,INS,DEL,UPD,MOV

Date Structure

property	description
lable	tag name
type	Element or Text Node
value	text string value
index
nMD
tMD
nPtr
Op	EditOption
nId
pPtr
data	extra data field