Пользовательский компаратор TreeSet не работает с одинаковыми объектами

У меня проблема с реализацией компаратора TreeSet. У меня есть простая игра, в которой животные ходят по доске, каждый ход они делают одно движение, если они умирают по какой-либо причине, они помечаются как «мертвые», помещаются в список «Мертвые организмы», а затем удаляются из «очереди» дерева. " в этом фрагменте кода (я не могу удалить их сразу, потому что перебираю набор деревьев):

for(Organism org : DeadOrganisms){
    queue.remove(org);
}

Проблема в том, что некоторые из них вообще не удаляются, даже несмотря на то, что в конце каждого хода они возвращаются в список DeadOrganisms из-за того, что помечены как «мертвые». Будучи уверенным, что .remove вызывается при каждом включении мертвого организма, я почти уверен, что проблема заключается в классе Comparator:

class MyComparator implements Comparator<Organism> {
    @Override
    public int compare(Organism o1, Organism o2) {
        if (o1.getName().equals(o2.getName())) {
            return 0;
        }
        if (o1.getInitiative() > o2.getInitiative()) {
            return -1;
        } else if (o1.getInitiative() == o2.getInitiative()) {
            if (o1.getAge() > o2.getAge()) {
                return -1;
            } else {
                return 1;
            }
        } else {
            return 1;
        }
    }

}

Предполагается, что компаратор проверяет, совпадает ли имя o1 (уникальное для каждого персонажа на доске) с именем o2, а остальная часть кода предназначена для сортировки набора деревьев по инициативе персонажа или возрасту, если инициатива равна. Фрагмент кода абстрактного класса Organism, из которого происходят все символы:

public abstract class Organism {
    protected int lastxpos;
    protected int lastypos;
    private final World myworld;
    private int strength;
    private int initiative;
    private int xPos;
    private int yPos;
    private int age;
    private String name;
    Color color;
    private boolean isdead;
    public Organism(World world, String name){
        this.name = name;
        this.color = Color.RED;
        this.strength = 0;
        this.initiative = 0;
        this.xPos = 0;
        this.yPos = 0;
        this.age = 0;
        this.isdead = false;
        this.myworld = world;
    }

Я знаю, что либо делаю что-то не так, либо неправильно понимаю, как работают TreeSets (или и то, и другое), но я не могу понять, что именно. Я также знаю, что .remove

удаляет элемент e такой, что (o==null ? e==null : o.equals(e))

Так что в моем понимании это роль

if (o1.getName().equals(o2.getName())) {
    return 0;
}

в моем классе Comparator, но, возможно, я что-то неправильно понимаю. Я был бы очень признателен за любую помощь в этом.

@ РЕДАКТИРОВАТЬ Я не знаю, имеет ли это значение, но пока я тестирую его на одном типе животных, с тем же возрастом и инициативой, поэтому единственная разница между всеми животными - это их имя.

@EDIT2 Я также заметил, что если удаляемый организм находится первым в "очереди" набора деревьев, то в методе сравнения после вызова queue.remove(org) "org" никогда не оказывается по сравнению с 1-м объектом в наборе деревьев (он же сам) только со вторым, третьим и т. д.

@EDIT3 Для пользователя NPE в комментариях: Объявление очереди:

public class World extends JPanel{
    *_declarations of some variables_*
    private final TreeSet<Organism> queue;

Инициализация очереди:

public World(int sizeX, int sizeY) {
        this.queue = new TreeSet<>(new MyComparator());
        *_ommitting rest of constructor code_*
    }

Объявление и инициализация DeadOrganisms:

