Contains() agissant différemment sur List et TreeSet

Question

J'ai rencontré un cas étrange où la fonction semble fonctionner différemment entre une liste et un TreeSet dans Scala et je ne sais pas pourquoi ou comment la résoudre.

J'ai créé une classe appelée DataStructure pour des raisons de concision. Il contient deux éléments: une paire de coordonnées (i, j) et une Int. (C'est plus compliqué que cela, mais dans ce MWE, c'est à quoi ça ressemble) Il a un comparateur personnalisé qui va trier par le Int, et j'ai remplacé hashCode et equals de sorte que deux éléments contenant la même paire de coordonnées (i, j) sont traités comme égal indépendamment du Int.

Lorsque je mets une instance de DataStructure dans un List et un TreeSet, le programme n'a aucun problème pour trouver des correspondances exactes. Toutefois, lors de la vérification d'un nouvel élément qui a la même paire de coordonnées, mais Int différent, le List.contains renvoie true tandis que TreeSet.contains renvoie false. Pourquoi cela arrive-t-il et comment puis-je le résoudre?

C'est mon code réduit à un exemple de travail minimum:

Classe DataStructure

package foo 

class DataStructure(e1: (Int, Int), e2: Int) extends Ordered[DataStructure] { 
    val coord: (Int, Int) = e1 
    val cost: Int = e2 

    override def equals(that: Any): Boolean = { 
    that match { 
    case that: DataStructure => if (that.coord.hashCode() == this.coord.hashCode()) true else false 
    case _ => false 
    }} 
    override def hashCode(): Int = this.coord.hashCode() 

    def compare(that: DataStructure) = { 
    if (this.cost == that.cost) 
     0 
    else if (this.cost > that.cost) 
     -1 //reverse ordering 
    else 
     1 
    }  
} 

programme pilote

package runtime 

import foo.DataStructure 
import scala.collection.mutable.TreeSet 

object Main extends App { 
     val ts = TreeSet[DataStructure]() 

     val a = new DataStructure((2,2), 2) 
     val b = new DataStructure((2,3), 1) 

     ts.add(a) 
     ts.add(b) 

     val list = List(a, b) 

     val listRes = list.contains(a) // true 
     val listRes2 = list.contains(new DataStructure((2,2), 0)) // true 
     val tsRes = ts.contains(a) // true 
     val tsRes2 = ts.contains(new DataStructure((2,2), 0)) // FALSE! 

     println("list contains exact match: " + listRes) 
     println("list contains match on first element: " + listRes2) 
     println("TreeSet contains exact match: " + tsRes) 
     println("TreeSet contains match on first element: " + tsRes2) 
} 

Sortie:

list contains exact match: true 
list contains match on first element: true 
TreeSet contains exact match: true 
TreeSet contains match on first element: false 

Answer 1

Almo st certainement List.contains vérifie equals pour chaque élément pour trouver une correspondance, alors que TreeSet.contains marche dans l'arbre et utilise compare pour trouver une correspondance. Votre problème est que votre compare n'est pas compatible avec votre equals. Je ne sais pas pourquoi vous faites cela, mais ne proposent pas:

https://www.scala-lang.org/api/current/scala/math/Ordered.html

« Il est important que la méthode equals pour une instance de Ordonné [A] être conforme à la méthode comparer. »