long and stupid 

(Written while programming today. Ignore this post!)
Programming today:

Writing a node replacement function `replace_node_with_new` for my [python shallow tree library](github.com/jmacc93/shtree_py)

I find I need to be able to remove each child subtree from the to-be-removed node (or else I might end up with an accidental forest)

So I have to make a subtree remover function `remove_subtree`. But its probably a better idea to change the existing `remove_node` function so it has an option to remove child nodes too recursively (thus removing the subtree). Unfortunately, I could use recursion, but some subtrees might be potentially really deep, so I'll have to make a leaf-first node index generator to iterate a subtree so I can remove it without function recursion. Which is tricky because if the node you yielded is mutated (eg: removed) after the yield, and you try to get properties from that node, then that will fail or result in undefined behavior

---

Ok, finished with the subtree node generator and test. And with `remove_node`, and `replace_node_with_new`. And I'm mostly finished with a `replace_node` that I also wrote but ran into a bug, so I'll shelve that function for now. For reference, this all took 2 hours

Ran into some test failures with `remove_node`, which I solved by collecting all the traversed child subtree nodes and then just nullifying them in the tree (setting them to `None` nullifies them itc), which is much faster (and evidently less error prone) than calling `disconnect_parent`, etc on each child. While doing this, I noticed my random tree building and destroying `remove_node` unit test much more quickly destroys the tree it builds when it picks a random node and removing that node and its subtree, rather than just removing the node itself. This makes sense, but now I'm wondering how many random selections and `remove_node` calls with subtree removal it takes to destroy a tree on average. I might write a script to test this later

---

And now that i have `replace_node_with_new`, I can move on to the completing `greater_than_ef` which is what SetTL's draft executor calls when it encounters a `>` function (or it will, when I finish it), and needed `replace_node_with_new` to be finishable

Ok, I finished `greater_than_ef` and it seems to work, but I discovered the executor now is skipping certain parent call nodes for those nodes' parents, instead of calling the call nodes and continuing to their parents

I found that this problem was because I wasn't returning `True` from `print_ef`, which is an external function that removes itself during its execution, and so it also advances the execution head during its execution. External functions like `print_ef` can advance to the next executable node on their own, and if they don't advance the executor will advance after they're done, but to signal to the executor that an external function has advanced, and the executor shouldn't advance automatically, the external function should return `True`, or something else not `None`. Since I wasn't returning `True`, the `print_ef` function was advancing, and then the executor was advancing automatically as well, so every time I called `print_ef` while testing `greater_than_ef` it would skip over one node during execution

Anyway, I fixed that, and after fixing it I discovered that I can cheat a little with simple external functions and made `generic_fn_ef` which creates a closure that acts like `greater_than_ef` and a lesser than ef and all other n-ary operations, and all other kinds of functions otherwise that just take arguments and return a result. So I can even replace `print_ef`, and probably any other function that doesn't mess around with the stack or have to return non-value nodes, or whatever.

This took around 2 hours

---

Now since I have some condition to test with (`5 < 10`): onto testing the implementation I wrote yesterday of `if_ef` -- which is the analog of `if`, `if-else`, `if-else-if`, etc statements

I'm immediately running into the issue that the 3 print statements in the `if` statement I'm testing are all printing, when only one should print depending which condition in the `if` arguments is evaluating to true.

..
After about 2 hours of running into multiple small bugs, `if_ef` apparently works correctly

Follow

I tested how long it takes to entirely remove all nodes from a randomly constructed tree such that if you remove a parent node all child nodes below it are also removed, and it seems that on average the removal-count-complexity is O(sqrt(n)) where n is the number of initial nodes in the random tree. If you remove the nodes one by one, with no subtree removal on parent removal, then it takes n steps to remove all the nodes

Note: the O(sqrt(n)) complexity depends on what type of random graph is constructed; I built the random graphs for this test by adding a new child to a uniformly-selected random node in the graph

Now to try and find why this is true, theoretically (I imagine its either really simple or really complex)

Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves
An inclusive, Academic Freedom, instance
All cultures welcome.
Hate speech and harassment strictly forbidden.