CompareTo può restituire 0, in alternativa a TreeSet/TreeMap

Question

Ho bisogno di un insieme ordinato di oggetti e sto attualmente utilizzando lo TreeSet. Il mio problema è che il compareTo degli oggetti restituirà spesso 0, il che significa che l'ordine di questi due oggetti deve essere lasciato invariato. TreeMap (utilizzato da TreeSet per impostazione predefinita) li considererà quindi come lo stesso oggetto, che non è vero.

Quale alternativa a TreeMap è possibile utilizzare?

---

Caso di utilizzo: ho un set di oggetti visualizzabili. Voglio ordinarli per la coordinata Y, in modo che siano resi nell'ordine corretto. Naturalmente, due oggetti potrebbero avere la stessa coordinata Y.

Answer 1

Si sta definendo un criterio da confrontare, ma è necessario aggiungere ulteriori criteri.

Tu dici:

Ho un insieme di oggetti visualizzabili. Voglio ordinarli per la coordinata Y, in modo che siano resi nell'ordine corretto. Naturalmente, due oggetti potrebbero avere la stessa coordinata Y.

Quindi, se due elementi hanno la stessa coordinata Y, cosa si inserisce per primo? Quali sarebbero gli altri criteri?

può essere il tempo di creazione, può essere la coordinata x, devi solo definirlo:

Map<String,Thing> map = new TreeMap<String,Thing>(new Comparator<Thing>(){ 
    public int compare(Thing one, Thing two) { 
     int result = one.y - two.y; 
     if(result == 0) { // same y coordinate use another criteria 
      result = one.x - two.x; 
      if(result == 0) { //still the same? Try another criteria (maybe creation time 
       return one.creationTime - two.creationTime 
      } 
      } 
      return result; 
    } 
}); 

È necessario definire quando uno Thing è superiore/inferiore/uguale/che altro Thing. Se uno degli attributi è uguale all'altro, probabilmente non dovresti spostarli. Se c'è altro attributo per confrontare l'uso.

Answer 2

ho una mia idea, ma è più di una soluzione

int compare(Object a, Object b) { 
    an = a.seq + (a.sortkey << 16); // allowing for 65k items in the set 
    bn = b.seq + (a.sortKey << 16); 
    return an - bn; // can never remember whether it's supposed to be this or b - a. 
} 

• SortKey = ciò che conta davvero per l'ordinamento, ad esempio una coordinata Y
• ss = un numero progressivo assegnato agli oggetti aggiunti al set

Answer 3

Ci sono 2 cose importanti da ricordare quando si utilizzano insiemi ordinati (ad esempio TreeSet):

1) Si sono insiemi; due elementi uguali non possono accedere alla stessa collezione

2) L'uguaglianza deve essere coerente con il meccanismo di confronto (sia comparatore o comparabili)

Pertanto, nel caso si dovrebbe "rompere i legami" aggiungendo qualche ordinamento secondaria criteri. Ad esempio: prima utilizzare l'asse Y, quindi X e quindi un identificatore univoco dell'oggetto.

Vedi anche http://eyalsch.wordpress.com/2009/11/23/comparators/

Answer 4

Il problema si sta eseguendo in è che compareTo ritorno 0 significa che gli oggetti sono uguali.Allo stesso tempo, li stai mettendo in un set, che non consente più copie di elementi uguali.

O riscrivete il vostro compareTo in modo che gli elementi non uguali restituiscano valori diversi o utilizzate qualcosa come un java.util.PriorityQueue che consente più copie di elementi uguali.

Answer 5

L'ho già fatto. È una multi-mappa ordinata ed è solo una TreeMap di oggetti List. Ti piace questa ..

Map<KeyType, List<ValueType>> mmap = new TreeMap<KeyType, List<ValueType>>(); 

È necessario costruire una nuova LinkedList ogni volta che viene introdotta una nuova chiave, quindi potrebbe essere utile ad avvolgerla in una classe contenitore personalizzato. Cercherò di trovare qualcosa.

---

Quindi, ho gettato questo contenitore personalizzato insieme rapidamente (completamente non testato), ma potrebbe essere quello che stai cercando. Tieni presente che dovresti utilizzare questo tipo di contenitore solo se stai veramente cercando una mappa ordinata di elenchi di valori. Se esiste un ordine naturale dei valori, è necessario utilizzare un set di alberi come suggerito da altri.

import java.util.LinkedList; 
import java.util.List; 
import java.util.Map; 
import java.util.Set; 
import java.util.TreeMap; 

public class MTreeMap<K, V> { 

    private final Map<K, List<V>> mmap = new TreeMap<K, List<V>>(); 
    private int size = 0; 

    public MTreeMap() { 
    } 

    public void clear() { 
     mmap.clear(); 
     size=0; 
    } 

    public boolean containsKey(K key) { 
     return mmap.containsKey(key); 
    } 

    public List<V> get(K key) { 
     return mmap.get(key); 
    } 

    public boolean isEmpty() { 
     return mmap.isEmpty(); 
    } 

    public Set<K> keySet() { 
     return mmap.keySet(); 
    } 

    public Collection<List<V>> valueLists() { 
     return mmap.values(); 
    } 

    public void put(K key, V value) { 

     List<V> vlist = mmap.get(key); 
     if (null==vlist) { 
     vlist = new LinkedList<V>(); 
     mmap.put(key, vlist); 
     } 
     vlist.add(value); 
     ++size; 
    } 

    public List<V> remove(Object key) { 
     List<V> vlist = mmap.remove(key); 

     if (null!=vlist) { 
     size = size - vlist.size() ; 
     } 
     return vlist; 
    } 

    public int size() { 
     return size; 
    } 

    public String toString() { 
     return mmap.toString(); 
    } 

} 

---

Ecco un test rudimentale:

public class TestAnything { 

    public static void main(String[] args) { 

     MTreeMap<Integer, String> mmap = new MTreeMap<Integer, String>(); 

     mmap.put(1, "Value1"); 
     mmap.put(2, "Value2"); 
     mmap.put(3, "Value3"); 
     mmap.put(1, "Value4"); 
     mmap.put(3, "Value5"); 
     mmap.put(2, "Value6"); 
     mmap.put(2, "Value7"); 

     System.out.println("size (1) = " + mmap.get(1).size()); 
     System.out.println("size (2) = " + mmap.get(2).size()); 
     System.out.println("size (3) = " + mmap.get(3).size()); 
     System.out.println("Total size = " + mmap.size()); 

     System.out.println(mmap); 
    } 

} 

Il risultato è questo:

size (1) = 2 
size (2) = 3 
size (3) = 2 
Total size = 7 
{1=[Value1, Value4], 2=[Value2, Value6, Value7], 3=[Value3, Value5]}