/* Manden bugs a: alexloves@gmail.com
   
   Compilado correctamente en linux bajo g++ version 4.1.2 20060928 
   Se ha obtenido una buena parte del código del libro "Estructura de Datos: Implementación clásica
    y orientada a objetos". Salamanca. Año 2000: De copyraits no sé mucho, pero gran parte del curro es
    de Roberto Berjón, es material didáctico y no sé si hay que pagarle algo por usar esto comercialmente.
    Me ha costado muchísimo trabajo que esto compile, pues el libro no está perfecto (syntaxis) ni es totalmente completo.
    Están resueltos muchos de sus ejercicios, espero que me mandéis los que me faltan, pues la forma y la idea es genial.
    Considero a Roberto Berjón un genio y espero que siga profesionalmente igual. Intachable.
*/
//Se necesita malgorithms.h para compilar este vector. Lo dejo en la misma carpeta donde está este fichero.

//Función que devuelve el mayor de dos parámetros.
template <class TYPE>
TYPE mmax(TYPE arg1, TYPE arg2)
{
	if (arg1 > arg2) return arg1;
	else return arg2;
}

//Clase iterador que es un puntero que va recorriendo el vector avanzando o retrociendo
// y devuelve sus valores y nos dice si son iguales o distintos (según sean el tipo contenedor)
template <class TYPE>
class riterator_mvector : public MITERATOR <RANDOM_ACCESS_ITERATOR_TAG, TYPE, ptrdiff_t>

{
	public:
		typedef riterator_mvector<TYPE>								RITERATOR_TYPE;

		typedef const RITERATOR_TYPE&								CONST_REF_RITERATOR_TYPE;
		typedef typename MITERATOR<RANDOM_ACCESS_ITERATOR_TAG, TYPE, ptrdiff_t>::PTR_ELEMENT  	PTR_ELEMENT;
		typedef typename MITERATOR<RANDOM_ACCESS_ITERATOR_TAG, TYPE, ptrdiff_t>::DISTANCE 	DISTANCE;
		typedef typename MITERATOR<RANDOM_ACCESS_ITERATOR_TAG, TYPE, ptrdiff_t>::REF_ELEMENT 	REF_ELEMENT;

	private:
		PTR_ELEMENT p;

	public:
		riterator_mvector(PTR_ELEMENT pp): p(pp) {}
		riterator_mvector(CONST_REF_RITERATOR_TYPE i): p(i.p) {}

		RITERATOR_TYPE operator +(int cont)
		{
			RITERATOR_TYPE temp;
			temp = p - cont;
			return (temp);
		}

		RITERATOR_TYPE operator +=(int cont)
		{
			p -= cont;
			return *this;
		}

		RITERATOR_TYPE operator ++()
		{
			--p;
			return *this;
		}

		RITERATOR_TYPE operator ++(int)
		{
			RITERATOR_TYPE temp(*this);
			--p;
			return temp;
		}

		RITERATOR_TYPE operator -(int cont)
		{
			RITERATOR_TYPE temp;
			temp = p + cont;
			return(temp);
		}

		RITERATOR_TYPE operator --()
		{
			++p;
			return *this;
		}

		RITERATOR_TYPE operator --(int)
		{
			RITERATOR_TYPE temp(*this);
			++p;
			return temp;
		}

		RITERATOR_TYPE operator ->() const
		{
			return p;
		}

		DISTANCE operator -(CONST_REF_RITERATOR_TYPE i) const
		{
			return p-i.p;
		}

		PTR_ELEMENT base()
		{
			return p;
		}

		CONST_REF_RITERATOR_TYPE operator =(CONST_REF_RITERATOR_TYPE i)
		{
			p=i.p;
			return i;
		}

		bool operator ==(CONST_REF_RITERATOR_TYPE i) const
		{
			return p==i.p;
		}

		bool operator !=(CONST_REF_RITERATOR_TYPE i) const
		{
			return p!=i.p;
		}
};


