#ifndef VEC_H
#define VEC_H

#include <algorithm>
#include <cstddef>
#include <memory>
#include<iostream>
#include<stdexcept>
template <class T> class Vec;/* This forward declaration gives us enough 
				information about Vec<T> to declare a 
				pointer, and use 'Vec' functions in the 
				definition of V. The compiler is very 
				insistent about needing the friend declared
				first. A forward declaration doesn't seem to
				work.
*/



template <class T> class sumVec;
/*********************************************************************
 * 'V' is a handle class for 'Vec' and its descendants. It maintains a
 * 'Vec' pointer, allocating and deallocating memory as necessary. 
 * The constructors can produce 'Vec's or 'sumVec's. The public 
 * functions pass off to the correct version of virtual functions.
 *********************************************************************/
template <class T> class V {
public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef size_t size_type;
	typedef T value_type;
	typedef T& reference;
	typedef const T& const_reference;
	
	//Constructors allocate new Vec's or sumVecs
	 V(): ptr(0){}
	 V(size_t n, const T& t=T(), bool maintain_sum=false){
		 if(maintain_sum)
			 ptr=new sumVec<T>(n,t);
		 else
			 ptr=new Vec<T>(n,t);
	 }
	V(const V& rhs): ptr(0) {
		if(rhs.ptr) ptr=rhs.ptr->clone();
	}
	
	//Reclaim old allocated memory during assignment.
	V& operator=(const V& rhs){
		if(&rhs!=this)
		{
			delete ptr;
			if(rhs.ptr)
				ptr=rhs.ptr->clone();
			else 
				ptr=0;
		}
		return *this;
	}

	// Reclaim dynamically allocated memory with the destructor.
	~V(){delete ptr;};

	// Provide pass-through's for the public functions of Vec.
	// Note that ptr=0 often must be handled as a special case.
	void push_back(const T& t, bool maintain_sum=false){
		if(ptr)
			ptr->push_back(t);
		else
			if(maintain_sum)
				ptr=new sumVec<T>(1,t);
			else 
				ptr=new Vec<T>(1,t);
		
	}
	void show(){ 
		if(ptr)
			ptr->show();
	}
		
	void clear(){
		if(ptr)
			(*ptr).clear();
	}

	T& operator[](size_type i) { 
		if(ptr)
			return (*ptr)[i]; }
	const T& operator[](size_type i) const{ 
		if(ptr)
			return (*ptr)[i]; }
	iterator begin() { 
		if(ptr) 
			return ptr->data;
		else throw std::runtime_error("uninitialized V");	
	}
	const_iterator begin() const {
		if(ptr) 
			return ptr->data;
		else throw std::runtime_error("uninitialized V");	
	}
	iterator end() { 
		if(ptr) 
			return ptr->avail;
		else throw std::runtime_error("uninitialized V");	
	}                
	const_iterator end() const { 
		if(ptr) 
			return ptr->avail;
		else throw std::runtime_error("uninitialized V");	
	}

protected:	
	 Vec<T>* ptr;
};

template <class T> class Vec {

	

public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef size_t size_type;
	typedef T value_type;
	typedef T& reference;
	typedef const T& const_reference;

	Vec() { create(); }
	explicit Vec(size_type n, const T& t = T()) { create(n, t); }

	Vec(const Vec& v) { create(v.begin(), v.end()); }
	Vec& operator=(const Vec&);
	virtual ~Vec() { uncreate(); }/*Use a virtual destructor for any 
					base class to make sure memory 
					is returned correctly.
					*/

	T& operator[](size_type i) { return data[i]; }
	const T& operator[](size_type i) const { return data[i]; }

	virtual void push_back(const T& t) {
		if (avail == limit)
			grow();
		unchecked_append(t);
	}

	size_type size() const { return avail - data; }  

	iterator begin() { return data; }
	const_iterator begin() const { return data; }

	iterator end() { return avail; }                 
	const_iterator end() const { return avail; }     
	virtual void clear() { uncreate(); }
	bool empty() const { return data == avail; }
	virtual void show()const;

protected:
	iterator data;	// first element in the `Vec'
	iterator avail;	// (one past) the last element in the `Vec'
	iterator limit;	// (one past) the allocated memory

	// facilities for memory allocation
	std::allocator<T> alloc;	// object to handle memory allocation

	// allocate and initialize the underlying array
	void create();
	void create(size_type, const T&);
	void create(const_iterator, const_iterator);
	void uncreate();

	// support functions for `push_back'
	void grow();
	void unchecked_append(const T&);

	//'clone' is a support function for 'V', for deep copies.
	virtual Vec<T>* clone() const {return new Vec<T>(*this);}
	
	//Give 'V' access to 'clone'.
	friend  class V<T>;
};

template <class T> void Vec<T>::create()
{
	data = avail = limit = 0;
}

template <class T> void Vec<T>::create(size_type n, const T& val)
{
	data = alloc.allocate(n);
	limit = avail = data + n;
	std::uninitialized_fill(data, limit, val);
}

template <class T>
void Vec<T>::create(const_iterator i, const_iterator j)
{
	data = alloc.allocate(j - i);
	limit = avail = std::uninitialized_copy(i, j, data);
}
template <class T>
void Vec<T>::uncreate()
{
	if (data) {
		// destroy (in reverse order) the elements that were constructed
		iterator it = avail;
		while (it != data)
			alloc.destroy(--it);

		// return all the space that was allocated
		alloc.deallocate(data, limit - data);
	}
	// reset pointers to indicate that the `Vec' is empty again
	data = limit = avail = 0;

}



template <class T> void Vec<T>::grow()
{
	// when growing, allocate twice as much space as currently in use
	size_type new_size = std::max(2 * (limit - data), ptrdiff_t(1));

	// allocate new space and copy existing elements to the new space
	iterator new_data = alloc.allocate(new_size);
	iterator new_avail = std::uninitialized_copy(data, avail, new_data);

	// return the old space
	uncreate();

	// reset pointers to point to the newly allocated space
	data = new_data;
	avail = new_avail;
	limit = data + new_size;
}

// assumes `avail' points at allocated, but uninitialized space
template <class T> void Vec<T>::unchecked_append(const T& val)
{
	alloc.construct(avail++, val);
}

template <class T>
Vec<T>& Vec<T>::operator=(const Vec& rhs)
{
	// check for self-assignment
	if (&rhs != this) {

		// free the array in the left-hand side
		uncreate();

		// copy elements from the right-hand to the left-hand side
		create(rhs.begin(), rhs.end());
	}
	return *this;
}

template <class T>
void Vec<T>::show()const
{
	for(const_iterator i=data; i!=avail; i++)
		std::cout<<*i<<" ";
}

#endif