//total size of list
#define LISTSIZE 2000000
//range of nums within the list
#define RANGE 1000

//for printing to stdout
#include <iostream>
//for rand() & srand()
#include <cstdlib>
//to seed srand()
#include <ctime>
//for GetTickCount()
#include "windows.h"
//our actual class
#include "bucketsort.cpp"

using namespace std;

int main()
{
	//vars for tick count
	//correct microsoft data type is DWORD, but it works with long w/no difference
	long start, stop;

	//instantiate our object that does the work
	bucketsort<int> a;

	//this is our sample deque
	deque<int> s;

	//seed rand()
	srand(time(NULL));

	//fill our input deque with numbers from 1-RANGE
	/*for(int i = 0; i < LISTSIZE; i++)
	{
		s.push_back(rand() % RANGE);
	}*/

	for(int i = 0; i < LISTSIZE; i++)
	{
		s.push_back(rand() % RANGE);
	}

	for(int i = 0; i < LISTSIZE; i++)
	{
		s.push_back((rand() % RANGE) * -1);
	}

	for(int i = 0; i < LISTSIZE; i++)
	{
		s.push_back(rand() % RANGE);
	}

	for(int i = 0; i < LISTSIZE; i++)
	{
		s.push_back((rand() % RANGE) * -1);
	}

	for(int i = 0; i < LISTSIZE; i++)
	{
		s.push_back(rand() % RANGE);
	}

	for(int i = 0; i < LISTSIZE; i++)
	{
		s.push_back((rand() % RANGE) * -1);
	}

	for(int i = 0; i < LISTSIZE; i++)
	{
		s.push_back(rand() % RANGE);
	}
	
	cout<<"\nbefore sort:"<<endl;
	//a.print(s);

	cout<<"\nSorting...\n"<<endl;

	//start time
	start = GetTickCount();
	
	//sort the list
	a.splitsort(s);

	//stop time
	stop = GetTickCount();

	cout<<"\n\nafter sort:"<<endl;
	//a.print(s);

	//print time to sort
	cout<<"\ntime to sort is "<<stop - start<<" milliseconds."<<endl;

	return 0;
}

#include <deque>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

template <class T>
class bucketsort
{
public:
	void sort(deque<T> &);
	void splitsort(deque<T> &);
	void print(deque<T> &);
};

template <class T>
void bucketsort<T>::print(deque<T> & x)
{
	//instantiate our iterator
	std::deque<T>::iterator itr; 

	//from start to end cout<< the dereferenced iterator
	//(the value currently pointed at)
	for(itr = x.begin(); itr != x.end(); ++itr)
	{
		cout<<*itr<<" ";
	}
	cout<<endl;
}

template <class T>
void bucketsort<T>::sort(deque<T> & d)
{
	//save deque size to prevent calling this function more than once
	int size = d.size();

	//find the biggest element in the deque
	//value of (max_element returns a pointer so we dereference it
	double range = *max_element(d.begin(), d.end());

	T* unsorted = new T[size];

	for(int x = 0; x < size; x++)
	{
		unsorted[x] = d.front();
		d.pop_front();
	}

	//uncomment to see the biggest element DEBUGGING CODE
	//cout<<range<<"\n"<<endl;

	//looping vars
	int i = 0, j = 0;

	//our buckets (+1 so indices will match elements)
	deque<T> buckets(range + 1);

	//set all vals in buckets to zero
	//the first part of the loop is empty
	//b/c i already == zero, so we don't have to declare extra crap.
	for(; i < range; i++) buckets[i] = 0;
	
	//fill each bucket with vals
	//if a val within range exists increment that bucket
    for(i = 0; i < size; i++) ++buckets[unsorted[i]];

	//here's the crazy sorting part...
	//if the bucket is empty we move on,
	//else we push that onto our sorted deque
	//decrement each bucket until its empty
	//then we stick the next val into our deque
	//there's a lot of weird crap going on in this line
	//that could have been split up, but i like weird code
	for(i = 0; i < range + 1; i++) while(buckets[i]-- != 0) unsorted[j++] = i;

	for(int y = 0; y < size; y++) d.push_back(unsorted[y]);

	delete [] unsorted;


	//uncomment the below line if you want to see the buckets
	//and what they hold DEBUGGING CODE
	//for(int k = 0; k < range + 1; k++) cout<<buckets[k]<<" "<<endl;
}

template <class T>
void bucketsort<T>::splitsort(deque<T> & d)
{
	deque<T> neg;
	deque<T> pos;

	//fill up neg and pos
	while(!d.empty())
	{
		if(d.front() < 0)
		{
			//convert each element of neg to a positive # for bucketsort
			neg.push_back(-1 * d.front());
			d.pop_front();
		}
		else
		{
			//otherwise put the # in pos
			pos.push_back(d.front());
			d.pop_front();
		}
	}

	//sort both lists
	sort(neg);
	sort(pos);

	//put neg numbers back in
	while(!neg.empty())
	{
		//multiply each # of sorted neg deck by -1 to convert back to negative
		//and then push it back into the original deque from the back
		d.push_back(neg.back() * -1);
		neg.pop_back();
	}

	//put pos numbers back in
	while(!pos.empty())
	{
		d.push_back(pos.front());
		pos.pop_front();
	}
}