Как сопоставить отсортированный индекс обратно с исходным индексом для коллекции, которую я сортирую

Question

У меня есть коллекция (список<Rectangle>), которую мне нужно отсортировать влево-вправо.Эта часть проста.Затем я хочу перебрать прямоугольники в их оригинал упорядочивайте, но легко находите их индекс в отсортированной коллекции.indexOf() не будет работать, так как у меня может быть несколько одинаковых объектов.Я не могу отделаться от ощущения, что должен быть простой способ сделать это.

Answer 1

Я нашел решение - но, возможно, есть более аккуратное / оптимальное.

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

Если у вас нет десятков тысяч объектов, вы могли бы просто сохранить их в двух отдельных коллекциях, одной оригинальной, другой отсортированной.Помните, что классы коллекций в Java хранят только ссылки к объектам, так что это занимает не так много памяти, как может показаться.

Answer 3

Клонируйте списки и отсортируйте один из них.Наличие двух ссылок на один и тот же объект не будет иметь большого значения для indexOf(), поскольку указатели на один и тот же объект одинаковы, и вы не можете отличить их друг от друга.Если у вас есть два объекта, которые равны, но не идентичны, и вы хотите различать их, то у вас действительно есть проблема, поскольку indexOf() использует метод equal.В этом случае лучшим решением может быть простое прохождение по списку и проверка подлинности объекта (==).

Answer 4

Другой способ - отсортировать массив индексов вместо сортировки исходного списка.Массив начинается как идентификационный массив a [0] = 0, a [1] = 1 и т.д., Затем используйте пользовательский компаратор / сортировку, чтобы получить индексный массив.не требует много дополнительного места, так как у вас есть только дополнительный массив целых чисел вместо другой коллекции.