// segmented_array.h - v1.1.10
/* 
 * 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 SEGMENTED_ARRAY_H
#define SEGMENTED_ARRAY_H

#include <cassert>
#include <cstddef>
#include <tr1/type_traits>
#include <stdexcept>
#include <list>
#include "vecarray.h"

namespace lib
{
	template <typename T, std::size_t N = 64, typename A = std::allocator<T> >
	class segmented_array
	{
	public:
		typedef vecarray<T, N> segment;
		typedef std::list<segment, typename A:: template rebind<segment>::other> segment_list;
	
	public:
		typedef T value_type;
		typedef typename A::reference reference;
		typedef typename A::pointer pointer;
		typedef typename A::const_reference const_reference;
		typedef typename A::const_pointer const_pointer;
		typedef typename segment::size_type size_type;
		typedef typename segment::difference_type difference_type;
		typedef typename segment::parameter_type parameter_type;
		typedef A allocator_type;
		enum { segment_length = N };
		
		class iterator;
		class const_iterator;
	
	private:
		template <typename Pointer, typename Reference, typename SegmentListIterator, typename SegmentIterator, typename Segment>
		class iterator_base : public std::iterator<std::random_access_iterator_tag, value_type, difference_type, Pointer, Reference>
		{
		public:
			typedef SegmentListIterator segment_list_iterator_type;
			typedef SegmentIterator segment_iterator_type;
			typedef Segment segment_type;
		private:
			friend class iterator_base<pointer, reference, typename segment_list::iterator, typename segment::iterator, segment>;
			friend class iterator_base<const_pointer, const_reference, typename segment_list::const_iterator, typename segment::const_iterator, const segment>;
		protected:
			iterator_base() {}
			iterator_base(const iterator_base& x) : iPosition(x.iPosition), iSegment(x.iSegment), iSegmentCurrent(x.iSegmentCurrent), iEnd(x.iEnd) {}
			template <typename Pointer2, typename Reference2, typename SegmentListIterator2, typename SegmentIterator2, typename Segment2>
			iterator_base(const iterator_base<Pointer2, Reference2, SegmentListIterator2, SegmentIterator2, Segment2>& x) : iPosition(x.iPosition), iSegment(x.iSegment), iSegmentCurrent(x.iSegmentCurrent), iEnd(x.iEnd) {}
			iterator_base(size_type position, segment_list_iterator_type seg, size_type index, segment_list_iterator_type end) : iPosition(position), iSegment(seg), iSegmentCurrent(seg != end ? seg->begin() + index : 0), iEnd(end) {}
		public:
			size_type position() const { return iPosition; }
			template <typename Pointer2, typename Reference2, typename SegmentListIterator2, typename SegmentIterator2, typename Segment2>
			bool operator==(const iterator_base<Pointer2, Reference2, SegmentListIterator2, SegmentIterator2, Segment2>& rhs) const { return iPosition == rhs.iPosition; }
			template <typename Pointer2, typename Reference2, typename SegmentListIterator2, typename SegmentIterator2, typename Segment2>
			bool operator!=(const iterator_base<Pointer2, Reference2, SegmentListIterator2, SegmentIterator2, Segment2>& rhs) const { return iPosition != rhs.iPosition; }
			template <typename Pointer2, typename Reference2, typename SegmentListIterator2, typename SegmentIterator2, typename Segment2>
			bool operator<(const iterator_base<Pointer2, Reference2, SegmentListIterator2, SegmentIterator2, Segment2>& rhs) const { return iPosition < rhs.iPosition; }
			template <typename Pointer2, typename Reference2, typename SegmentListIterator2, typename SegmentIterator2, typename Segment2>
			bool operator>(const iterator_base<Pointer2, Reference2, SegmentListIterator2, SegmentIterator2, Segment2>& rhs) const { return iPosition > rhs.iPosition; }
			template <typename Pointer2, typename Reference2, typename SegmentListIterator2, typename SegmentIterator2, typename Segment2>
			bool operator<=(const iterator_base<Pointer2, Reference2, SegmentListIterator2, SegmentIterator2, Segment2>& rhs) const { return iPosition <= rhs.iPosition; }
			template <typename Pointer2, typename Reference2, typename SegmentListIterator2, typename SegmentIterator2, typename Segment2>
			bool operator>=(const iterator_base<Pointer2, Reference2, SegmentListIterator2, SegmentIterator2, Segment2>& rhs) const { return iPosition >= rhs.iPosition; }
		protected:
			void increment() 
			{ 
				++iPosition;
				if (is_end() || (++iSegmentCurrent == seg().end())) 
					increment_segment();
			}
			void decrement() 
			{ 
				--iPosition;
				if (is_end() || (iSegmentCurrent-- == seg().begin())) 
					decrement_segment();
			}
			void increment_segment()
			{
				assert(!is_end());
				++iSegment;
				if (is_end())
				{
					iSegmentCurrent = 0;
				}
				else
					iSegmentCurrent = seg().begin();
			}
			void decrement_segment()
			{
				--iSegment;
				assert(!is_end());
				iSegmentCurrent = seg().end();
				--iSegmentCurrent; 
			}
			void add(difference_type n) 
			{ 
				if (n <= 0 || is_end())
					return;
	
				difference_type startDifference = seg().end() - (iSegmentCurrent + 1);
				if (n <= startDifference)
				{
					iPosition += n;
					iSegmentCurrent += n;
					return;
				}
	
				size_type currPos = iPosition + startDifference + 1;
				size_type endPos = iPosition + n;
				segment_list_iterator_type currSegment = iSegment;
				++currSegment;
				while(currSegment != iEnd)
				{
					size_type segmentSize = currSegment->size();
					if (endPos < currPos + segmentSize)
					{
						iSegmentCurrent = currSegment->begin() + (endPos - currPos);
						currPos = endPos;
						break;
					}
					currPos += segmentSize;
					++currSegment;
				}
				
				iPosition = currPos;
				iSegment = currSegment;
				if (currSegment == iEnd)
					iSegmentCurrent = 0;
			}
			void subtract(difference_type n) 
			{ 
				if (n <= 0)
					return;
	
				if (is_end())
				{
					decrement();
					--n;
				}
	
				size_type count; 
				while (n > (count = static_cast<size_type>(iSegmentCurrent - seg().begin()) +1)) 
				{ 
					n -= count;
					iPosition -= count;
					decrement_segment();
					if (is_end())
						return;
				}
				iSegmentCurrent -= n;
				iPosition -= n;
				if (iSegmentCurrent < seg().begin())
					decrement_segment();
			}
			bool is_end() const { return iSegment == iEnd; }
			size_type index() const { return iSegmentCurrent - seg().begin(); }
			size_type available() const { return !is_end() ? seg().available() : 0; }
			size_type after() const { return !is_end() ? seg().after(index()) : 0; }
			segment_type& seg() const { return *iSegment; }
			segment_list_iterator_type iter() const { return iSegment; }
			segment_iterator_type current() const { return iSegmentCurrent; }
		protected:
			size_type iPosition;
			segment_list_iterator_type iSegment;
			segment_iterator_type iSegmentCurrent;
			segment_list_iterator_type iEnd; // need this so traversal operators don't dereference end() 
		};
		
	public:
		class iterator : public iterator_base<pointer, reference, typename segment_list::iterator, typename segment::iterator, segment>
		{
		private:
			friend class segmented_array<T, N, A>;
			friend class const_iterator;
			typedef  iterator_base<pointer, reference, typename segment_list::iterator, typename segment::iterator, segment> base;
		public:
			iterator() {}
			iterator(const iterator& x) : iterator_base<pointer, reference, typename segment_list::iterator, typename segment::iterator, segment>(x) {}
		private:
			iterator(size_type position, typename segment_list::iterator seg, size_type index, typename segment_list::iterator end) : iterator_base<pointer, reference, typename segment_list::iterator, typename segment::iterator, segment>(position, seg, index, end) {}
		public:
			iterator& operator++() { base::increment(); return *this; }
			iterator& operator--() { base::decrement(); return *this; }
			iterator operator++(int) { iterator ret(*this); operator++(); return ret; }
			iterator operator--(int) { iterator ret(*this); operator--(); return ret; }
			reference operator*() const { return *base::current(); }
			pointer operator->() const { return &(operator*()); }
			reference operator[](difference_type n) { iterator tmp(*this); tmp += n; return *tmp; }
			iterator operator+(difference_type n) { iterator tmp(*this); tmp += n; return tmp; }
			iterator operator-(difference_type n) { iterator tmp(*this); tmp -= n; return tmp; }
			iterator operator+=(difference_type n) { base::add(n); return *this; }
			iterator operator-=(difference_type n) { base::subtract(n); return *this; }
			difference_type operator-(const iterator& x) const { return base::position() - x.base::position(); }
		private:
			operator typename segment_list::iterator() const { return base::iter(); }
			operator typename segment_list::const_iterator() const { return base::iter(); }
		};
		
		class const_iterator : public iterator_base<const_pointer, const_reference, typename segment_list::const_iterator, typename segment::const_iterator, const segment>
		{
		private:
			friend class segmented_array<T, N, A>;
			typedef iterator_base<const_pointer, const_reference, typename segment_list::const_iterator, typename segment::const_iterator, const segment> base;
		public:
			const_iterator() {}
			const_iterator(const const_iterator& x) : iterator_base<const_pointer, const_reference, typename segment_list::const_iterator, typename segment::const_iterator, const segment>(x) {}
			const_iterator(const iterator& x) : iterator_base<const_pointer, const_reference, typename segment_list::const_iterator, typename segment::const_iterator, const segment>(x) {}
		private:
			const_iterator(size_type position, typename segment_list::const_iterator seg, size_type index, typename segment_list::const_iterator end) : iterator_base<const_pointer, const_reference, typename segment_list::const_iterator, typename segment::const_iterator, const segment>(position, seg, index, end) {}
		public:
			const_iterator& operator++() { base::increment(); return *this; }
			const_iterator& operator--() { base::decrement(); return *this; }
			const_iterator operator++(int) { const_iterator ret(*this); operator++(); return ret; }
			const_iterator operator--(int) { const_iterator ret(*this); operator--(); return ret; }
			const_reference operator*() const { return *base::current(); }
			const_pointer operator->() const { return &(operator*()); }
			reference operator[](difference_type n) { const_iterator tmp(*this); tmp += n; return *tmp; }
			const_iterator operator+(difference_type n) { const_iterator tmp(*this); tmp += n; return tmp; }
			const_iterator operator-(difference_type n) { const_iterator tmp(*this); tmp -= n; return tmp; }
			const_iterator operator+=(difference_type n) { base::add(n); return *this; }
			const_iterator operator-=(difference_type n) { base::subtract(n); return *this; }
			difference_type operator-(const const_iterator& x) const { return base::position() - x.base::position(); }
		private:
			operator typename segment_list::const_iterator() const { return base::iter(); }
		};
	
	private:
		class checked_iterator : iterator
		{
		private:
			typedef iterator base;
		public:
			checked_iterator(const iterator& x) : iterator(x) {}
			reference operator*() const { if (!base::is_end()) return *base::current(); else { throw_out_of_range(); assert(false); return *((T*)0); } }
			pointer operator->() const { return &(operator*()); }
		private:
			void throw_out_of_range() const { throw std::out_of_range("segmented_array::iterator"); }
		};
	
		class checked_const_iterator : const_iterator
		{
		private:
			typedef const_iterator base;
		public:
			checked_const_iterator(const const_iterator& x) : const_iterator(x) {}
			const_reference operator*() const { if (!base::is_end()) return *base::current(); else { throw_out_of_range(); assert(false); return *((T*)0); } }
			const_pointer operator->() const { return &(operator*()); }
		private:
			void throw_out_of_range() const { throw std::out_of_range("segmented_array::const_iterator"); }
		};
	
	public:
		// construction
		segmented_array() : iSize(0) {}
		segmented_array(const A& allocator) : iSegments(allocator), iSize(0) {}
		segmented_array(const segmented_array& rhs) : iSize(0) 
		{
			insert(begin(), rhs.begin(), rhs.end());
		}
		template <typename T2, std::size_t N2, typename A2>
		segmented_array(const segmented_array<T2, N2, A2>& rhs) : iSize(0) 
		{
			insert(begin(), rhs.begin(), rhs.end());
		}
		segmented_array(size_type n, parameter_type value) : iSize(0)
		{
			insert(begin(), n, value);
		}
		template <typename InputIterator>
		segmented_array(InputIterator first, InputIterator last) : iSize(0)
		{
			insert(begin(), first, last);
		}
		// traversals
		iterator begin() { return iterator(0, iSegments.begin(), 0, iSegments.end()); }
		iterator end() { return iterator(size(), iSegments.end(), 0, iSegments.end()); }
		const_iterator begin() const { return const_iterator(0, iSegments.begin(), 0, iSegments.end()); }
		const_iterator end() const { return const_iterator(size(), iSegments.end(), 0, iSegments.end()); }
		iterator locate(size_type position)
		{
			typename segment_list::iterator currSegment = iSegments.begin();
			size_type currPos = 0;
			while(currSegment != iSegments.end())
			{
				if (position < currPos + currSegment->size())
					return iterator(position, currSegment, position - currPos, iSegments.end());
				currPos += currSegment->size();
				++currSegment;
			}
			return end();
		}
		const_iterator locate(size_type position) const
		{			
			typename segment_list::const_iterator currSegment = iSegments.begin();
			size_type currPos = 0;
			while(currSegment != iSegments.end())
			{
				if (position < currPos + currSegment->size())
					return const_iterator(position, currSegment, position - currPos, iSegments.end());
				currPos += currSegment->size();
				++currSegment;
			}
			return end();
		}
		size_type locate(const const_iterator& position) const
		{
			return position.position();
		}
		bool empty() const { return iSegments.empty(); }
		size_type size() const { return iSize; }
		// element access
		reference operator[](size_type n) { return *locate(n); }
		reference at(size_type n) { return *checked_iterator(locate(n)); }
		const_reference operator[](size_type n) const { return *locate(n); }
		const_reference at(size_type n) const { return *checked_const_iterator(locate(n)); }
		reference front() { return *begin(); }
		reference back() { return *--end(); }
		const_reference front() const { return *begin(); }
		const_reference back() const { return *--end(); }
		// modifiers
		segmented_array& operator=(const segmented_array& rhs)
		{
			if (&rhs != this)
				assign(rhs.begin(), rhs.end());
			return *this;
		}
		template<typename T2, std::size_t N2, typename A2>
		segmented_array& operator=(const segmented_array<T2, N2, A2>& 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)
		{
			if (position == begin())
			{
				do_insert(position, &value, &value+1);
				return begin();
			}
			else
			{
				iterator ret = position; --ret;
				do_insert(position, &value, &value+1);
				return ++ret;
			}
		}
		void insert(iterator position, size_type n, parameter_type value)
		{
			while(n > 0)
			{
				position = 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());
		}
		iterator erase(iterator position) 
		{ 
			iterator next = position; ++next;
			next.iPosition = position.position();
			position.seg().erase(position.seg().locate(position.index()));
			--iSize;
			if (position.seg().empty())
			{
				iSegments.erase(position);
				return next;
			}
			else
			{
				if (&next.seg() != &position.seg())
					return next;
				else
					return position;
			}
		}
		void erase(iterator first, iterator last) 
		{ 
			if (first == last)
			{
				return;
			}
			else if (first.iter() == last.iter())
			{
				size_type oldSize = first.seg().size();
				first.seg().erase(first.seg().locate(first.index()), last.seg().locate(last.index()));
				iSize -= (oldSize - first.seg().size());
				if (first.seg().empty())
					iSegments.erase(first.iter());
			}
			else
			{
				bool lastIsEnd = (last == end());
				for (typename segment_list::iterator i = ++first.iter(); i != last.iter(); )
				{
					iSize -= i->size();
					i = iSegments.erase(i);
				}
				size_type oldSize = first.seg().size();
				first.seg().erase(first.seg().locate(first.index()), first.seg().end());
				iSize -= (oldSize - first.seg().size());
				if (first.seg().empty())
					iSegments.erase(first.iter());
				if (!lastIsEnd)
				{
					size_type oldSize = last.seg().size();
					last.seg().erase(last.seg().begin(), last.seg().locate(last.index()));
					iSize -= (oldSize - last.seg().size());
					if (last.seg().empty())
						iSegments.erase(last.iter());
				}
			}
		}
		void remove(parameter_type value, bool multiple = true)
		{
			for (iterator i = begin(); i != end(); )
			{
				if (*i == value)
				{
					i = erase(i);
					if (!multiple)
						return;
				}
				else
					++i;
			}
		}
		void clear()
		{
			erase(begin(), end());
		}
		void push_front(parameter_type value)
		{
			insert(begin(), value);
		}
		void pop_front()
		{
			erase(begin());
		}
		void push_back(parameter_type value)
		{
			if (size() > 0)
			{
				iterator last = end(); --last;
				if (last.seg().available() > 0)
				{
					last.seg().push_back(value);
					++iSize;
				}
				else
					insert(end(), value);
			}
			else
				insert(end(), value);
		}
		void pop_back()
		{
			erase(--end());
		}
		void swap(segmented_array& x)
		{
			iSegments.swap(x.iSegments);
			std::swap(iSize, x.iSize);
		}
		template <typename T2, std::size_t N2, typename A2>
		void swap(segmented_array<T2, N2, A2>& rhs)
		{
			segmented_array 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)
			{
				position = insert(position, *first++);
				++position;
			}
		}
		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)
			{
				position = insert(position, value);
				++position;
				--n;
			}
		}
		void do_insert(iterator position, const_pointer first, const_pointer last)
		{
			size_type n = last - first;
			if (position.is_end())
			{
				if (position != begin())
					--position;
				size_type available = position.available();
				size_type count = 0;
				if (available > 0)
				{
					count = n > available ? available : n;
					position.seg().insert(position.seg().end(), first, first + count);
					iSize += count;
					first += count;
					n -= count;
				}
				if (n > 0)
				{
					size_type npos = position.position() + count;
					position = iterator(npos, iSegments.insert(position.is_end() ? position : ++position, segment()), 0, iSegments.end());
				}
			}
			if (n > 0)
			{
				typename segment_list::iterator next = position; ++next;
	
				if (n <= position.available())
				{
					position.seg().insert(position.seg().locate(position.index()), first, last);
					iSize += n;
				}
				else if (n <= position.available() + (next != iSegments.end() ? next->available() : 0))
				{
					size_type in_next = n - position.available();
					size_type copy_next = position.after() > in_next ? in_next : position.after();
					size_type insert_next = last - (first + position.available() + copy_next);
					next->insert(next->begin(), last - insert_next, last);
					next->insert(next->begin() + insert_next, position.seg().end() - copy_next, position.seg().end());
					position.seg().erase(position.seg().end() - copy_next, position.seg().end());
					position.seg().insert(position.seg().locate(position.index()), first, first + position.available());
					iSize += n;
				}
				else
				{
					size_type needed = n - position.available();
					iSegments.insert(next, segment());
					size_type allocated = N;
					while(needed > allocated)
					{
						iSegments.insert(next, segment());
						allocated += N;
					}
					size_type in_next = n - position.available();
					size_type copy_next = position.after() > in_next ? in_next : position.after();
					size_type insert_next = last - (first + position.available() + copy_next);
					next = position; ++next;
					const_pointer seg = first + position.available() + copy_next;
					while (insert_next + copy_next > N && insert_next > 0)
					{
						size_type to_insert = insert_next > N ? N : insert_next;
						next->insert(next->begin(), seg, seg + to_insert);
						++next;
						seg += to_insert;
						insert_next -= to_insert;
					}
					next->insert(next->begin(), seg, seg + insert_next);
					next->insert(next->begin() + insert_next, position.seg().end() - copy_next, position.seg().end());
					position.seg().erase(position.seg().end() - copy_next, position.seg().end());
					position.seg().insert(position.seg().locate(position.index()), first, first + position.available());
					iSize += n;
				}
			}
		}
	
	private:
		// attributes
		segment_list iSegments;
		size_type iSize;
	};
}

#endif // SEGMENTED_ARRAY_H