template <class TYPE, class ALLOCATOR=mallocator<TYPE> >
class mvector
{
	public: //typenames NO en LIBRO
		typedef typename ALLOCATOR::ELEMENT			ELEMENT;
		typedef typename ALLOCATOR::PTR_ELEMENT			PTR_ELEMENT;
		typedef typename ALLOCATOR::CONST_PTR_ELEMENT		CONST_PTR_ELEMENT;
		typedef typename ALLOCATOR::REF_ELEMENT			REF_ELEMENT;
		typedef typename ALLOCATOR::CONST_REF_ELEMENT		CONST_REF_ELEMENT;
		typedef typename ALLOCATOR::DIFERENCE			DIFERENCE;
		typedef typename ALLOCATOR::SIZE			SIZE;

		typedef typename ALLOCATOR::PTR_ELEMENT 		ITERATOR_TYPE;
		typedef typename ALLOCATOR::CONST_PTR_ELEMENT		CONST_ITERATOR_TYPE;

		typedef const ALLOCATOR&				CONST_REF_ALLOCATOR;

		typedef riterator_mvector<TYPE>				RITERATOR_TYPE;
		typedef riterator_mvector<const TYPE>			CONST_RITERATOR_TYPE;
		
		typedef mvector<TYPE, ALLOCATOR>			VECTOR_TYPE;

	private:
		PTR_ELEMENT	vector_address;		//Dirección del comienzo del vector
		PTR_ELEMENT	vector_end_address;	//Dirección del siguiente elemento al último del vector

		SIZE 		vector_elements;	//Número de elementos que contiene el vector
		SIZE 		increment;		//Elementos que adicionalmente se reservan cuando se produce reasignación
		SIZE 		offset;			//Número de elementos disponibles
	
		ALLOCATOR 	a;			//Asignador de memoria
		
		
		void init();						//Proc. Inicializador del vector
		
		//Métodos de ayuda a la inserción
		
		PTR_ELEMENT shift_right(SIZE, PTR_ELEMENT);
		PTR_ELEMENT expand(PTR_ELEMENT, SIZE);

	public:
		
		//Constructor que crea un vector con elementos inicializándolos y un valor por defecto CONST_REF_... NO EN LIBRO
		//NULL da tres warnings. el SIZE creo que podría ser un <int> porque se supone que es el número de elementos a insertar.
	explicit mvector<TYPE, ALLOCATOR> (SIZE pele, CONST_REF_ELEMENT pvalu = TYPE(NULL), CONST_REF_ALLOCATOR pa = ALLOCATOR()):a(pa)
		{
			init();
			for (SIZE p = pele; p != SIZE(0); p-- ) 
			{
				insert(vector_address, pvalu);
			}
		}
		
		//Constructor por defecto
		
	explicit mvector<TYPE, ALLOCATOR> (CONST_REF_ALLOCATOR = ALLOCATOR() );
		
		//Constructor copia
		
	mvector<TYPE, ALLOCATOR> (const mvector<TYPE, ALLOCATOR>&);
		
		//Constructor "Especial" que crea un nuevo vector con los elementos que haya entre i_begin e i_end
		
	template <class ITER_IN>
	explicit mvector<TYPE, ALLOCATOR> (ITER_IN i_begin, ITER_IN i_end, CONST_REF_ALLOCATOR pa= ALLOCATOR()): a(pa)
	{
		init();
		insert(vector_address, i_begin, i_end); //resize(elements, value);
	}
		//Destructor de objeto mvector
		
	virtual ~mvector();
		
		//Método especial de ayuda a los programadores. Depurador
		
		void State(void)
		{
			cout<<endl<<"-------Estado del vector--------"<<endl;
			
			cout<<endl<<"Inicio del Vector:--- " <<	vector_address;
			cout<<endl<<"Fin del Vector:------ " <<	vector_end_address;
			cout<<endl<<"Offset:-------------- " <<	offset;
			cout<<endl<<"Incremento:---------- " <<	increment;
			cout<<endl<<"Vector_elements:----- " <<	vector_elements     <<endl;
		}
		//Métodos de asignación
		template<class ITER_IN>
		void assign (ITER_IN i_begin, ITER_IN i_end)
		{
			ITERATOR_TYPE i = vector_address;
			while ( (i != vector_end_address) && (i_begin != i_end) ) *i++ = *i_begin++;
			if (i_begin != i_end) insert (vector_end_address, i_begin, i_end);
			else erase(i, end());
		}
		
