<?php
/********** Generating sorted structure (array / SplMaxHeap): *************/

function generateSorted($start = 300000, $elementsNum = 10000, $dev = 30, $heap = false){
	$sorted = $heap ? new SplMaxHeap() : array();
	for($i = 1; $i <= $elementsNum; $i++){
		$rand = mt_rand(1, $dev);
		$start -= $rand;
		if(!$heap){
			$sorted[] = $start;
		}else{
			$sorted->insert($start); 
		}
	}
	return $sorted;
}

/********************** Four insert functions: **************************/

// for loop, and array copying
function insert1(&$arr, $elem){
	if(empty($arr)){
		$arr[] = $elem;
		return true;
	}
	$c = count($arr);
	$lastIndex = $c - 1;
	$tmp = array();
	$inserted = false;
	for($i = 0; $i < $c; $i++){
		if(!$inserted && $arr[$i] <= $elem){
			$tmp[] = $elem;
			$inserted = true;
		}
		$tmp[] = $arr[$i];
		if($lastIndex == $i && !$inserted) $tmp[] = $elem;
	}
	$arr = $tmp;
	return true;
}

// new element inserted at the end of array 
// and moved up until correct place
function insert2(&$arr, $elem){
	$c = count($arr);
	array_push($arr, $elem);
	for($i = $c; $i > 0; $i--){
		if($arr[$i - 1] >= $arr[$i]) break;
		$tmp = $arr[$i - 1];
		$arr[$i - 1] = $arr[$i];
		$arr[$i] = $tmp;
	}
	return true;
}

// binary search for correct place + array_splice() to insert element
function insert3(&$arr, $elem){
	$startIndex = 0;
	$stopIndex = count($arr) - 1;
	$middle = 0;
	while($startIndex < $stopIndex){
		$middle = ceil(($stopIndex + $startIndex) / 2);
		if($elem > $arr[$middle]){
			$stopIndex = $middle - 1;
		}else if($elem <= $arr[$middle]){
			$startIndex = $middle;
		}
	}
	$offset = $elem >= $arr[$startIndex] ? $startIndex : $startIndex + 1; 
	array_splice($arr, $offset, 0, array($elem));
}

// for loop to find correct place + array_splice() to insert
function insert4(&$arr, $elem){
	$c = count($arr);
	$inserted = false;
	for($i = 0; $i < $c; $i++){
		if($elem >= $arr[$i]){
			array_splice($arr, $i, 0, array($elem));
			$inserted = true;
			break;
		}
	}
	if(!$inserted) $arr[] = $elem;
	return true;
}

/*********************** Speed tests: *************************/

// check if array is sorted descending
function checkIfArrayCorrect($arr, $expectedCount = null){
	$c = count($arr);
	if(isset($expectedCount) && $c != $expectedCount) return false;
	$correct = true;
	for($i = 0; $i < $c - 1; $i++){
		if(!isset($arr[$i + 1]) || $arr[$i] < $arr[$i + 1]){
			$correct = false;
			break;
		}
	}
	return $correct;
}
// claculates microtimetime diff
function timeDiff($startTime){
	$diff = microtime(true) - $startTime;
	return $diff;
}
// prints formatted execution time info
function showTime($func, $time){
	printf("Execution time of %s(): %f s\n", $func, $time);
}
// generated elements num
$elementsNum = 10000;
// generate starting point
$start = 300000;
// generated elements random range  1 - $dev
$dev = 50;


echo "Generating array with descending order, $elementsNum elements, begining from $start\n";
$startTime = microtime(true);
$arr = generateSorted($start, $elementsNum, $dev);
showTime('generateSorted', timeDiff($startTime));

$step = 2;
echo "Generating second array using range range(), $elementsNum elements, begining from $start, step $step\n";
$startTime = microtime(true);
$arr2 = range($start, $start - $elementsNum * $step, $step);
showTime('range', timeDiff($startTime));

echo "Generating SplMaxHeap, $elementsNum elements, begining from $start\n";
$startTime = microtime(true);
$heap = generateSorted($start, $elementsNum, $dev, true);
showTime('SplMaxHeap', timeDiff($startTime));

echo "Checking if array is correct\n";
$startTime = microtime(true);
$sorted = checkIfArrayCorrect($arr, $elementsNum);
showTime('checkIfArrayCorrect', timeDiff($startTime));

if(!$sorted) die("Array is not in descending order!\n");
echo "Array OK\n";

$toInsert = array();

// number of elements to insert from every range
$randElementNum = 20;

// some ranges of elements to insert near begining, middle and end of generated array
// start value => end value
$ranges = array(
	300000 => 280000,
	160000 => 140000,
	30000 => 0,
);
foreach($ranges as $from => $to){
	$values = array();
	echo "Generating $randElementNum random elements from range [$from - $to] to insert\n";
	while(count($values) < $randElementNum){
		$values[mt_rand($from, $to)] = 1;
	}
	$toInsert = array_merge($toInsert, array_keys($values));
}
// some elements to insert on begining and end of array
array_push($toInsert, 310000);
array_push($toInsert, -1000);

echo "Generated elements: \n";
for($i = 0; $i < count($toInsert); $i++){
	if($i > 0 && $i % 5 == 0) echo "\n";
	printf("%8d, ", $toInsert[$i]);
	if($i == count($toInsert) - 1) echo "\n";
}
// functions to test
$toTest = array('insert1' => null, 'insert2' => null, 'insert3' => null, 'insert4' => null);
foreach($toTest as $func => &$time){
	echo "\n\n================== Testing speed of $func() ======================\n\n";
	$tmpArr = $arr;
	$startTime = microtime(true);
	for($i = 0; $i < count($toInsert); $i++){
		$func($tmpArr, $toInsert[$i]);
	}
	$time = timeDiff($startTime);
	showTime($func, $time);
	echo "Checking if after using $func() array is still correct: \n";
	if(!checkIfArrayCorrect($tmpArr, count($arr) + count($toInsert))){
		echo "Array INCORRECT!\n\n";
	}else{
		echo "Array OK!\n\n";
	}
	//echo "Few elements from begining of array:\n";
	//print_r(array_slice($tmpArr, 0, 5));
	
	//echo "Few elements from end of array:\n";
	//print_r(array_slice($tmpArr, -5));

	//echo "\n================== Finished testing $func() ======================\n\n";
}

echo "\n\n================== Testing speed of SplMaxHeap::insert() ======================\n\n";
$startTime = microtime(true);
for($i = 0; $i < count($toInsert); $i++){
	$heap->insert($toInsert[$i]);
}
$time = timeDiff($startTime);
showTime('SplMaxHeap::insert', $time);
$toTest['SplMaxHeap::insert'] = $time;
echo "\n\n================== Functions time summary  ======================\n\n";
foreach($toTest as $func => $time){
	printf("%18s() => %.10f\n", $func, $time);
}