Java Collections.sort () не сортирует

Question

У меня проблемы с Java, встроенным в метод Collections.sort (). Я пытаюсь отсортировать ArrayList пользовательского типа объекта под названием TreeNode. Я использовал этот метод в прошлом с успехом и хотел бы взглянуть со стороны, чтобы не пропустить ничего очевидного.

Я бы хотел отсортировать эти объекты TreeNode по целочисленному полю, которое они все назвали myWeight, целочисленное представление количества раз, когда конкретный символ появляется в текстовом файле. В моем проекте я использую пользовательский класс с именем TreeNode и два потомка этого класса с именами InternalNode и LeafNode. Эти узлы используются для построения дерева Хаффмана для кодирования текстового файла. Я удостоверился, что все они реализуют Comparable, и я попробовал варианты только родительского класса TreeNode, имеющего метод CompareTo (), имея все они имеют идентичный метод CompareTo (), я отказался от моего CompareTo () реализация для использования внутри него метода Integer.compare (), но без кубиков.

Я также пытался использовать компаратор и передавать его в качестве параметра метода Collections.sort (), но ничего не изменилось.

Здесь я пытаюсь вызвать сортировку и отобразить результаты:

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

Ниже приведены мои классы объектов, которые я тоже пытаюсь сравнить.

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

РЕДАКТИРОВАТЬ *** Да, может помочь, если бы я опубликовал вывод этой вещи тоже. Вот что я получаю, когда запускаю этот код из прочитанного мной текстового файла:

 65007
  514908
! 3923
" 17970
# 1
$ 2
% 1
' 7529
( 670
) 670
* 300
, 39891
- 6308
. 30806
/ 29
0 179
1 392
2 147
3 61
4 23
5 55
6 57
7 40
8 193
9 35
: 1014
; 1145
= 2
? 3137
@ 2
A 6574
B 3606
C 2105
D 2017
E 2259
F 1946
G 1303
H 4378
I 7931
J 308
K 1201
L 713
M 3251
N 3614
O 1635
P 6519
Q 35
R 3057
S 2986
T 6817
U 254
V 1116
W 2888
X 673
Y 1265
Z 108
[ 1
] 1
à 4
a 199232
b 31052
c 59518
d 116273
ä 1
e 312974
f 52950
g 50023
h 163026
i 166350
é 1
j 2266
ê 11
k 19230
l 95814
m 58395
n 180559
o 191244
p 39014
q 2295
r 145371
s 159905
t 219589
u 65180
v 25970
w 56319
x 3711
y 45000
z 2280
 1

Answer 1

Вы можете создать отдельный класс, который реализует интерфейс Comparator, и переопределить метод compare следующим образом:

public class SortByWeight implements Comparator<TreeNode> {


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

Затем при сравнении в методе создайте новый экземпляр компаратора.

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

Выход этого

1
2
5

Надеюсь, это поможет.

Answer 2

Проблема, с которой вы столкнулись, заключается в том, что вы определили myWeight как в TreeNode, так и в LeafNode. В результате переменная myWeight, используемая методом compareTo, может отличаться от переменной, записываемой конструктором LeafNode и записываемой при печати LeafNode.myWeight.

Возможно, вы просто хотите удалить повторное определение myWeight из LeafNode.

См. Раздел о скрытии переменных здесь: https://dzone.com/articles/variable-shadowing-and-hiding-in-java

Answer 3

Вы можете использовать Comparator<TreeNode>. Таким образом, если вы когда-нибудь добавите поле в класс TreeNode, вы можете просто реализовать другой компаратор и передать его в метод Collections.sort(). Но по умолчанию, если вы все еще хотите, чтобы они были Comparable, вы можете оставить их с методом compareTo() по умолчанию:

Выход:

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

Компаратор, используемый для сортировки:

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