		//Operador de asignación. Como el constructor copia
		
		VECTOR_TYPE operator = (const VECTOR_TYPE& pmv)
		{
			init();

			increment = pmv.increment;

			assign(pmv.vector_address, pmv.vector_end_address);
		}
		
		//Métodos de inserción

		ITERATOR_TYPE push_back(CONST_REF_ELEMENT=TYPE() );

		ITERATOR_TYPE insert(ITERATOR_TYPE, CONST_REF_ELEMENT=TYPE(0) );

		template<class IN_ITER>
		void insert(ITERATOR_TYPE i, IN_ITER i_begin, IN_ITER i_end)
		{
			PTR_ELEMENT index;

			SIZE n = SIZE(i_end - i_begin);

			if(offset >= n)
			{
				index = shift_right(n,i);
				
				vector_end_address += n;
			}
			else index = expand(i,n);
			while(i_begin != i_end) 
				a.construct(index++, *i_begin++);
		}

		//Métodos de eliminación
		ITERATOR_TYPE erase(ITERATOR_TYPE, ITERATOR_TYPE);
		void clear(void);

		//Métodos de acceso a los datos de elementos
		CONST_REF_ELEMENT operator [](SIZE) const;
		REF_ELEMENT operator [](SIZE);

		CONST_REF_ELEMENT operator * () const {return *(vector_address);}
		REF_ELEMENT operator * () {return *(vector_address);}
		
		//Métodos de iteradores
		ITERATOR_TYPE begin()
		{
			return vector_address;
		}
		
		ITERATOR_TYPE end()
		{
			return vector_end_address;
		}
		
		CONST_ITERATOR_TYPE begin() const
		{
			return CONST_PTR_ELEMENT(vector_address);
		}
		
		CONST_ITERATOR_TYPE end() const
		{
			return CONST_PTR_ELEMENT(vector_end_address);
		}
                //Otros Métodos
                bool empty() const
		{
			return (vector_elements==0);
		}
		
		SIZE size(void) const
                {
			return (vector_elements);
		}
		
		SIZE capacity() const
		{
			return (vector_elements + offset);
		}
		
		//Su mecanismo es muy sencillo porque devuelve el mayor de los dos parámetros genéricos
		void set_increment(SIZE pincrement)
		{
			increment = mmax<SIZE>(SIZE(0), pincrement);
		}
		
		//Operadores especiales de igualdad, desigualdad, mayor, menor que, mayor_igual y menor_igual.

		bool operator == (const VECTOR_TYPE& pmv)
		{
			return(vector_elements == pmv.vector_elements );
		}
		
		bool operator >= (const VECTOR_TYPE& pmv)
		{
			return (vector_elements >= pmv.vector_elements );
		}

		bool operator <= (const VECTOR_TYPE& pmv)
		{
			return(vector_elements <= pmv.vector_elements );
		}
		
		bool operator > (const VECTOR_TYPE& pmv)
		{
			return (vector_elements > pmv.vector_elements );
		}

		bool operator < (const VECTOR_TYPE& pmv)
		{
			return(vector_elements < pmv.vector_elements );
		}
		
		bool operator != (const VECTOR_TYPE& pmv)
		{
			return (vector_elements != pmv.vector_elements );
		}


};


//Inicializador del vector (lo pone a 0)

template <class TYPE, class ALLOCATOR>
void mvector<TYPE, ALLOCATOR>::init()
{
	vector_address 		= NULL;
	vector_end_address 	= NULL;
	offset 			= 0;
	increment		= 10;
	vector_elements 	= 0;

}

//Constructor por defecto

template <class TYPE, class ALLOCATOR>
mvector<TYPE, ALLOCATOR>::mvector(CONST_REF_ALLOCATOR pa): a(pa)
{
	init();
}

//Constructor copia

template <class TYPE, class ALLOCATOR>
mvector<TYPE, ALLOCATOR>::mvector(const VECTOR_TYPE& pmv):a(pmv.a)
{
	init();

	increment = pmv.increment;

	assign(pmv.vector_address, pmv.vector_end_address);
}

