// pOCONTAINER - The Ordered Container
// version 0.1, 01-03-2008
//
// Copyright (C) 2008 by Bartosz Lenar
// bartosz@lenar.org	
// Licence: GNU LGPLv3
// 
// Some formal speech:
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License (version 3)
// as published by the Free Software Foundation.
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.


#ifndef POCONTAINER_H
#define POCONTAINER_H

#include <iostream>
#include <vector>

template <class TYPE>
class pOCONTAINER
{
public:
	// default constructor
	pOCONTAINER();
	
	// constructor which initiates container with a values in selected array
	pOCONTAINER(std::vector<TYPE> array);

	// clears the container
	void clear();
	
	// returns size of the container
	int size();

	// adds/removes object
	void addObject(TYPE object);
	void removeObject(TYPE object);

	// adds objects from selected array
	void addArray(std::vector<TYPE> &array);
	void addArray(pOCONTAINER<TYPE> &array);
	
	// copies container's objects to the selected array
	void getArray(std::vector<TYPE> &array);

	// functions return and instantly remove selected objects from the container
	TYPE getAndRemove(int order);	
	TYPE getFirstAndRemove();
	TYPE getLastAndRemove();
			
	// functions return informations about the order of selected object
	int findObjectsOrder(TYPE object);
	bool isObjectInside(TYPE object);

	// overloaded operator which gives oportunity to use the container as ordinary array
	TYPE& operator[](unsigned int iterator);
	
	// returns pointer to the object with selected order
	TYPE* getObject(int order);
	
	// after using functions operator[] or getObject, if you made changes that are crucial 
	// for the position of the object in array, run function reloadObject, which recounts the order
	// of object you modified
	void reloadObject(int order);
	
	// overloaded operators which can be used instead of addObject and addArray
	void operator+=(TYPE object);
	void operator+=(std::vector<TYPE> &array);
	
private:
	// base array
	std::vector<TYPE> array;
	
	// counts the order for the selected object
	int getRightPlace(TYPE object);
	
	// function dedicated for recursing
	int getRightPlace(TYPE &object, int start, int end, int& iterator);
	int findObjectsOrder(TYPE &object, int start, int end, int &iterator);
};

template <class TYPE>
pOCONTAINER<TYPE>::pOCONTAINER()
{
}

template <class TYPE>
pOCONTAINER<TYPE>::pOCONTAINER(std::vector<TYPE> array)
{
	this->addArray(array);
}

template <class TYPE>
void pOCONTAINER<TYPE>::clear()
{
	this->array.clear();
}

template <class TYPE>
int pOCONTAINER<TYPE>::size()
{
return ( this->array.size() );
}


template <class TYPE>
TYPE* pOCONTAINER<TYPE>::getObject(int order)
{
	return ( &this->array[order] );
}

template <class TYPE>
void pOCONTAINER<TYPE>::addObject(TYPE object)
{
	// if empty, just add the object
	if ( this->array.empty() )
	{
		this->array.push_back(object);
	}
	// if not, count the right order of the object and place it there
	else
	{
		this->array.insert(this->array.begin() + getRightPlace(object), object);
	}
}

template <class TYPE>
void pOCONTAINER<TYPE>::removeObject(TYPE object)
{
	if ( !this->array.empty() )
	{
		this->array.erase(this->array.begin() + findObjectsOrder(object));
	}
}

template <class TYPE>
void pOCONTAINER<TYPE>::addArray(std::vector<TYPE> &table)
{
	for( int i=0; i< table.size(); ++i )
	{
		this->addObject( table[i] );
	}
}


template <class TYPE>
void pOCONTAINER<TYPE>::addArray(pOCONTAINER<TYPE> &table)
{
	for( int i=0; i< table.size(); ++i )
	{
		this->addObject( table[i] );
	}
}

template <class TYPE>
void pOCONTAINER<TYPE>::getArray(std::vector<TYPE> &table)
{
	for( int i=0; i< this->array.size(); ++i)
	{
		table.push_back( this->array[i] );
	}
}

template <class TYPE>
TYPE pOCONTAINER<TYPE>::getAndRemove(int order)
{
	// first make a copy, then erase the object and return the copy
	TYPE result = this->array[order];
	this->array.erase( this->array.begin() + order);
	return ( result );
}

