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

Question

У меня есть коллекция (Список ), которую мне нужно отсортировать влево-вправо. Это легко. Затем я хочу перебрать прямоугольники в их оригинальном порядке, но легко найти их индекс в отсортированной коллекции. 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

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

Answer 4

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