/*
Hello flipcoders, here's my recently completed assortment of useful
templated array routines, mostly sorting routines.
I know some of these are quite basic routines, but they are good to have handy.
I'm fairly sure these are bug free, (I've tested them thoroughly)
but if you find a bug, or have other suggestions or comments, let me know.
Yeah I know you could just use STL for these things, but you might learn
more from this code. If nothing more these should be very useful to beginners.
To use these all you need to do is have an array (any type) and
define a few operators for that data type.

For example given the following data type:

typedef unsigned short keyType;
typedef struct item {
	keyType key;
	long foo;
	char bar;
};

The routines below will require that you define some or all of the following:
(unless you're using built in data types)

inline int operator <  (item &a, item &b) {return a.key < b.key;}
inline int operator == (item &a, item &b) {return a.key == b.key;}
inline int operator &  (item &a, unsigned long b) {return ((unsigned long)a.key) & b;}

If the key is not the entire item, also define these:

inline int operator == (item &a, keyType b) {return a.key == b;}
inline int operator <  (item &a, keyType b) {return a.key < b;}

Also if necessary, define a copy constructor.
You can now use the routines below like this:

const int arraysize = 1000;
item myarray[arraysize];
...
QuickSort(myarray, arraysize);

I hope the rest is mostly self-explanatory.
Written on a Mac using Symantec C++ v8.6.
Permission to use/copy/modify/distribute hereby granted.

Later on I'll post a similiar thing for lists.

[NZ]_i/\/\alc
(Malcolm)
*/

#ifndef MyArrayUtils
#define MyArrayUtils

#define CutOff 16 //final Insertionsort cutoff size. Set to zero or more
#define MEDIAN_OF_THREE //Better Quicksort splitter method option. Comment out if you like
#define SMALLEST_FIRST //Reduces stack memory usage. Comment out if you like

//If search fails this is returned
#define NotFound -1
//Basic item swap macro
#define Swap(a,b) do{TItem x=(a);(a)=(b);(b)=x;}while(false)

// *** Utilities ***
// Return true if the array is sorted
template <class TItem, class TSize>
int Sorted(TItem a[], TSize n) {
	for (TSize i = n-1; i > 0; --i)
		if (a[i] < a[i-1])
			return false;
	return true;
}

// Reverses the array
template <class TItem, class TSize>
void Reverse(TItem a[], TSize n) {;
	for (TSize i = (--n-1)>>1; i >= 0; --i)
		Swap(a[i], a[n-i]);
}

// *** Searching ***
// O(logn) : sorted only
template <class TItem, class TSize, class TKey>
TSize BinarySearch(TItem a[], TSize n, TKey find) {
	TSize l = 0, r = n-1;
	while (l <= r) {
		TSize m = (l + r)>>1;
		if (a[m] < find)
			l = m + 1;
		else
			r = m - 1;
	}
	if (a[l] == find)
		return l;
	else
		return NotFound;
}

// O(n) : sorted only
template <class TItem, class TSize, class TKey>
TSize SortedSequentialSearch(TItem a[], TSize n, TKey find) {
	for (TSize i=0; i < n; ++i)
		if (a[i] < find)
			continue;
		else if (a[i] == find)
			return i;
		else
			return NotFound;
	return NotFound;
}

// O(n) : sorted only
template <class TItem, class TSize, class TKey>
inline TSize SequentialSearch(TItem a[], TSize n, TKey find) {
	for (TSize i=0; i < n; ++i)
		if (a[i] == find)
			return i;
	return NotFound;
}

// *** Sorting ***
// O(nlogn) : uses stack memory : only integer keys
template <class TItem, class TSize>
void RadixExchangeSortAux(TItem a[], TSize l, TSize r, unsigned long mask) {
	while (r - l > CutOff) {
		TSize i = l, j = r-1;
		while (i <= j) {
			while (((a[i] & mask) <=0) && i<=j) ++i;
			while (((a[j] & mask) > 0) && i<=j) --j;		
			if (i < j) {
				Swap(a[i], a[j]);
				++i; --j;
			}
		}
		if ((mask>>=1) == 0) break;
#ifdef SMALLEST_FIRST
		if (i-l <= r-j) {
#endif
			RadixExchangeSortAux(a, l, i, mask);
			l = i;
#ifdef SMALLEST_FIRST
		} else {
			RadixExchangeSortAux(a, i, r, mask);
			r = i;
		}
#endif
	}
}
template <class TItem, class TSize>
void RadixExchangeSort(TItem a[], TSize n) {
	RadixExchangeSortAux(a, (TSize)0, n, (unsigned long)0x80000000);
#if CutOff > 0
	InsertionSort(a, n);
#endif
}

// O(nlogn) .. O(n^2)
template <class TItem, class TSize>
void QuickSortAux(TItem a[], TSize l, TSize r) { 
	while (r - l > CutOff) {
		TSize i = (l+r)>>1, j;
#ifdef MEDIAN_OF_THREE
		if (a[i] < a[l]) Swap(a[i], a[l]);
		if (a[r] < a[l]) Swap(a[r], a[l]);
		if (a[r] < a[i]) Swap(a[r], a[i]);
		TItem x = a[i];
		i = l, j = r;
#else
		TItem x = a[i];
		i = l-1, j = r+1;
#endif
		do {
			while (a[++i] < x) ;
			while (x < a[--j]) ;
			if (j < i) break;
			Swap(a[i], a[j]);
		} while (true);		
#ifdef SMALLEST_FIRST
		if (j-l <= r-i) {
#endif
			QuickSortAux(a, l, j);
			l = i;
#ifdef SMALLEST_FIRST
		} else {
			QuickSortAux(a, i, r);
			r = j;
		}
#endif
	}
}
template <class TItem, class TSize>
void QuickSort(TItem a[], TSize n) {
	QuickSortAux(a, (TSize)0, n-1);
#if CutOff > 0
	InsertionSort(a, n);
#endif
}

