var delay = 30;
var numCols = 4;
var numElems = 50;
var dcf = {delay:delay,numCols:numCols,numElems:numElems};
const graphlist = {
	//bogo: null,
	bubble: null,
	circle: null,
	cocktail: null,
	comb: null,
	counting: null,
	cycle: null,
	gnome: null,
	heap: null,
	insertion: null,
	//intro: null,
	//library: null,
	merge: null,
	pancake: null,
	//patience: null,
	//permutation: null,
	quick: null,
	radix: null,
	selection: null,
	shell: null,
	sleep: null,
	slow: null,
	stooge: null,
	strand: null
}
const sort = {
	bogo: bogoSort,
	bubble: bubbleSort,
	circle: circleSort,
	cocktail: cocktailSort,
	comb: combSort,
	counting: countingSort,
	cycle: cycleSort,
	gnome: gnomeSort,
	heap: heapSort,
	insertion: insertionSort,
	intro: introSort,
	merge: mergeSort,
	pancake: pancakeSort,
	selection: selectionSort,
	shell: shellSort,
	quick: quickSort,
	radix: radixSort,
	sleep: sleepSort,
	slow: slowSort,
	stooge: stoogeSort,
	strand: strandSort
}
var gui = new dat.GUI();
var numElemsController = gui.add(dcf, 'numElems', 0, 400);
var delayController = gui.add(dcf, 'delay', 0, 700).step(10);
var colController = gui.add(dcf, 'numCols', 0, 4).step(1);
numElemsController.onChange(v => numElems = v);
delayController.onChange(v => delay = v);
colController.onChange(v => numCols = v);
gui.close();
if (!String.prototype.padStart) {
    String.prototype.padStart = function padStart(targetLength,padString) {
        targetLength = targetLength>>0;
        padString = String(padString || ' ');
        if (this.length > targetLength) {
            return String(this);
        }
        else {
            targetLength = targetLength-this.length;
            if (targetLength > padString.length) {
                padString += padString.repeat(targetLength/padString.length);
            }
            return padString.slice(0,targetLength) + String(this);
        }
    };
}
const shuffle = v => {
    for(var j, x, i = v.length; i; j = Math.floor(Math.random() * i), x = v[--i], v[i] = v[j], v[j] = x);
    return v;
};
function EventQueue(_graph) {
	var remaining = [],
		graph = _graph;
	this.push = function(x, y) {
		remaining.push([JSON.parse(JSON.stringify(x)), y]);
	}
	this.pop = function() {
		return remaining.shift();
	}
	this.empty = function() {
		return remaining.length == 0;
	}
	this.run = function() {
		if (this.empty()) {
			finish(graph);
			return;
		}
		var vals = this.pop();
		setGraphVals(graph, vals[0], vals[1]);
		setTimeout(() => {
			this.run();
		}, delay); 
	}
}
function appendBarElems(elem, n) {
	var h0 = 1/n * 200;
	for (var i = 0; i < n; i++) {
		var e = document.createElement('DIV');
		e.classList.add('bar');
		var h = i / n * 200;
		h += h0;
		e.style.height = h + "px";
		if (e.style.height == "0px") e.style.height = "1px";
		e.style.marginTop = 200 - h + "px";
		elem.appendChild(e);
	}
}
function createGraph(n) {
	var graph = document.createElement('SECTION');
	appendBarElems(graph, n);
	return graph;
}
function fillGraphs(tgt, graphs, n) {
	var cols = numCols;
	var rows = n / numCols;
	var glist = [];
	for (var i in graphs) {
		glist.push([i, graphs[i]]);
	}
	for (var i = 0; i < rows; i++) {
		var row = document.createElement("DIV");
		row.classList.add('row');
		var stop;
		for (var j = 0; j < cols; j++) {
			var ind = i * numCols + j;
			if (ind >= glist.length) {
				stop = true;
				if (j < numCols && j > 0) {
					for (var k = j; k < numCols; k++) {
						var b = document.createElement("ARTICLE");
						b.classList.add('graph');
						row.appendChild(b);
					}
				}
				break;
			}
			var a = document.createElement("ARTICLE");
			a.classList.add('graph');
			a.insertAdjacentHTML('beforeend', "<label>" + glist[ind][0] + " sort</label>");
			var g = createGraph(n);
			a.appendChild(g);
			graphs[glist[ind][0]] = a.children[1];
			row.appendChild(a);
			
		}
		tgt.appendChild(row);
		if (stop) break;
	}
	return graphs;
}
function init() {
	var elem = document.querySelector('main');
	elem.innerHTML = "";
	var graphs = fillGraphs(elem, graphlist, numElems);
	scramble(graphs, graphs['bubble']);
	for (var i in graphs) {
		if (sort[i]) startSort(i, graphs[i]);
	} 
}
function scramble(graphs, graph) {
	var arr = [];
	for (var i = 0; i < graph.children.length; i++) {
		arr.push(parseInt(graph.children[i].style.height));
	}
	shuffle(arr);
	/* arr = [88,92,108,32,44,28,40,184,104,120,128,164,188,180,20,68,176,96,84,116,132,112,172,196,148,12,80,160,192,16,48,168,56,100,124,36,8,76,156,24,4,52,140,144,64,60,200,72,152,136]; */
	for (var i in graphs) {
		graphs[i].children = setGraphVals(graphs[i].children, arr);
	}
}
function setGraphVals(graph, arr, changed) {
	if (changed < 0) return;
	if (!(changed instanceof Array)) {
		changed = [changed];
	}
	for (var i = 0; i < graph.length; i++) {
		graph[i].style.height = arr[i] + "px";
		graph[i].style.marginTop = 200 - arr[i] + "px";
		graph[i].classList.remove('active');
		if (changed.indexOf(i) > -1) graph[i].classList.add('active');
	}
	return graph;
}
function finish(graph, i) {
	var i = i || 0;
	if (i == 0 || i >= graph.length) {
		for (var j = 0; j < graph.length; j++) graph[j].classList.remove('active');
		if (i >= graph.length) return;
	}
	if (i > 0) graph[i - 1].classList.remove('active');
	graph[i].classList.add('active');
	graph[i].classList.add('done');
	setTimeout(function() {
		finish(graph, i + 1);
	}, Math.min(delay, 50));
}
function sorted(arr) {
	return arr.toString() == arr.sort((x, y) => x - y).toString();
}
function startSort(which, graph) {
	var arr = [];
	for (var i = 0; i < graph.children.length; i++) {
		arr.push(parseInt(graph.children[i].style.height));
	}
	sort[which](graph.children, arr);
}
function swap(arr, i, j) {
	var temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	return arr;
}
function bubbleSort(graph, arr, inner, _i, _j) {
	var q = new EventQueue(graph);
	_bubbleSort(q, arr);
	q.run();
}
function _bubbleSort(q, arr) {
	var n = arr.length;
	while (n) {
		var newN = 0;
		for (var i = 1; i < n; i++) {
			if (arr[i - 1] > arr[i]) {
				swap(arr, i - 1, i);
				newN = i;
			}
			q.push(arr, i);
		}
		n = newN;
	}
}
function circleSort(graph, arr) {
	var q = new EventQueue(graph);
	while (_circleSort(q, arr, 0, arr.length - 1, 0));
	q.run();
}
function _circleSort(q, arr, lo, hi, swaps) {
	if (lo == hi) return swaps;
	var high = hi,
		low = lo,
		mid = Math.floor((hi - lo) / 2);
	while (lo < hi) {
		if (arr[lo] > arr[hi]) {
			swap(arr, lo, hi);
			swaps++;
			q.push(arr, [lo, hi]);
		}
		lo++;
		hi--;
	}
	if (lo == hi) {
		if (arr[lo] > arr[hi + 1]) {
			swap(arr, lo, hi + 1);
			swaps++;
			q.push(arr, [lo, hi + 1]);
		}
	}
	swaps = _circleSort(q, arr, low, low + mid, swaps);
	swaps = _circleSort(q, arr, low + mid + 1, high, swaps);
	return swaps;
}
function cocktailSort(graph, arr, swapped, inner, _i, _min, _max) {
	var q = new EventQueue(graph);
	_cocktailSort(q, arr);
	q.run();
	/* var swapped = swapped || false;
	var max = _max || arr.length - 1,
		min = _min || 0;
	var i = (_i == null ? (inner != 2 ? min : max) : _i),
		c = -1;
	if (!swapped && inner == 0) { 
		finish(graph); 
		return;
	}
	if (inner == 0 || inner == null) {
		cocktailSort(graph, arr, false, 1, i, min, max);
	} else if (inner == 1) {
		if (i < max) {
			c = i + 1;
			if (arr[i] > arr[i + 1]) {
				swap(arr, i, i + 1);
				swapped = true;
			}
			setGraphVals(graph, arr, c);
			setTimeout(function() {
				cocktailSort(graph, arr, swapped, 1, i + 1, min, max);
			}, delay);
		} else {
			if (!swapped) {
				finish(graph); 
				return;
			}
			cocktailSort(graph, arr, swapped, 2, max - 1, min, max - 1);
		}
	} else if (inner == 2) { 
		if (i >= min) {
			c = i;
			if (arr[i] > arr[i + 1]) {
				swap(arr, i, i + 1);
				swapped = true;
			}  
			setGraphVals(graph, arr, c);
			setTimeout(function() {
				cocktailSort(graph, arr, swapped, 2, i - 1, min, max);
			}, delay); 
		} else { 
			cocktailSort(graph, arr, swapped, 0, min + 1, min + 1, max); 
		}
	} */
}
function _cocktailSort(q, arr) {
	var begin = 0,
		end = arr.length - 1;
	while (begin <= end) {
		var nBegin = end,
			nEnd = begin,
			swapped = false;
		for (var ii = begin; ii <= end; ii++) {
			if (arr[ii] > arr[ii + 1]) {
				swap(arr, ii, ii + 1);
				q.push(arr, ii + 1);
				swapped = true;
				nEnd = ii;
			}
		}
		if (!swapped) break;
		end = nEnd - 1;
		swapped = false;
		for (var ii = end; ii >= begin; ii--) {
			if (arr[ii] > arr[ii + 1]) {
				swap(arr, ii, ii + 1);
				q.push(arr, ii);
				nBegin = ii;
				swapped = true;
			}
		}
		if (!swapped) break;
		begin = nBegin + 1;
	}
}
function combSort(graph, arr) {
	var q = new EventQueue(graph);
	_combSort(q, arr);
	q.run();
}
function _combSort(q, arr) {
	var gap = arr.length - 1,
		swaps;
	while (gap != 1 && swaps != 0) {
		gap = Math.floor(gap / 1.25);
		if (gap < 1) gap = 1;
		var i = 0;
		swaps = 0;
		while (i + gap < arr.length) {
			if (arr[i] > arr[i + gap]) {
				swap(arr, i, i + gap);
				swaps = 1;
			}
			q.push(arr, [i + gap, i]);
			i++;
		}
	}
}
function countingSort(graph, arr) {
	var q = new EventQueue(graph);
	_countSort(q, arr);
	q.run();
}
function _countSort(q, arr) {
	var z = 0,
		count = [],
		min = Math.min(...arr),
		max = Math.max(...arr);
    for (var i = min; i <= max; i++) {
        count[i] = 0;
    }
    for (var i = 0; i < arr.length; i++) {
        count[arr[i]]++;
		q.push(arr, i);
    }
    for (var i = min; i <= max; i++) {
        while (count[i]-- > 0) {
            arr[z++] = i;
			q.push(arr, z - 1);
        }
    }
}
function cycleSort(graph, arr) {
	var q = new EventQueue(graph);
	_cycleSort(q, arr);
	q.run();
}
function _cycleSort(q, arr) {
	var w = 0;
	for (var start = 0; start < arr.length - 1; start++) {
		var val = arr[start];
		var pos = start;
		for (var i = start + 1; i < arr.length; i++) {
			//q.push(arr, i);
			if (arr[i] < val) pos++;
		}
		if (pos == start) continue;
		while (val == arr[pos]) pos++;
		var tmp = arr[pos];
		arr[pos] = val;
		val = tmp;
		q.push(arr, [pos, start]);
		w++;
		
		while (pos != start) {
			pos = start;
			for (var i = start + 1; i < arr.length; i++) {
				q.push(arr, i);
				if (arr[i] < val) pos++;
			}
			while (val == arr[pos]) pos++;
			var tmp = arr[pos];
			arr[pos] = val;
			val = tmp;
			q.push(arr, pos);
			w++;
		}
	}
	return w;
}
function gnomeSort(graph, arr) {
	var q = new EventQueue(graph);
	_gnomeSort(q, arr);
	q.run();
}
function _gnomeSort(q, arr) {
	var i = 1,
		j = 2;
	while (i < arr.length) {
		if (arr[i - 1] <= arr[i]) {
			q.push(arr, i)
			i = j;
			j++;
		} else {
			swap(arr, i - 1, i);
			q.push(arr, i - 1);
			i--;
			if (i == 0) {
				i = j;
				j++;
			}
		}
	}
}
function heapSort(graph, arr) {
	var q = new EventQueue(graph);
	_heapSort(q, arr);
	q.run();
}
function _heapSort(q, arr) {
	_heapify(q, arr);
	var end = arr.length - 1;
	while(end > 0) {
		swap(arr, 0, end);
		q.push(arr, end);
		_heap_sift_down(q, arr, 0, end);
		end--;
	}
}
function _heapify(q, arr) {
	var i = Math.floor(arr.length / 2 - 1);
	while (i >= 0) {
		_heap_sift_down(q, arr, i, arr.length);
		i--;
	}
}
function _heap_sift_down(q, heap, i, max) {
	var iBig, c1, c2;
	while (i < max) {
		iBig = i;
		c1 = 2 * i + 1;
		c2 = c1 + 1;
		if (c1 < max && heap[c1] > heap[iBig]) iBig = c1;
		if (c2 < max && heap[c2] > heap[iBig]) iBig = c2;
		if (iBig == i) return;
		swap(heap, i, iBig);
		q.push(heap, iBig);
		i = iBig;
	}
}
function insertionSort(graph, arr, inner, _i, _j) {
	var q = new EventQueue(graph);
	_insertionSort(q, arr);
	q.run();
}
function _insertionSort(q, arr) {
	for (var i = 1; i < arr.length; i++) {
		var x = arr[i],
			j = i - 1;
		while (j >= 0 && arr[j] > x) {
			arr[j + 1] = arr[j];
			q.push(arr, j + 1);
			j--;
		}
		arr[j + 1] = x;
		q.push(arr, j + 1);
	}
}
function introSort(graph, arr) {
	var q = new EventQueue(graph);
	_introSort(q, arr, Math.ceil(Math.abs(Math.log(arr.length)) * 2));
	q.run();
}
function _introSort(q, arr, maxDepth) {
	var n = arr.length;
	if (n <= 1) return;
	else if (maxDepth == 0) _heapSort(q, arr);
	else {
		var p = _partition(q, arr, 0, arr.length - 1);
		_introSort(q, arr.slice(0, p), maxDepth - 1);
		_introSort(q, arr.slice(p + 1, n), maxDepth - 1);
		//q.push(arr, maxDepth)
	}
}
function mergeSort(graph, arr) {
	var q = new EventQueue(graph);
	_mergeSort(q, arr);
	q.run();
}
function _mergeSort(q, arr) {
	if (arr.length == 1) return;
	var mid = Math.floor(arr.length / 2),
		left = arr.slice(0, mid),
		right = arr.slice(mid);
	_mergeSort(q, left);
	_mergeSort(q, right);
	_merge(q, arr, left, right);
}
function _merge(q, arr, left, right) {
	var a = 0;
	while (left.length && right.length) {
		arr[a++] = (right[0] < left[0] ? right.shift() : left.shift());
		q.push(arr, a - 1);
	}
	while (left.length) {
		arr[a++] = left.shift();
		q.push(arr, a - 1);
	}
	while (right.length) {
		arr[a++] = right.shift();
		q.push(arr, a - 1);
	}
}
function pancakeSort(graph, arr) {
	var q = new EventQueue(graph);
	_pancakeSort(q, arr);
	q.run();
}
function _pancakeSort(q, arr) {
	for (var i = arr.length - 1; i >= 1; i--) {
        var maxIdx = 0;
        var max = arr[0];
        for (var j = 1; j <= i; j++) {
            if (arr[j] > max) {
                max = arr[j];
                maxIdx = j;
            }
        }
        if (maxIdx == i) 
            continue;
        var newSlice;
        if (maxIdx > 0) {
            newSlice = arr.slice(0, maxIdx + 1).reverse();
            for (var j = 0; j <= maxIdx; j++) {
                arr[j] = newSlice[j];
				q.push(arr, j);
			}
        }
        newSlice = arr.slice(0, i + 1).reverse();
        for (var j = 0; j <= i; j++) {
            arr[j] = newSlice[j];
			q.push(arr, j);
		}
    }
    return arr;
}
function bogoSort(graph, arr) {
	if (sorted(arr)) {
		finish(graph);
		return;	
	}
	var g = shuffle(arr);
	setGraphVals(graph, g, 'bogo');
	setTimeout(function() {
		bogoSort(graph, g);
	}, delay);
}
function selectionSort(graph, arr) {
	var q = new EventQueue(graph);
	_selectionSort(q, arr);
	q.run();
}
function _selectionSort(q, arr) {
	var i, j, n = arr.length;
	for (j = 0; j < n - 1; j++) {
		var iMin = j;
		for (i = j + 1; i < n; i++) {
			if (arr[i] < arr[iMin]) iMin = i;
			q.push(arr, i);
		}
		if (iMin != j) swap(arr, j, iMin);
		q.push(arr, j);
	}
}
function shellSort(graph, arr) {
	var q = new EventQueue(graph);
	_shellSort(q, arr);
	q.run();
}
function _shellSort(q, arr) {
	var gaps = [701, 301, 132, 57, 23, 10, 4, 1];
	for (var g in gaps) {
		var gap = gaps[g];
		for (var i = gap; i < arr.length; i++) {
			var temp = arr[i];
			for (var j = i; j >= gap & arr[j - gap] > temp; j -= gap) {
				arr[j] = arr[j - gap];
				q.push(arr, j);
			}
			arr[j] = temp;
			q.push(arr, j);
		}
	}
}
function quickSort(graph, arr) {
	var q = new EventQueue(graph);
	_quickSort(q, arr, 0, arr.length - 1)
	q.run();
}
function _quickSort(q, arr, lo, hi) {
	if (lo < hi) {
		var p = _partition(q, arr, lo, hi);
		_quickSort(q, arr, lo, p - 1);
		_quickSort(q, arr, p + 1, hi);
	}
}
function _partition(queue, arr, lo, hi) {
	var pivot = arr[hi];
	var i = lo - 1;
	for (var j = lo; j < hi; j++) {
		if (arr[j] < pivot) {
			i++;
			swap(arr, i, j);
			queue.push(arr, [i, hi]);
		}
	}
	swap(arr, i + 1, hi);
	queue.push(arr, [i + 1, hi]);
	return i + 1;
}
function radixSort(graph, arr) {
	var q = new EventQueue(graph);
	_radixSort(q, arr);
	q.run();
}
function _radixSort(q, arr) {
	arr = arr.map(x => x.toString());
	var numDigits = Math.max(...arr.map(x => x.length));
	arr = arr.map(x => x.padStart(numDigits, '0'));
	var buckets = [[],[],[],[],[],[],[],[],[],[]];
	for (var i = 0; i < numDigits; i++) {
		for (var j = 0; j < arr.length; j++) { // enqueue
			var num = parseInt(arr[j][arr[j].length - 1 - i]);
			buckets[num].push(arr[j]);
			q.push(arr, j);
		}
		var res = [];
		for (var j = 0; j < buckets.length; j++) { // dequeue
			while (buckets[j].length) {
				res.push(buckets[j].shift());
			}
		}
		arr = res;
		q.push(arr, '')
	}
}
function sleepSort(graph, arr) {
	var _sleepInd = 0;
	var _sleepSet = function(arr, x) {
		arr[_sleepInd++] = x;
	}
	var q = new EventQueue(graph);
	_sleepInd = 0;
	_sleepSort(q, arr, _sleepSet).then(() => {
		q.run();
	})
}
function _sleepSort(q, arr, set) {
	return new Promise((resolve, reject) => {
		var max = Math.max(...arr);
		var a = JSON.parse(JSON.stringify(arr));
		for (let i = 0; i < a.length; i++) {
			setTimeout(function() {
				set(arr, a[i]);
				q.push(arr, i);
				if (a[i] == max) resolve();
			}, a[i] * 20);
		}
	})
}
function slowSort(graph, arr) {
	var q = new EventQueue(graph);
	_slowSort(q, arr, 0, arr.length - 1);
	q.run();
}
function _slowSort(q, arr, i, j) {
	if (i >= j) return; 
	var m = Math.abs(Math.floor((i + j) / 2));
	_slowSort(q, arr, i, m);
	_slowSort(q, arr, m + 1, j);
	if (arr[j] < arr[m]) {
		swap(arr, j, m);
	}
		q.push(arr, j);
	_slowSort(q, arr, i, j - 1);
}
function stoogeSort(graph, arr) {
	var q = new EventQueue(graph);
	_stoogeSort(q, arr, 0, arr.length - 1);
	q.run();
}
function _stoogeSort(q, arr, i, j) {
	if (arr[j] < arr[i]) {
		swap(arr, i, j);
	}
	if (j - i > 1) {
		q.push(arr, [i, j])
		var t = Math.floor((j - i + 1) / 3);
		_stoogeSort(q, arr, i, j - t);
		_stoogeSort(q, arr, i + t, j);
		_stoogeSort(q, arr, i, j - t);
	}
}
function strandSort(graph, arr) {
	var q = new EventQueue(graph);
	_strandSort(q, arr);
	q.run();
}
function _strandSort(q, arr) {
	var result = [];
	//return;
	while (arr.length) {
		var sorted = [];
		var remain = [];
		sorted.push(arr.shift());
		for (var i = 0; i < arr.length; i++) {
			q.push(arr, i);
			if (sorted[sorted.length - 1] <= arr[i]) {
				sorted.push(arr[i]);
			} else {
				remain.push(arr[i]);
			}
		}
		result = _strandMerge(q, sorted, result);
		arr = remain;
		q.push(result, result.length - 1);
	}
	return result;
}
function _strandMerge(q, left, right) {
	var res = [];
	while (left.length && right.length) {
		if (left[0] <= right[0]) {
			res.push(left.shift());
		} else {
			res.push(right.shift());
		}
		q.push(res, res.length - 1);
	}
	while (left.length) {
		res.push(left.shift());
		q.push(res, res.length - 1);
	}
	while (right.length) {
		res.push(right.shift());
		q.push(res, res.length - 1);
	}
	return res;
}

document.getElementById('run').addEventListener('click', function(e) {
	init();
});
init();