package rac;

import schemeFactory.*;

public class RACHeap implements IRAContainer {
    /*
     * Initialize _table to reference a single-element array of
     * Comparable.
     */
    private Comparable[] _table = new Comparable[1];
    private int _tableOccupancy = 0;

    /*
     * An AList factory used by elements()
     */
    private IListFactory _lf = new CompositeListFactory();

    /**
     * Clears the contents of the RAC, leaving it empty.
     *
     * Implemented by replacing the existing array with a new,
     * empty one.
     */
    public void clear() {
	_table = new Comparable[1];
	_tableOccupancy = 0;
    }

    /**
     * Returns true if the RAC is empty and false otherwise.
     */
    public boolean isEmpty() {
	return _tableOccupancy == 0;
    }

    /**
     * Returns an AList of the objects corresponding to the entire
     * contents of the RAC.
     */
    public AList elements() {
	AList l = _lf.makeEmptyList();

	for (int i = _tableOccupancy - 1; i >= 0; i--)
	    l = _lf.makeNEList(_table[i], l);

	return l;
    }

    /**
     * Removes and returns the highest priority object from the RAC.
     */
    public Object get() {
	Object result = _table[0];
	_tableOccupancy--;
	if (_tableOccupancy > 0) {
	    _table[0] = _table[_tableOccupancy];

	    ComparableHeapifier.Singleton.siftDown(_table, 0, 0,
						   _tableOccupancy - 1);
	}
	else
	    _table[0] = null;

	return (result);
    }

    /**
     * Inserts the given object into the RAC.  Requires that the object
     * is Comparable.
     */
    public void put(Object input) {
	if (_tableOccupancy == _table.length) {

	    Comparable[] newTable = new Comparable[2*_table.length];

	    for (int i = 0; i < _table.length; i++)
		newTable[i] = _table[i];
	    
	    _table = newTable;
	}
	_table[_tableOccupancy] = (Comparable)input;
	_tableOccupancy++;

	ComparableHeapifier.Singleton.siftUp(_table, 0,
					     _tableOccupancy - 1);
    }

    /**
     */
    public static void main(String[] args)
    {
	RACHeap rach = new RACHeap();
	rach.put(new Integer(13));
	rach.put(new Integer(135));
	rach.put(new Integer(1357));
	System.out.println(rach.get());
	System.out.println(rach.get());
	System.out.println(rach.get());
	System.out.println(rach.get());
    }
}