Java Collections.sort() not sorting

Question

I'm having issues with Java's built in Collections.sort() method. I'm trying to sort an ArrayList of custom object type called TreeNode. I've used the method in the past with success and would like an outside look to see if I'm missing anything obvious.

The way I'd like to sort these TreeNode objects is by an integer field they all have called myWeight, an integer representation of the amount of times a specific character appears in a text file. In my project I use a custom class called TreeNode and two children of that class named InternalNode and LeafNode. These nodes are used to build a Huffman Tree for encoding a text file. I've made sure that all of these implement Comparable and I've tried variations of only the parent TreeNode class having a compareTo() method, having all of them have an identical compareTo() method, I've foregone my compareTo() implementation to use the Integer.compare() method inside of it instead, but no dice.

I've also tried using a comparator and passing that as a parameter of the Collections.sort() method as well but nothing changed from that as well.

Here is where I'm trying to call the sort and display the results:

        private void generateHuffmanTreeTest(final HashMap<Character, Integer> theMap) {
            ArrayList<TreeNode> sortedList = new ArrayList<TreeNode>();
            System.out.println("Generating the Huffman Tree with new logic...");

            for (Map.Entry<Character, Integer> entry : theMap.entrySet()) {
                sortedList.add(new LeafNode(entry.getKey(), entry.getValue()));
            }

            Collections.sort(sortedList);
            for (int i = 0; i < sortedList.size(); i++) {
        LeafNode n = (LeafNode) sortedList.get(i);
        System.out.println(n.myData + " " + n.myWeight);
    }

Below are my object classes that I'm trying to compare as well.

    public class TreeNode implements Comparable<TreeNode> {

    /** Left child of this node. */
    public TreeNode myLeft;

    /** Right child of this node. */
    public TreeNode myRight;

    /** 
     * Weight of all nodes branching from this one, or the weight
     * of just this node if this node is a leaf.
     */
    public int myWeight;

    /**
     * Default constructor. Should not be used to create pure 
     * TreeNode objects.
     * No TreeNodes should be constructed, only InternalNodes
     * and LeafNodes should comprise the tree.
     */
    public TreeNode() {

    }



    /**
     * Sets the left child of this node.
     * 
     * @param theNode The node to become the left child.
     */
    public void setLeft(final TreeNode theNode) {
        myLeft = theNode;
    }

    /**
     * Sets the right child of this node.
     * 
     * @param theNode The node to become the right child.
     */
    public void setRight(final TreeNode theNode) {
        myRight = theNode;
    }

    /**
     * Compares two TreeNodes based on their myWeight field.
     */
    @Override
    public int compareTo(TreeNode theOther) {
        int result = 0;

        if (myWeight < theOther.myWeight) result = -1;
        if (myWeight > theOther.myWeight) result = 1;

        return result;
    }

}

    public class InternalNode extends TreeNode implements Comparable<TreeNode> {

    /**
     * Creates a new InternalNode.
     */
    public InternalNode() {
        super();

    }

    /**
     * Calculates the weight of both children from this Node.
     */
    public void calcWeight() {
        int result = 0;

        if (myLeft != null) result = result + myLeft.myWeight;
        if (myRight != null) result = result + myRight.myWeight;

        myWeight = result;
    }

    /**
     * Sets the left child of this node.
     * 
     * @param theNode The child to be set.
     */
    public void setLeft(final TreeNode theNode) {
        myLeft = theNode;

    }

    /**
     * Sets the right child of this node.
     * 
     * @param theNode The child to be set.
     */
    public void setRight(final TreeNode theNode) {
        myRight = theNode;

    }

    /**
     * Compares two TreeNodes based on their myWeight field.
     */
    @Override
    public int compareTo(TreeNode theOther) {
        int result = 0;

        if (myWeight < theOther.myWeight) result = -1;
        if (myWeight > theOther.myWeight) result = 1;

        return result;
    }
}

    public class LeafNode extends TreeNode implements Comparable<TreeNode> {

    /** Char value for this node to hold. */
    public char myData;

    /** Weight value of the char this node holds. */
    public int myWeight;

    /**
     * Creates a new LeafNode that contains a char value for it to 
     * hold as well as a weight value that is equal to the number
     * of times that character appears in the target String.
     * 
     * @param theData The char value for this node to hold.
     * @param theWeight The frequency of the char value in the text.
     */
    public LeafNode(final char theData, final int theWeight) {
        super();
        myData = theData;
        myWeight = theWeight;

    }

    /**
     * Compares two TreeNodes based on their myWeight field.
     */
    @Override
    public int compareTo(TreeNode theOther) {
        int result = 0;

        if (myWeight < theOther.myWeight) result = -1;
        if (myWeight > theOther.myWeight) result = 1;

        return result;
    }
}

EDIT*** Yeah might help if I posted the output of this thing too. Here is what I get when I run this code from the text file I've read:

Where is the output? Is it just the last one line in your question which is 1 ? Also your compare impl can be just return this.myWeight - theOther.myWeight; — SomeDude
– SomeDude, Commented May 1, 2018 at 18:57
Hi @SomeDude I forgot to include the output in my original post. It should be there now. As you can see it just prints the contents of the List in some default order which I'm assuming is ASCII order or something of that effect. — B_Ran
– B_Ran, Commented May 1, 2018 at 19:00

VeeArr · Accepted Answer · 2018-05-01 19:15:45Z

2

The issue that you are having is that you have defined myWeight in both TreeNode and in LeafNode. As a result, the myWeight variable being used by the compareTo method may not be the same as the one being written by the LeafNode constructor and written out when you print LeafNode.myWeight.

You probably just want to remove the repeated definition of myWeight from LeafNode.

See the section on variable hiding here: https://dzone.com/articles/variable-shadowing-and-hiding-in-java

answered May 1, 2018 at 19:15

VeeArr

6,2183 gold badges26 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

B_Ran Over a year ago

This was my issue. Mistakenly declared that variable in LeafNode as well as its parent TreeNode, so when I was calling Collections.sort() on my list the value it was seeing for myWeight on all those nodes was 0, leaving them all in place.

user5063151 · Accepted Answer · 2018-05-01 19:07:29Z

You can use Comparator<TreeNode>. That way, if you ever add a field to the TreeNode class, you can just implement a different comparator and pass that to the Collections.sort() method. But, by default, if you still want them to be Comparable, you can leave them with a default compareTo() method:

Output:

[1, 5, 6, 0, 1, 0, 8, 3, 7, 4]
[0, 0, 1, 1, 3, 4, 5, 6, 7, 8]

TreeNode:

public static class TreeNode implements Comparable<TreeNode> {

  public TreeNode(int weight) {
    this.myWeight = weight;
  }

  public int myWeight;

  public String toString() {

  return "" + myWeight;
}

@Override
public int compareTo(TreeNode o) {

  int val = 0;

    if (myWeight > o.myWeight) {
      val = 1;

    } else if (myWeight < o.myWeight){

      val = -1;
    }


    return val;
  }
}

Comparator, used for sorting:

public static class TreeNodeComparator implements Comparator<TreeNode> {

  // Sorts by default `compareTo()`, You can always change this
  // If you want to sort by another property
  @Override
  public int compare(TreeNode o1, TreeNode o2) {

    return o1.compareTo(o2);
  }
}

Main:

public static void main(String[] args) throws Exception {


  java.util.ArrayList<TreeNode> nodes = new java.util.ArrayList<>();

  for (int i = 10; i > 0; i--) {

    int val = ThreadLocalRandom.current().nextInt(0, 10);

    TreeNode node = new TreeNode(val);

    nodes.add(node);

  }

  System.out.println(nodes);

  Collections.sort(nodes, new TreeNodeComparator());


  System.out.println(nodes);
}

Sam · Accepted Answer · 2018-05-01 19:07:46Z

You can create a separate class which implements the Comparator interface, and override the compare method like so:

public class SortByWeight implements Comparator<TreeNode> {


@Override
public int compare(TreeNode o1, TreeNode o2) {
return o1.myWeight - o2.myWeight;
}
}

Then when comparing in the method, create a new instance of the comparator.

 ArrayList<TreeNode> sortedList = new ArrayList<TreeNode>();
    System.out.println("Generating the Huffman Tree with new logic...");

    TreeNode t = new TreeNode();
    t.myWeight = 2;

    TreeNode r = new TreeNode();
    r.myWeight = 5;

    TreeNode q = new TreeNode();
    q.myWeight = 1;

    sortedList.add(t);
    sortedList.add(r);
    sortedList.add(q);

     //new comparator here
    Collections.sort(sortedList, new SortByWeight());

    for (int i = 0; i < sortedList.size(); i++) {
        System.out.println(sortedList.get(i).myWeight);
    }

The output of this is

1
2
5

Hope it helps.

Collectives™ on Stack Overflow

Java Collections.sort() not sorting

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related