Reputation: 39

Java Collections.sort() not sorting

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:

Upvotes: 0

Answers (3)

VeeArr

Reputation: 6178

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

Upvotes: 2

Sam

Reputation: 1304

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.

Upvotes: 1

user5063151

Reputation:

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);
}

Upvotes: 1

Java Collections.sort() not sorting

Answers (3)

Related Questions