List groupingBy Objects fields and count occurrences

Question

I've got a List<TermNode> which contains all operands of an operation like + or *. That is, it is not a binary tree structure, but rather a tree where each node may contain multiple children. A TermNode may either be a variable, an operator, a function or a number. A number and a variable node contain an empty list of children (Think of the children as arguments to an operation).

public class TermNode {

    /**
     * The value this {@link TermNode} holds.
     */
    private String value;

    /**
     * The arguments of this {@link TermNode}.
     * 
     * This {@link List} is empty if the {@link TermTypeEnum} of this {@link TermNode}
     * is either {@link TermTypeEnum}.NUMBER or {@link TermTypeEnum}.VARIABLE.
     */
    private List<TermNode> children;

    /**
     * The {@link TermTypeEnum} of this {@link TermNode}.
     */
    private TermTypeEnum type;

    public TermNode(ComplexNumber number) {
        this(number.toString(), new ArrayList<TermNode>(), TermTypeEnum.NUMBER);
    }

    public TermNode(String variable) {
        this(variable, new ArrayList<TermNode>(), TermTypeEnum.VARIABLE);
    }

    public TermNode(Operator operator, List<TermNode> children) {
        this(operator.getOperator(), children, TermTypeEnum.OPERATOR);
    }

    public TermNode(Function function, List<TermNode> children) {
        this(function.getName(), children, TermTypeEnum.FUNCTION);
    }

    public TermNode(String value, List<TermNode> children, TermTypeEnum type) {
        this.value = value;
        this.children = children;
        this.type = type;
    }

    public TermNode(TermNode node) {
        this.value = node.getValue();
        this.children = node.getChildren();
        this.type = node.getType();
    }

    /**
     * 
     * @return The value of this {@link TermNode}.
     */
    public String getValue() {
        return value;
    }

    /**
     * 
     * @return The {@link List} of arguments for this {@link TermNode}.
     */
    public List<TermNode> getChildren() {
        return children;
    }

    /**
     * 
     * @return The {@link TermTypeEnum} of this {@link TermNode}.
     */
    public TermTypeEnum getType() {
        return type;
    }

    /**
     * 
     * @return True, if this {@link TermNode} represents a {@link ComplexNumber}.
     */
    public boolean isNumber() {
        return this.type == TermTypeEnum.NUMBER;
    }

    /**
     * 
     * @return True, if this {@link TermNode} represents a variable.
     */
    public boolean isVariable() {
        return this.type == TermTypeEnum.VARIABLE;
    }

    /**
     * 
     * @return True, if this {@link TermNode} represents an {@link Operator}.
     */
    public boolean isOperator() {
        return this.type == TermTypeEnum.OPERATOR;
    }

    /**
     * 
     * @return True, if this {@link TermNode} represents a {@link Function}.
     */
    public boolean isFunction() {
        return this.type == TermTypeEnum.FUNCTION;
    }

    /**
     * 
     * @return A {@link HashSet} object to compare two {@link TermNode} elements in equality.
     */
    public HashSet<TermNode> getHash() {
        return new HashSet<>(children);
    }

}

To simplify an expression like x + x + x + x or sin(x) * sin(x) I've started to implement a method which updates a node like x + x + x + x to a 4 * x node.

---

To start with the expressions, I will provide an example with the expression x + x + x + x:

1. Compute the reverse polnish notation / the post fix order for the expression.

   The result is x x x x + + +.

2. Create the expression tree / term tree with TermNodes (see code of TermNode above). Algorithm is the following one:

   public void evaluate() {
       Stack<TermNode> stack = new Stack<TermNode>();
   
       for(String token : rpn) {
           if(OperatorUtil.containsKey(token)) {
               Operator operator = OperatorUtil.getOperator(token);
               List<TermNode> children = new ArrayList<TermNode>() {{
                   add(stack.pop());
                   add(stack.pop());
               }};
   
               TermNode node = simplifyOperator(operator, children);
               stack.push(node);
           } else if(FunctionUtil.containsKey(token.toUpperCase())) {
               Function function = FunctionUtil.getFunction(token.toUpperCase());
               List<TermNode> children = new ArrayList<TermNode>(function.getNumParams());
   
               for(int i = 0; i < function.getNumParams(); i++) {
                   children.add(stack.pop());
               }
   
               TermNode node = simplifyFunction(function, children);
               stack.push(node);
           } else {
               if(VariableUtil.containsUndefinedVariable(token.toUpperCase())) {
                   stack.push(new TermNode(token));
               } else {
                   stack.push(new TermNode(new ComplexNumber(token)));
               }
           }
       }
   }
   

