casey-c
commented
7 years ago I thought about it more and figured the stack of QLists would be the way to go. I let it just simmer for a bit and out of the blue figured out a semi-okay way to do it. I've implemented it in https://github.com/casey-c/egg/commit/a7ad0fd1c761a4a1cf7277acdc6c3d9898dfa649 . I think it's okay, but I'm not positive that it works 100%. I also hope I didn't break any of the other operators, but I think they're okay as far as I can tell.
It was pretty tricky to come up with this solution, and coding it up turned out to be just as messy and disgusting as I thought it'd be. I'm know for sure there's a lot of room for cleanup (this is one of the worst commits ever in this project, IMO), but I'm too tired to figure it out right now. I'm going to try and do some cleanup and hopefully stumble upon a better solution that doesn't involve code duplication (root nodes and non root nodes are handled the same way with a very minor difference...) and hopefully am able to come up with some compact, reusable functions for the operators, since they all kind of do the same thing.
If I can get rid of the root's dupe code and see if I can shrink the if-else chain to be a bit more readable, I'd be happy. I'll try and get to this when I document this branch.
The biconditional (%) of the new formula input (I) window is broken. It's a bit more complicated than all the other operators. Other operators work great with the stack data structure - just pop, set, and add. Biconditionals unfortunately have a required symmetry in their existential graph conversion: P ↔ Q becomes:
which doesn't really translate well when the stack input ↔ P Q pops the desired key and sets it immediately, making the TreeNodes that it needs to fill, and filling them as soon as those nodes are popped from their own todo stack.
Biconditionals need to make multiple copies of the graphs, just with the inputs swapped. With a longer and more complicated equation like: (P ∧ (Q ∨ R)) ↔ ¬(S ∧ T), this issue becomes far more pronounced. We no longer have to copy just P and Q as above, but entire operator chains. This simply doesn't work with the stack data structure, but I'm hesitant to make a work around that gets rid of the stack simply because it's so good, relatively clean, and simple to implement for the other "normal" operators.
The current implementation maintains two parallel stacks, one for the actual polish notation input, and one for the created existential graph nodes. They get popped and set in unison, and when the formula is well-formed, both stacks are empty and the existential graph is fully and correctly built. Workarounds for the biconditional would either need to add a lot of excess case checking for biconditionals and lots of extra logic for copying the graph but switching places, or do away with the stack altogether, and only build the existential graph at the very end instead of as it is inputted.
The second option is probably the most viable, but it would involve parsing the polish notation (↔ ∧ P ∨ Q R ¬ ∧ S T in the above example) tree a second time, and would still require lots of additional branching to duplicate the biconditional halves. If we kept the stack, we'd probably have a stack of QList<TreeNode*>, where normal operators QLists' would have only one element as usual, but the biconditional would update every item in the list. It'd be doable but quite the headache.
Any solution that I can think of at the moment would be far too messy and difficult to maintain if necessary. I only see a single good option at the moment; disable the keybind for the biconditional operator and set it as a future goal to implement later.