How to map sorted index back to original index for collection I'm sorting

Question

I've got a collection (List<Rectangle>) which I need to sort left-right. That part's easy. Then I want to iterate through the Rectangles in their original order, but easily find their index in the sorted collection. indexOf() won't work, since I may have a number of equal objects. I can't help feeling there should be an easy way to do this.

Answer 1

I've found a solution - but perhaps there is a neater/more optimal one out there.

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

If you don't have tens of thousands of objects, you could just store them in two separate collections, one original, one sorted. Remember that collection classes in Java only store references to objects, so this doesn't take up as much memory as it might seem.

Answer 3

Clone the lists and sort one of them. Having two references of the same object is will not matter too much with indexOf() since the pointers to the same object are the same and you can't tell between them. If you have two objects that are equal but not identical and you do want to distinguish between them then you do have a problem since indexOf() is using the equal method. In this case the best solution might be to simply iterate through the list and check for object identity (==).

Answer 4

Another way is to sort an array of indexes instead of sorting the original list. The array starts as an identity array a[0] = 0, a[1] = 1, etc, then use a custom comparator/sort to get an index array. doesn't require much extra space, as you only have an extra array of integers instead of another collection.