// Copyright (C) 2011 Milo Yip
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

#ifndef RAPIDJSON_INTERNAL_STACK_H_
#define RAPIDJSON_INTERNAL_STACK_H_

RAPIDJSON_NAMESPACE_BEGIN
namespace internal
{

///////////////////////////////////////////////////////////////////////////////
// Stack

//! A type-unsafe stack for storing different types of data.
/*! \tparam Allocator Allocator for allocating stack memory.
 */
template <typename Allocator>
class Stack
{
  public:
    // Optimization note: Do not allocate memory for stack_ in constructor.
    // Do it lazily when first Push() -> Expand() -> Resize().
    Stack(Allocator *allocator, size_t stackCapacity)
        : allocator_(allocator),
          ownAllocator_(0),
          stack_(0),
          stackTop_(0),
          stackEnd_(0),
          initialCapacity_(stackCapacity)
    {
        RAPIDJSON_ASSERT(stackCapacity > 0);
    }

#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
    Stack(Stack &&rhs)
        : allocator_(rhs.allocator_),
          ownAllocator_(rhs.ownAllocator_),
          stack_(rhs.stack_),
          stackTop_(rhs.stackTop_),
          stackEnd_(rhs.stackEnd_),
          initialCapacity_(rhs.initialCapacity_)
    {
        rhs.allocator_       = 0;
        rhs.ownAllocator_    = 0;
        rhs.stack_           = 0;
        rhs.stackTop_        = 0;
        rhs.stackEnd_        = 0;
        rhs.initialCapacity_ = 0;
    }
#endif

    ~Stack() { Destroy(); }

#if RAPIDJSON_HAS_CXX11_RVALUE_REFS
    Stack &operator=(Stack &&rhs)
    {
        if (&rhs != this)
        {
            Destroy();

            allocator_       = rhs.allocator_;
            ownAllocator_    = rhs.ownAllocator_;
            stack_           = rhs.stack_;
            stackTop_        = rhs.stackTop_;
            stackEnd_        = rhs.stackEnd_;
            initialCapacity_ = rhs.initialCapacity_;

            rhs.allocator_       = 0;
            rhs.ownAllocator_    = 0;
            rhs.stack_           = 0;
            rhs.stackTop_        = 0;
            rhs.stackEnd_        = 0;
            rhs.initialCapacity_ = 0;
        }
        return *this;
    }
#endif

    void Clear() { stackTop_ = stack_; }

    void ShrinkToFit()
    {
        if (Empty())
        {
            // If the stack is empty, completely deallocate the memory.
            Allocator::Free(stack_);
            stack_    = 0;
            stackTop_ = 0;
            stackEnd_ = 0;
        }
        else
            Resize(GetSize());
    }

    // Optimization note: try to minimize the size of this function for force inline.
    // Expansion is run very infrequently, so it is moved to another (probably non-inline) function.
    template <typename T>
    RAPIDJSON_FORCEINLINE T *Push(size_t count = 1)
    {
        // Expand the stack if needed
        if (stackTop_ + sizeof(T) * count >= stackEnd_)
            Expand<T>(count);

        T *ret = reinterpret_cast<T *>(stackTop_);
        stackTop_ += sizeof(T) * count;
        return ret;
    }

    template <typename T>
    T *Pop(size_t count)
    {
        RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
        stackTop_ -= count * sizeof(T);
        return reinterpret_cast<T *>(stackTop_);
    }

    template <typename T>
    T *Top()
    {
        RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
        return reinterpret_cast<T *>(stackTop_ - sizeof(T));
    }

    template <typename T>
    T *Bottom()
    {
        return (T *)stack_;
    }

    Allocator &GetAllocator() { return *allocator_; }
    bool Empty() const { return stackTop_ == stack_; }
    size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
    size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }

  private:
    template <typename T>
    void Expand(size_t count)
    {
        // Only expand the capacity if the current stack exists. Otherwise just create a stack with
        // initial capacity.
        size_t newCapacity;
        if (stack_ == 0)
        {
            if (!allocator_)
                ownAllocator_ = allocator_ = RAPIDJSON_NEW(Allocator());
            newCapacity = initialCapacity_;
        }
        else
        {
            newCapacity = GetCapacity();
            newCapacity += (newCapacity + 1) / 2;
        }
        size_t newSize = GetSize() + sizeof(T) * count;
        if (newCapacity < newSize)
            newCapacity = newSize;

        Resize(newCapacity);
    }

    void Resize(size_t newCapacity)
    {
        const size_t size = GetSize();  // Backup the current size
        stack_            = (char *)allocator_->Realloc(stack_, GetCapacity(), newCapacity);
        stackTop_         = stack_ + size;
        stackEnd_         = stack_ + newCapacity;
    }

    void Destroy()
    {
        Allocator::Free(stack_);
        RAPIDJSON_DELETE(ownAllocator_);  // Only delete if it is owned by the stack
    }

    // Prohibit copy constructor & assignment operator.
    Stack(const Stack &);
    Stack &operator=(const Stack &);

    Allocator *allocator_;
    Allocator *ownAllocator_;
    char *stack_;
    char *stackTop_;
    char *stackEnd_;
    size_t initialCapacity_;
};

}  // namespace internal
RAPIDJSON_NAMESPACE_END

#endif  // RAPIDJSON_STACK_H_
