-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs.ts
86 lines (76 loc) · 1.61 KB
/
bfs.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/* eslint-disable functional/prefer-readonly-type */
/* eslint-disable functional/no-loop-statement */
/* eslint-disable functional/immutable-data */
import { Obj, Result } from './types';
import { getPropsAmount, isDiffSimply, joinPath } from './utils';
/**
* !just simply consider it will only change one path in one operation!
* !and think prop will never have function value!
* !don't support add/remove/move item in array!
*
* add item:
* {
* children: []
* }
* to:
* {
* children: [
* { ... }
* ]
* }
*
* remove item:
* {
* children: [{ ... }]
* }
* to:
* {
* children: []
* }
*
* move item:
* {
* children: [
* {name: 'one'},
* {name: 'two'}
* ]
* }
* to:
* {
* children: [
* {name: 'two'},
* {name: 'one'}
* ]
* }
* @param newObj
* @param oldObj
*/
export function getDiffByBFS(newObj: Obj, oldObj: Obj): Result | null {
const newObjs: Obj[] = [newObj]
const oldObjs: Obj[] = [oldObj]
const paths: string[] = ['']
while (newObjs.length) {
const newTarget = newObjs.shift()!
const oldTarget = oldObjs.shift()!
const path = paths.shift()!
const target = getPropsAmount(newObj) >= getPropsAmount(oldObj) ? newTarget : oldTarget
for (const key in target) {
const newValue = newTarget[key] as Obj
const oldValue = oldTarget[key] as Obj
if (isDiffSimply(newValue, oldValue)) {
return {
path: joinPath(path, key),
newValue: newValue,
oldValue: oldValue,
}
}
if (typeof newValue !== 'object') {
continue
}
newObjs.push(newValue)
oldObjs.push(oldValue)
paths.push(joinPath(path, key))
}
}
return null;
}