Classic Algorithms Implemented by me in C/C++   Leave a comment

#ifndef __MARZAN_ALGORITHM_IMPL_h__
#define __MARZAN_ALGORITHM_IMPL_h__

#include <stack>

#include <iterator>
#include <memory>

#include <queue>

#include <cmath>

#include <xutility>

#include <tchar.h>

using namespace std;

namespace marzan{

#ifndef TCHAR
	#ifdef _UNICODE
		#define TCHAR wchar_t
	#else
		#define TCHAR char
	#endif
#endif

//[p, q)
/*
template
copy_if(_IT1& _F, _IT1& _L, _IT2& _U, _Pred _pred)
{
    while(_F!=_L){
        if(_pred(*_F)) 
              *_U++ = *_F;		 
		_F++;
    }
}

template
copy_ex(_IT1 _F, _IT1 _L, _IT2 _U){while(_F!=_L) *_U++ = *_F++;}
*/

//************************
template
class bidir_iterator : public iterator<bidirectional_iterator_tag, typename _IT::char_type>
{
	bidir_iterator(_IT &it, const typename _IT::char_type& _V) : 
			pit(&it), oty(_V),
			_Got(false),//last char in stack
			_Eof(false),
			_Bof(false){}
public:
	bidir_iterator(_IT &it)	: 
			pit(&it), oty(*it),
			_Got(false),//last char in stack
			_Eof(false),
			_Bof(false){}

	bidir_iterator() : 
			pit(0), oty(_IT::char_type()),
			_Got(true),//last char in stack 
			_Eof(false),
			_Bof(false){}

	bool operator==(const _IT& oit)
	{
		_IT& it = *pit;
		return (it==oit);
	}
	bool operator!=(const _IT& oit)
	{
		return !(*this==oit);
	}

	bool operator==(const bidir_iterator<_IT>& oit){
		return (_Got && oit._Got) || (_Got==oit._Got && pit==oit.pit);
	}
	bool operator!=(const bidir_iterator<_IT>& oit){
		return !(*this==oit);
	}

	void _Inc()
	{
		_forward.push(oty);
		_IT& it = *pit;
		oty = *++it;		
		_Eof = (it==_IT());
	}

	void _Dec()
	{
		oty = _forward.top();
		_forward.pop();
	}

	bidir_iterator<_IT>& operator++(){
		if(_backwrd.empty())
			_Inc();
		else{
			oty = _backwrd.top();
			_backwrd.pop();		
			_forward.push(oty);
		}		
		return *this;
	}
	bidir_iterator<_IT> operator++(int){//postfix						
		_IT& it = *pit;
		bidir_iterator<_IT> tmp(it, oty);
		if(_backwrd.empty())
			_Inc();			
		else{
			oty = _backwrd.top();
			_backwrd.pop();		
			_forward.push(oty);			
		}
		return tmp;
	}
	bidir_iterator<_IT>& operator--(){
		if(!_Bof && _forward.empty())
			throw logic_error("pointer was not advanced correctly before using this operator.");
		if(_Eof){
			_Dec();
			_Eof = false;
		}
		if(!_Bof){
			_Dec();
			_Bof = _forward.empty();
		}
		else{
			_Got = _Bof;
			_Bof = false;			
		}
		return *this;
	}
	bidir_iterator<_IT> operator--(int){//postfix		
		if(!_Bof && _forward.empty())
			throw logic_error("pointer was not advanced correctly before using this operator.");

		if(_Eof){
			_Dec();
			_Eof = false;
		}
		if(!_Bof)
			_backwrd.push(oty);
		bidir_iterator<_IT> tmp(*pit, oty);
		if(!_Bof){
			_Dec();
			_Bof = _forward.empty();
		}
		else{
			_Got = _Bof;
			_Bof = false;			
		}
		return tmp;
	}

	typename _IT::char_type operator*()
		{return oty;}
	typename _IT::char_type operator*() const
		{return oty;}
	typename _IT::char_type* operator->()
		{return &**this;}
private:
	typename _IT::char_type oty;
	_IT* pit;
	bool _Got;	
	bool _Eof;
	bool _Bof;

	stack _backwrd;
	stack _forward;
};
//************************

template
_C iter_cat(const iterator<_C, _Ty, _D>& it)
{
	return _C();
}

template
random_access_iterator_tag iter_cat(const T* p)
{
	return random_access_iterator_tag();
}

template
void iter_swap_ex(_IT1 _X, _IT2 _Y, _Ty *)
{
	_Ty tmp = *_X;
	*_X = *_Y, *_Y = tmp;
}

template
_Ty* Val_type(const _Ty*){
	return ((_Ty*)(0));
}

template
void _iter_swap(_IT1 _X, _IT2 _Y)
{
	iter_swap_ex(_X, _Y, Val_type(_X));
}

template
void reverse_ex(_BIT _F, _BIT _L)
{
	Reverse(_F, _L, iter_cat(_F));
}

//  1 2 3 4 5 6 (eos)

template
void Reverse(_BIT _F, _BIT _L, bidirectional_iterator_tag){
	for(; _F!=_L && _F!= --L; ++_F)
		_iter_swap(_F, _L);
} 

template
void Reverse(_RAI _F, _RAI _L, random_access_iterator_tag){
	for(; _F < _L; _F++)
		_iter_swap(_F, --_L);
}

typedef unsigned int __uint;
typedef unsigned __int64 __uint64;

template
_Ty geometric_summ_horner(_Ty x, __uint n){
	_Ty result = 0;
	for(__uint ix=0;ix < n;++ix)
		result = result * x + 1;
	return result;
}

template
_Ty geometric_summ_horner(_Ty cx[], _Ty x, __uint n){
	_Ty result = 0;
	for(__uint ix=0;ix < n;++ix){
		result = result * x + cx[ix];
	}
	return result;
}

template
_Ty power(_Ty x, __uint n){ //O(log n)
	if(n==0)
		return 1;
	else if(n%2==0)
		return power(x * x, n / 2);
	else
		return x * power(x * x, n / 2);
}

template
_Ty power2(_Ty x, __uint n){ //O(n)
	if(n==0)
		return 1;
	else if(n==1)
		return x;
	_Ty result = 1;
	while(n > 0){
		if(n%2==0){
			//2^8 = (2 * 2) * (2 * 2) * (2 * 2) * (2 * 2)
			result *= (x * x);
			n-= 2;
		}else{
			//2^7 = (2 * 2 * 2) * (2 * 2) * (2 * 2)
			result *= (x * x * x);
			n-= 3;
		}
	}
	return result;
}

template
_Ty geometric_summ_q(_Ty x, unsigned int n){
	return ((power(x, n + 1) - 1) / (x - 1));
}

template
_Ty geometric_summ_horner(_Ty cx[], unsigned int k, unsigned int n){
	_Ty result = 0;
	for(unsigned int ix=0;ix < n;++ix){
		result += cx[ix] * (power(2.0, k * ix));		
	}
	return result;
}

template
_RIT binary_search(_RIT _F, _RIT _L, const _Ty _X)
{
	__uint _Len = (_L - _F);
	int _LF = 0,
		_RT = _Len - 1;

	while(!(_RT < _LF)){//_LF <=_RT
		int _MID = (_LF + _RT) / 2;
		if(*(_F + _MID) < _X)
			_LF = _MID + 1;
		else if(_X < *(_F + _MID))
			_RT = _MID - 1;
		else
			return (_F + _MID);
	}

	return _L;
}

//is a similar to a natural human lookup of the requested key _X or word in a diccionary
//Gonnet, Rogers, and George.
template
_RIT interpolation_binary_search(_RIT _F, _RIT _L, const _Ty _X) //Theta(log(log n))
{
	__uint _Len = (_L - _F);
	int _LF = 0,
		_RT = _Len - 1;

	while(!(_RT < _LF)){//_LF <=_RT
		int _MID = (_LF + _RT) / 2;
		if(*(_F + _MID) < _X)
		{
			if((*_F + _RT)==_X)
				return (_F + _RT);

			_LF = _MID + 1;
			if(*(_F + _LF) == _X)
				return (_F + _LF);	
		}
		else if(_X < *(_F + _MID))
		{
			if((*_F + _LF)==_X)
				return (_F + _LF);

			_RT = _MID - 1;
			if(*(_F + _RT) == _X)
				return (_F + _RT);				
		}
		else
			return (_F + _MID);
	}

	return _L;
}

template
bool is_palindrome(_IT _F, _IT _L)
{
	volatile bool bVal = false;
	__uint _len = _L-_F;
	TCHAR* _O = new TCHAR[_len+1], *_P = _O;
	_len = 0;
	while(_F!=_L)
	{
		if(_istalpha(*_F)){
			if(_istupper(*_F))
				*_O++ = _tolower(*_F);
			else
				*_O++ = *_F;
			_len++;
		}
		_F++;
	}
	_O = _P;
	*(_O+_len) = _T('');	
	TCHAR *_FC = _O,
		  *_LC = _O + (_len - 1);
	while(*_FC==*_LC)
	{
		if(_FC>=_LC){
			bVal = true;
			break;
		}
		++_FC;--_LC;
	}

	delete []_O;
	return bVal;
}

inline bool is_palindrome(const TCHAR* phrase_word, const __uint _len)
{
	return is_palindrome(phrase_word, phrase_word+_len);
}

inline bool is_palindrome(const TCHAR* phrase_word)
{
	return is_palindrome(phrase_word, phrase_word+_tcslen(phrase_word));
}

inline bool is_palindrome(const basic_string& phrase_word)
{
	return is_palindrome(phrase_word.begin(), phrase_word.end());
}

__int64 Fibonacci(__uint n) //TOP-DOWN (DIV-&-CQR)
{
	if(n==0 || n==1)
		return n;
	else{
		__int64 a = Fibonacci((n + 1) / 2);
		__int64 b = Fibonacci(((n + 1) / 2) - 1);

		if(n%2==0)
			return a * (a + 2 * b); //to avoid a a third mult. a * a + (2 * a * b)
		else
			return a * a + b * b;

	}
}

//H A S H E S   &   H A S H   F U N C T I O N S 

typedef unsigned int hash_value;
typedef unsigned __int64 hash_value64;

//D I V I S I O N
inline hash_value hash_uint(__uint _X, __uint _M){return _X % _M;}
inline hash_value hash_uint(__uint _X){return hash_uint(_X, ~0U);}

//M U L T I P L I C A T I O N
inline hash_value hash_mult(__uint _X, __uint a, __uint w, __uint k){return a *_X >> (w - k);}

//M I D D L E   S Q U A R E 
inline hash_value hash_msqr(__uint _X, __uint w, __uint k){ return hash_mult(_X, _X, w, k);}

inline hash_value hash_fib(__uint _X, __uint w, __uint k){
	__uint a = (__uint)power(2, w) * (sqrt((float)5)-1) / 2;	
	return hash_mult(_X, a, w, k);
}

inline hash_value hash_fib2(__uint _X, __uint w, __uint k){
	__uint a = (__uint )(~0U) * (sqrt((float)5)-1) / 2;
	return hash_mult(_X, a, w, k);
}

inline hash_value hash_fib(__uint _X, __uint W, __uint w, __uint k){
	__uint a = (__uint )W * (sqrt((float)5)-1) / 2;
	return hash_mult(_X, a, w, k);
}

#ifndef TCHAR
	inline hash_value hash_char(char c){return abs(c);}
	inline hash_value hash_char(wchar_t wc){return abs(wc);}
#else
	inline hash_value hash_char(TCHAR tc){return abs(tc);}
#endif

hash_value hash_int(int _K);
hash_value64 hash_int64W(__int64 _K);
hash_value64 hash_int64W2(__int64 _K);

inline hash_value hash_double(double _X, __uint _W)
{
	if(_X==0)
		return 0;
	int exp = 0;
	double m = frexp(_X, &exp);
	return static_cast<hash_value>((2 * fabs(m) - 1) * _W);
}

inline hash_value hash_double(double _X)
{
	return hash_double(_X, ~0U);
}

template
hash_value hash_string_horner(_IT _F, _IT _L, __uint _B)
{
	hash_value result = 0;
	while(_F!=_L){
		result = result * _B + *_F; //using horner's rule
		_F++;
	}
	return result;
}

template
hash_value hash_string_fast(_IT _F, _IT _L, __uint _b)
{
	hash_value result = 0;
	while(_F!=_L){					 //using horner's rule and	
		result = result << _b ^ *_F; //using left shift multiplication and xoring in place of addition
		_F++;
	}
	return result;
}

template
hash_value hash_string(_IT _F, _IT _L, __uint _b)
{
	hash_value mask = (~0U) << ((sizeof(__uint) * 8) - _b);
	hash_value result = 0;
	while(_F!=_L){					//using horner's rule and xoring with the possibly lost _b bits out
		result = (result & mask) ^ (result << _b) ^ *_F;
		_F++;
	}
	return result;
}

template
hash_value hash_container(const _Cy& _C)
{
	typedef typename _Cy::iterator it = _C.begin();
	hash_value result = 0;
	while(it!=_C.end())
		result += hash(*it++);
	return result;
}

inline __uint hgof(hash_value _hsh, const __uint& _M = ~0U){return _hsh % _M;}

// H A S H   D E F A U L T   T E M P L A T E   F U N C T I O N
template
inline hash_value hash(const _Ty& _V){
	return hash_fib(reinterpret_cast<__uint>(_V), ~0U, 32, 13);
}

// H A S H   S P E C I A L I Z A T I O N S 
template<>
inline hash_value hash(const int& _X){return hash_int(_X);}
template<>
inline hash_value hash(const __int64& _X){return hash_int64W(_X);}

template<>
inline hash_value hash(const __uint& _X){return hash_uint(_X);}

#ifndef TCHAR
	template<>
	inline hash_value hash(const char& _C){return hash_char(_C);}
	template<>
	inline hash_value hash(const wchar_t& _C){return hash_char(_C);}

