Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | /* eslint-disable */
import { v4 as uuidv4 } from 'uuid';
import TreeUtils from '../../utils/TreeUtils';
export default class Node {
values;
children;
parent;
id;
constructor(node = 0) {
this.values = [];
this.children = [];
this.parent = undefined;
this.id = `N${uuidv4()}`;
if (node !== 0) {
for (let i = 0; i < node.children.length; i++) {
this.children.push(new Node(node.children[i]));
this.children[i].parent = this;
}
this.parent = node.parent;
this.values = node.values;
}
}
split() {
const parent = new Node();
this.parent = parent;
const right = new Node();
right.parent = parent;
right.values = this.values.slice(3);
right.children = this.children.slice(3);
for (let i = 0; i < right.children.length; i++) right.children[i].parent = right;
parent.children.push(this, right);
parent.values.push(this.values[2]);
this.values = this.values.slice(0, 2);
this.children = this.children.slice(0, 3);
return parent;
}
findIdxPos(val) {
let idx = 0;
while (val >= this.values[idx] && idx <= this.values.length) {
idx += 1;
}
return idx;
}
getLeft() {
if (this.parent === undefined) {
return undefined;
}
const value = this.values[0];
const idx = this.parent.findIdxPos(value);
if (idx > 0) {
return this.parent.children[idx - 1];
}
return undefined;
}
getRight() {
if (this.parent === undefined) {
return undefined;
}
const value = this.values[this.values.length - 1];
const idx = this.parent.findIdxPos(value);
if (idx < this.parent.children.length - 1) {
return this.parent.children[idx + 1];
}
return undefined;
}
insertIndex(value, node = undefined) {
let idx = 0;
while (value > this.values[idx] && idx < this.values.length) {
idx += 1;
}
if (this.values[idx] === value) {
return; // value existiert bereits
}
if (node !== undefined) {
this.values.splice(idx, 0, node.values[0]);
this.children.splice(idx + 1, 0, node.children[1]);
for (let i = 0; i < this.children.length; i += 1) {
this.children[i].parent = this;
}
// eslint-disable-next-line no-param-reassign
node.parent = this.parent;
} else {
this.values.splice(idx, 0, value);
}
}
isLeaf() {
return this.children.length === 0;
}
}
|