Code Review Asked by Kittoes0124 on January 27, 2021
Despite the many decent answers to this question, one was unable to find an iterative solution. Here’s what I came up with:
Code:
type CircularReferenceHandler = (parentKey: IndexKey, parentValue: Dictionary<IndexKey, any>, childKey: IndexKey, childValue: Dictionary<IndexKey, any>) => void;
type Dictionary<TKey extends IndexKey, TValue> = Record<TKey, TValue>;
type IndexKey = (number | string);
const processCircularReferences = <T extends object>(input: T, handler: CircularReferenceHandler, initialPathValue = "o"): T => {
const objectStack = [{ k: initialPathValue, v: input, },];
const objectTracker = new WeakSet<Dictionary<IndexKey, any>>();
objectTracker.add(input);
while (objectStack.length) {
const { k: parentKey, v: parentValue } = objectStack.shift()!;
for (const [childKey, childValue] of Object.entries(parentValue)) {
if ((childValue && ("object" === typeof childValue))) {
if (objectTracker.has(childValue)) {
handler(parentKey, parentValue, childKey, childValue);
}
else {
objectStack.push({ k: `${parentKey}.${childKey}`, v: childValue, });
objectTracker.add(childValue);
}
}
}
}
return input;
}
Usage:
let o: any = { x: 0, y: 1, };
o.me = {};
o.me.self = o;
o.self = o;
processCircularReferences(o, (pK, pV, cK, _cV) => {
console.log(`${pK}.${cK}`);
pV[cK] = undefined;
});
console.log(o);
/*
[log]: o.me.self
[log]: o.self
[log]: {
me: {
self: undefined
},
self: undefined,
x: 0,
y: 1
}
*/
.join('.')
the list, or do something else, it's up to the callback. An added bonus: You can get rid of the initialPathValue parameter since that just has to do with formatting the result, not the business logic.Here's an example (in javascript) that applies the above suggestions:
const topOfStack = array => array[array.length - 1];
function* findCircularReferences(rootObj) {
const stack = [{ path: [], objectsInPath: [rootObj] }];
while (stack.length) {
const { path, objectsInPath } = stack.pop();
for (const [childKey, childObj] of Object.entries(topOfStack(objectsInPath))) {
if (typeof childObj !== 'object' || childObj === null) continue;
const nextStackEntry = {
path: [...path, childKey],
objectsInPath: [...objectsInPath, childObj],
};
if (objectsInPath.includes(childObj)) {
yield nextStackEntry;
} else {
stack.push(nextStackEntry);
}
}
}
}
// Should find two circular references
const obj1 = { obj3: null };
const obj2 = { obj1, 'obj1-again': obj1 };
const obj3 = { obj2 };
obj1.obj3 = obj3;
console.log([...findCircularReferences(obj1)].map(({ path }) => path));
// Should not find any circular references
const dupEntry = { x: 2 };
console.log([...findCircularReferences([dupEntry, dupEntry])].map(({ path }) => path));
Answered by Scotty Jamison on January 27, 2021
Following testcase breaks your code:
const o={};
o.x = o.y = {};
This is due to objectTracker
tracks all seen values not all parent values.
initialPathValue
looks strange to me. The parameter has no meaning to this function as far as I can tell..
s in keys. For example: { "a.b": {}, "a": { "b": {} } }
. To avoid any confusion, I would suggest use string[]
instead.objectStack
is named as Stack, but you are using it as a Queue. I believe there should be a mistake here. Maybe you want pop()
instead of shift()
.parentValue
is a WeakSet
. But I cannot find a reason why any objects in it will be garbage collected during the functions life cycle. So maybe a simple Set
would fint your requirement.Answered by tsh on January 27, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP