<?php

/*
 *
 * @author: barce[a t]codebley.com
 */
// create an array of random numbers

$data_size   = 1000;
$i_buckets   = 10;
$bucket_size = $data_size / $i_buckets;

$i_sent = 1;

// TODO: improve the algorithm below b/c it can take really long
while($i_sent > 0) {
	$i_rand = rand(1, $data_size);
	if (!in_array($i_rand, $a_list)) {
		$a_list[] = $i_rand;
	}
	if (count($a_list) == $data_size) {
		$i_sent = 0;
	}
}


print "here's what we've got:\n";
foreach($a_list as $item) {
	print "$item ";
}
print "\n";


$bsorter = new BucketSorter($a_list, $bucket_size, $i_buckets);
$bsorter->bucketize();
$bsorter->sortBuckets();
// print_r($bsorter->a_buckets);
$a_sorted_list = $bsorter->sortedResults();
print "here's what we've got sorted:\n";
foreach($a_sorted_list as $item) {
	print "$item ";
}
print "\n";


class BucketSorter {

	var $a_list;
	var $i_buckets;
	var $list_size;
	var $bucket_size;
	var $a_buckets;
	var $a_sorted;
	

	function __construct($a_list, $bucket_size, $i_buckets) {
		$this->a_list      = $a_list;
		$this->i_buckets   = $i_buckets;
		$this->list_size   = count($a_list);
		$this->bucket_size = $bucket_size;
		// $this->bucket_size = $this->list_size / $i_buckets;

		// make buckets
		for ($i = 1; $i <= $i_buckets; $i++) {
			$i_multiple = $i * $this->bucket_size;
			$this->a_buckets[$i_multiple] = array();
		}
	}

	/*
	 * This function puts the input into buckets
	 */
	function bucketize() {

		$i_sent = 1;
		$j = 1;

		for ($i = 0; $i < $this->list_size; $i++) {
			while ($i_sent > 0) {
				// we bucket based on multiples of bucket_size
				$i_multiple = $j * $this->bucket_size; 
				if ($this->a_list[$i] <= $i_multiple) {
					array_unshift($this->a_buckets[$i_multiple], $this->a_list[$i]);
					$i_sent = 0;
				}
				if ($j >= $this->i_buckets) { $i_sent = 0; }
				$j++;
			}
			$i_sent = 1;
			$j = 1;
		}
	}

	/*
	 * Each bucket is sorted using an insert_sort
	 */
	function sortBuckets() {
		for ($i = 1; $i <= $this->i_buckets; $i++) {
			$i_multiple = $i * $this->bucket_size;
			$this->a_buckets[$i_multiple] = 
				insert_sort($this->a_buckets[$i_multiple]);
		}

	}

	function sortedResults() {
		$a_sorted_array = array();
		for ($i = 1; $i <= $this->i_buckets; $i++) {
			$i_multiple = $i * $this->bucket_size;
			foreach ($this->a_buckets[$i_multiple] as $item) {
				$a_sorted_array[] = $item;
			}

		}
		return $a_sorted_array;

	}


}

function insert_sort($a_bucket) {
	$data_size = count($a_bucket); 
	$i_limit = $data_size - 1;

	for ($i = 1; $i < $data_size; $i++) {
		$tmp = $a_bucket[$i];
		$j = $i - 1;
		while (($j >=0) && ($a_bucket[$j] > $tmp)) {
			$a_bucket[$j+1] = $a_bucket[$j];
			$j--;
		}
		$a_bucket[$j+1] = $tmp;
	}
	return $a_bucket;
}

?>