//Destructor por defecto

template <class TYPE, class ALLOCATOR>
mvector<TYPE, ALLOCATOR>::~mvector()
{
	clear();
}

//Métodos de asignación

/* 
   Método privado shitf_right encargado de desplazar a la derecha el vector. (4 bytes para un int).
   Siempre que haya espacio suficiente en el vector, copiando bytes, sin construir los elementos ya construidos.
   No destruye los copiados, se construirán cuando sean insertados los nuevos.
   El método devuelve la dirección del elemento a partir del cual el método insert producirá los nuevos.
   "i" es el punto de inserción del vector: "vector_address"->comienzo vector. normalmente desde insert.
   Deja abierta la puerta a que se inserte en el comienzo, en cualquier punto o en el final del vector 
   explicación memcpy en http://man.he.net/man3/memcpy. memcpy(destino,origen,size). Copia bloques de bytes de memoria 
   Supongo que lo más económico para el micro es usar como punto de inserción del vector el vector_end_address o iterador.end()
*/

template <class TYPE, class ALLOCATOR>
typename mvector<TYPE, ALLOCATOR>::PTR_ELEMENT 		mvector<TYPE, ALLOCATOR>::shift_right(SIZE elements, PTR_ELEMENT i)
{
	PTR_ELEMENT index2 = vector_end_address + elements;  //nuevo vector resultante vector + elements + final del vector
	PTR_ELEMENT index1 = vector_end_address; //Será el punto desde donde se empiece a reservar espacio a los nuevos elementos

	//Desde index1 (final del vector) hasta i (punto de insercion), hacia atrás, se recopian elementos 
	//dejando el espacio (sin destruir) para albergar los nuevos elementos, tantos como sean elements.
	while (index1 != i) 	memcpy(--index2, --index1, sizeof(ELEMENT) ); 

	offset   	-= elements; //Se disminuye el offset () que es el espacio reservado a futuros elementos
	vector_elements += elements; // Se aumenta el número de elementos del vector
	
	return index1; //Devuelve el último elemento del antiguo vector, a partir del cual, "insert" meterá los nuevos elements
}

/*
   Método expand.
   Produce una reasignación de memoria de tal forma que la nueva capacidad del vector sea igual
   a su tamaño más el número de los elementos a insertar (elements). Cuando se copian los elementos del hueco
   actual de memoria al nuevo hueco, se dejan sin valor los elementos (elements) que 
   se desearán copiar en el otro elemento referenciado por el iterador i. Esos se emplearán para almacenar
   los que se quieren insertar después. El método devuelve la dirección del primero de los libres
*/

template<class TYPE, class ALLOCATOR>
typename mvector<TYPE, ALLOCATOR>::PTR_ELEMENT 		mvector<TYPE, ALLOCATOR>::expand(PTR_ELEMENT i, SIZE elements)
{
	PTR_ELEMENT vector_address2 = a.allocate(vector_elements + elements + increment);

	PTR_ELEMENT index1 = vector_address;  //Vector_address=Antiguo vector que será destruido
	PTR_ELEMENT index2 = vector_address2; //vector_address2=contiene el inicio del nuevo vector a construir
	PTR_ELEMENT ret;

	//El puntero i marca hasta donde se quiere insertar, el límite superior...
	while (index1 != i)	//Se copian los elementos antiguos hasta donde apunte i
	{					//YA que es allí donde queremos insertar los nuevos
		memcpy(index2++, index1++, vector_end_address - vector_address);
    	}
	ret = index2;  //Almacena donde se van a insertar los nuevos
	index2+=elements;  //
	while (index1 != vector_end_address)  //Se copian el resto de elementos antiguos
	{
		memcpy(index2++, index1++, sizeof(ELEMENT) );
	}
	a.deallocate(vector_address); //Se libera espacio del antiguo vector
	
	vector_address     =  vector_address2; 
	vector_end_address =  index2; //Se acota el fin del vector
	vector_elements    += elements; 
	offset             =  increment; //Reasigna el espacio sin usar
	return ret;
}

