//
// Copyright (c) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for full license information.
//

//
// ArrayStack: A stack, implemented as a growable array

template <class T>
class ArrayStack
{
    static const int builtinSize = 8;
    
public:
    ArrayStack(Compiler *comp, int initialSize = builtinSize)
    {
        compiler = comp;

        if (initialSize > builtinSize)
        {
            maxIndex = initialSize;
            data = new(compiler, CMK_ArrayStack) T[initialSize];
        }
        else
        {
            maxIndex = builtinSize;
            data = builtinData;
        }

        tosIndex = 0;
    }

    void Push(T item)
    {
        if (tosIndex == maxIndex)
            Realloc();
        
        data[tosIndex] = item;
        tosIndex++;
    }

    void Realloc()
    {
        // get a new chunk 2x the size of the old one
        // and copy over
        T* oldData = data;
        noway_assert(maxIndex*2 > maxIndex);
        data = new(compiler, CMK_ArrayStack) T[maxIndex*2];
        for (int i=0; i<maxIndex; i++)
        {
            data[i] = oldData[i];
        }
        maxIndex *= 2;
    }

    // reverse the top N in the stack
    void ReverseTop(int number)
    {
        if (number < 2)
            return;

        assert(number <= tosIndex);

        int start = tosIndex - number;
        int offset = 0;
        while (offset < number/2)
        {
            T temp;
            int index = start+offset;
            int otherIndex = tosIndex - 1 - offset;
            temp = data[index];
            data[index] = data[otherIndex];
            data[otherIndex] = temp;

            offset++;
        }
    }

    T Pop()
    {
        assert(tosIndex > 0);
        tosIndex--;
        return data[tosIndex];
    }

    T Top()
    {
        assert(tosIndex > 0);
        return data[tosIndex-1];
    }

    // return the i'th from the top
    T Index(int idx)
    {
        assert(tosIndex > idx);
        return data[tosIndex - 1 - idx];
    }

    int Height()
    {
        return tosIndex;
    }

    // return the bottom of the stack
    T Bottom()
    {
        assert(tosIndex > 0);
        return data[0];
    }

    // return the i'th from the bottom
    T Bottom(int indx)
    {
        assert(tosIndex > indx);
        return data[indx];
    }

    void Reset()
    {
        tosIndex = 0;
    }

private:
    Compiler *compiler; // needed for allocation
    int tosIndex; // first free location
    int maxIndex;
    T* data;
    // initial allocation
    T builtinData[builtinSize]; 
};