Come mappare l'indice ordinato di nuovo all'indice originale per la raccolta Sto ordinando

Question

Ho una collezione (Elenco < Rectangle >) che devo ordinare da sinistra a destra. Quella parte è facile. Quindi voglio scorrere i Rettangoli nel loro originale , ma trovare facilmente il loro indice nella raccolta ordinata. indexOf () non funzionerà, poiché potrei avere un numero di oggetti uguali. Non posso fare a meno di pensare che dovrebbe esserci un modo semplice per farlo.

Answer 1

Ho trovato una soluzione, ma forse ce n'è una più ordinata / più ottimale là fuori.

List<Rectangle> originalRects = ...;

/* record index of each rectangle object.
 * Using a hash map makes lookups efficient,
 * and using an IdentityHashMap means we lookup by object identity
 * not value.
 */
IdentityHashMap<Rectangle, Integer> originalIndices = new IdentityHashMap<Rectangle, Integer>();
for(int i=0; i<originalRects.size(); i++) {
    originalIndices.put(originalRects.get(i), i);
}

/* copy rectangle list */
List<Rectangle> sortedRects = new ArrayList<Rectangle>();
sortedRects.addAll(originalRects);

/* and sort */
Collections.sort(sortedRects, new LeftToRightComparator());

/* Loop through original list */
for(int i=0; i<sortedRects.size(); i++) {
    Rectangle rect = sortedRects.get(i);
    /* Lookup original index efficiently */
    int origIndex = originalIndices.get(rect);

    /* I know the original, and sorted indices plus the rectangle itself */
...

Answer 2

Se non hai decine di migliaia di oggetti, puoi semplicemente memorizzarli in due raccolte separate, una originale e una ordinata. Ricorda che le classi di raccolta in Java memorizzano solo riferimenti agli oggetti, quindi questo non occupa tutta la memoria che potrebbe sembrare.

Answer 3

Clona gli elenchi e ordina uno di essi. Avere due riferimenti dello stesso oggetto non avrà troppa importanza con indexOf () poiché i puntatori allo stesso oggetto sono gli stessi e non è possibile distinguerli. Se hai due oggetti uguali ma non identici e vuoi distinguerli, allora hai un problema poiché indexOf () sta usando il metodo uguale. In questo caso, la soluzione migliore potrebbe essere quella di scorrere semplicemente l'elenco e verificare l'identità dell'oggetto (==).

Answer 4

Un altro modo è ordinare un array di indici invece di ordinare l'elenco originale. L'array inizia come un array di identità a [0] = 0, a [1] = 1, ecc., Quindi utilizza un comparatore / ordinamento personalizzato per ottenere un array di indice. non richiede molto spazio extra, poiché hai solo un array extra di numeri interi invece di un'altra raccolta.