//añade un nuevo elemento con el valor avlue al final del vector. Si no hay elementos
//libres, es necesaria una reasignación de memoria. El método devuelve el iterador correspondiente al
//nuevo elemento insertado.

template<class TYPE, class ALLOCATOR>
typename mvector<TYPE, ALLOCATOR>::ITERATOR_TYPE 	mvector<TYPE, ALLOCATOR>::push_back(CONST_REF_ELEMENT value)
{
	if (!offset) expand(vector_end_address, 1); //Si no hay espacio, se reconstruye el vector
	else
	{
		++vector_end_address; //Si no, se aumenta el vector por que tiene espacio añadido (increment)
		--offset; //Se disminuye la capacidad del vector restante
		++vector_elements; //Se aumenta el vector de elementos
	}
	a.construct(vector_end_address-1, value); //Se construye el objeto
	return (vector_end_address-1); //Se retorna el iterador con su posición
}

//Añade un nuevo elemento al vector el valor val usando como punto de insercion el iterador i
//Que será a partir de ese puntero donde se inserten los nuevos elementos
//Si hay elementos libres, se produce un desplazamiento a la derecha, si no los hay, se produce una
//reasignación de memoria. El método devuelve el iterador correspondiente al elemento insertado
template<class TYPE, class ALLOCATOR>
typename mvector<TYPE, ALLOCATOR>::ITERATOR_TYPE 	mvector<TYPE, ALLOCATOR>::insert(ITERATOR_TYPE i, CONST_REF_ELEMENT value)
{
	PTR_ELEMENT ret; //Elemento que almacenará el puntero al nuevo elemento insertado

	if (!offset) ret = expand(i,1); //Si no hay espacio, se reconstruye el vector
	else
	{
		shift_right(1,i); //Se desplaza hacia la derecha el resto de antiguos elementos para albergar el nuevo
		++vector_end_address; //Se aumenta la capacidad del vector de elementos en una unidad
		ret = i; //Ret toma la dirección de memoria donde se ha de insertar el nuevo elemento.
	}
	a.construct(ret,value); //Se construye el objeto
	return ret;
}

template <class TYPE, class ALLOCATOR> 
typename mvector<TYPE, ALLOCATOR>::CONST_REF_ELEMENT 	mvector<TYPE, ALLOCATOR>::operator [](SIZE index) const
{
	if (index >= vector_elements) cout<<"Vector fuera de rango\n"; //throw VECTOR_OUT_OF_RANGE(vector_elements, index);
	return *(vector_address + index);
}

template <class TYPE, class ALLOCATOR> 
typename mvector<TYPE, ALLOCATOR>::REF_ELEMENT 		mvector<TYPE, ALLOCATOR>::operator [](SIZE index) 
{
	if (index >= vector_elements) cout<<"Vector fuera de rango \n"; //throw VECTOR_OUT_OF_RANGE(vector_elements, index);
	return *(vector_address+index);
}

//Eliminador de objetos del vector (entre dos iteradores)
template<class TYPE, class ALLOCATOR>
typename mvector<TYPE, ALLOCATOR>::ITERATOR_TYPE 	mvector<TYPE, ALLOCATOR>::erase(ITERATOR_TYPE i_begin, ITERATOR_TYPE i_end)
{
	ITERATOR_TYPE ret = i_begin;
	
	PTR_ELEMENT i = i_begin;
	
	DIFERENCE d;

	while (i != i_end)  
		a.destroy(i++);  //Se borran los que están dentro de los iteradores
		
	
	
	d = i_end - i_begin;	//se calcula la diferencia de los objetos a borrar
	
	while(i_end != vector_end_address) memcpy(i_begin++, i_end++, sizeof(ELEMENT) ); //Se reconstruye el vector
	
	vector_end_address -= d; 
	
	vector_elements -= d;
	
	offset += d; 

	return ret; //Se devuelve el comienzo del nuevo vector.
	
}

//Borra el vector en su totalidad
template <class TYPE, class ALLOCATOR>
void							mvector<TYPE, ALLOCATOR>::clear(void)
{
	erase(vector_address, vector_end_address);  //Destruye el rango desde comienzo al final del vector
}