	template<>
	inline hash_value hash(const basic_string& str){return hash_string(str.begin(), str.end(), sizeof(char) * 8);}
	template<>
	inline hash_value hash(const basic_string<wchar_t>& str){return hash_string(str.begin(), str.end(), sizeof(wchar_t) * 8);}
#else
	template<>
	inline hash_value hash(const TCHAR& _C){return hash_char(_C);}

	template<>
	inline hash_value hash(const basic_string& str){return hash_string(str.begin(), str.end(), sizeof(TCHAR) * 8);}
#endif

template<>
inline hash_value hash(const double& _X){return hash_double(_X);}

#ifndef TCHAR
	inline hash_value hash(const char* _S){return hash_string(_S, _S + strlen(_S), sizeof(char) * 8);}
	inline hash_value hash(const wchar_t* _S){return hash_string(_S, _S + wcslen(_S), sizeof(wchar_t) * 8);}
#else
	inline hash_value hash(const TCHAR* _S){return hash_string(_S, _S + _tcslen(_S), sizeof(TCHAR) * 8);}
#endif

//O P E N   S C A T T E R   T A B L E   A L G O R I T H M S 

// L I N E A R
template //c(i) = ai + b : for any M, a must be zero. _Iy can be just i or ai + b.
class linear_probing_hash
{
public:
	static __uint hash(const _Ty& _X, const __uint& _Iy, const __uint _M){
		//cout << (hgof(marzan::hash(_X), _M) + _Iy) << endl;
		return (hgof(marzan::hash(_X), _M) + _Iy) % _M;
	}
	linear_probing_hash(){}
	~linear_probing_hash(){}
	inline __uint operator()(const _Ty& _X, const __uint& _Iy, const __uint _M){
		return linear_probing_hash<_Ty>::hash(_X, _Iy, _M);
	}
};

// Q U A D R A T I C   P R O B I N G
template //c(i) = a(i^2) + b(i) + y : c(i) can be i^2 for any M.
class quad_probing_hash
{
public:
	static __uint hash(const _Ty& _X, const __uint& _Iy, const __uint _M){
		//cout << (hgof(marzan::hash(_X), _M) + (_Iy * _Iy)) << endl;
		return (hgof(marzan::hash(_X), _M) + (_Iy * _Iy)) % _M;
	}
	quad_probing_hash(){}
	~quad_probing_hash(){}
	inline __uint operator()(const _Ty& _X, const __uint& _Iy, const __uint _M){
		return quad_probing_hash<_Ty>::hash(_X, _Iy, _M);
	}
};

// D O U B L E   H A S H I N G 
// Hi(_X) = (H(_X) + i * H'(_X)) mod M
// The collision resolution function is c(i) = i* H'(_X)
//H'(_X)  can take any values between 1 and M - 1 and
//M must be a prime number; and
//H'(_X) and M, satisfies Prop 2 when they are relatively primes.

//H(_X) = g o f --> g(_X) = _X mod M.
//then,
//H'(_X) = g' o f --> g'(_X) = 1 + (_X mod (M - 1)).
//Double hashing becomes a linear search when H'(_X) == 1. 
//So, it results in Hi(_X) = (H(_X) + i) mod M, with probability of Pi = 1/(M - 1).

template 
class double_hash
{
public:
	static __uint hash(const _Ty& _X, const __uint& _Iy, const __uint _M){
		//cout << (hgof(marzan::hash(_X), _M) + _Iy * (1 + hgof(marzan::hash(_X), _M - 1))) << endl;

		return (hgof(marzan::hash(_X), _M) + _Iy * (1 + hgof(marzan::hash(_X), _M - 1))) % _M; //g'(_X) = 1 + (x mod (M - 1)).
	}
	double_hash(){}
	~double_hash(){}
	inline __uint operator()(const _Ty& _X, const __uint& _Iy, const __uint _M){
		return double_hash<_Ty>::hash(_X, _Iy, _M);
	}
};

// I N T E G E R   H A S H   F U N C T I O N S 
//R O B E R T   J E N K I N S   M I X   A L G O R I T H M 
//
int hash_int(int aRN, int bRN, int cK)
{
	int a = aRN,
		b = bRN,
		c = cK;

	//61 right shifted
	//34 left shifted
	//======
	//95 bits in total
	a=a-b; a=a-c; a=a^(c>>13);
	b=b-c; b=b-a; b=b^(a<<8); 	c=c-a; c=c-b; c=c^(b>>13);

	a=a-b; a=a-c; a=a^(c>>12);
	b=b-c; b=b-a; b=b^(a<<16); 	c=c-a; c=c-b; c=c^(b>>5);

	a=a-b; a=a-c; a=a^(c>>3);
	b=b-c; b=b-a; b=b^(a<<10); 	c=c-a; c=c-b; c=c^(b>>15);

	return c;
}

//R O B E R T   J E N K I N S  32 bit  M I X   A L G O R I T H M 
inline hash_value hash_int(int _K)
{
	_K += (_K << 12); 	_K ^= (_K >> 22);
	_K += (_K << 4); 	_K ^= (_K >> 9);
	_K += (_K << 10); 	_K ^= (_K >> 2);
	_K += (_K << 7); 	_K ^= (_K >> 12);

	return abs(_K);
}

//T H O M A S   W A N G  32 bit M I X   A L G O R I T H M 
/*
NOTE: Using substitution box in every function

  For better hash, must use power of 2 for the hash table size; ie.: 2**20 v 2**32.

  For 32bit word operations, O N L Y   C E R T A I N  pairs of shift amounts 
  W I L L   B E   R E V E R S I B L E. the valid pairs include:

 [
     (17, 16), (16, 17), (14, 19), (19, 14), (13, 20), (20, 13), (10, 23), (23, 10), (8, 25), (25, 8)
 ]
*/

hash_value hash_int32tw(int _K)
{
	_K += ~(_K << 15); 	_K ^=  (_K >> 10);	//>>>

	_K +=  (_K << 3); 	_K ^=  (_K >> 6);	//>>>

	_K += ~(_K << 11); 	_K ^=  (_K >> 16);	//>>>

	return abs(_K);
}

//T H O M A S   W A N G  64 bit M I X   A L G O R I T H M 
hash_value64 hash_int64W(__int64 _K)
{
	_K += ~(_K << 32); 	_K ^=  (_K >> 22);	//>>>
	_K += ~(_K << 13); 	_K ^=  (_K >> 8);	//>>>
	_K +=  (_K << 3); 	_K ^=  (_K >> 15);	//>>>
	_K += ~(_K << 27); 	_K ^=  (_K >> 31);	//>>>

	return _K;
}

hash_value64 hash_int64W2(__int64 _K)
{
	__int64 c1 = 0x6e5ea73858134343L;
	__int64 c2 = 0xb34e8f99a2ec9ef5L;

	_K ^= ((c1 ^ _K) >> 32); //>>>
	_K *= c1;
	_K ^= ((c2 ^ _K) >> 31); //>>>
	_K *= c2;
	_K ^= ((c1 ^ _K) >> 32); //>>>

	return _K;
}

//Hash function used in the Portable C Compiler from P.J. Weinberger
//To test the uniform distribution, it should use this formula:
	//Sum(j=0,m-1) of [ b_j * (b_j + 1) / 2 ]
	//to randomly distribute strings it has : (n / 2m)(n + 2m - 1)
//From the book: Compilers: Principles, Techniques  & Tools (Aho, Sethi & Ullman)
template
hash_value hash_pjw(_IT _F, _IT _L, int _M = (~0U) - 1) //default is 2^32 - 1
{
	hash_value _hash = 0, g;
	//
	while(_F!=_L)
	{
		_hash = (_hash << 4) + *_F; // _hash * power(2, 4) + *_F 		if((g = _hash & 0xF0000000)){ 			_hash ^= (g >> 24);
			_hash ^= (g);
		}
		_F++;
	}
	//
	return hgof(_hash, _M);
}

template >
    class array
{
	//typedef _Ty value_type;
	typedef typename _Ay allocator_type;
	typedef typename allocator<_Ty>::pointer pointer;
	typedef typename allocator<_Ty>::const_pointer const_pointer;

	typedef typename allocator<_Ty>::reference reference;
	typedef typename allocator<_Ty>::const_reference const_reference;

	typedef typename allocator<_Ty>::value_type value_type;	
	typedef typename allocator<_Ty>::size_type size_type;
protected:
	_Ay _alloc;
	pointer data;
	unsigned int _base;
	size_type length;
public:
	size_type size() const{
		return length;
	}
	unsigned int base() const{
		return _base;
	}
	const_pointer ptr()const{
		return data;
	}
	array() : _base(0), length(0){
		data = _alloc.allocate(0, 0);
	}
	~array(){
		_alloc.deallocate(data, length);
	}
	array(size_type _N, unsigned int _By = 0) : length(_N), _base(_By){
		data = _alloc.allocate(_N, 0);
	}

	array(const array& _a){
		_base = _a._base;
		length = _a.length;
		data = _alloc.allocate(_a.length, 0);
		for(unsigned int x=0;x<length; x++)
			_alloc.construct(&data[x], _a.data[x]);
	}

	array& operator=(const array& _a){
		if(this!=&_a){
			_alloc.deallocate(data, length);
			_base = _a._base;
			length = _a.length;
			data = _alloc.allocate(_a.length, 0);
			for(unsigned int x=0;x<length; x++)
				_alloc.construct(&data[x], _a.data[x]);
		}
		return *this;
	}

	void set_base(unsigned int _By){
		_base = _By;
	}

	allocator_type& get_allocator(){
		return _alloc;
	}

	bool resize(size_type _N){
		pointer _new_data = _alloc.allocate(_N, 0);
		if(_new_data==0)
			return false;
		size_type _Nsz = min(length, _N);
		//copy at least the min...
		for(unsigned int ix=0;ix< _Nsz; ix++) 			_alloc.construct(&_new_data[ix], data[ix]); 		 		_alloc.deallocate(data, length); 		length = _Nsz; 		//point to new storage... 		data = _new_data; 		return true; 	} 	bool remove(const value_type& _Vy) 	{ 		if(length > 0){
			__uint index = 0;
			while(index < length){
				if(data[index] == _Vy){
					_alloc.destroy(&data[index]);
					while(index < length)
					{						
						data[index] = data[index + 1];
						index++;
					}
					return true;
				}
				index++;
			}
		}
		return false;
	}
	void remove_all_of(const value_type& _Vy) //O(n)
	{
		pointer _new_stg = _alloc.allocate(length, 0); //O(1)
		if(_new_stg){
			unsigned int i = 0, x = 0;
			while(i < length) //O(n)
			{
				//if(!(data[i]==_Vy))
				if(data[i] < _Vy || _Vy < data[i])
				{
					_alloc.construct(&_new_stg[x], data[i]); //O(1)
					x++;
				}
				_alloc.destroy(&data[i]);
				i++;
			}
			//dealloc and assign new address...
			_alloc.deallocate(data); //O(1)
			data = _new_stg;
		}
	}

	__uint linear_find_offset_of(const _Ty& _X)//O(n)
	{		
		__uint index = 0;
		while(index < length)
		{
			if(data[index]==_X)
				return index;
			index++;
		}
		return length;//not found!
	}

	__uint binary_search_offset_of(const _Ty& _X)//O(log n)
	{
		int _Left = 0,
			_Right = length - 1;

		while(!(_Right < _Left)) //Left <= _Right
		{
			int _Mid = (_Left + _Right) / 2;
			if(data[_Mid] < _X)
				_Left = _Mid + 1;
			else if(_X < data[_Mid]) 				_Right = _Mid - 1; 			else 				return _Mid;//offset found! 		} 		return length;//not found! 	} 	const_reference operator[](unsigned int _Py) const{ 		unsigned int offset = _Py-_base; 		if(offset>=length)
			throw out_of_range("subscript is out of range!");
		return data[offset];
	}
	reference operator[](unsigned int _Py){
		unsigned int offset = _Py-_base;
		if(offset>=length)
			throw out_of_range("subscript is out of range!");
		return data[offset];
	}
};

template
__uint binary_search(const _Ar& the_array, const _Ty& _X, __uint _F, __uint _L)
{
	if(_F > 0 && _L==0)
		throw invalid_argument("invalid argument value for _L.");		
	else if(_L==1 || (_L - _F)==1) //to avoid infinite loops for (_F==_L==1) running in O(1)
	{
		if(the_array[_F]== _X)
			return _F;
		else if(the_array[_L]== _X)
			return _L;
		else
			return the_array.size();//fail
	}else{
		__uint _MID = (_F + _L) / 2;
		if(the_array[_MID] < _X)
			return binary_search(the_array, _X, _MID + 1, _L);
		else if(_X < the_array[_MID])		
			return binary_search(the_array, _X, _F, _MID - 1);
		else
			return _MID;
	}
}

__uint Fibonacci(__uint n, __uint k) //BOTTOM-UP (DYN-PRGN)
{
	if(n < k - 1U && n >=0)
		return 0;
	else if(n==(k - 1U))
		return 1;
	else{
		array<__uint> Fib(n + 1);
		//Init array...
		for(__uint i=0; i< k - 1U; ++i)		
			Fib[i] = 0;

		//First Partial Solution...
		Fib[k - 1U] = 1; //S_i
		for(i = k; i <= n; i++)
		{
			__uint summ = 0;
			for(__uint j = 1; j <= k; ++i) 
			{
				summ += Fib[i - j]; //This computes S_i+1 from S_i...
			}
			Fib[i] = summ;
		}
		return Fib[n];
	}
}

__int64 FibonacciH(unsigned int n) //My own implementation for the Fibonacci Sequence Generator in O(n) time.
{
	if(n==0)
		return 0;
	if(n==1)
		return 1;

	__int64 *arFib = new __int64[n + 1];

	//the first partial solution
	arFib[0] = 0;
	arFib[1] = 1;

	__int64 result = 0;
	for(unsigned int i=2;i<=n; i++)
	{
		//this establishes that the next Fibonacci number is given by the sum of the previous ones:
		// Fib(n) = Fib(n-1) + Fib(n-2);

		arFib[i] = arFib[i-1] + arFib[i-2];
	}
	result = arFib[n];

	delete []arFib;

	return result;
}

__int64 FibonacciH2(unsigned int n) //My own implementation for the Fibonacci Sequence Generator in O(n) time.
{
	if(n==0)
		return 0;
	if(n==1)
		return 1;

	array<__int64> arFib(n + 1);

	//the first partial solution
	arFib[0] = 0;
	arFib[1] = 1;

	for(unsigned int i=2;i<=n; i++)
	{
		//this establishes that the next Fibonacci number is given by the sum of the previous ones:
		// Fib(n) = Fib(n-1) + Fib(n-2);

		arFib[i] = arFib[i-1] + arFib[i-2];
	}	
	return arFib[n];
}

// B I N O M I A L   C O E F F I C I E N T S 
__uint Binom(__uint n, __uint m)
{
	if(m==0)
		return 1;
	if(n==m)
		return 1;
	array<__uint> b(n + 1);
	b[0] = 1;
	for(__uint i=1; i<=n; ++i) 	{ 		b[i] = 1; 		for(__uint j = i - 1U; j > 0; j--)
			b[j] += b[j - 1U];
	}
	return b[m];
}

//two-dimensional array

template >
    class array_2d
{
	_Ay _alloc;
	array<_Ty, _Ay> _array; //TODO : this type class will be substituted by the range_array
public:
	typedef typename allocator<_Ty>::pointer pointer;
	typedef typename allocator<_Ty>::const_pointer const_pointer;

	typedef typename allocator<_Ty>::reference reference;
	typedef typename allocator<_Ty>::const_reference const_reference;

	typedef typename allocator<_Ty>::value_type value_type;	
	typedef typename allocator<_Ty>::size_type size_type;

	typedef unsigned int uint_type;	

	typedef uint_type rowid_type;
	typedef uint_type colid_type;
protected:
	rowid_type number_of_rows;
	colid_type number_of_columns;
public:
	class row
	{
		array_2d<_Ty, _Ay>* pa2d;		
		rowid_type rowid;
	public:
		row(array_2d<_Ty, _Ay>& a2d, const rowid_type& _rowid) : pa2d(&a2d), rowid(_rowid) {}

		reference operator[](const colid_type& columnid){
			return pa2d->select(rowid, columnid);
		}
	};
public:
	array_2d(uint_type m = 1, uint_type n = 1) :_array(m * n), 
										number_of_rows(m), 
										number_of_columns(n) {
		for(uint_type x=0;x<_array.size();x++) 			_array[x] = _Ty(); 	} 	row operator[](const rowid_type rowid){ 		return row(*this, rowid); 	} 	reference select(rowid_type i, colid_type j) 	{ 		if(i >=number_of_rows)
			throw out_of_range("invalid row!");
		if(j >=number_of_columns)
			throw out_of_range("invalid column");
		return _array[i * number_of_columns + j];
	}

};//array_2d[i][j];

//matrix implementation : is an array_2d with matrix operations...
template >
    class matrix : public array_2d<_Ty, _Ay>
{
public:
	typedef typename allocator<_Ty>::pointer pointer;
	typedef typename allocator<_Ty>::const_pointer const_pointer;

	typedef typename allocator<_Ty>::reference reference;
	typedef typename allocator<_Ty>::const_reference const_reference;

	typedef typename allocator<_Ty>::value_type value_type;	
	typedef typename allocator<_Ty>::size_type size_type;

	typedef unsigned int uint_type;	

	typedef uint_type rowid_type;
	typedef uint_type colid_type;
public:
	uint_type rows_count() const{
		return number_of_rows;
	}
	uint_type columns_count() const{
		return number_of_columns;
	}
	matrix(rowid_type m, colid_type n) : array_2d<_Ty, _Ay>(m, n){}

	matrix(matrix<_Ty, _Ay>& rvm) : array_2d<_Ty, _Ay>(rvm.number_of_rows, rvm.number_of_columns)
	{
		for(uint_type i=0;i<number_of_rows;i++)
			for(uint_type j=0;j<number_of_columns;j++)
				(*this)[i][j] = rvm[i][j];
	}

	matrix<_Ty, _Ay>& operator=( matrix<_Ty, _Ay>& rvm)
	{
		if(number_of_rows!=rvm.number_of_rows)
			throw invalid_argument("rows between matrices A and B, differs!.incompatible matrices.");
		if(number_of_columns!=rvm.number_of_columns)
			throw invalid_argument("columns between matrices A and B, differs!.incompatible matrices.");
		if(this!=&rvm)
		{
			for(uint_type i=0;i<number_of_rows;i++)
				for(uint_type j=0;j<number_of_columns;j++)
					(*this)[i][j] = rvm[i][j];
		}
		return *this;
	}

	//matrix multiplication...
	matrix<_Ty, _Ay> operator*(matrix<_Ty, _Ay>& rvm){
		//A = m * n;
		//B = n * p;
		//C = AB = m * p  A_n==B_n
		if(number_of_columns!=rvm.number_of_rows)
			throw invalid_argument("incompatibles matrices!");

		matrix<_Ty, _Ay> result(number_of_rows, rvm.number_of_columns); // m * p
		for(uint_type i=0;i<number_of_rows;i++)
		{
			for(uint_type j=0;j<rvm.number_of_columns;j++)
			{
				//(number_of_columns==rvm.number_of_rows)
				value_type c_ij = value_type();
				for(uint_type k=0;k<number_of_columns;k++)
					c_ij += ((*this)[i][k] * rvm[k][j]);
				//assign to C[i][j]...
				result[i][j] = c_ij;

			}
		}

		return result;
	}
	matrix<_Ty, _Ay> operator+(matrix& rvm){
		if(number_of_rows!=rvm.number_of_rows)
			throw invalid_argument("rows between matrices A and B, differs!.incompatible matrices.");
		if(number_of_columns!=rvm.number_of_columns)
			throw invalid_argument("columns between matrices A and B, differs!.incompatible matrices.");

		matrix<_Ty, _Ay> m_c(number_of_rows, rvm.number_of_columns);
		for(uint_type i=0;i<number_of_rows;i++)
			for(uint_type j=0;j<rvm.number_of_columns;j++)
				m_c[i][j] = (*this)[i][j] + rvm[i][j];

		return m_c;
	}

	matrix<_Ty, _Ay> operator^(__uint n)
	{
		matrix<_Ty, _Ay>& X = *this;
		if(n > 1)
		{
			matrix<_Ty, _Ay> R = *this;
			for(__uint exp=1;exp< n;exp++)
				R = R * X;
			return R;

		}
		return X;
	}

	//vector multiplication...
	vector<_Ty> operator*(const vector<_Ty>& v)
	{
		matrix<_Ty, _Ay>& X = *this;
		if(v.size() != X.columns_count())
			throw invalid_argument("matrix and vector must have the same number of columns to be multiplied.");

		vector<_Ty> vr(v.size());
		for(__uint i=0; i<X.rows_count();i++)
			for(__uint j=0;j<v.size();j++)
			{
				vr[j] += v[j] * X[i][j];
			}
		return vr;
	}
	//scalar multiplication...
	matrix<_Ty, _Ay> operator*(const _Ty& v)
	{
		matrix<_Ty, _Ay>& X = *this;

		for(__uint i=0; i<X.rows_count();i++)
			for(__uint j=0;j<X.columns_count();j++)
			{
				X[i][j] = (X[i][j] * v);
			}
		return X;
	}
};

template<>
matrix power(matrix X, __uint n){
	if(n > 1)
	{
		matrix R = X;
		for(__uint exp=1;exp< n;exp++)
			R = R * X;
		return R;
	}
	return X;
}

template<>
matrix power(matrix X, __uint n){
	if(n > 1)
	{
		matrix R = X;
		for(__uint exp=1;exp< n;exp++)
			R = R * X;
		return R;
	}
	return X;
}

template<>
matrix power(matrix X, __uint n){
	if(n > 1)
	{
		matrix R = X;
		for(__uint exp=1;exp< n;exp++)
			R = R * X;
		return R;
	}
	return X;
}

template<>
matrix<__int64> power(matrix<__int64> X, __uint n){
	if(n > 1)
	{
		matrix<__int64> R = X;
		for(__uint exp=1;exp< n;exp++)
			R = R * X;
		return R;
	}
	return X;
}

template
vector<_Ty> operator*(const vector<_Ty>& v, matrix<_Ty>& X)
{
	if(v.size() != X.columns_count())
		throw invalid_argument("matrix and vector must have the same number of columns to be multiplied.");

	vector<_Ty> vr(v.size());
	for(__uint i=0; i<X.rows_count();i++)
		for(__uint j=0;j<v.size();j++)
		{
			vr[j] += v[j] * X[i][j];
		}
	return vr;
}

//scalar multiplication...
template
matrix<_Ty> operator*(const _Ty& v, matrix<_Ty>& _M)
{
	matrix<_Ty> _X = _M;
	for(__uint i=0; i<_X.rows_count();i++)
		for(__uint j=0;j<_X.columns_count();j++)
		{
			_X[i][j] = (_X[i][j] * v);
		}
	return _X;
}

template
void display_matrix(matrix<_Ty>& X, __uint exp1 = 1, __uint exp2 = 1)
{
	matrix<_Ty> R(X.rows_count(), X.columns_count());
	R = X;
	for(__uint exp=exp1;exp <= exp2;exp++)
	{
		//R = X ^ exp;
		cout << _T("P^(") << exp << _T(") = ") << endl;
		for(__uint ii=0;ii<R.rows_count(); ii++){
			for(__uint jj=0;jj<R.columns_count(); jj++)
				cout << _T("[ ") << ii << _T(" , ") << jj << _T(" ]= ") << R[ii][jj] << _T("\t");
			cout << endl;
		}
		R = R * X;
		cout << endl;
	}
}

// H A S H   T A B L E S
template* > >
class hash_table
{
	array<pair<_Ky, _Vy>*, _Ay > hash_tbl;
	_Ay _alloc;
	__uint _size_ht;
	__uint _capacity;
public:
	typedef pair<_Ky, _Vy> value_type;
	typedef typename _Ay::size_type size_type;
	typedef typename _Ay::pointer pointer;
	typedef typename _Ay::const_pointer const_pointer;
	typedef typename _Ay::reference reference;
	typedef typename _Ay::const_reference const_reference;

	hash_table(const __uint sz) : hash_tbl(sz), _capacity(sz), _size_ht(0) {
		for(long _i=0;_i<_capacity;_i++)
			hash_tbl[_i] = 0;	
	}
	~hash_table(){
		for(long _i=0;_i<_capacity;_i++){			
			delete hash_tbl[_i];
			_alloc.destroy(&hash_tbl[_i]);
		}
	}

	hash_table(const hash_table& _HT) : hash_tbl(_HT.capacity()), _capacity(_HT.capacity()), _size_ht(0){
		for(long _i=0;_i<_HT.capacity();_i++){
			hash_tbl[_i] = 0;
			if(_HT.hash_tbl[_i])
				_alloc.construct(&hash_tbl[_i], new pair<_Ky, _Vy>(*_HT.hash_tbl[_i]));
			_size_ht++;
		}
	}

	hash_table& operator=(const hash_table& _HT){
		if(this!=&_HT){
			for(long _i=0;_i<_HT.capacity() || _i< capacity();_i++){
				if(hash_tbl[_i]){
					delete hash_tbl[_i];
					_alloc.destroy(&hash_tbl[_i]);
				}
				hash_tbl[_i] = 0;
				if(_HT.hash_tbl[_i])
					_alloc.construct(&hash_tbl[_i], new pair<_Ky, _Vy>(*_HT.hash_tbl[_i]));
				_size_ht++;
			}			
		}
		return *this;
	}
public:
	size_type capacity(){
		return _capacity;
	}
	size_type size() const {
		return _size_ht;
	}
	__uint insert(const _Ky& _K, const _Vy& _V){
		return insert(pair<_Ky, _Vy>(_K, _V));
	}
	__uint insert(pair<_Ky, _Vy>& _KV){
		__uint hgf = _H(hash(_KV.first));

		if(hash_tbl[hgf]){
			delete hash_tbl[hgf];
			_alloc.destroy(&hash_tbl[hgf]);
		}
		_alloc.construct(&hash_tbl[hgf], new pair<_Ky, _Vy>(_KV));
		_size_ht++;
		return hgf;
	}

	class iterator;
	friend class iterator;
	class iterator : public std::iterator<bidirectional_iterator_tag, pair<_Ky, _Vy> >
	{
		hash_table<_Ky, _Vy>* _ht;		
		__uint _index;
	public:		
		iterator() : _ht(0), _index(~0U) {}
		iterator(hash_table<_Ky, _Vy>& ht, __uint index) : _ht(&ht), _index(index){}		
		iterator(const iterator& it){
			_ht		= it._ht;
			_index	= it._index;
		}
		~iterator(){}

		bool operator==(const iterator& it){return (_ht==it._ht && _index==it._index);}
		bool operator!=(const iterator& it){return !(*this==it);}

		pair<_Ky, _Vy>& operator*(){return *_ht->hash_tbl[_index];}
		pair<_Ky, _Vy>* operator->(){return _ht->hash_tbl[_index];}

		iterator& operator++(){
			if(_index >= _ht->_capacity)
				throw out_of_range("position is out of upper bound range!");
			_index++;
			while(_index < _ht->_capacity && _ht->hash_tbl[_index]==0) _index++;
			return *this;
		}
		iterator operator++(int){			
			if(_index >= _ht->_capacity)
				throw out_of_range("position is out of upper bound range!");
			iterator tmp(*_ht, _index);
			_index++;
			while(_index < _ht->_capacity && _ht->hash_tbl[_index]==0) _index++;
			return tmp;
		}

		iterator& operator--(){
			if(_index <= 0) 				throw out_of_range("position is out of lower bound range!");			 			_index--; 			while(_index > 0 && _ht->hash_tbl[_index]==0) _index--;
			return *this;
		}
		iterator operator--(int){
			if(_index <= 0) 				throw out_of_range("position is out of lower bound range!"); 			if(_index==_ht->_capacity) _index--;
			iterator tmp(*_ht, _index);
			_index--;
			while(_index > 0 && _ht->hash_tbl[_index]==0) _index++;
			return tmp;
		}

		iterator& operator=(const iterator& it){
			if(this!=&it){
				_ht		= it._ht;
				_index	= it._index;
			}
			return *this;
		}
	};

	iterator begin(){
		if(size() > 0){
			__uint x = 0;
			while(x < _capacity && hash_tbl[x]==0) x++;
			return iterator(*this, x);
		}
		return end();
	}

	iterator end(){return iterator(*this, _capacity);}

	iterator find(const _Ky& _K){
		__uint hgf = _H(hash(_K));
		if(hash_tbl[hgf]!=0)
			return iterator(*this, hgf);		
		return end();
	}
	bool remove(const _Ky& _K){
		iterator it = find(_K);
		if(it!=end()){
			pair<_Ky, _Vy>* ppair = &*it;
			hash_tbl.remove(*it);
			_size_ht--;
			ppair = 0;
		}
		return false;
	}

	bool empty(){
		return (size()==0);
	}

	_Vy& operator[](const _Ky& _K){
		iterator it = find(_K);
		if(it==end()){
			__uint ix = insert(_K, _Vy());
			return hash_tbl[ix]->second;
		}else
			return hash_tbl[_H(hash(_K))]->second;
		return it->second;
	}
private:
	inline __uint _H(const hash_value& _hash){ return _hash % _capacity;}
};

// C H A I N E D  S C A T T E R   T A B L E S
template* > >
    class chain_scatter_table
{
	array<pair<_Ky, __uint>*, _Ay> hash_tbl;
	_Ay _alloc;
	__uint _size_ht;
	__uint _capacity;
public:
	enum { null = ((__uint)-1), };

	typedef typename _Ky value_type;
	typedef typename _Ay::size_type size_type;
	typedef typename _Ay::pointer pointer;
	typedef typename _Ay::const_pointer const_pointer;
	typedef typename _Ay::reference reference;
	typedef typename _Ay::const_reference const_reference;

	chain_scatter_table(const __uint sz) : hash_tbl(sz), _capacity(sz), _size_ht(0) {
		for(long _i=0;_i<_capacity;_i++)
			hash_tbl[_i] = 0;	
	}
	~chain_scatter_table(){
		for(long _i=0;_i<_capacity;_i++){			
			delete hash_tbl[_i];
			_alloc.destroy(&hash_tbl[_i]);
		}
	}

	chain_scatter_table(const chain_scatter_table& _HT) : hash_tbl(_HT.capacity()), _capacity(_HT.capacity()), _size_ht(0){
		for(long _i=0;_i<_HT.capacity();_i++){
			hash_tbl[_i] = 0;
			if(_HT.hash_tbl[_i])
				_alloc.construct(&hash_tbl[_i], new pair<_Ky, __uint>(*_HT.hash_tbl[_i]));
			_size_ht++;
		}
	}

	chain_scatter_table& operator=(const chain_scatter_table& _HT){
		if(this!=&_HT){
			for(long _i=0;_i< _HT.capacity() && _i< capacity();_i++){
				if(hash_tbl[_i]){
					delete hash_tbl[_i];
					_alloc.destroy(&hash_tbl[_i]);
				}
				hash_tbl[_i] = 0;
				if(_HT.hash_tbl[_i])
					_alloc.construct(&hash_tbl[_i], new pair<_Ky, __uint>(*_HT.hash_tbl[_i]));
				_size_ht++;
			}			
		}
		return *this;
	}
public:
	size_type capacity(){
		return _capacity;
	}
	size_type size() const {
		return _size_ht;
	}
	__uint insert(const _Ky& _K){ //O(1) + O(n + M) + O(1)
		//
		if(size()==capacity())
			throw domain_error("scatter table is full!");
		__uint probe = _H(hash(_K)); //O(1)
		if(hash_tbl[probe]){ //if already other hashes to this probe, look for an empty slot...
			while(hash_tbl[probe]->second!= null){ //next!= null
				//while exists a chain item...
				probe = hash_tbl[probe]->second;
			}
			__uint _tail = probe;
			//look for an empty slot for this _K...
			probe = (probe + 1) % _capacity; //begins from the next after tail to the _capacity, 
			//or from the beginning until an empty slot is found...
			while(hash_tbl[probe]!=0)
				probe = (probe + 1)% _capacity;
			hash_tbl[_tail]->second = probe;
		}
		//create a pair<Key, next offset is -1>()...
		_alloc.construct(&hash_tbl[probe], new pair<_Ky, __uint>(_K, null));		
		_size_ht++;
		return probe;
		//
	}

	class iterator;
	friend class iterator;
	class iterator : public std::iterator<bidirectional_iterator_tag, pair<_Ky, __uint> >
	{
		chain_scatter_table<_Ky>* _ht;		
		__uint _index;
	public:		
		iterator() : _ht(0), _index(~0U) {}
		iterator(chain_scatter_table<_Ky>& ht, __uint index) : _ht(&ht), _index(index){}		
		iterator(const iterator& it){
			_ht		= it._ht;
			_index	= it._index;
		}
		~iterator(){}		

		bool operator==(const iterator& it){return (_ht==it._ht && _index==it._index);}
		bool operator!=(const iterator& it){return !(*this==it);}

		_Ky& operator*(){return _ht->hash_tbl[_index]->first;}
		_Ky* operator->(){return &_ht->hash_tbl[_index]->first;}

		iterator& operator++(){
			if(_index >= _ht->_capacity)
				throw out_of_range("position is out of upper bound range!");
			__uint _prev_index = _index;
			_index = _ht->hash_tbl[_index]->second;
			if(_index==null){
				_index = _prev_index + 1;
				while(_index < _ht->_capacity && _ht->hash_tbl[_index]==0) _index++;
			}
			return *this;
		}
		iterator operator++(int){			
			if(_index >= _ht->_capacity)
				throw out_of_range("position is out of upper bound range!");
			iterator tmp(*_ht, _index);
			__uint _prev_index = _index;
			_index = _ht->hash_tbl[_index]->second;
			if(_index==null){
				_index = _prev_index + 1;
				while(_index < _ht->_capacity && _ht->hash_tbl[_index]==0) _index++;
			}
			return tmp;
		}

		iterator& operator--(){
			if(_index <= 0) 				throw out_of_range("position is out of lower bound range!");			 			_index--; 			while(_index > 0 && _ht->hash_tbl[_index]==0) _index--;
			return *this;
		}
		iterator operator--(int){
			if(_index <= 0) 				throw out_of_range("position is out of lower bound range!"); 			if(_index==_ht->_capacity) _index--;
			iterator tmp(*_ht, _index);
			_index--;
			while(_index > 0 && _ht->hash_tbl[_index]==0) _index++;
			return tmp;
		}

		iterator& operator=(const iterator& it){
			if(this!=&it){
				_ht		= it._ht;
				_index	= it._index;
			}
			return *this;
		}
		__uint index()const {return _index;}
	};

	iterator begin(){
		if(_capacity > 0){
			__uint x = 0;
			while(x < _capacity && hash_tbl[x]==0) x++; 			return iterator(*this, x); 		} 		return end(); 	} 	iterator end(){return iterator(*this, _capacity);} 	iterator find(const _Ky& _K){  //O(M) 		__uint hgf = _H(hash(_K)); 		if(hash_tbl[hgf]!=0){ 			while(hash_tbl[hgf]->second!=null && hash_tbl[hgf]->first!=_K)
				hgf = hash_tbl[hgf]->second;

			if(hash_tbl[hgf]->first==_K)
				return iterator(*this, hgf);
		}
		return end();
	}

	bool remove(const _Ky& _K){
		//
		if(size()==0)
			throw domain_error("the scatter table is empty!");
		iterator it = find(_K);
		//not found?
		if(it==end())
			throw invalid_argument("key value not found!");		
		__uint index = it.index();
		for(;;)
		{
			//find the next item who can be safely moved up
			__uint j = null;
			//iterate the chain from index...
			for(j = hash_tbl[index]->second; j!=null; j = hash_tbl[j]->second)
			{
				__uint hgf = _H(hash(hash_tbl[j]->first));

				//from j to j->next...
				//find the one who can be moved up...
				volatile bool bhash_same_index = false;
				for(__uint k = hash_tbl[index]->second; 
							(k!=hash_tbl[j]->second && !bhash_same_index);k = hash_tbl[k]->second)
				{
								//skip it if the current hash to same index where was found!
								if(hgf==k)
									bhash_same_index = true;
				}
				if(!bhash_same_index)
					break;							
			}
			if(j==null)
				break;
			//set to the previous moved slot (only the movable ones)
			hash_tbl[index]->first = hash_tbl[j]->first;			
			index = j;

		}
		delete hash_tbl[index];
		_alloc.destroy(&hash_tbl[index]);
		hash_tbl[index] = 0;
		//
		for(__uint j= (index + capacity() - 1)% capacity(); j!=index; 
					j= (j + capacity() - 1)% capacity())
					{
						//if some item in the hash table points to the deleted item (the last one),
						//point it to null
						if(hash_tbl[j] && hash_tbl[j]->second==index){
							hash_tbl[j]->second = null;
							break;
						}
					}
		_size_ht--;
		return true;
	}

	bool empty(){
		return (size()==0);
	}

	__uint operator[](const _Ky& _K){
		iterator it = find(_K);
		if(it==end()){
			__uint ix = insert(_K);
			return hash_tbl[ix]->second;
		}
		return it->second;
	}
private:
	inline __uint _H(const hash_value& _hash){ return _hash % _capacity;}
};

template
class pair_ex : public pair<_Ky, _Vy>
{	
public:
	typedef enum State { empty, occupied, deleted} State;	
	State state;
	pair_ex() : pair<_Ky, _Vy>(_Ky(), _Vy()), state(empty) {}
	pair_ex(const _Ky& _K, const _Vy& _V) : pair<_Ky, _Vy>(_K, _V), state(occupied) {}
	pair_ex(const pair_ex<_Ky, _Vy>& _Pex) : pair<_Ky, _Vy>(_Pex), state(_Pex.state) {}
	~pair_ex(){}

	pair_ex<_Ky, _Vy>& operator=(const pair_ex<_Ky, _Vy>& _Pex){
		if(this!=&_Pex)
		{
			first		= _Pex.first;
			second		= _Pex.second;
			state		= _Pex.state;
			//dis-occupy the copied one...
			_Pex.state = deleted;
		}
		return *this;
	}
};

// O P E N   S C A T T E R   T A B L E 
template > >
    class open_scatter_table
{
	array<pair_ex<_Ky, _Vy>, _Ay > hash_tbl;
	_Ay _alloc;

	double_hash<_Ky> _hash;
	//quad_probing_hash<_Ky> _hash;
	//linear_probing_hash<_Ky> _hash; 	
	__uint _size_ht;
	__uint _capacity;	
public:
	typedef pair_ex<_Ky, _Vy> value_type;
	typedef typename _Ay::size_type size_type;
	typedef typename _Ay::pointer pointer;
	typedef typename _Ay::const_pointer const_pointer;
	typedef typename _Ay::reference reference;
	typedef typename _Ay::const_reference const_reference;

	open_scatter_table(const __uint sz) : hash_tbl(sz), _capacity(sz), _size_ht(0) {
		for(long _i=0;_i<_capacity;_i++)
			_alloc.construct(&hash_tbl[_i], pair_ex<_Ky, _Vy>()); 
	}
	~open_scatter_table(){
		for(long _i=0;_i<_capacity;_i++){			
			_alloc.destroy(&hash_tbl[_i]);
		}
	}

	open_scatter_table(const open_scatter_table& _HT) : hash_tbl(_HT.capacity()), _capacity(_HT.capacity()), _size_ht(0){
		for(long _i=0;_i<_HT.capacity();_i++){			
			_alloc.construct(&hash_tbl[_i], pair_ex<_Ky, _Vy>(_HT.hash_tbl[_i]));
			_size_ht++;
		}
	}

	open_scatter_table& operator=(const open_scatter_table& _HT){
		if(this!=&_HT){
			for(long _i=0;_i<_HT.capacity() || _i< capacity();_i++){				
				_alloc.destroy(&hash_tbl[_i]);								
				_alloc.construct(&hash_tbl[_i], pair_ex<_Ky, _Vy>(_HT.hash_tbl[_i]));
				_size_ht++;
			}			
		}
		return *this;
	}
public:
	size_type capacity(){
		return _capacity;
	}
	size_type size() const {
		return _size_ht;
	}
	__uint insert(const _Ky& _K, const _Vy& _V){
		return insert(pair_ex<_Ky, _Vy>(_K, _V));
	}
	__uint insert(const pair_ex<_Ky, _Vy>& _KV){
		if(size()==capacity())
			throw domain_error("scatter table is full");

		__uint hgf = find_unoccupied(_KV.first);
		hash_tbl[hgf].first		= _KV.first;
		hash_tbl[hgf].second	= _KV.second;
		hash_tbl[hgf].state		= pair_ex<_Ky, _Vy>::occupied;
		_size_ht++;
		return hgf;
	}

	class iterator;
	friend class iterator;
	class iterator : public std::iterator<bidirectional_iterator_tag, pair_ex<_Ky, _Vy> >
	{
		open_scatter_table<_Ky, _Vy>* _ht;		
		__uint _index;
	public:		
		iterator() : _ht(0), _index(~0U) {}
		iterator(open_scatter_table<_Ky, _Vy>& ht, __uint index) : _ht(&ht), _index(index){}		
		iterator(const iterator& it){
			_ht		= it._ht;
			_index	= it._index;
		}
		~iterator(){}

		iterator& operator=(const iterator& it){
			if(this!=&it){
				_ht		= it._ht;
				_index	= it._index;
			}
			return *this;
		}

		bool operator==(const iterator& it){return (_ht==it._ht && _index==it._index);}
		bool operator!=(const iterator& it){return !(*this==it);}

		pair_ex<_Ky, _Vy>& operator*(){return _ht->hash_tbl[_index];}
		pair_ex<_Ky, _Vy>* operator->(){return &_ht->hash_tbl[_index];}

		iterator& operator++(){
			if(_index >= _ht->_capacity)
				throw out_of_range("position is out of upper bound range!");
			_index++;
			while(_index < _ht->_capacity && 
				(_ht->hash_tbl[_index].state==pair_ex<_Ky, _Vy>::empty || 
					 _ht->hash_tbl[_index].state==pair_ex<_Ky, _Vy>::deleted)) _index++;
			return *this;
		}
		iterator operator++(int){			
			if(_index >= _ht->_capacity)
				throw out_of_range("position is out of upper bound range!");
			iterator tmp(*_ht, _index);
			_index++;
			while(_index < _ht->_capacity && 
					(_ht->hash_tbl[_index].state==pair_ex<_Ky, _Vy>::empty || 
					 _ht->hash_tbl[_index].state==pair_ex<_Ky, _Vy>::deleted)) _index++;
			return tmp;
		}

		iterator& operator--(){
			if(_index <= 0)
				throw out_of_range("position is out of lower bound range!");			
			_index--;
			while(_index < _ht->_capacity && 
					(_ht->hash_tbl[_index].state==pair_ex<_Ky, _Vy>::empty || 
					 _ht->hash_tbl[_index].state==pair_ex<_Ky, _Vy>::deleted)) _index--;
			return *this;
		}
		iterator operator--(int){
			if(_index <= 0) 				throw out_of_range("position is out of lower bound range!"); 			if(_index==_ht->_capacity) _index--;
			iterator tmp(*_ht, _index);
			_index--;
			while(_index < _ht->_capacity && 
					(_ht->hash_tbl[_index].state==pair_ex<_Ky, _Vy>::empty || 
					 _ht->hash_tbl[_index].state==pair_ex<_Ky, _Vy>::deleted)) _index--;
			return tmp;
		}
		__uint index() const{return _index;}
	};

