idlize

1
/*
2
 * Copyright (c) 2022-2023 Huawei Device Co., Ltd.
3
 * Licensed under the Apache License, Version 2.0 (the "License");
4
 * you may not use this file except in compliance with the License.
5
 * You may obtain a copy of the License at
6
 *
7
 * http://www.apache.org/licenses/LICENSE-2.0
8
 *
9
 * Unless required by applicable law or agreed to in writing, software
10
 * distributed under the License is distributed on an "AS IS" BASIS,
11
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
 * See the License for the specific language governing permissions and
13
 * limitations under the License.
14
 */
15

16
import { assert } from "chai"
17
import { TreeNode } from "../../src/tree/TreeNode"
18

19
class StringNode extends TreeNode {
20
    readonly content: string
21

22
    constructor(content: string, ...children: StringNode[]) {
23
        super()
24
        this.content = content
25
        this.appendChildren(...children)
26
    }
27

28
    toString(): string {
29
        return this.content
30
    }
31
}
32

33
function contentOf(node: TreeNode) {
34
    return (node as StringNode)?.content
35
}
36

37
function assertContent(node: TreeNode, content: string) {
38
    assert.equal(contentOf(node), content)
39
}
40

41
function assertRoot(node: TreeNode) {
42
    assert.isUndefined(node.parent)
43
    assert.equal(node.depth, 0)
44
    assert.equal(node.index, -1)
45
}
46

47
function assertLeaf(node: TreeNode) {
48
    assert.equal(node.childrenCount, 0)
49
}
50

51
function assertNoChildAt(parent: TreeNode, index: number) {
52
    assert.isUndefined(parent.childAt(index))
53
}
54

55
function assertChildAt(parent: TreeNode, index: number): TreeNode {
56
    let child = parent.childAt(index)
57
    assert.isDefined(child)
58
    assert.equal(child?.parent, parent)
59
    assert.equal(child?.index, index)
60
    return child!
61
}
62

63
function assertToString(root: TreeNode, expected: string) {
64
    assert.equal(root.toHierarchy(), expected)
65
}
66

67
function assertRemoveChildrenAt(root: TreeNode, index: number, count: number, expected: number) {
68
    let childrenCount = root.childrenCount
69
    let children = root.removeChildrenAt(index, count)
70
    assert.equal(children.length, expected)
71
    assert.equal(root.childrenCount, childrenCount - expected)
72
    for (let i = 0; i < expected; i++) {
73
        assertRoot(children[i])
74
    }
75
}
76

77
function createRoot() {
78
    return new StringNode("root",
79
        new StringNode("first"),
80
        new StringNode("second"),
81
        new StringNode("third"))
82
}
83

84
function createDigitsRoot() {
85
    return new StringNode("digits",
86
        new StringNode("0"),
87
        new StringNode("1"),
88
        new StringNode("2"),
89
        new StringNode("3"),
90
        new StringNode("4"),
91
        new StringNode("5"),
92
        new StringNode("6"),
93
        new StringNode("7"),
94
        new StringNode("8"),
95
        new StringNode("9"))
96
}
97

98
suite("TreeNode", () => {
99
    test("single node", () => {
100
        let node = new StringNode("node")
101
        assertContent(node, "node")
102
        assertRoot(node)
103
        assertLeaf(node)
104
    })
105
    test("simple root", () => {
106
        let root = createRoot()
107
        assertContent(root, "root")
108
        assertRoot(root)
109
        assert.equal(root.childrenCount, 3)
110
        assertNoChildAt(root, Number.MIN_VALUE)
111
        assertNoChildAt(root, Number.MAX_VALUE)
112
        assertNoChildAt(root, Number.MIN_SAFE_INTEGER)
113
        assertNoChildAt(root, Number.MAX_SAFE_INTEGER)
114
        assertNoChildAt(root, -1)
115
        assertNoChildAt(root, 3)
116
        assertNoChildAt(root, 0.1)
117
        assertNoChildAt(root, 2.9)
118
        let node0 = assertChildAt(root, 0)
119
        assertContent(node0, "first")
120
        assertLeaf(node0)
121
        let node1 = assertChildAt(root, 1)
122
        assertContent(node1, "second")
123
        assertLeaf(node1)
124
        let node2 = assertChildAt(root, 2)
125
        assertContent(node2, "third")
126
        assertLeaf(node2)
127
        const children = root.children.slice()
128
        assert.equal(children.length, 3)
129
        assert.equal(children[0], node0)
130
        assert.equal(children[1], node1)
131
        assert.equal(children[2], node2)
132
        assertToString(root,
133
            "root\n" +
134
            "  first\n" +
135
            "  second\n" +
136
            "  third")
137
    })
138
    test("iterate for each child", () => {
139
        let root = createRoot()
140
        let count = 0
141
        let children = ["first", "second", "third"]
142
        root.forEach(node => {
143
            assert.equal(children[count], contentOf(node))
144
            count++
145
        })
146
        assert.equal(count, 3)
147
    })
148
    test("iterate for each child with index", () => {
149
        let root = createRoot()
150
        let count = 0
151
        root.forEach((node, index) => {
152
            assert.equal(index, count)
153
            count++
154
        })
155
        assert.equal(count, 3)
156
    })
157
    test("iterate through not every child", () => {
158
        let root = createRoot()
159
        let count = 0
160
        assert(!root.every(node => {
161
            count++
162
            return contentOf(node).length == 5
163
        }))
164
        assert.equal(count, 2)
165
    })
166
    test("iterate through every child with index", () => {
167
        let root = createRoot()
168
        let count = 0
169
        let children = ["first", "second", "third"]
170
        assert(root.every((node, index) => {
171
            assert.equal(index, count)
172
            count++
173
            return children[index] === contentOf(node)
174
        }))
175
        assert.equal(count, 3)
176
    })
177
    test("iterate through some children", () => {
178
        let root = createRoot()
179
        let count = 0
180
        assert(root.some(node => {
181
            count++
182
            let size = contentOf(node).length
183
            return contentOf(node).length == 6
184
        }))
185
        assert.equal(count, 2)
186
    })
187
    test("iterate through some children with index", () => {
188
        let root = createRoot()
189
        let count = 0
190
        assert(root.some((node, index) => {
191
            assert.equal(index, count)
192
            count++
193
            return index == 0
194
        }))
195
        assert.equal(count, 1)
196
    })
197
    test("find child by content", () => {
198
        let root = createRoot()
199
        assert.equal(root.find((node):TreeNode|undefined => contentOf(node) == "second" ? node : undefined), assertChildAt(root, 1))
200
    })
201
    test("find child by index", () => {
202
        let root = createRoot()
203
        assert.equal(root.find((node, index):TreeNode|undefined => index == 1 ? node : undefined), assertChildAt(root, 1))
204
    })
205
    test("insert, move and remove children", () => {
206
        let root = createRoot()
207
        assert(!root.removeChild(new StringNode("second"))) // non-existent node
208
        assertToString(root,
209
            "root\n" +
210
            "  first\n" +
211
            "  second\n" +
212
            "  third")
213
        let second = assertChildAt(root, 1)
214
        second.appendChildren(new StringNode("1"), new StringNode("2"), new StringNode("3"))
215
        assertToString(root,
216
            "root\n" +
217
            "  first\n" +
218
            "  second\n" +
219
            "    1\n" +
220
            "    2\n" +
221
            "    3\n" +
222
            "  third")
223
        second.removeFromParent()
224
        assertRoot(second)
225
        assertToString(second,
226
            "second\n" +
227
            "  1\n" +
228
            "  2\n" +
229
            "  3")
230
        assertToString(root,
231
            "root\n" +
232
            "  first\n" +
233
            "  third")
234
        assert(!root.removeChild(second)) // cannot remove twice
235
        assert(root.insertChildAt(0, second))
236
        assertToString(root,
237
            "root\n" +
238
            "  second\n" +
239
            "    1\n" +
240
            "    2\n" +
241
            "    3\n" +
242
            "  first\n" +
243
            "  third")
244
        let first = root.removeChildAt(1)
245
        assert.isDefined(first)
246
        assertRoot(first!)
247
        assertContent(first!, "first")
248
        root.appendChild(first!)
249
        assertToString(root,
250
            "root\n" +
251
            "  second\n" +
252
            "    1\n" +
253
            "    2\n" +
254
            "    3\n" +
255
            "  third\n" +
256
            "  first")
257
    })
258
    test("insert several children at once", () => {
259
        let root = createRoot()
260
        let children = [new StringNode("second.1"), new StringNode("second.2"), new StringNode("second.3")]
261
        assert(!root.insertChildrenAt(Number.MIN_VALUE, ...children))
262
        assert(!root.insertChildrenAt(Number.MAX_VALUE, ...children))
263
        assert(!root.insertChildrenAt(Number.MIN_SAFE_INTEGER, ...children))
264
        assert(!root.insertChildrenAt(Number.MAX_SAFE_INTEGER, ...children))
265
        assert(!root.insertChildrenAt(-1, ...children))
266
        assert(!root.insertChildrenAt(4, ...children))
267
        assert(!root.insertChildrenAt(0.1, ...children))
268
        assert(!root.insertChildrenAt(2.9, ...children))
269
        assert(root.insertChildrenAt(2, ...children))
270
        assertToString(root,
271
            "root\n" +
272
            "  first\n" +
273
            "  second\n" +
274
            "  second.1\n" +
275
            "  second.2\n" +
276
            "  second.3\n" +
277
            "  third")
278
        assert(root.insertChildrenAt(0, new StringNode("zero")))
279
        assertToString(root,
280
            "root\n" +
281
            "  zero\n" +
282
            "  first\n" +
283
            "  second\n" +
284
            "  second.1\n" +
285
            "  second.2\n" +
286
            "  second.3\n" +
287
            "  third")
288
        assert(root.insertChildrenAt(root.childrenCount, new StringNode("third.A"), new StringNode("third.B")))
289
        assertToString(root,
290
            "root\n" +
291
            "  zero\n" +
292
            "  first\n" +
293
            "  second\n" +
294
            "  second.1\n" +
295
            "  second.2\n" +
296
            "  second.3\n" +
297
            "  third\n" +
298
            "  third.A\n" +
299
            "  third.B")
300
    })
301
    test("remove several children at once", () => {
302
        let root = createDigitsRoot()
303
        assertToString(root,
304
            "digits\n" +
305
            "  0\n" +
306
            "  1\n" +
307
            "  2\n" +
308
            "  3\n" +
309
            "  4\n" +
310
            "  5\n" +
311
            "  6\n" +
312
            "  7\n" +
313
            "  8\n" +
314
            "  9")
315
        assertRemoveChildrenAt(root, Number.MIN_VALUE, 1, 0)
316
        assertRemoveChildrenAt(root, Number.MAX_VALUE, 1, 0)
317
        assertRemoveChildrenAt(root, Number.MIN_SAFE_INTEGER, 1, 0)
318
        assertRemoveChildrenAt(root, Number.MAX_SAFE_INTEGER, 1, 0)
319
        assertRemoveChildrenAt(root, -1, 1, 0)
320
        assertRemoveChildrenAt(root, root.childrenCount, 1, 0)
321
        assertRemoveChildrenAt(root, 0.1, 1, 0)
322
        assertRemoveChildrenAt(root, 2.9, 1, 0)
323
        // remove leading nodes
324
        assertRemoveChildrenAt(root, 0, 1 + root.childrenCount, 0)
325
        assertRemoveChildrenAt(root, 0, 2, 2)
326
        assertToString(root,
327
            "digits\n" +
328
            "  2\n" +
329
            "  3\n" +
330
            "  4\n" +
331
            "  5\n" +
332
            "  6\n" +
333
            "  7\n" +
334
            "  8\n" +
335
            "  9")
336
        // remove trailing nodes
337
        assertRemoveChildrenAt(root, root.childrenCount - 1, 2, 0)
338
        assertRemoveChildrenAt(root, root.childrenCount - 2, 2, 2)
339
        assertToString(root,
340
            "digits\n" +
341
            "  2\n" +
342
            "  3\n" +
343
            "  4\n" +
344
            "  5\n" +
345
            "  6\n" +
346
            "  7")
347
        // remove inner nodes
348
        assertRemoveChildrenAt(root, 1, root.childrenCount, 0)
349
        assertRemoveChildrenAt(root, 1, 4, 4)
350
        assertToString(root,
351
            "digits\n" +
352
            "  2\n" +
353
            "  7")
354
    })
355
    test("remove trailing children at once", () => {
356
        let root = createDigitsRoot()
357
        assert.equal(root.childrenCount, 10)
358
        assert.equal(root.removeChildrenAt(Number.MIN_VALUE).length, 0)
359
        assert.equal(root.removeChildrenAt(Number.MAX_VALUE).length, 0)
360
        assert.equal(root.removeChildrenAt(Number.MIN_SAFE_INTEGER).length, 0)
361
        assert.equal(root.removeChildrenAt(Number.MAX_SAFE_INTEGER).length, 0)
362
        assert.equal(root.removeChildrenAt(-1).length, 0)
363
        assert.equal(root.removeChildrenAt(root.childrenCount).length, 0)
364
        assert.equal(root.removeChildrenAt(0.1).length, 0)
365
        assert.equal(root.removeChildrenAt(2.9).length, 0)
366
        assert.equal(root.childrenCount, 10)
367
        assert.equal(root.removeChildrenAt(7).length, 3)
368
        assert.equal(root.childrenCount, 7)
369
        assert.equal(root.removeChildrenAt(6).length, 1)
370
        assert.equal(root.childrenCount, 6)
371
        assert.equal(root.removeChildrenAt(1).length, 5)
372
        assert.equal(root.childrenCount, 1)
373
        assert.equal(root.removeChildrenAt(0).length, 1)
374
        assert.equal(root.childrenCount, 0)
375
    })
376
})
377