/
KeyTree.js
121 lines (107 loc) · 4.06 KB
/
KeyTree.js
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import { compareString } from 'source/common/compare.js'
import { createTreeDepthFirstSearch } from 'source/common/data/Tree.js'
// NOTE:
// - keyTreeJSON (source data):
// ```
// [
// { key: 'key',
// subList: [
// { key: 'key',
// subList: [
// { key: 'key' },
// { key: 'key' }
// ]
// },
// { key: 'key' }
// ]
// },
// { key: 'key' },
// { key: 'key' }
// ]
// ```
// - keyTreeString (compact save format):
// `key[key[key,key]key]key,key`
// TODO: HACK:
// for the replace method to work, the value should not have `{}[],":`
// or just use [a-zA-Z0-9_-]
const REGEXP_NAME = /[\w-]+/
const createKeyTree = ({
NAME_KEY = 'key', // should be /\w+/
NAME_SUB_LIST = 'subList' // should be /\w+/
}) => {
if (!REGEXP_NAME.test(NAME_KEY)) throw new Error(`expect ${NAME_KEY} to match: ${REGEXP_NAME}`)
if (!REGEXP_NAME.test(NAME_SUB_LIST)) throw new Error(`expect ${NAME_SUB_LIST} to match: ${REGEXP_NAME}`)
const stringify = (keyTreeJSON) => JSON.stringify(keyTreeJSON)
.replace(REGEXP_MAX_BRACKET_LEFT, '[')
.replace(REGEXP_MAX_BRACKET_RIGHT, (match, $1) => ']'.repeat($1.length / 2))
.replace(REGEXP_MAX_COMMA, ',')
const REGEXP_MAX_COMMA = new RegExp(`"},{"${NAME_KEY}":"`, 'g')
const REGEXP_MAX_BRACKET_LEFT = new RegExp(`(?:","${NAME_SUB_LIST}":|^)\\[{"${NAME_KEY}":"`, 'g')
const REGEXP_MAX_BRACKET_RIGHT = new RegExp(`"((?:}])+)(?:},{"${NAME_KEY}":"|$)`, 'g')
const parse = (keyTreeString) => JSON.parse(
keyTreeString
.replace(REGEXP_MIN_COMMA, `"},{"${NAME_KEY}":"`)
.replace(REGEXP_MIN_BRACKET_RIGHT, (match, $1, offset, string) => `"${'}]'.repeat($1.length)}${offset + match.length !== string.length ? `},{"${NAME_KEY}":"` : ''}`)
.replace(REGEXP_MIN_BRACKET_LEFT, (match, offset) => `${offset !== 0 ? `","${NAME_SUB_LIST}":` : ''}[{"${NAME_KEY}":"`)
)
const REGEXP_MIN_COMMA = /,/g
const REGEXP_MIN_BRACKET_LEFT = /\[/g
const REGEXP_MIN_BRACKET_RIGHT = /(]+)/g
return { stringify, parse }
}
const createKeyTreeEnhanced = ({
NAME_KEY = 'key', // should be /\w+/
NAME_SUB_LIST = 'subList' // should be /\w+/
}) => {
const createBuilder = (rootKey) => {
const listMap = new Map()
const add = (key, position, upperKey) => {
let list = listMap.get(upperKey)
if (list === undefined) {
list = []
listMap.set(upperKey, list)
}
list.push([ key, position ])
}
const build = () => {
const rootSubList = []
let initKey = rootKey
while (initKey) {
const { [ NAME_SUB_LIST ]: subList } = buildSub(initKey)
__DEV__ && initKey !== rootKey && console.log(`appending unlinked ${NAME_KEY} from ${initKey}`, subList)
if (subList !== undefined) rootSubList.push(...subList)
initKey = listMap.keys().next().value
}
return rootSubList.length === 0
? { [ NAME_KEY ]: rootKey }
: { [ NAME_KEY ]: rootKey, [ NAME_SUB_LIST ]: rootSubList }
}
const buildSub = (key) => {
const object = { [ NAME_KEY ]: key }
const subList = listMap.get(key)
listMap.delete(key)
if (subList !== undefined && subList.length !== 0) object[ NAME_SUB_LIST ] = subList.sort(sortFunc).map(([ subKey ]) => buildSub(subKey))
return object
}
const sortFunc = ([ keyA, positionA ], [ keyB, positionB ]) => positionA - positionB || compareString(keyA, keyB)
return { add, build }
}
const keyTreeJSONDepthFirstSearch = createTreeDepthFirstSearch(([ node, index, upperKey ]) => (
node[ NAME_SUB_LIST ] &&
node[ NAME_SUB_LIST ].length &&
node[ NAME_SUB_LIST ].map((subNode, index) => [ subNode, index, node[ NAME_KEY ] ])
))
const walkKeyTreeJSON = (
keyTreeJSON,
func = ([ node, index, upperKey ]) => {} // return true to stop search
) => keyTreeJSONDepthFirstSearch([ keyTreeJSON, 0, undefined ], func)
return {
...createKeyTree({ NAME_KEY, NAME_SUB_LIST }),
createBuilder,
walkKeyTreeJSON
}
}
export {
createKeyTree,
createKeyTreeEnhanced
}