3. Somewhere in the simplifyOperator method I want to fold the variables with the same values. For the expression above, the tree looks like this:

               _______  OPERATOR  _______
              /           "+"            \
             /         /       \          \
       VARIABLE    VARIABLE   VARIABLE    VARIABLE
         "x"          "x"       "x"          "x"
   

4. The goal is to convert this tree to a simpler tree by evaluating the children field in the TreeNode: This expression consists of one OPERATOR TermNode with operator + with a children List<TermNode> which contains a VARIABLE TermNode with value x four times (not four times the same TermNode, just 4 TermNodes with the exact same values, children and type. Here is when my problem comes in:

   private TermNode rearrangeTerm(Operator operator, List<TermNode> children) {
       Map<TermNode, Integer> occurrences = children.stream()
               .collect(Collectors.groupingBy(term -> term, Collectors.summingInt(term -> 1)));
   
       List<Pair<TermNode, Integer>> simplification = occurrences.entrySet().stream()
               .map(entry -> new Pair<TermNode, Integer>(entry.getKey(), entry.getValue())).collect(Collectors.toList());
   
       List<TermNode> rearranged = simplification.stream().map(pair -> rearrangeTerm(operator, pair)).collect(Collectors.toList());
   
       return new TermNode(operator.getOperator(), rearranged, TermTypeEnum.OPERATOR);
   }
   

   This method is being invoked by passing the arguments rearrangeTerm(operator, children) to the method where operator is our + operator and children is our list of TermNode elements which contains the variable x four times.

   At this point term -> term the Collectors.groupingBy does not group the TermNode elements by their field values (value, children and type) but as TermNode reference itself. So the question is, how can I group TermNode elements by their fields (two TermNode elements are equal if all of their fields match (the order of the elements in the children list may be different, but what is important is that the occurrences of the elements in the children list of each TermNode match. And of course the TermNode type has to match as well. The question here is only how do I change the rearrangeTerm method so that the Map contains only one entry with ("x", 4) for the expression x + x + x + x?

Answer 1

Thanks for your answers, I ultimately had to rewrite the equals(Object obj) and the hashCode() of my TermNode class.

I followed multiple stackoverflow sites and used this approach:

@Override
public boolean equals(Object other) {
    if(this == other) {
        return true;
    }

    if((other == null) || (other.getClass() != this.getClass())) {
        return false;
    }

    TermNode node = (TermNode)other;

    return this.value.equals(node.getValue()) 
            && PlotterUtil.isEqual(this.children, node.getChildren()) 
            && this.type == node.getType();
}

Since the TermNode class contains a List<TermNode> field, one need to check if the list of arguments is equal as well, but ignore the order of the arguments since the arguments are either a single value like a number or a single variable or they are contained in another TermNode like an Operator. A Function should never ignore the order of arguments. To check for the equality of two lists I used this code from here.

public static boolean isEqual(List<TermNode> one, List<TermNode> two) {
    if(one == null && two == null) {
        return true;
    }

    if((one != null && two == null) || (one == null && two != null)) {
        return false;
    }

    if(one.size() != two.size()) {
        return false;
    }

    one = getSortedList(one);
    two = getSortedList(two);

    return one.equals(two);
}

This also solves the problem with

Map<TermNode, Integer> occurrences = 
    children.stream().collect(Collectors
        .groupingBy(term -> term, Collectors.summingInt(term -> 1))
    );

because the Map<TermNode, Integer> checks for equal keys in term -> term via the equals(Object obj) and the hashCode() methods of an object.

Answer 2

This would be far too long for a comment here, so posting as an answer...

So the general idea is that you need to be able to tell if two TermNodes objects are the same or not; for that you could add a method to your object that would flatten your object and somehow compute a String from each of it's fields recursively and sorted alpha-numerically. Since your objects are only made of two fields: value and TermTypeEnum that would not be too hard to accomplish, something like this may be (obviously not compiled):

private List<String> flattened;

private List<String> flatten(TermNode node){
    if(node.getChildren() > 0){
        // some recursion here
    } else {
        // probably some checks here
        flattened.add(node.value + node.type)
    }
}

// this will give you a sorted String from all the values
public String toCompareBy(){
    return flatnned.sorted()... 
}

And so this code of yours:

Map<TermNode, Integer> occurrences = children.stream()
        .collect(Collectors.groupingBy(
            term -> term, 
            Collectors.summingInt(term -> 1)));

Could change to something like this:

 children.stream()
         .collect(Collector.toMap(
               Function.identity(),
               Collectors.summingInt(x -> 1),
               (left, right) -> {
                    return left + right;// or left + 1
               }
               () -> new TreeMap<>(Comparator.comparing(TermNode::toCompareBy))
         ))