Classificando estrutura de dados personalizada em Key in TreeMap

Question

Estou tentando classificar um TreeMap por chave.Key é alguma DataStructure personalizada com int, List, String, etc.O membro no qual espero uma classificação tem algumas duplicatas.Digamos que esse membro seja Rank.Mais de 1 objeto pode ter a mesma classificação.

Exemplo de versão simplificada:

OBSERVAÇÃO:no método CompareTo abaixo de 0 não é retornado intencionalmente para NÃO ignorar duplicatas. (Corrija-me se esta não for a maneira correta de evitar duplicatas)

import java.util.TreeMap;


public class TreeTest {

public static void main(String[] args) {
    TreeMap<Custom,String> t = new TreeMap<Custom,String>();
    Custom c1 = new Custom();
    c1.setName("a");
    c1.setRank(0);

    Custom c2 = new Custom();
    c2.setName("b");
    c2.setRank(1);

    Custom c3 = new Custom();
    c3.setName("c");
    c3.setRank(0);

    t.put(c1, "first");
    t.put(c2, "Second");
    t.put(c3, "Third");

    System.out.println(t.keySet());

    for(Custom c:t.keySet()){
        System.out.println(t.get(c));
    }
  }
}

E objeto personalizado

package com.example.ui;

 public class Custom implements Comparable<Custom>{

int rank;
String name;

public int getRank() {
    return rank;
}

public void setRank(int rank) {
    this.rank = rank;
}

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}



@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    result = prime * result + rank;
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Custom other = (Custom) obj;
    if (name == null) {
        if (other.name != null)
            return false;
    } else if (!name.equals(other.name))
        return false;
    if (rank != other.rank)
        return false;
    return true;
}

    // 0 is not returned intentionally to NOT ignore duplicates.
 public int compareTo(Custom o) {
    if(o.rank>this.rank)
        return 1;
    if(o.rank==this.rank)
        return -1;
    return -1;
 }
 }

Saída::

[com.example.ui.Custom@fa0, com.example.ui.Custom@fbe, com.example.ui.Custom@f80]
null
null
null

Esperado:Primeiro, Segundo, Terceiro com base na Classificação 0,1,0 respectivamente.

Eu olhei alguns exemplos no Google.A maioria deles foi o uso básico no TreeMap Sort, usando chaves ou valores com tipos de dados primitivos, mas nenhum com duplicatas quando a classificação do membro faz parte da tecla Dataestrutura de chave personalizada.

Por favor ajude?

Answer 1

O problema é que sua implementação de compareTo não é consistente com iguais, o que é exigido por TreeMap.Nos documentos da API:

Observe que a ordem mantida por um mapa classificado (se um comparador explícito é ou não fornecido) deve ou não ser consistente com iguais se esse mapa classificado for implementar corretamente a interface do mapa.

Uma possível implementação consistente seria primeiro comparar por classificação e depois por nome, se os valores de classificação forem iguais.Para duas instâncias de Custom com classificações iguais e nomes idênticos, você não deve esperar poder armazená-las como chaves no mesmo mapa - Isso viola o contrato do Mapa.

public int compareTo(Custom o) {
  int ret = this.rank - o.rank;

  // Equal rank so fall back to comparing by name.
  if (ret == 0) {
    ret = this.name.compareTo(o.name);
  }

  return ret;
}

Answer 2

Conforme mencionado, sua implementação de equals e compareTo não é consistente entre si.Se eu li sua pergunta corretamente, o que você precisa é preservar duplicatas que tenham a mesma chave.Eu recomendo que você dê uma olhada no ÁrvoreMultimapa das coleções do Google Guava.Ele cria contêineres de conjunto para cada objeto de valor para que valores diferentes com a mesma chave sejam preservados.por exemplo.

treeMultimap.put ("rank1", "Joe");
treeMultimap.put ("rank1", Jane");
treeMultimap.get ("rank1"); // Set("Joe","Jane");

A restrição nesta estrutura de dados é que os pares K,V devem ser únicos.Ou seja, você não pode inserir ("rank1", "Joe") duas vezes no Multimapa.

Uma observação importante:A razão pela qual você vê tantos exemplos de Map usando tipos simples e, em particular, strings, é que as chaves em um mapa devem ser imutáveis.Os valores iguais e de código hash de um objeto não devem mudar durante o tempo em que ele é usado como chave em um mapa.Traduzido para o seu exemplo, você não pode fazer customObject.setRank(...) e atualiza um valor de classificação quando ele é usado como chave.Para fazer isso, primeiro você precisa remover a chave e seus valores, atualizá-la e inseri-la novamente.

Answer 3

Você também pode fazer isso implementando Comparator como tipo interno anônimo e substituindo compare() para retornar a comparação desejada.

public class TreeMaps 
{
    public static void main(String[] args) 
    {
    Custom c1 = new Custom(1,"A");
    Custom c2 = new Custom(3,"C");
    Custom c3 = new Custom(2,"B");

    TreeMap<Custom , Integer > tree = new TreeMap<Custom, Integer>  (new Comparator<Custom>() {

                                            @Override
                                            public int compare(Custom o1, Custom o2) {

                                                return o1.rank - o2.rank;
                                            }
                                        });
    tree.put(c1, 1);
    tree.put(c2, 2);
    tree.put(c3, 3);

    System.out.println(tree);
}
}

class Custom
{
int rank ; 
String name  ; 
public Custom(int rank , String name) {
    this.rank = rank ;
    this.name = name ;

}

@Override
public String toString()
{
    return "Custom[" + this.rank + "-" + this.name + "]" ;
}
}