// vecarray.h - v1.1.6
/* 
 * Copyright (c) 2008 Leigh Johnston.  All Rights Reserved.
 *
 * Permission to use, copy, modify and distribute this
 * software and its documentation for any purpose is hereby
 * granted, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * The author makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

#ifndef VECARRAY_H
#define VECARRAY_H

#include <cassert>
#include <cstddef>
#include <tr1/type_traits>
#include <algorithm>
#include <memory>
#include <stdexcept>

/* 
 * WARNING: only define NO_VECARRAY_OVERFLOW_PREVENTION on a
 * project wide basis, not on a per-file basis to ensure you do not violate the ODR! 
 */

namespace lib
{
	#ifndef NO_VECARRAY_OVERFLOW_PREVENTION
	struct vecarray_overflow : public std::exception
	{
		const char* what() { return "vecarray overflow"; }
	};
	#endif

	namespace detail
	{
		class alignment_dummy;
		typedef void (*function_ptr)();
		typedef int (alignment_dummy::*member_ptr);
		typedef int (alignment_dummy::*member_function_ptr)();
		union max_align
		{
			char dummy0; short dummy1; int dummy2; long dummy3; 
			float dummy4; double dummy5; long double dummy6; 
			void* dummy7; 
			function_ptr dummy8; member_ptr dummy9; member_function_ptr dummy10;
		};

		template <typename T, typename Pointer, typename IsScalar>
		struct vecarray_scalar_trait_impl
		{ 
			typedef Pointer pointer;
			typedef IsScalar type;
			typedef const T& parameter_type; 
			inline static void construct(pointer object, parameter_type value)
			{
				new (static_cast<void*>(object)) T(value);
			}
			inline static void destruct(pointer object)
			{
				object->~T();
			}
			inline static void destruct(pointer first, pointer last)
			{
				while(first != last)
				{
					first->~T();
					++first;
				}
			}
		};
		template <typename T, typename Pointer>
		struct vecarray_scalar_trait_impl<T, Pointer, std::tr1::true_type>
		{ 
			typedef Pointer pointer;
			typedef std::tr1::true_type type;
			typedef T parameter_type; 
			inline static void construct(pointer object, parameter_type value)
			{
				*object = value;
			}
			inline static void destruct(pointer object)
			{
			}
			inline static void destruct(pointer first, pointer last)
			{
			}
		};
	}
	
	template<typename T, std::size_t N>
	class vecarray
	{
	public:
		typedef T value_type;
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef pointer iterator;
		typedef const_pointer const_iterator;
		typedef std::size_t size_type;
		typedef std::ptrdiff_t difference_type;
	private:
		typedef detail::vecarray_scalar_trait_impl<T, pointer, typename std::tr1::is_scalar<T>::type> scalar_trait;
	public:
		typedef typename scalar_trait::parameter_type parameter_type;
	
	private:
		union
		{
			detail::max_align dummy0;
			char iData[sizeof(T) * N];
		} iAlignedBuffer;
		size_type iSize;
	
