// 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_

namespace rapidjson {
	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 (!allocator_)
					ownAllocator = allocator_ = new Allocator();
			}

			~Stack() {
				Allocator::Free(stack_);
				delete ownAllocator; // Only delete if it is owned by the stack
			}

			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)
					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;
			}

			// 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
} // namespace rapidjson

#endif // RAPIDJSON_STACK_H_
