import { min } from "./util.sol";

export { ResizableArray, IndexOutOfBounds };

error IndexOutOfBounds();
error InvalidReserve();

// All declarations inside a template automatically turn into templates.
// When accessed from outside, the value for T has to be explicitly
// given (unless it is auto-deduced).
// Inside the template area, template parameters can be mentioned
// when accessing other templatized declartions but they can
// also be omitted.
template[T]
{

struct ResizableArray
{
    uint length;
    T[] data;

    invariant { length < data.length }
}

// "member" attaches the function as a member to the type.
// alternative: "bound"?
// It cannot be called without the type.
// Problem: the inner workings may be obivous if the first parameter is a struct,
// but it may not be that obvious if it is a complex array.
// Name clashes could maybe only be detected at the point where the function is used.


/// Reserves a certain capacity but does not change the length of
/// the array. Re-allocates if needed.
/// capacity has to be at least the current length.
member function reserve(ResizableArray memory array, uint capacity)
{
    require(capacity >= array.length, InvalidReserve());
    if (capacity <= array.data.length)
        return;

    T[] memory newData = new T[](capacity);
    for (uint i = 0; i < array.length; i++)
        newData[i] = array.data[i];
    array.data = newData;
}


/// Sets the length to the given value and re-allocates the
/// data if required.
member function resize(ResizableArray memory array, uint length)
{
    // grow if needed
    uint newCapacity = array.data.length;
    while (newCapacity < length) newCapacity *= 2;
    array.reserve(newCapacity);

    // zero-initialize in case we reduced the size
    for (uint i = array.length; i < length; i++)
    {
        // for template types, we allow data location even if the template
        // parameter is a value type
        T memory zero;
        array.data[i] = zero;
    }
    array.length = length;
    assert(array.length <= array.data.length);
}

member function at(ResizableArray memory array, uint index) returns (T memory)
{
    require(index < array.length, IndexOutOfBounds());
    return array.data[index];
}


member function push(ResizableArray memory array, T memory value)
{
    array.resize(array.length + 1);
    array.at(array.length - 1) = value;
}

}