How to use iterators in java?

Question

I have implemented Priority Queue interface for making heap. Can you tell me how to implement an iterator on the top of that? point me to some apropriate tutorial,i am new to java and on a very short deadline here. Actually i need a method to find and modify an object from heap on the basis of Object.id. I dont care if it is O(n).

public interface PriorityQueue {

    /**
     * The Position interface represents a type that can
     * be used for the decreaseKey operation.
     */
    public interface Position {

        /**
         * Returns the value stored at this position.
         * @return the value stored at this position.
         */
        Comparable getValue();
    }

    Position insert(Comparable x);

    Comparable findMin();

    Comparable deleteMin();

    boolean isEmpty();

    int size();

    void decreaseKey(Position p, Comparable newVal);
}

// BinaryHeap class

public class OpenList implements PriorityQueue {

    public OpenList() {
        currentSize = 0;
        array = new Comparable[DEFAULT_CAPACITY + 1];
    }

    public OpenList(int size) {
        currentSize = 0;
        array = new Comparable[DEFAULT_CAPACITY + 1];
        justtocheck = new int[size];
    }

    public OpenList(Comparable[] items) {
        currentSize = items.length;
        array = new Comparable[items.length + 1];

        for (int i = 0; i < items.length; i++) {
            array[i + 1] = items[i];
        }
        buildHeap();
    }

    public int check(Comparable item) {
        for (int i = 0; i < array.length; i++) {
            if (array[1] == item) {
                return 1;
            }
        }
        return array.length;
    }

    public PriorityQueue.Position insert(Comparable x) {
        if (currentSize + 1 == array.length) {
            doubleArray();
        }

        // Percolate up
        int hole = ++currentSize;
        array[ 0] = x;

        for (; x.compareTo(array[hole / 2]) < 0; hole /= 2) {
            array[hole] = array[hole / 2];
        }
        array[hole] = x;

        return null;
    }

    public void decreaseKey(PriorityQueue.Position p, Comparable newVal) {
        throw new UnsupportedOperationException(
            "Cannot use decreaseKey for binary heap");
    }

    public Comparable findMin() {
        if (isEmpty()) {
            throw new UnderflowException("Empty binary heap");
        }
        return array[ 1];
    }

    public Comparable deleteMin() {
        Comparable minItem = findMin();
        array[ 1] = array[currentSize--];
        percolateDown(1);

        return minItem;
    }

    private void buildHeap() {
        for (int i = currentSize / 2; i > 0; i--) {
            percolateDown(i);
        }
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public int size() {
        return currentSize;
    }

    public void makeEmpty() {
        currentSize = 0;
    }
    private static final int DEFAULT_CAPACITY = 100;
    private int currentSize;      // Number of elements in heap
    private Comparable[] array; // The heap array
    public int[] justtocheck;

    private void percolateDown(int hole) {
        int child;
        Comparable tmp = array[hole];

        for (; hole * 2 <= currentSize; hole = child) {
            child = hole * 2;
            if (child != currentSize &&
                array[child + 1].compareTo(array[child]) < 0) {
                child++;
            }
            if (array[child].compareTo(tmp) < 0) {
                array[hole] = array[child];
            } else {
                break;
            }
        }
        array[hole] = tmp;
    }

    private void doubleArray() {
        Comparable[] newArray;

        newArray = new Comparable[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            newArray[i] = array[i];
        }
        array = newArray;

}

Answer 1

Your underlying data structure is an array, which is difficult to write a Java-style iterator for. You could try creating a container class implementing java.util.Iterator which holds a reference to your Comparable element and its current array index. You'll need to manually update the index when you move the container.

Answer 2

You might look at java.util.PriorityQueue. If you're in a hurry, Arrays.sort() may suffice. Once sorted, Arrays.binarySearch() becomes possible.