v1
- by alexapp68 1/3/202500
Setup JavaScript
let _id = 0;
class Entity {
constructor(parent) {
this.id = _id++;
this.children = [];
this.parent = parent;
if (parent) {
parent.addChild(this);
}
}
addChild(child) {
this.children.push(child);
child.parent = this;
}
}
const root = new Entity(null);
const entity1 = new Entity(root);
const entity2 = new Entity(root);
const entity3 = new Entity(entity1);
const entity4 = new Entity(entity2);
const entity5 = new Entity(entity3);
const entity6 = new Entity(entity4);
const entity7 = new Entity(entity3);
const entity8 = new Entity(entity4);ready
function everyChildWithDive(node, callback, offset = 0) {
const queue = [node];
while (queue.length > 0) {
// shift() is used for breadth-first approach, use pop() for depth-first
const current = queue.shift();
callback(current);
const children = current.children;
for (let i = 0; i < children.length; i++) {
queue.push(children[i]);
}
}
}
let c = 0;
everyChildWithDive(root, (node) => { c+= node.id; });
ready
function everyChildWithDive(node, callback, offset = 0) {
let children = node.children;
let length = children.length;
if (length < 1) {
return;
}
let parent = node;
let stackIndex = 0;
const stack = [offset];
while (offset < length) {
const child = children[offset];
const result = callback(child, offset, stackIndex);
if (result === 2) {
return 2;
}
stack[stackIndex] = ++offset;
if (result !== 1) {
const childChildren = child.children;
const childChildrenLength = childChildren.length;
if (childChildrenLength > 0) {
offset = 0;
parent = child;
children = childChildren;
length = childChildrenLength;
stackIndex++;
stack.push(offset);
continue;
}
}
while (offset === length && stackIndex > 0) {
stack.pop();
offset = stack[--stackIndex];
parent = parent.parent;
children = parent.children;
length = children.length;
}
}
}
let c = 0;
everyChildWithDive(root, (node) => { c+= node.id; });
ready
function everyChildWithDive(node, callback, offset = 0) {
const stack = [{ node, index: offset, depth: 0 }];
while (stack.length > 0) {
const { node: currentNode, index: currentIndex, depth } = stack.pop();
const children = currentNode.children;
for (let i = currentIndex; i < children.length; i++) {
const child = children[i];
const result = callback(child, i, depth);
stack.push({ node: child, index: 0, depth: depth + 1 });
break;
}
}
}
let c = 0;
everyChildWithDive(root, (node) => { c+= node.id; });
ready
function everyChildWithDive(node, callback, offset = 0) {
let children = node.children;
let length = children.length;
if (length < 1) {
return;
}
if (offset < 0) {
offset += length;
}
const stack = [offset];
let stackIndex = 0;
while (stackIndex >= 0) {
const currentOffset = stack[stackIndex];
while (currentOffset < length) {
const child = children[currentOffset];
const result = callback(child, currentOffset, stackIndex);
if (result === 2) {
return 2;
}
if (result !== 1) {
const childChildren = child.children;
const childChildrenLength = childChildren.length;
if (childChildrenLength > 0) {
stackIndex++;
stack.push(0);
children = childChildren;
length = childChildrenLength;
break;
}
}
stack[stackIndex] = ++currentOffset;
}
if (currentOffset >= length) {
stackIndex--;
if (stackIndex >= 0) {
children = node.children;
length = children.length;
}
}
}
}
let c = 0;
everyChildWithDive(root, (node) => { c+= node.id; });