Message from JavaScript discussions
September 2017
— I am recreating Array.prototype.filter for object trees... but it's harder than I thought
Either I can code it memory inefficient and clone the object tree all the time, discarding parts it turns out were not needed, or I can store an index of "current path in tree" and backtrack, which is processing inefficient!
— The issue is, the algorithm won't know what subsections of the graph need to be cloned until a nested value triggers true from the filter callback
— So you could be 100 nodes deep... and either be ready to throw ALL of them in the trash, or backtrack to clone them, revisiting each one
— I like the index part better since it would use a bit less memory, however I'm not sure how to integrate it into an external strategy that can't see inside the search algorithm! It won't know when a branch occurs at all to change it's working path
— The MAIN issue though, is the choice of search algorithm. I am using IDDFS which works all wonky like, going forwards to enumerate and backwards to traverse, in a first-in last-out fashion... if I used recursive DFS it would traverse the first node it sees etc... whereas in IDDFS we would skip past nodes to traverse the very last one that was seen
— Hmm... I figured it out by using a nifty behavior of my iddfs. Data parity can be established between the node stack and another stack, which can be a path stack (an ordered set of arrays of strings). By adding to the path stack when I add to the node stack, I get a list of all paths the algorithm went down! Problem defeated haha
— Now I can use those paths to backtrack and recreate a subgraph from the root node, even though I'm not using DFS to eliminate the subgraph
— This is also great for unit tests since now I have an explicit log of the paths that were taken, and they are deterministic so very easily expect able
— Https://github.com/Floofies/Differentia.js/blob/master/spec/Spec.js#L34
— Here is the test object
— This rule means that i can speak russian?:
- Feel free to speak any language.