	iterator begin(){		
		if(size() > 0){
			__uint x = 0;
			while(x < capacity() && 
				(hash_tbl[x].state==pair_ex<_Ky, _Vy>::empty || 
				hash_tbl[x].state==pair_ex<_Ky, _Vy>::deleted)) x++;
			return iterator(*this, x);
		}		
		return end();
	}

	iterator end(){return iterator(*this, _capacity);}

	iterator find(const _Ky& _K){
		return iterator(*this, find_match(_K));
	}

private:
	inline __uint C(const __uint& _i){return (__uint)_i;/*linear collision resolution strategy*/}

	__uint find_match(const _Ky& _K){ 
		__uint hgf = _H(hash(_K));
		if(hash_tbl[hgf].first==_K && hash_tbl[hgf].state==pair_ex<_Ky, _Vy>::occupied)
			return hgf;

		for(__uint i=0;i< capacity(); i++){
			__uint const probe = _hash(_K, C(i), capacity());
			if(hash_tbl[probe].state==pair_ex<_Ky, _Vy>::empty)
				break;
			if(hash_tbl[probe].first==_K && hash_tbl[probe].state==pair_ex<_Ky, _Vy>::occupied)
				return probe;
		}
		return capacity();
	}
	__uint find_unoccupied(const _Ky& _K){ //T(H(_K)) + O(n) --> n/M is the load factor...
		__uint offset = _H(hash(_K));	
		cout << _T("offset = ") << offset << endl;
		if(hash_tbl[offset].state!=pair_ex<_Ky, _Vy>::occupied)
			return offset;

		for(__uint i=0;i< size() + 1; i++){
			__uint probe = (__uint)_hash(_K, C(i), capacity());
			if(hash_tbl[probe].state!=pair_ex<_Ky, _Vy>::occupied)
				return probe;
		}
		return capacity();
	}

public:
	bool remove(const _Ky& _K){
		if(_size_ht==0)
			throw domain_error("Scatter table is empty.");
		iterator it = find(_K);
		if(it!=end()){
			__uint i = it.index();
			for(;;)
			{
				for(__uint j = (i + 1 ) % capacity();
					hash_tbl[j].state==pair_ex<_Ky, _Vy>::occupied;
					j = ( j + 1) % capacity())
				{
						__uint const h = _H(hash(hash_tbl[j].first));
						//offsets
						/*
						0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
						-------------------------------------------
						            | | 
						      h     i j   h'  ::empty)
					break;
				_alloc.destroy(&hash_tbl[i]);
				_alloc.construct(&hash_tbl[i], hash_tbl[j]);
				i = j;
			}			
			_alloc.destroy(&hash_tbl[i]);
			_alloc.construct(&hash_tbl[i], pair_ex<_Ky, _Vy>());
			_size_ht--;			
			return true;
		}
		return false;
	}

	bool empty(){
		return (size()==0);
	}

	_Vy& operator[](const _Ky& _K){
		iterator it = find(_K);
		if(it==end()){
			__uint ix = insert(_K, _Vy());
			return hash_tbl[ix].second;
		}
		return it->second;
	}
private:
	inline __uint _H(const hash_value& _Hh){ return _Hh % _capacity;}
};

//S I M P L E   N - A R Y   T R E E 
template
class TreeNode
{
	T obj;
	array<TreeNode*> _childNodes;
	short count;
public:
	typedef T value_type;
	TreeNode() : _childNodes(5), count(0), obj(0) {}
	TreeNode(const T& _object, short maxNodes = 5) : 
			obj(_object), 
			_childNodes(maxNodes), 
			count(0) {}
	T& object(){
		return obj;
	}
	array<TreeNode*>& childNodes()
	{
		return _childNodes;
	}
	short nodesCount(){//the degree or depth level
		return count;
	}
	bool addNode(TreeNode* node){
		if(count< _childNodes.size()){
			_childNodes[count++] = node;
			return true;
		}
		return false;
	}

public:
	static void removeNodes(TreeNode* node)
	{		
		for(short i=0;i< node->nodesCount(); i++){
			TreeNode*& child = node->childNodes()[i];
			removeNodes(child);
			node->childNodes().get_allocator().destroy(&child);
		}
		delete node;
	}
};

// T R A V E R S A L   C L A S S E S 
template
class TreeVisitor
{
public:
	TreeVisitor(){}
	virtual void Previsit(const _Ty& _V){cout << _T("(");}
	virtual void Visit(const _Ty& _V){cout << _V;}
	virtual void Postvisit(const _Ty& _V){cout << _T(")");}

};

// D E P T H - F I R S T   T R A V E R S A L   A L G O R I T H M S   F O R   N - A R Y   T R E E S 
template
void depth_first(_Tr& tree, _Pred& pred)
{
	if(!tree.empty())
	{		
		pred.Previsit(tree.node_root());
		pred.Visit(tree.node_root());
		pred.Postvisit(tree.node_root());
		for(__uint i=0; i< tree.tree_degree(); i++)
			depth_first(tree.node(i), pred);				
	}
}

template
void depth_first_binary(_Tr& bin_tree, _Pred& pred)
{
	if(!bin_tree.empty())
	{
		if(!bin_tree.left_tree().empty())
			pred.Previsit(bin_tree.node_root());
		depth_first_binary(bin_tree.left_tree(), pred);

		pred.Visit(bin_tree.node_root());

		depth_first_binary(bin_tree.right_tree(), pred);
		if(!bin_tree.right_tree().empty())
			pred.Postvisit(bin_tree.node_root());
	}
}

//C O M P L E T E   N - A R Y   T R E E  
template
class NaryTree
{
	array<NaryTree<_Ty>* > subtree;
	__uint degree;
	_Ty* root;
public:
	typedef NaryTree<_Ty> nodeType;
	typedef _Ty root_type;
	typedef _Ty value_type;
	NaryTree(const __uint& N) : subtree(0), degree(N), root(0) {for(__uint i=0;i<degree;i++) subtree[i] = 0;}
	NaryTree(const __uint& N, const _Ty& r) : subtree(N), degree(N), root(const_cast<_Ty*>(&r)) {
		for(__uint i=0;i< degree;i++)
			subtree[i] = new NaryTree<_Ty>(N);
	}
	~NaryTree(){
		if(root!=0)
			for(__uint i=0;i< degree;i++)
				delete subtree[i];
	}
	root_type& node_root() const{
		if(root==0)
			throw logic_error("This tree is empty!");
		return *root;
	}
	bool empty() const{
		return (root==0);
	}
	bool attach_root(const _Ty& r){
		if(!empty())
			return false;
		root = &r;
		subtree.resize(degree);

		for(__uint i=0;i<degree;i++)
			subtree[i] = new NaryTree<_Ty>(N);
	}
	root_type& detach_root(){
		if(!leaf())
			throw domain_error("This tree node must be a leaf. Operation cancelled!");
		_Ty& r = *root;
		for(__uint i=0;i<degree;i++)
			delete subtree[i];
		subtree.resize(0);
		return r;
	}

	NaryTree<_Ty>& node(const __uint& n){
		if(empty())
			throw domain_error("This tree node is empty!");
		if(n>=degree)
			throw invalid_argument("Invalid argument!");
		return *subtree[n];
	}
	bool leaf() const{
		bool is_leaf = true && !empty();
		for(__uint i=0;i<degree;i++) 
			is_leaf &= (subtree[i]==0);
		return is_leaf;
	}	

	bool attach_node(const __uint& ih, NaryTree<_Ty>& node)
	{
		if(empty())
			throw domain_error("This tree node is empty and cannot be used in node attachment operation.");
		if(!subtree[ih]->empty())
			return false;
		delete subtree[ih];
		subtree[ih] = &node;
		return true;
	}

	NaryTree<_Ty>& detach_node(const __uint& ih){
		if(empty())
			throw domain_error("This tree node is empty and cannot be detached.");		
		NaryTree<_Ty>& tree = *subtree[ih];
		subtree[ih] = new NaryTree<_Ty>(degree);
		return tree;
	}

	__uint tree_degree()const{
		return degree;
	}
};

// B I N A R Y   T R E E  ( N - A R Y   W H E R E   N = 2)
template
    class binary_tree
{
protected:
	_Ty* root;
	binary_tree<_Ty>* left;
	binary_tree<_Ty>* right;
	bool owner;
public:
	binary_tree(bool bOwner = false) : 
		owner(bOwner),
		root(0), 
		left(0), 
		right(0) {}
	binary_tree(_Ty& r, bool bOwner = false) : 
		root(&r), 
		left(new binary_tree<_Ty>()),
		right(new binary_tree<_Ty>()),
		owner(bOwner) {}

	virtual bool attach_root(_Ty& r){
		if(root==0){
			root	= &r;
			left	= new binary_tree<_Ty>();
			right	= new binary_tree<_Ty>();
			return true;
		}
		return false;
	}
	_Ty& detach_root(){
		if(empty())
			throw domain_error("This binary tree node is empty.");
		if(leaf()){
			delete left;
			delete right;
			left	= 0;
			right	= 0;
			_Ty& r = *root;
			root	= 0;
			return r;
		}
		throw domain_error("This tree node is not a leaf. Operation cancelled!");
	}
	virtual ~binary_tree(){
		if(!empty())
		{	
			if(owner)
				delete root;
			delete left;
			delete right;
			root	= 0;
			left	= 0;
			right	= 0;
		}
	}

	bool empty() const {return (root==0);}
	bool leaf() const {
		return !empty() && (left->empty() && right->empty());
	}

	binary_tree<_Ty>& left_tree() const{
		return *left;
	}
	binary_tree<_Ty>& right_tree() const{
		return *right;
	}

	_Ty& node_root() const{
		return *root;
	}

	bool attach_left(binary_tree<_Ty>& lt){
		if(left->empty()){
			delete left;
			left = <
			return true;
		}
		return false;
	}
	bool attach_right(binary_tree<_Ty>& rt){
		if(right->empty()){
			delete right;
			right = &rt;
			return true;
		}
		return false;
	}

	int compare(binary_tree<_Ty>& bt){
		if(empty())
			return bt.empty() ? 0 : -1; //eq or less than you!
		else if(bt.empty())
			return 1;
		else{
			if(*root==*bt.root){
				int lc = left->compare(bt.left_tree());
				if(lc==0)
					return right->compare(bt.right_tree());
				else
					return lc;				
			}else{
				return (*root < *bt.root) ? -1 : 1;
			}
		}
	}
};

//BST
template
    class binary_search_tree : public binary_tree<_Ty>
{
public:
	binary_search_tree() : binary_tree<_Ty>() 
		{owner = false;}
	binary_search_tree(_Ty& r, bool bOwner = false) : root(&r), 
								left(new binary_search_tree<_Ty>()),
								right(new binary_search_tree<_Ty>()),
								owner(bOwner) {}
	virtual ~binary_search_tree(){}
	template
	class key_value
	{
		_Ty *key;
	public:
		key_value(_Ty *_K = 0): key(_K) {}
		_Ty* value(){return key;}
		bool valid(){return (key!=0);}
		bool empty(){return (key==0);}
	};
	inline _Ty& key() const{
		return *root;
	}
	binary_search_tree<_Ty>& left_tree() const{
		return *dynamic_cast<binary_search_tree<_Ty>*>(left);
	}
	binary_search_tree<_Ty>& right_tree() const{
		return *dynamic_cast<binary_search_tree<_Ty>*>(right);
	}
protected:
	void left_ptr(binary_search_tree<_Ty>* _LF)
		{left = _LF;}
	void right_ptr(binary_search_tree<_Ty>* _RT)
		{right = _RT;}
	void root_ptr(_Ty* _K)
		{root = _K;}

	bool attach_left(binary_search_tree<_Ty>& lt){
		if(left->empty()){
			delete left;
			left = <
			return true;
		}else{
			binary_search_tree<_Ty>* bst_left = dynamic_cast<binary_search_tree<_Ty>*>(left);
			return bst_left->attach_left(lt);
		}
		return false;
	}
	bool attach_right(binary_search_tree<_Ty>& rt){
		if(right->empty()){
			delete right;
			right = &rt;
			return true;
		}else{
			binary_search_tree<_Ty>* bst_right = dynamic_cast<binary_search_tree<_Ty>*>(right);
			return bst_right->attach_right(lt);
		}
		return false;
	}

	virtual bool attach_root(const _Ty& r){
		if(root==0){
			root	= const_cast<_Ty*>(&r);
			left	= new binary_search_tree<_Ty>();
			right	= new binary_search_tree<_Ty>();
			return true;
		}
		return false;
	}

	binary_search_tree<_Ty>* find_tree(const _Ty& _X)
	{
		if(empty())
			return 0;
		if(key()==_X)
			return this;
		else if(_X < key())
			return left_tree().find_tree(_X);
		else
			return right_tree().find_tree(_X);			
	}

public:
	binary_search_tree<_Ty>* insert(const _Ty& _V)
	{
		binary_search_tree<_Ty>* p = 0;
		if(empty()){
			attach_root(_V);
			p = this;
		}else{
			if(_V==key())
				p = this;
			else if(_V < key())
				p = left_tree().insert(_V);
			else
				p = right_tree().insert(_V);			
		}
		Balance();
		return p;
	}

	key_value<_Ty> find(const _Ty& _X) //S(_X) = O(log(n)) ^ U(_X) = O(log(n)) ;n = depth
	{
		binary_search_tree<_Ty>* _BST = find_tree(_X);
		if(_BST)
			return key_value<_Ty>(&_BST->key());
		else
			return key_value<_Ty>();
	}
	key_value<_Ty> find_min(){
		if(empty())
			return key_value<_Ty>();
		if(!left_tree().empty())
			return left_tree().find_min();
		else
			return key_value<_Ty>(&key());
	}
	key_value<_Ty> find_max(){
		if(empty())
			return key_value<_Ty>();

		if(!right_tree().empty())
			return right_tree().find_max();
		else
			return key_value<_Ty>(&key());
	}

	bool remove(const _Ty& _X)
	{
		bResult = false;
		if(empty())
			return false;
		if(_X==key())
		{
			if(!left_tree().empty())
			{
				key_value<_Ty> _KV = left_tree().find_max(); //find the largest in the left tree...
				if(_KV.valid()){
					root = _KV.value();
					left_tree().remove(*_KV.value());
				}
			}else if(!right_tree().empty())
			{
				key_value<_Ty> _KV = right_tree().find_min(); //find the smallest in the right tree...
				if(_KV.valid()){
					root = _KV.value();
					right_tree().remove(*_KV.value());
				}
			}else
				detach_root(); //when found, detach it...
			bResult = true;
		}else if(_X < key())
			bResult = left_tree().remove(_X);
		else
			bResult = right_tree().remove(_X);
		Balance();
		return bResult;
	}
	virtual void Balance(){}
};

//A D E L S O N   V E L S K I I   L A N D I S   T R E E  ( A V L   B A L A N C E D   T R E E )
template
    class AVLTree : public binary_search_tree<_Ty>
{
protected:
	int height;

	int BalanceFactor() const{
		return (left_tree().Height() - right_tree().Height());
	}
	void AdjustHeight(){
		if(empty())
			height = -1;
		else
			height = max(left_tree().Height(), right_tree().Height()) + 1;
	}

	virtual bool attach_root(const _Ty& r){
		if(root==0){
			root	= const_cast<_Ty*>(&r);
			left	= new AVLTree<_Ty>();
			right	= new AVLTree<_Ty>();
			return true;
		}
		return false;
	}

	// R O T A T I O N   M E M B E R S
	//When an AVL tree becomes unbalanced after an insertion, exactly one single or double
	//rotation is required to balance the tree.

	//S I N G L E   R O T A T I O N 
	virtual void LLRotation(){
		if(empty())
			throw domain_error("invalid rotation operation on an empty tree.");

		binary_search_tree<_Ty>* tmp = &right_tree();

		right_ptr(&left_tree());

		left_ptr(&right_tree().left_tree());
		right_tree().left_ptr(&right_tree().right_tree());
		right_tree().right_ptr(tmp);

		//swap keys...
		_Ty* tmpKey = &key();
		root_ptr(&right_tree().key());
		right_tree().root_ptr(tmpKey);

		right_tree().AdjustHeight();
		AdjustHeight();
	}

	virtual void RRRotation(){
		if(empty())
			throw domain_error("invalid rotation operation on an empty tree.");

		binary_search_tree<_Ty>* tmp = &left_tree();

		left_ptr(&right_tree());

		right_ptr(&left_tree().right_tree());
		left_tree().right_ptr(&left_tree().left_tree());
		left_tree().left_ptr(tmp);

		//swap keys...
		_Ty* tmpKey = &key();
		root_ptr(&left_tree().key());
		left_tree().root_ptr(tmpKey);

		left_tree().AdjustHeight();
		AdjustHeight();

	}

	//D O U B L E   R O T A T I O N 
	virtual void LRRotation(){
		if(empty())
			throw domain_error("invalid rotation on an empty tree.");
		left_tree().RRRotation();
		LLRotation();
	}

	virtual void RLRotation(){
		if(empty())
			throw domain_error("invalid rotation on an empty tree.");
		right_tree().LLRotation();
		RRRotation();
	}

	//B A L A N C E R
	virtual void Balance(){
		AdjustHeight();
		if(abs(BalanceFactor()) > 1)
		{
			if(BalanceFactor() > 0)
			{
				if(left_tree().BalanceFactor() > 0)
					LLRotation();
				else
					LRRotation();
			}else{
				if(right_tree().BalanceFactor() < 0)
					RRRotation();
				else
					RLRotation();
			}
		}
	}
public:
	AVLTree() : binary_search_tree<_Ty>(), height(-1) {}
	~AVLTree(){}

	AVLTree<_Ty>& left_tree() const{
		return *dynamic_cast<AVLTree<_Ty>*>(left);
	}
	AVLTree<_Ty>& right_tree() const{
		return *dynamic_cast<AVLTree<_Ty>*>(right);
	}
	int Height() const{
		return height;
	}
};

// R E D - B L A C K   T R E E  (TODO : R E S E A R C H )
template
	class red_black_tree : public AVLTree<_Ty>
{
	binary_search_tree<_Ty>* _Parent;
public:
	enum { _Red, _Black } _Color;

	red_black_tree(binary_search_tree<_Ty>* _Pr = 0) : 
						AVLTree<_Ty>(), 
						_Parent(_Pr), 
						_Color(_Back) {}
	virtual void Balance(){
		AVLTree<_Ty>::Balance();
	}
};

template
void postfix_to_infix(basic_istream<_E>& strm)
{
	_E c;
	// E X P R E S S I O N   T R E E 
	//binary oper = (n - 1) / 2;
	//operands    = (n + 1) / 2;
	typedef binary_tree<_E> expression_tree;

	stack<expression_tree*> expr_stack;
	while(strm >> c, !strm.eof())
	{
		if(_istdigit(c) || _istalpha(c))
			expr_stack.push(new expression_tree(*new _E(c), true));
		else{
			if(c==_T('+') || c==_T('-') || c==_T('*') || c==_T('/'))
			{
				if(expr_stack.empty())
					throw domain_error("syntax error parsing postfix expression.");
				//create a expression tree...
				expression_tree* result = new expression_tree(*new _E(c), true);
				expression_tree* right	= expr_stack.top();expr_stack.pop();
				if(expr_stack.empty())
					throw domain_error("syntax error parsing postfix expression.");
				expression_tree* left	= expr_stack.top();expr_stack.pop();
				result->attach_right(*right);
				result->attach_left(*left);
				expr_stack.push(result);
			}else if(c==_T(';')) break;
		}
	}
	expression_tree* result = expr_stack.top();expr_stack.pop();

	depth_first_binary(*result, TreeVisitor<_E>());
	delete result;
}

//Q U E U E   B A S E D   I M P L E M E N T A T I O N
template
void BreadthFirstTraversal(const TreeNode* node)
{
	if(!node)
		return;
	queue<TreeNode* > qtrav;
	qtrav.push(const_cast<TreeNode*>(node));

	while(!qtrav.empty()){
		TreeNode* the_node = qtrav.front();
		qtrav.pop();
		cout << the_node->object() << endl;
		array<TreeNode*>& childNodes = the_node->childNodes();
		for(short i=0;i< the_node->nodesCount();i++){
			qtrav.push(childNodes[i]);
			cout << childNodes[i]->object() << " ";
		}
		cout << endl;
	}
}

//S T A C K   B A S E D   I M P L E M E N T A T I O N
template
void BreadthFirstTraversal2(const TreeNode* node)
{
	if(!node)
		return;
	stack<TreeNode* > strav;
	strav.push(const_cast<TreeNode*>(node));

	while(!strav.empty()){
		TreeNode* the_node = strav.top();
		strav.pop();
		cout << the_node->object() << endl;
		array<TreeNode*>& childNodes = the_node->childNodes();
		for(short i=0;i< the_node->nodesCount();i++){
			strav.push(childNodes[i]);
			cout << childNodes[i]->object() << " ";
		}
		cout << endl;
	}
}

//D R A W   T H E   P A S C A L' S   T R I A N G L E	
template
void pascal_triangle(basic_ostream<_E>& os, const __uint& nx)
{
	for(__uint n = 0; n <=nx; ++n)
	{
		for(__uint m = 0; m <= n; ++m)
		{
			os << Binom(n, m) << _T(" ");
		}		
		os << endl;
	}
}

// A C K E R M A N N ' S  R E C U R S I V E   F U N C T I O N 

template
_Ty ackermann_fn(const _Ty& _M, const _Ty& _N)
{
	if(_M==0 && _N >= 0)
		return _N + 1;
	else if(_M >= 1 && _N==0)
		return ackermann_fn(_M - 1, 1);
	else if(_N >= 1 && _M)
		return ackermann_fn(_M - 1, ackermann_fn(_M, _N - 1));

	return 0;
}

/*
   The Euclid's Algorithm is used to determine the Greatest Common Divisor of 'a' and 'b',
   denoted by gcd(a, b)
   for instance,
   gcd(10, 5) = 5;
   gcd(10, 13)= 1;
   gcd(5,0)   = 5;

  This algorithm can be used to determine the common factor between to large integers 
  (ie.: 200 bits integers) without factoring a and b. This is one of the most famous 
  theoretic algorithms, dating back to at least 300 B.C.

  the running time is O(log2(max(a , b)))

  if we consider d = ax + by, where d = gcd(a, b), then the hypothesis is true, and if we can calculate
  x from equation ax mod b = 1, then x is the multiplicative inverse of a, modulo b.
*/
__uint gcd(__uint a, __uint b)
{
	if(!b)
		return a;
	else
		return gcd(b, a%b); 
}

#define EuclidGCD(x, y) gcd(x, y)

class RandomNumberGenerator
{
	long seed;
	long const a;
	long const m;
	long const q;
	long const r;

public:
	RandomNumberGenerator() :
	  					seed(1L),
						a(16807L),
						m(2147483647L),
						q(127773L),
						r(2836L) {}
	void SetSeed(long s);
	double Next();
	long NextEx();
};

class RandomVariable
{
protected:
	RandomNumberGenerator PSeudoRNG;
public:
	virtual double Generate() = 0;
};

class SimpleRV: public RandomVariable
{
public:
	double Generate();
};

class UniformRV : public RandomVariable
{
	double u;
	double v;
public:
	UniformRV(const double& _u, const double& _v) : u(_u), v(_v) {}
	double Generate();
};

class ExpRV : public RandomVariable
{
	double mu;
public:
	ExpRV(double _mu) : mu(_mu) {}
	double Generate();
};

void RandomNumberGenerator::SetSeed(long s)
{
	if(s < 1 || s >= m)
		throw exception("invalid seed");
	seed = s;
}

double RandomNumberGenerator::Next()
{
	seed = a * (seed % q) - r * (seed / q);
	if(seed < 0)
		seed += m;
	return (double)seed / (double)m;
	//return seed % m;
}

long RandomNumberGenerator::NextEx()
{
	seed = a * (seed % q) - r * (seed / q);
	if(seed < 0)
		seed += m;
	return seed % m;
}

double SimpleRV::Generate(){return PSeudoRNG.Next();}
double UniformRV::Generate(){ return u + (v - u) * PSeudoRNG.Next();}
double ExpRV::Generate(){ return -mu * log(PSeudoRNG.Next()); }

typedef RandomNumberGenerator PRNG;

//TODO : Cryptographic Key Generator using the NextEx member from PRNG

// S O R T I N G   A L G O R I T H M S 

//S T R A I G H T   I N S E R T I O N   S O R T 
template
void InsertionSort(_Ay& arr, const __uint n) //O(n) | O(n^2)
{
	for(__uint i = 1;i < n; ++i) 		for(__uint j = i; j > 0 && arr[j - 1U] > arr[j]; --j)
			swap(arr[j], arr[j - 1U]);
}

template
void InsertionSort(array<_Ty>& arr){InsertionSort(arr, arr.size());}

// B I N A R Y   I N S E R T I O N   S O R T 
template
void BinaryInsertionSort(_Ay& arr, const __uint n) //O(n log n)
{
	for(__uint i = 1; i < n; ++i)
	{		
		__uint left		= 0,
			   right	= i;
		while(left < right) 		{ 			__uint const middle = (left + right) / 2; 			if(arr[i] >= arr[middle])
				left = middle + 1;
			else
				right = middle;
		}
		for(__uint j = i; j > left; --j)
			swap(arr[j - 1U], arr[j]);
	}
}

template
void BinaryInsertionSort(array<_Ty>& arr){BinaryInsertionSort(arr, arr.size());}

// E X C H A N G E   S O R T I N G 

//B U B B L E   S O R T 
template
void BubbleSort(_Ay& arr, const __uint n) //Theta(n^2)
{
	for(__uint i = n; i > 1; --i)
		for(__uint j = 0; j < i - 1U; ++j) 			if(arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

template
void BubbleSort(array<_Ty>& arr){BubbleSort(arr, arr.size());}

//S T R A I G H T   S E L E C T I O N   S O R T 
template
void SelectionSort(_Ay& arr, const __uint n) //O(n^2)
{
	for(__uint i = n; i > 1; --i)
	{
		__uint max = 0;
		for(__uint j = 1; j < i; ++j) 			if(arr[j] > arr[max])
				max = j;
		swap(arr[i - 1U], arr[max]);
	}
}

template
void SelectionSort(array<_Ty>& arr){SelectionSort(arr, arr.size());}

//Q U I C K   S O R T  : Median of Three

template
class MedianOfThreeQuickSort
{
protected:
	__uint cutOff; //stop recursion when length falls below this critical value
	__uint SelectPivot(_Ay& arr, __uint left, __uint right);
	void QuickSort(_Ay& arr, __uint left, __uint right);	
public:
	void Sort(_Ay& arr, __uint n);
	MedianOfThreeQuickSort() : cutOff(2){}
};

template
__uint MedianOfThreeQuickSort<_Ay>::SelectPivot(
								_Ay& arr, __uint left, __uint right)
{
	__uint middle = (left + right) / 2;
	if(arr[left] > arr[middle])
		swap(left, middle);
	if(arr[left] > arr[right])
		swap(left, right);
	if(arr[middle] > arr[right])
		swap(middle, right);
	return middle;
}

template
void MedianOfThreeQuickSort<_Ay>::Sort(_Ay& arr, __uint n)
{
	QuickSort(arr, 0, n - 1U);
	InsertionSort(arr, n);
}

template
void MedianOfThreeQuickSort<_Ay>::QuickSort(_Ay& arr, __uint left, __uint right)
{
	if((right - left) + 1 > cutOff)
	{
		__uint const pivot = SelectPivot(arr, left, right);
		swap(arr[pivot], arr[right]);		
		__uint i = left;
		__uint j = right - 1U;
		for(;;)
		{
			while(i < j && arr[i] < arr[right]/*pivot*/) ++i;
			while(i < j && arr[right]/*pivot*/ < arr[j]) ++j; 			if(i >= j) break;
			swap(arr[i++], arr[j--]);
		}
		if(arr[right] < arr[i])
			swap(arr[right], arr[i]);
		if(left < i) 			QuickSort(arr, left, i - 1U); 		if(right > i)
			QuickSort(arr, i + 1, right);
	}
}

template
void QuickSort(_Ay& arr, __uint n)
{
	MedianOfThreeQuickSort<_Ay> QSort;
	QSort.Sort(arr, n);
}

template
void QuickSort(array<_Ty>& arr){QuickSort(arr, arr.size());}

// S T L   V E R S I O N   O F   S O R T I N G   A L G O R I T H M S 

//S T R A I G H T   S E L E C T I O N   S O R T 
template
void selection_sort(_RIT _F, _RIT _L)	//O(n^2)
{
	_RIT _FI = _L;
	while((_F + 1) < _FI)
	{
		_RIT _Mx = _F,
			 _X	 = _F + 1;
		while(_X < _FI){
			if(*_Mx < *_X)
				_Mx = _X;
			++_X;
		}
		swap(*(_FI - 1U), *_Mx);
		--_FI;
	}
}

//S T R A I G H T   I N S E R T I O N   S O R T 
template
void insertion_sort(_RIT _F, _RIT _L)	//O(n) | O(n^2)
{
	_RIT _FI = _F + 1;
	while(_FI != _L)
	{
		_RIT _X = _FI;
		while(_F < _X && *_X < *(_X - 1U)){
			swap(*_X, *(_X - 1U));
			_X--;
		}
		++_FI;
	}
}

// B I N A R Y   I N S E R T I O N   S O R T 
template
void binary_insertion_sort(_RIT _F, _RIT _L) //O(n log n)
{
	_RIT _FI = _F + 1;
	while(_FI < _L)
	{
		_RIT _LF = _F,
			 _RT = _FI;
		while(_LF < _RT)
		{
			_RIT _MID = _LF + ((_RT - _LF) / 2);
			if(!(*_FI < *_MID))
				_LF = _MID + 1;
			else
				_RT = _MID;
		}
		_RIT _X = _FI;
		while(_LF < _X)
		{
			swap(*(_X - 1), *_X);
			--_X;
		}
		++_FI;
	}
}

// E X C H A N G E   S O R T I N G 

//B U B B L E   S O R T 
template
void bubble_sort(_RIT _F, _RIT _L) //Theta(n^2)
{
	_RIT _FI = _L;
	while((_F + 1) < _FI)
	{
		_RIT _X = _F;
		while(_X < (_FI - 1U))
		{
			if(*(_X + 1) < *_X)
				swap(*_X, *(_X + 1));
			++_X;
		}
		--_FI;
	}
}

//Q U I C K S O R T 
template
class quick_sort_moft
{	
protected:
	__uint cutOff; //stop recursion when length falls below this critical value
	_RIT select_pivot(_RIT _LF, _RIT _RT);
	void q_sort(_RIT _LF, _RIT _RT);
public:
	void sort(_RIT _F, _RIT _L);
	quick_sort_moft() : cutOff(2){}
};

template
_RIT quick_sort_moft<_RIT>::select_pivot(_RIT _LF, _RIT _RT)
{
	_RIT _MID = _LF + (_RT - _LF) / 2;
	if(*_MID < *_LF)
		swap(*_MID, *_LF);
	if(*_RT < *_LF)
		swap(*_RT, *_LF);
	if(*_RT < *_MID)
		swap(*_RT, *_MID);
	return _MID;
}

template
void quick_sort_moft<_RIT>::sort(_RIT _F, _RIT _L)
{
	q_sort(_F, _L - 1U);
	insertion_sort(_F, _L);
}

template
void quick_sort_moft<_RIT>::q_sort(_RIT _LF, _RIT _RT)
{
	if((_RT - _LF) + 1 > cutOff)
	{
		_RIT _Pv = select_pivot(_LF, _RT);
		swap(*_Pv, *_RT);
		_RIT _Pivot = _RT;
		_RIT _FI = _LF,
			 _X	 = _RT - 1U;
		for(;;)
		{
			while(_FI < _X && *_FI < *_Pivot) ++_FI;
			while(_FI < _X && *_Pivot < *_X)  --_X;

			if(!(_FI < _X)) break;
			swap(*_FI++, *_X--);			
		}
		if(*_Pivot < *_FI)
			swap(*_Pivot, *_FI);
		if(_LF < _FI)
			q_sort(_LF, _FI - 1U);
		if(_FI < _RT)
			q_sort(_FI + 1, _RT);
	}
}

template
void quick_sort(_RIT _F, _RIT _L)
{
	quick_sort_moft<_RIT> qsort;
	qsort.sort(_F, _L);
}

//H A S H   S E A R C H 

template
__uint hash_search(_Ay& arr, __uint n, const _Ty& _X, _HashOp _hash)
{
	__uint _Pos = hgof(_hash(_X),n);
	if(arr[_Pos]==_X)
		return _Pos;
	else{
		__uint _Runner = _Pos + 1;
		while((_Runner % n)!= _Pos){			
			if(arr[_Runner]==_X)
				return _Runner;
			_Runner = (_Runner % n) + 1;
		}
		return n;
	}
}

template
__uint hash_search(array<_Ty> arr, const _Ty& _X, _HashOp _hash)
	{return hash_search(arr, arr.size(), _X, _hash);}

/* SCATTER CHAINED HASH TABLE 
_______________________________________________
INSERT ALGORITHM

void insert( key, r )
     typekey key;  dataarray r;
{ 
	extern int n, nextfree;
    int i;

     i = hashfunction( key );
     if ( empty(r[i]) ) {
          r[i].k = key;
          r[i].next = (-1);
          n++;
     }
     else { // *** Find end of chain ***
          while ( r[i].next!=(-1) && r[i].k!=key )  i = r[i].next;
          if ( r[i].k==key )  Error; // *** key already in table ***;
          else {
               // *** Find next free location ***
               while ( !empty(r[nextfree]) && nextfree>=0 )  nextfree--;
               if ( nextfree
Advertisements

Posted February 2, 2013 by hmarzan

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: