Порядок в TreeSet неверен. ⇐ JAVA

[Anonymous]

Я пытаюсь решить https://leetcode.com/problems/lru-cache/description/.

Я использую набор деревьев, чтобы сохранять уникальные ключи и упорядочивать их на основе горит, когда он вставлен. Набор деревьев не возвращает элементы так, как я указал с помощью Camparator.

Код: Выделить всё

class LRUCache {

Map keyValue;// ()
TreeSet keys; //key, timestamp (1,-1000)
int capacity;//2
int timestamp;
public LRUCache(int capacity) {
keyValue = new HashMap(capacity);
keys = new TreeSet((Pair a,Pair b) -> {
System.out.println("inside comparator implementation");
int result = a.x == b.x ? 0 : a.y - b.y == 0 ? -1 : a.y - b.y;
System.out.println("result: " + result);
return result;
});
this.capacity = capacity;
}

public int get(int key) {

timestamp++;
Pair pair = new Pair(key, timestamp);
boolean found = keys.contains(pair);
if (found) {
System.out.println("keys contains " + key + ". So, removing it to update");
keys.remove(pair);
} else {
System.out.println("keys doesn't contains " + key + ". So, not removing it. Directly adding it");
}

boolean added = keys.add(pair);
System.out.println("add status: " + added + " for: " + pair);

return keyValue.getOrDefault(key, -1);
}

public void put(int key, int value) {
int priority = Integer.MIN_VALUE + timestamp++;
Pair pair = new Pair(key, priority);
System.out.println("key: " + key + " priority: " + priority);
boolean found = keys.contains(pair);
if (!found) {
System.out.println("keys doesn't " + key + " and " + value + ". So, adding to keys");
keys.add(pair);
} else {
System.out.println("keys contains " + key + " and " + value + ".  Итак, не добавляем к ключам");

keyValue.put(key, value);
if (keys.size() > емкость) {
System.out.println("размер > емкость");
Удаление пары = keys.first();
System.out.println("удаление: " + удалить);
ключи. удалить(удалить);
keyValue.remove(remove.x);
 
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(2);
System.out.println();
System.out.println("помещаем 1,1");
lruCache.put(1, 1);

System.out.println();
System.out.println("помещаем 2,2");
lruCache.put(2, 2);

System.out.println();
System.out.println("получение 1");
System.out.println(lruCache.get(1));

System.out.println();
System.out.println("c");
lruCache.put(3, 3);

System.out.println();
System.out.println("получение 2");
System.out.println(lruCache.get(2));

Код: Выделить всё

class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}

public boolean equals(Object o) {
System.out.println("inside pair equals");
if (this == o) {
return true;
}
if (!(o instanceof Pair)) {
return false;
}
return this.x == ((Pair) o).x;
}

public int hashCode() {
return x;
}

@Override
public String toString() {
return "Pair{" +
"x=" + x +
", y=" + y +
'}';
}
}

I'm expecting (2, -2147483647) to be dropped after adding (3,3), since (2, -2147483647) has negative timestamp.
This is the set that is printed before I expected (2, -2147483647) is removed.

Код: Выделить всё

[Pair{x=1, y=3}, Pair{x=2, y=-2147483647}, Pair{x=3, y=-2147483645}]

Why is

Код: Выделить всё

Pair{x=1, y=3}

first compared to

Код: Выделить всё

{x=2, y=-2147483647}

.
I wrote the comparator to order in treeset based on y values, why is it working as expected?
I tried creating a TreeSetPractise

Код: Выделить всё

public class TreeSetPractise {
public static void main(String[] args) {
TreeSet ts = new TreeSet(( a,  b) -> {
System.out.println("inside comparator implementation");
int result = a.x == b.x ? 0 : a.y - b.y == 0 ? -1 : a.y - b.y;
System.out.println("result: " + result);
return result;
});
ts.add(new Pair(1,10));
ts.add(new Pair(2, -20));
ts.add(new Pair(3, 30));
System.out.println(ts);
for (Pair i : ts) {
System.out.println(i);
}
}
}

Код: Выделить всё

class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public String toString() {
return "Pair{" +
"x=" + x +
", y=" + y +
'}';
}
}

This is working as expected.
The main problem here is, for the elements of TreeSet:Pair{x,y} has to check equality on x and ordering on y.
Meaning Set functionality is based on x and Tree functionality is based on y.

Update[/b]: Most of the comments/answers points out here that my comparator is wrong. The only problem with it might be overflow, but there is no problem with logic.
Also, the bigger problem for me is, TreeSet is considering two objects to be equal if comparator is returning 0. Shouldn't it call equals method on if compareTo returns 0?


Источник: https://stackoverflow.com/questions/781 ... in-treeset