template <class TYPE>
TYPE pOCONTAINER<TYPE>::getFirstAndRemove()
{
	return ( this->getAndRemove(0) );
}


template <class TYPE>
TYPE pOCONTAINER<TYPE>::getLastAndRemove()
{
	return ( this->getAndRemove(this->array.size() - 1) );
}


template <class TYPE>
int pOCONTAINER<TYPE>::findObjectsOrder(TYPE object)
{
	// the error code is -1
	// return it when the array is empty...
	if ( this->array.size() == 0 )
	{
		return -1;
	}
	
	// ... if the first member of the array is greater than the selected object ...
	if ( this->array[0] > object )
	{
		return (-1);
	}
	
	// ... and if the last member of the array is smaller than the selected object.
	else if (object > this->array[ this->size() -1 ])
	{
		return (-1);
	}
	
	// check if first member is equal to the selected object...
	else if ( this->array[0] == object )
	{
		return 0;
	}
	
	// do the same with the last
	else if ( this->array[ this->size()-1 ] == object )
	{
		return (this->size()-1);
	}
	
	// in every else case start the recursive searching
	else 
	{
		int iterator;
		return ( this->findObjectsOrder(object,0,(this->size()-1),iterator));
	}
}

template <class TYPE>
bool pOCONTAINER<TYPE>::isObjectInside(TYPE object)
{
	return ( this->findObjectsOrder(object) != -1 );
}

template <class TYPE>
TYPE& pOCONTAINER<TYPE>::operator[](unsigned int iterator)
{
	return this->array[iterator];
}  

template <class TYPE>
void pOCONTAINER<TYPE>::reloadObject(int order)
{
	this->addObject( this->getAndRemove(order) );
}

template <class TYPE>
void pOCONTAINER<TYPE>::operator+=(TYPE object)
{
	this->addObject(object);
}

template <class TYPE>
void pOCONTAINER<TYPE>::operator+=(std::vector<TYPE> &array)
{
	this->addArray(array);
}

template <class TYPE>
int pOCONTAINER<TYPE>::findObjectsOrder(TYPE &object, int start, int end, int &iterator)
{

	// set iterator in the middle of searching area
	iterator = (start+end)/2;
	
	// check if the member in the middle is equal to the selected object
	if ( this->array[iterator] == object )
	{
		return iterator;
	}
	// if is it greater, then it should be the end of the next searching area
	else if ( this->array[iterator] > object )
	{
		end = iterator;
	}
	// if is it smaller, then it should be the beginning
	else if ( object > this->array[iterator] )
	{
		start = iterator;
	}		

	// check integrity
	if ( (end-start) == 1)
	{
		return (-1);
	}
		
	// search the next area using recursion
	return (this->findObjectsOrder(object, start, end, iterator));
	
}


template <class TYPE>
int pOCONTAINER<TYPE>::getRightPlace(TYPE object)
{
	
	// if the beginning of the array is equal or greater, then return the beginning as the right place of object
	if ( !(object > this->array[0]) )
	{
		return 0;
	}
	// check the last and the one before last cell
	else if ( (object > this->array[this->size()-1]) || (object == this->array[this->size()-1]))
	{
		return (this->size());
	}
	else if ( (object > this->array[this->size()-2]) || (object == this->array[this->size()-2]))
	{
		return (this->size()-1);
	}
	
	// in every else case, search using recursion
	else
	{
		int iterator;
		TYPE* candidate;
		TYPE tempObject = object;
		return ( getRightPlace(tempObject,0,(this->size()-1),iterator) );
	}
}


template <class TYPE>
int pOCONTAINER<TYPE>::getRightPlace(TYPE &object, int start, int end, int& iterator)
{
	iterator = (start+end)/2;
	
	if (this->array[iterator] == object)
	{
		return iterator;
	}
	else if (object > this->array[iterator] )
	{
		if ((this->array[iterator+1] > object) || (this->array[iterator+1] == object))
		{
			return (iterator+1);
		}
		else
		{
			start = iterator;
		}
	}
	else if (this->array[iterator] > object)
	{
		if (!(this->array[iterator+1] > object))
		{
			return (iterator);
		}
		else
		{
			end = iterator;
		}
	}
		
	return ( getRightPlace(object,start,end,iterator) );
}


#endif