package com.srbenoit.sparsearray;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.List;
import java.util.logging.Level;
import com.srbenoit.log.LoggedObject;

/**
 * An array of objects that supports addition and deletion of objects, but will not change the
 * index of a object once added. That is, deleting objects makes the array sparse, and adding new
 * objects may fill in gaps left by deleting objects before appending to the end of the array.
 * Storage is allocated in blocks of fixed size as needed to add objects.
 *
 * @param  <E>  the type of object this array manages
 */
public class SparseArray<E> extends LoggedObject implements Iterable<E> {

    /** number of objects in an allocated block */
    public static final int BLOCK_SIZE = 64;

    /** the class of objects this array manages */
    private final Class<E> objClass;

    /** index of first available position in array */
    private transient int firstAvailable;

    /** total number of objects in the array */
    private transient int numObjects;

    /** array of objects */
    private transient E[] objects;

    /** listeners registered to be notified with the array structure changes */
    private final List<SparseArrayListener> listeners;

    /**
     * Constructs a new <code>SparseArray</code> with a default capacity.
     *
     * @param  clazz  the class of object this array will manage
     */
    public SparseArray(final Class<E> clazz) {

        this(clazz, BLOCK_SIZE);
    }

    /**
     * Constructs a new <code>SparseArray</code> with capacity for a specified number of objects.
     * Use this constructor if you know how many objects will ultimately be added to the array.
     *
     * @param  clazz        the class of object this array will manage
     * @param  initialSize  the initial capacity of array to allocate
     */
    @SuppressWarnings({ "unchecked" })
    public SparseArray(final Class<E> clazz, final int initialSize) {

        this.firstAvailable = 0;
        this.numObjects = 0;
        this.objClass = clazz;
        this.objects = (E[]) Array.newInstance(clazz, initialSize);

        this.listeners = new ArrayList<SparseArrayListener>(1);
    }

    /**
     * Adds a listener to the list of those registered to be notified when the sparse array
     * structure changes.
     *
     * @param  listener  the new listener to register
     */
    public void addListener(final SparseArrayListener listener) {

        synchronized (this.listeners) {

            if (!this.listeners.contains(listener)) {
                this.listeners.add(listener);
            }
        }
    }

    /**
     * Removes a listener from the list of those registered to be notified when the sparse array
     * structure changes.
     *
     * @param  listener  the listener to remove
     */
    public void removeListener(final SparseArrayListener listener) {

        synchronized (this.listeners) {

            this.listeners.remove(listener);
        }
    }

    /**
     * Gets the length of the allocated array.
     *
     * @return  the length of the array (includes empty positions)
     */
    public int capacity() {

        return this.objects.length;
    }

    /**
     * Sets the capacity of this array, allocating new objects if needed. If the current array is
     * already large enough to accommodate the request, no changes are made (that is, the capacity
     * after this request may be larger than the requested capacity).
     *
     * @param  newCap  the new capacity
     */
    @SuppressWarnings("unchecked")
    public void setCapacity(final int newCap) {

        int len;
        E[] newArray;

        len = this.objects.length;

        if (newCap > len) {
            newArray = (E[]) Array.newInstance(this.objClass, newCap);
            System.arraycopy(this.objects, 0, newArray, 0, len);
            this.objects = newArray;
        }
    }

    /**
     * Gets the number of objects in this list.
     *
     * @return  the number of objects in the array
     */
    public int size() {

        return this.numObjects;
    }

    /**
     * Tests whether the array contains an object at a particular index.
     *
     * @param   index  the index to test
     * @return  <code>true</code> if the index is filled; <code>false</code> if not
     */
    public boolean isFilled(final int index) {

        return this.objects[index] != null;
    }

    /**
     * Gets the index of the next filled index after (or including) a given starting index.
     *
     * @param   index  the starting index
     * @return  the next filled index, or -1 if no indices are filled from the start index on
     */
    public int nextFilled(final int index) {

        int result;

        result = -1;

        for (int i = index; i < this.objects.length; i++) {

            if (this.objects[i] != null) {
                result = i;

                break;
            }
        }

        return result;
    }

    /**
     * Removes an object from the array.
     *
     * @param   index  the index of the object to remove
     * @return  <code>true</code> if an object was present at the requested index and was removed;
     *          <code>false</code> otherwise
     */
    public E remove(final int index) {

        E obj;

        if (this.objects[index] != null) {
            obj = this.objects[index];
            this.objects[index] = null;
            this.numObjects--;

            if (index < this.firstAvailable) {
                this.firstAvailable = index;
            }
        } else {
            obj = null;
        }

        return obj;
    }

    /**
     * Adds an object to the array, increasing allocated storage if needed.
     *
     * @param   object  the object to add
     * @return  the index of the newly added object in the tuple array
     */
    @SuppressWarnings("unchecked")
    public int add(final E object) {

        int len;
        int index;
        boolean notify;

        // If we need to allocate more space, do it
        len = this.objects.length;

        if (this.numObjects == len) {
            setCapacity(len + BLOCK_SIZE);
            index = len;
            this.firstAvailable = len + 1;

            if (this.objects[this.firstAvailable] != null) {
                LOG.log(Level.WARNING, "After expanding sparse array, next item filled",
                    new Exception());
            }

            notify = true;
        } else {
            index = this.firstAvailable;

            this.firstAvailable = len;

            for (int i = index + 1; i < len; i++) {

                if (this.objects[i] == null) {
                    this.firstAvailable = i;

                    break;
                }
            }

            notify = false;
        }

        if (this.objects[index] != null) {
            LOG.log(Level.WARNING,
                "SparseArray of len " + this.objects.length + " stomping entry at " + index,
                new Exception());
        }

        this.objects[index] = object;
        this.numObjects++;

        if (notify) {

            synchronized (this.listeners) {

                for (SparseArrayListener list : this.listeners) {
                    list.capacityChanged(this, capacity());
                }
            }
        }

        return index;
    }

    /**
     * Attempts to add a tuple at a particular index.
     *
     * @param   object  the tuple to add
     * @param   index   the index at which to add the tuple
     * @throws  SparseArrayException  if the supplied index is not valid (either the array does not
     *                                contain the index, or there is already a tuple at the index)
     */
    public void add(final E object, final int index) throws SparseArrayException {

        if (this.objects.length > index) {

            if (this.objects[index] != null) {
                throw new SparseArrayException("Index " + index + " already occupied");
            }

            this.objects[index] = object;
            this.numObjects++;
        } else {
            throw new SparseArrayException("Index " + index + " out of bounds");
        }
    }

    /**
     * Gets an object from the array.
     *
     * @param   index  the index of the object to get
     * @return  the object
     */
    public E get(final int index) {

        return this.objects[index];
    }

    /**
     * Gets an iterator that will iterate over the filled elements in the sparse array.
     *
     * @return  the iterator
     */
    public Iterator<E> iterator() {

        return new SparseArrayIterator<E>(this);
    }
}