#pragma once


#include <assert.h>
//#include <vector>
#include <algorithm>
#include <utility>
#include <functional>


template <class T, class pred = std::less<T> >
class KSortVector
{
public:
	void insert( const T& value )
	{
		std::vector<T>::iterator it = std::lower_bound( m_vector.begin(), m_vector.end(), value, pred() );
		m_vector.insert( it, value );
	}

	int	search_index( const T& value ) const
	{
		std::vector<T>::const_iterator it = std::lower_bound( m_vector.begin(), m_vector.end(), value, pred() );
		if ( it == m_vector.end() ) return -1;
		if ( pred()( value, *it ) ) return -1;
		int idx = int( it - m_vector.begin() );
		return idx;
	}

	std::pair<bool,T*> search_or_insert( const T& value )
	{
		std::vector<T>::iterator it = std::lower_bound( m_vector.begin(), m_vector.end(), value, pred() );
		bool bInserted = (it == m_vector.end()) ? true : pred()( value, *it );
		int index = it - m_vector.begin();
		if ( bInserted )
			m_vector.insert( it, value );
		return std::pair<bool,T*>( bInserted, &m_vector[ index ] ); 
	}

	typename std::vector<T>::const_iterator	begin()	const	{ return m_vector.begin(); }
	typename std::vector<T>::const_iterator	end()	const	{ return m_vector.end(); }
	typename std::vector<T>::iterator		begin()			{ return m_vector.begin(); }
	typename std::vector<T>::iterator		end()			{ return m_vector.end(); }

	typedef typename std::vector<T>::iterator iterator ;
	typedef typename std::vector<T>::const_iterator const_iterator ;
	
	void erase( int idx )					{ m_vector.erase( m_vector.begin() + idx ); }
	void erase( const T& value )
	{ 
		int idx = search_index( value );
		assert( idx != -1 );
		if ( idx == -1 ) return;
		m_vector.erase( m_vector.begin() + idx );
	}
	void clear()							{ m_vector.clear(); }

	bool has( const T& value ) const		{ return search_index( value ) != -1; }

	const T& at( int idx ) const			{ return m_vector[idx]; }
	const T& operator[] ( int idx ) const	{ return m_vector[idx]; }
	int size() const						{ return (int)m_vector.size(); }
	bool empty() const						{ return m_vector.empty(); }
	T& front()								{ return m_vector.front(); }

private:
	std::vector<T>	m_vector;
};