package de.renew.util;


/**
 * A random bag is a simple data structure that can take
 * an arbitrary number of objects and return them in a random order.
 * <p>
 * The implementation is based on an array. During the
 * extraction, a random element is removed and the
 * void position is filled in with the very last element.
 * <p>
 * Each operation runs in constant amortized time.
 *
 * @author Olaf Kummer
 **/
public class RandomBag {
    /**
     * Field containing the actual <code>Object</code>-type elements stored in the RandomBag
     */
    private Object[] _elements;
    /**
     * The size of the RandomBag, understood as the number of objects actually stored within it, and not the
     * size of the Array storing them.
     */
    private int _size;

    /**
     * Create a new RandomBag Object able to accept objects, with a size of 0.
     */
    public RandomBag() {
        _elements = new Object[8];
        _size = 0;
    }

    /**
     * Get the number of Objects stored in the RandomBag
     * @return the number of Objects
     */
    public int size() {
        return _size;
    }

    /**
     * Adjust the size of the storing array of the Randombag to the desired new capacity.
     * @param capacity the size of the new storage array
     */
    private void setCapacity(int capacity) {
        Object[] newElements = new Object[capacity];
        System.arraycopy(_elements, 0, newElements, 0, _size);
        _elements = newElements;
    }

    /**
     * Call to have the array have at least the capacity specified as the argument.
     * @param capacity the desired storage capacity of the array
     */
    private void ensureCapacity(int capacity) {
        if (capacity > _elements.length) {
            // Ensure that the capacity is at least doubled
            // each time.
            if (capacity < 2 * _elements.length) {
                capacity = 2 * _elements.length;
            }
            setCapacity(capacity);
        }
    }

    /**
     * Limit the storage capacity of the array so that it won't be resized in the near future.
     */
    private void limitCapacity() {
        // Ensure that the capacity can be at least halved
        // each time. Also, there must remain enough elements
        // that no enlargement is required in the near future.
        // It makes no sense to resize very small array,
        // because the creation of a new array is very expensive.
        if (_size >= 8 && _size * 4 < _elements.length) {
            setCapacity(_size * 2);
        }
    }

    /**
     * Insert a new object into the RandomBag.
     * @param elem the object to insert
     */
    public void insert(Object elem) {
        ensureCapacity(_size + 1);
        _elements[_size++] = elem;
    }

    /**
     * Check if there are no Objects stored in the RandomBag.
     * @return true if there are no objects stored in the array.
     */
    public boolean isEmpty() {
        return _size == 0;
    }

    /**
     * Remove a random Object from the bag
     * @return the removed randomly selected Object. Returns <code>null</code> if the bag is empty.
     */
    public Object extract() {
        if (isEmpty()) {
            return null;
        }
        Object elem = _elements[_size - 1];


        // Null the field to allow garbage collection.
        _elements[_size - 1] = null;
        _size = _size - 1;
        limitCapacity();

        return elem;
    }
}