    public void EndTurn(){
        List<Organism> DeadOrganisms = new ArrayList<>();
        *_omitting rest of the EndTurn code_*
     }

java comparator treeset
person Dan    schedule 13.05.2018    source источник
comment
Пожалуйста, покажите нам код, который объявляет и инициализирует queue и DeadOrganisms.   -  person NPE    schedule 13.05.2018

Ответы (2)


arrow_upward
0
arrow_downward

Из JavaDoc от java.util.Comparator:

Следует проявлять осторожность при использовании компаратора, способного навязывать порядок, несовместимый с равными, для упорядочения отсортированного набора (или отсортированной карты). Предположим, что отсортированный набор (или отсортированная карта) с явным компаратором c используется с элементами (или ключами), извлеченными из набора S. Если порядок, налагаемый c на S, несовместим с равными, отсортированный набор (или отсортированная карта) будет вести себя «странно». В частности, отсортированный набор (или отсортированная карта) будет нарушать общий контракт для набора (или карты), который определен в терминах равенства.

...что подозрительно похоже на то, что вы испытываете. Итак, давайте посмотрим на JavaDoc от java.util.Collection#remove:

Удаляет указанный элемент из этого набора, если он присутствует (дополнительная операция). Более формально удаляет элемент e такой, что (o==null ? e==null : o.equals(e)), если этот набор содержит такой элемент.

Так что Comparator тут даже не при чем. Поэтому решение состоит в том, чтобы реализовать методы equals и hashCode.

@Override
public int hashCode() {
    int hash = 3;
    hash = 97 * hash + this.initiative;
    hash = 97 * hash + this.age;
    hash = 97 * hash + Objects.hashCode(this.name);
    return hash;
}

@Override
public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (obj == null) {
        return false;
    }
    if (getClass() != obj.getClass()) {
        return false;
    }
    final Organism other = (Organism) obj;
    if (this.initiative != other.initiative) {
        return false;
    }
    if (this.age != other.age) {
        return false;
    }
    if (!Objects.equals(this.name, other.name)) {
        return false;
    }
    return true;
}

Примечание: оба метода были автоматически сгенерированы Netbeans.

person SeverityOne    schedule 13.05.2018

arrow_upward
0
arrow_downward

Большое спасибо за помощь, к сожалению, проблема была в другом. В компараторе вы можете видеть, что если инициатива равна, а возраст Организма1 НЕ больше, чем возраст Организма2, я бы просто поместил Организм1 после Организма2. Теперь предположим, что мои объекты в наборе деревьев - это A, B, C, D..., X, Y, Z, их инициатива и возраст одинаковы. Когда я добавляю их в свой набор деревьев, компаратор всегда возвращает 1, потому что инициатива и возраст одинаковы, а это означает, что порядок набора деревьев всегда будет порядком вставки. Теперь, когда я хотел удалить объект H, метод .remove входил в набор деревьев A,B,C,D,...,X,Y,Z, он начинался, например, с F (я не не знаю, выбирает ли он его случайным образом или это какой-то алгоритм) и вызовет компаратор с аргументами F и H, тогда компаратор вернет 1, как всегда в этом случае. Затем метод .remove "перепрыгнет" от F к, например, K, полностью пропуская H, он сравнит K и H, сравнение снова вернет 1, сообщая методу .remove, что H возможно находится дальше в наборе деревьев, тогда как на самом деле .remove уже пропустил мой объект H. Это приводит к тому, что .remove случайным образом не удаляет объект, потому что он пропустит его в своем алгоритме. Все, что мне нужно было сделать, это добавить статический счетчик к моим организмам. Теперь компаратор знает, что он ищет волка со значением счетчика 3, поэтому, если он перепрыгнет через него и найдет волка со значением счетчика 6, он узнает, что ему нужно вернуться.

TL;DR:

(TIL: алгоритм набора деревьев не перемещается от одного узла к его "соседу", а скорее "прыгает" по большим участкам (чем ближе мы приближаемся к нашему значению, тем меньше они становятся), а это означает, что если мы ищем 50 в нашем наборе {1,2....100}, он будет (например) переходить к 20, затем к 80, затем к 40, затем к 55 и т. д.)

.remove перепрыгнул бы через мой объект в наборе деревьев из-за неправильных операторов компаратора «если».

person Dan    schedule 13.05.2018