	public:
		// construction
		vecarray() : iSize(0)
		{
		}
		vecarray(const vecarray& rhs) : iSize(0)
		{
			insert(begin(), rhs.begin(), rhs.end());
		}
		template <typename T2, std::size_t N2>
		vecarray(const vecarray<T2, N2>& rhs) : iSize(0)
		{
			insert(begin(), rhs.begin(), rhs.end());
		}
		vecarray(size_type n, parameter_type value) : iSize(0)
		{
			insert(begin(), n, value);
		}
		template<typename InputIterator>
		vecarray(InputIterator first, InputIterator last) : iSize(0)
		{
			insert(begin(), first, last);
		}
		~vecarray()
		{
			clear();
		}
		// traversals
		iterator begin() { return reinterpret_cast<pointer>(iAlignedBuffer.iData); }
		const_iterator begin() const { return reinterpret_cast<const_pointer>(iAlignedBuffer.iData); }
		iterator end() { return reinterpret_cast<pointer>(iAlignedBuffer.iData) + iSize; }
		const_iterator end() const { return reinterpret_cast<const_pointer>(iAlignedBuffer.iData) + iSize; }
		iterator locate(size_type position) { return reinterpret_cast<pointer>(iAlignedBuffer.iData) + position; }
		const_iterator locate(size_type position) const { return reinterpret_cast<const_pointer>(iAlignedBuffer.iData) + position; }
		bool empty() const { return iSize == 0; }
		bool full() const { return iSize == N; }
		size_type size() const { return iSize; }
		size_type available() const { return N - iSize; }
		size_type capacity() const { return N; }
		size_type max_size() const { return N; }
		size_type after(size_type position) const { return position < iSize ? iSize - position : 0; }
		// element access
		reference operator[](size_type n) { return *(begin() + n); }
		const_reference operator[](size_type n) const { return *(begin() + n); }
		reference at(size_type n) { if (n < iSize) return operator[](n); else { throw_out_of_range("vecarray::at"); assert(false); return *((T*)0); } }
		const_reference at(size_type n) const { if (n < iSize) return operator[](n); else { throw_out_of_range("vecarray::at"); assert(false); return *((T*)0); } }
		reference front() { return *begin(); }
		reference back() { return *(begin() + (iSize - 1)); }
		const_reference front() const { return *begin(); }
		const_reference back() const { return *(begin() + (iSize - 1)); }
		// modifiers
		vecarray& operator=(const vecarray& rhs)
		{
			if (&rhs != this)
				assign(rhs.begin(), rhs.end());
			return *this;
		}
		template<typename T2, std::size_t N2>
		vecarray& operator=(const vecarray<T2, N2>& rhs)
		{
			if (static_cast<const void*>(&rhs) != static_cast<const void*>(this))
				assign(rhs.begin(), rhs.end());
			return *this;
		}
		template <typename InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			clear();
			insert(begin(), first, last);
		}
		void assign(size_type n, parameter_type value)
		{
			clear();
			insert(begin(), n, value);
		}
		iterator insert(iterator position, parameter_type value)
		{
			insert(position, &value, &value+1);
			return position;
		}
		void insert(iterator position, size_type n, parameter_type value)
		{
			while(n > 0)
			{
				insert(position, value);
				++position;
				--n;
			}
		}
		template <typename InputIterator>
		void insert(iterator position, InputIterator first, InputIterator last)
		{
			insert_dispatch(position, first, last, typename std::tr1::is_integral<InputIterator>::type());
		}
		void insert(iterator position, iterator first, iterator last)
		{
			insert(position, static_cast<const_iterator>(first), static_cast<const_iterator>(last));
		}
		void insert(iterator position, const_iterator first, const_iterator last)
		{
			difference_type n = last - first;
			overflow_check(n);
			iterator theEnd = end();
			difference_type t = theEnd - position;
			if (t > 0)
			{
				if (t > n)
				{
					std::uninitialized_copy(theEnd - n, theEnd, theEnd);
					std::copy_backward(position, theEnd - n, theEnd);
					std::copy(first, last, position);
				}
				else
				{
					std::uninitialized_copy(theEnd - t, theEnd, theEnd + (n - t));
					std::uninitialized_copy(first + t, last, theEnd);
					std::copy(first, first + t, position);
				}
			}
			else
			{
				std::uninitialized_copy(first, last, theEnd);
			}
			iSize += n;
		}
		iterator erase(iterator position) 
		{ 
			iterator last = end(); --last;
			std::copy(position + 1, end(), position);
			scalar_trait::destruct(last);
			--iSize;
			return position;
		}
		iterator erase(iterator first, iterator last) 
		{ 
			if (last != end())
				std::copy(last, end(), first);
			scalar_trait::destruct(end() - (last - first), end());
			iSize-=(last - first);
			return first;
		}
		void clear()
		{
			erase(begin(), end());
		}
		void push_back(parameter_type value)
		{
			push_back_dispatch(value, typename scalar_trait::type());
		}
		void pop_back()
		{
			erase(end() - 1);
		}
		void remove(parameter_type value, bool multiple = true)
		{
			for (iterator i = begin(); i != end(); )
			{
				if (*i == value)
				{
					erase(i);
					if (!multiple)
						return;
				}
				else
					++i;
			}
		}
		void resize(size_type n, parameter_type value = value_type())
		{
			if (iSize > n)
				erase(begin() + n, end());
			else if (iSize < n)
				insert(end(), n - iSize, value);
		}
		template <typename T2, std::size_t N2>
		void swap(vecarray<T2, N2>& rhs)
		{
			vecarray tmp = rhs;
			rhs = *this;
			*this = tmp;
		}
	
	private:
		template <typename InputIterator>
		void insert_dispatch(iterator position, InputIterator first, InputIterator last, std::tr1::false_type)
		{
			while(first != last)
				insert(position++, *first++);
		}
		template <typename Integer>
		void insert_dispatch(iterator position, Integer n1, Integer n2, std::tr1::true_type)
		{
			size_type n = static_cast<size_type>(n1);
			value_type value = static_cast<value_type>(n2);
			while(n > 0)
			{
				insert(position, value);
				++position;
				--n;
			}
		}
		void push_back_dispatch(parameter_type value, std::tr1::false_type)
		{
			overflow_check(1);
			scalar_trait::construct(end(), value);
			++iSize;
		}
		void push_back_dispatch(parameter_type value, std::tr1::true_type)
		{
			overflow_check(1);
			*end() = value;
			++iSize;
		}
		void throw_out_of_range(const char* s) const
		{
			throw std::out_of_range(s);
		}
		void overflow_check(size_type n) const
		{
			#ifndef NO_VECARRAY_OVERFLOW_PREVENTION
			if (iSize + n > N)
				throw vecarray_overflow();
			#endif
		}
	};
}

#endif // VECARRAY_H