/*
 *  BucketSort (Distrubution Counting)
 *
 *  21.11.1998, implemented by Michael Neumann (neumann@s-direktnet.de)
 */

# ifndef __BUCKETSORT_HEADER__
# define __BUCKETSORT_HEADER__

# include <algorithm>


// itemType must have an typecast to "int", which identifies the sortkey
template <class itemType, class indexType=int>
class BucketSort {
public:

	// the array b[] had to be the same size like a[]
	void Sort(itemType a[], itemType b[], indexType l, indexType r) {
   	a = &a[l]; b = &b[l];
		for(int i=0; i<sizeof(int); ++i) {
      	sort_byte(i,a,b,r-l+1);
         std::swap(a,b);
      }
   }

protected:
	sort_byte(int bytenr, itemType a[], itemType b[], indexType count) {
   	static indexType i;
      typedef unsigned char* UCP;

      for(i=0; i<256; ++i) occurences[i] = 0;	// better: memset
      for(i=0; i<count; ++i) ++occurences[((UCP)&a[i])[bytenr]];
    	for(i=1; i<256; ++i) occurences[i] += occurences[i-1];
      for(i=count-1; i>=0; --i)
      	b[--occurences[((UCP)&a[i])[bytenr]]] = a[i];
   }

	int occurences[256];
};

# endif