How to get unique indexes of a sorted Java ArrayList?

Question

I have an ArrayList that I need to sort but I need to get the indexes of the sorted items too. The ArrayList often has many duplicate values as it is updated and the indexex I get are duplicate. I need the unique indexes. Is there a way to get those indexes?

indices = new int[depth.size()];
ArrayList<Float> fStore = new ArrayList(depth);
Collections.sort(depth); 
for (int n=0; n<depth.size(); n++){      
  indices[n] = fStore.indexOf(depth.get(n));      
}

1. you don't show your objects; 2. there is no such thing as an "index" in Java. Please show some code. — fge, Jul 13 '15 at 17:46
@fge "2. there is no such thing as an "index" in Java" - ???? — brso05, Jul 13 '15 at 17:47
Post an example list, what output you want to get, and what you have tried already. — khelwood, Jul 13 '15 at 17:47
All the elements will be having a unique index, the fact that you are getting the same value is that, you are requesting the index of same variable again and again! — XOR-Manik, Jul 13 '15 at 17:48
@fge it's not the truth `int[] a = new int[5];` `a[0]` `0` IS AN INDEX... — brso05, Jul 13 '15 at 17:49
Technically in a Java ArrayList, each entry has one and only one "index", which is its position in the list. If you are talking about something else, please develop. Maybe you need to use another data structure like a SortedMap. — BladeCoder, Jul 13 '15 at 17:50
@brso05 in the list, yes; pertaining to the elements of the list, no — fge, Jul 13 '15 at 17:53
@fge so don't say `there is no such thing as an "index" in java` — brso05, Jul 13 '15 at 17:54
@fge I can create a class that has index as a property and put a bunch of objects in an `ArrayList` so each element will have an `index` property... — brso05, Jul 13 '15 at 17:55
[look at this](http://stackoverflow.com/questions/1429860/easiest-way-to-convert-a-list-to-a-set-java) — SerCrAsH, Jul 13 '15 at 17:57
@brso05 it is true nevertheless; it just happens that there is an interface in Java, `List`, which has a `.get()` method whose argument is an `int` and this argument is called an "index"; fundamentally, my statement holds true: there is no such thing as an index in Java (except for arrays) — fge, Jul 13 '15 at 18:11
@fge a `List` index and an `Array` index are fundamentally the same thing... — brso05, Jul 13 '15 at 18:13
@fge the underlying data structure of an `ArrayList` is an `Array`... — brso05, Jul 13 '15 at 18:14
@brso05 _because of the implementation_; a `List` has no guarantee _at all_ that the underlying data structure is an array — fge, Jul 13 '15 at 18:14
@fge when you pass an `int` to the `get()` method the method is going to the underlying array and using that `int` as the `index` of the underlying array. — brso05, Jul 13 '15 at 18:15
@brso05 read my comment above; there is no such guarantee; it is just a contract, and it just happens that the argument is called the _index_. And that is all there is to it — fge, Jul 13 '15 at 18:16
@fge read my comment above there is a guarantee that an `ArrayList` has an array as the underlying data structure...`ARRAYList` there are `indexes` in `Java` all over the place and it doesn't `"just happen to be called index"` it is called `index` because it's and `index` and that is all there is too it! — brso05, Jul 13 '15 at 18:18
@fge http://www.vogella.com/tutorials/JavaDatastructureList/article.html — brso05, Jul 13 '15 at 18:21

score 1 · Accepted Answer · answered Jul 13 '15 at 20:12

The problem with indexOf() is that it returns the index of the first occurrence of the element in the list, or -1 if not present. If your list has duplicates, then, for these duplicates, you'll get the index of their first occurrence within the list.

There are many ways to accomplish what you want. One is to use a SortedSet and a helper IndexedEntry class:

public class IndexedEntry<T extends Comparable<T>>
    implements Comparable<IndexedEntry<T>> {

    private final Integer index;

    private final T entry;

    public IndexedEntry(Integer index, T entry) {
        this.index = index;
        this.entry = entry;
    }

    public Integer getIndex() {
        return this.index;
    }

    public T getEntry() {
        return this.entry;
    }

    @Override
    public int compareTo(IndexedEntry<T> other) {
        int byEntry = this.getEntry().compareTo(other.getEntry());
        if (byEntry == 0) {
            return this.getIndex().compareTo(other.getIndex());
        }
        return byEntry;
    }

    @Override
    public String toString() {
        return "(" + this.entry + ", " + this.index + ")";
    }
}

The IndexedEntry class simply wraps a Comparable value and its index, and implements Comparable by first comparing the value, and if the value is equal, then it compares the index. This means that an ordered list of IndexedEntry will have its elements ordered by (value, index).

To use the IndexedEntry class, just iterate over your collection, create an IndexedEntry for each element by wrapping the element and its index, and then sort the list of IndexedEntry:

    List<Float> unordered = new ArrayList<>(Arrays.asList(3.2f, 1.0f, 7.5f, 3.2f, 0.8f));
    System.out.println(unordered); // [3.2, 1.0, 7.5, 3.2, 0.8]

    List<IndexedEntry<Float>> ordered = new ArrayList<>();
    for (int i = 0; i < unordered.size(); i++) {
        IndexedEntry<Float> entry = new IndexedEntry<>(i, unordered.get(i));
        ordered.add(entry);
    }
    Collections.sort(ordered);
    System.out.println(ordered); // [(0.8, 4), (1.0, 1), (3.2, 0), (3.2, 3), (7.5, 2)]

Once sorted, the ordered list will contain the elements along with the original index.

How to get unique indexes of a sorted Java ArrayList?

1 Answers1