// Given a double array, IndirectSort(array) is an Iterable<Integer>.
// The iterator returns array indices, sorted by the corresponding
// array values.  The array itself is not modified at all.

// Remark: this is an alternative to IndexMinPQ in GeomGraph.java

import java.util.*;

public class IndirectSort implements Iterable<Integer>
{
    private int N;
    private double[] array;
    private Integer[] index;

    public IndirectSort(double[] array) {
        this.array = array;
        N = array.length;
        index = new Integer[N];
        for (int i=0; i<N; ++i) index[i] = i;
        Arrays.sort(index, new Comp());
    }
    public Iterator<Integer> iterator() { return new Iter(); }

    // Really only need keep array for this method, could omit.
    public double value(int i) { return array[i]; }

    // Private implementation details.
    private class Comp implements Comparator<Integer> {
        public int compare(Integer a, Integer b) {
            return Double.compare(array[a], array[b]);
        }
    }
    public class Iter implements Iterator<Integer> {
        int i=0;
        public boolean hasNext() { return i<N; }
        public Integer next() { return index[i++]; }
        public void remove() { throw new UnsupportedOperationException(); }
    }
}