// O(nlogn)
template <class TItem, class TSize>
void HeapSortAux(TItem a[], TSize l, TSize r) {
	TSize j = l*2;
	TItem x = a[l];
	while (j <= r) {
		if (j < r) if (a[j] < a[j + 1]) ++j;
		if (! (x < a[j])) break;
		a[l] = a[j];
		l = j;
		j*=2;
	}
	a[l] = x;
}
template <class TItem, class TSize>
void HeapSort(TItem a[], TSize n) {
	--n;
	TSize k = n>>1;
	while (k >= 0)
		HeapSortAux(a, k--, n);
	k = n;
	while (k > 0) {
		Swap(a[0], a[k]);
		HeapSortAux(a, 0, --k);
	}
}

// O(nlogn) : Stable : uses double storage heap memory
template <class TItem, class TSize>
void MergeSortAux(TItem a[], TItem temp[], TSize l, TSize r) {
	if (l < r) {
		TSize m = (l + r)>>1;
		MergeSortAux(a, temp, l, m);
		MergeSortAux(a, temp, m + 1, r);
		TSize i=l, j=m+1, c=l;
		while (i <= m && j <= r)
			temp[c++] = (a[j] < a[i]) ? a[j++] : a[i++];
		while (i <= m) temp[c++] = a[i++];
		for (TSize k=l; k < c; ++k)
			a[k]=temp[k];
	}
}
template <class TItem, class TSize>
void MergeSort(TItem a[], TSize n) {
	TItem *temp = new TItem[n];
	if (temp == NULL) return;
	MergeSortAux(a, temp, (TSize)0, --n);
	delete[] temp;
}

template <class TItem, class TSize>
void ShellSort(TItem a[], TSize n) {
	const int incs[15] = { 3, 7, 21, 48, 112,
										336, 861, 1968, 4592, 13776,
										33936, 86961, 198768, 463792, 1391376 };
	for (int l = 14; l > 0; --l) {
		TSize m = incs[l];
		for (TSize j = m; j < n; ++j) {
			TSize i = j - m, k = j;
			while (a[k] < a[i]) {
				Swap(a[i], a[k]);
				if (i < m) break;
				k = i;
				i-=m;
			}
		}
	}
	InsertionSort(a, n);
}

template <class TItem, class TSize>
void CombSort(TItem a[], TSize n) {
	Boolean swapped = false;
	TSize gap = n, top;
	do {
		gap = (gap*10)/13;
		switch (gap) {
			case 0:
				gap = 1;
			break;
			case 9:
			case 10: 
				gap = 11;
			break;
			default: break;
		}
		swapped = false;
		top = n - gap;
		for (TSize i = 0; i < top; i++) {
			TSize j = i + gap;
			if (a[j] < a[i]) {
				Swap(a[i], a[j]);
				swapped = true;
			}
		}
	} while (swapped || (gap > 1));
}

// O(n^2) : Stable
template <class TItem, class TSize>
void BinaryInsertionSort(TItem a[], TSize n) {
	for (TSize i = 1; i < n; ++i) {
		TSize l=0, r=i-1, j=r;
		item x = a[i];
		while (l <= r) {
			TSize m = (l + r)>>1;
			if (x < a[m])
				r = m - 1;
			else
				l = m + 1;
		}
		while (j >= l) {
			a[j + 1] = a[j];
			--j;
		}
		a[l] = x;
	}
}

// O(n^2) : Stable
template <class TItem, class TSize>
void InsertionSort(TItem a[], TSize n) {
	--n;
	for (TSize i = 0; i < n; ++i) {
		item x = a[i + 1];
		TSize j = i;
		while ((x < a[j]) && (j >= 0)) {
			a[j + 1] = a[j];
			--j;
		}
		a[j + 1] = x;
	}
}

// O(n^2)
// (Dual SelectionSort)
template <class TItem, class TSize>
void ShakerSort2(TItem a[], TSize n) {
	TSize i = 0;
	--n;
	while (i < n) {
		TSize min = i;
		TSize max = i;
		for (TSize j = i + 1; j <= n; j++) {
			if (a[j] < a[min]) min = j;
			if (a[max] < a[j]) max = j;
		}
		Swap(a[min], a[i]);
		if (max == i)
			Swap(a[min], a[n]);
		else
			Swap(a[max], a[n]);
		i++; n--;
	}
}

// O(n^2)
template <class TItem, class TSize>
void SelectionSort(TItem a[], TSize n) {
	--n;
	for (TSize i = 0; i < n; ++i) {
		TSize m = i;
		for (TSize j = n; j > i; --j)
			if (a[j] < a[m])
				m = j;
		Swap(a[i], a[m]);
	}
}

// O(n^2): Stable
// (Bidirectional BubbleSort)
template <class TItem, class TSize>
void ShakerSort(TItem a[], TSize n) {
	TSize j, l=1, r=n-1, k=r;
	do {
		for (j = r; j >= l; --j)
			if (a[j] < a[j - 1]) {
				Swap(a[j - 1], a[j]);
				k = j;
			}
		l = k + 1;
		for (j = l; j <= r; ++j)
			if (a[j] < a[j - 1]) {
				Swap(a[j - 1], a[j]);
				k = j;
			}
		r = k - 1;
	} while (l <= r);
}

// O(n^2) : Stable
template <class TItem, class TSize>
void BubbleSort(TItem a[], TSize n) {
	--n;
	for (TSize i = 0; i < n; ++i)
		for (TSize j = n; j > i; --j)
			if (a[j] < a[j - 1])
				Swap(a[j - 1], a[j]);
}

#endif