Tree: equality #39
Description
We need an equals() function to determine whether two nodes (a.k.a. the root of their own subgraphs) are logically equivalent to each other. Since we're dealing with copies of TreeStates that may have their children list rearranged a bit, we need to do some logical computation to verify that they contain the same types of elements in the same frequency.
Calling the following template inside TreeState.h:
static bool equals(TreeState* first, TreeState* second)
will essentially call the TreeNode.h's equals function on the two TreeState's roots, with the function defined as follows:
bool equals(TreeNode* other)
This checks if the two nodes are the same type and then recursively checks all the children of each tree to ensure that they have a counterpart in the other. Placeholders should be ignored, while statements need an additional check for their name() equality.
The tricky bit here is that the two children lists of each node may not be in the same order, so we'll probably need some kind of O(n^2) operation to see if another node has the same details and children of its own. Further complications are that we can't just test types against each other. For example, a node can have multiple cut elements as its children, and this equality function needs to be able to determine which (if any) cut goes with which cut on the other. Sometimes it may be as easy as comparing the size of its own children list, but this can easily get much more complicated.
If I were to guess, recursion with DFS is probably the best way to accomplish this, but I'd definitely have to sit down and plan this all out before hand.
UPDATE:
This is dependent on issue #36