Skip to content

Instantly share code, notes, and snippets.

@allanlw
Created January 21, 2017 01:10
Show Gist options
  • Save allanlw/52fcbdea965b1862786ecf2dbf5ac3b6 to your computer and use it in GitHub Desktop.
Save allanlw/52fcbdea965b1862786ecf2dbf5ac3b6 to your computer and use it in GitHub Desktop.
Human Sort
<!DOCTYPE html>
<!--
This is a simple script to manually heap sort images.
It loads images from a relative file filelist.txt, which is a list of image (really page) URIs
separate by new lines.
It will prompt the user for comparisons. Press the A key for left image or F key for the right image.
When it's done it logs to console.log.
The status bar displays three counts: R/H/I
- R: The size of the result (e.g. that has been POPd from the heap)
- H: the size of the heap
- I: the total number of inputs.
Reasonable improvements would be:
- Using an N-ary heap instead of a binary heap, so that many options can be displayed at once.
-->
<style>
body, html {
margin: 0px;
padding: 0px;
width: 100%;
height: 100%;
}
#container {
top: 2em;
left: 0px;
right: 0px;
bottom: 0px;
position: absolute;
}
#a, #b {
width: 48%;
height: 100%;
border: 1px solid black;
float: left;
}
</style>
<span id="info"></span>
<div id="container">
<iframe id="a"></iframe>
<iframe id="b"></iframe>
</div>
<script>
var inputfiles, heap, httpRequest, promiseAccept, res;
async function doSorting(input) {
heap = new BinaryHeap(cmpFunc);
res = [];
for (var i = 0; i < input.length; i++) {
await heap.push(input[i]);
}
for (var i = 0; i < input.length; i++) {
res.push(await heap.pop());
}
return res;
}
function handleList() {
if (!(httpRequest.readyState === XMLHttpRequest.DONE && httpRequest.status === 200)) {
return;
}
inputfiles = httpRequest.responseText.split("\n").filter(function(x) { return x.length > 0; });
doSorting(inputfiles).then(function(x) {
console.log(x);
alert("Done!");
});
}
// Returns -1 if a is a better than b, else returns 1
function cmpFunc(a, b) {
document.getElementById("info").innerText = (
res.length + "/" + heap.size() + "/" + inputfiles.length + " -- " + a + " " + b
);
var x = document.getElementById("a");
var y = document.getElementById("b");
x.src = a;
y.src = b;
console.log("cmp2 " + a + " , "+ b)
return new Promise(function(accept) {
promiseAccept = accept;
});
}
document.onkeypress = function(e) {
if (e.key == 'a') {
promiseAccept(-1);
} else if (e.key == 'f') {
promiseAccept(1);
}
}
// Notes on sorting algorith choice.
// We _really_ care about the number of comparisons because of the human factor,
// so the worst-case complexity can't be more than n log n.
// We also can't parallelize, so this is not an issue.
// It's also better if the comparissons can be disparate. repeatedly comparing against
// the same image isn't great for the human (e.g. pivots and merges can be bad!)
// obviously some of this can't be avoided though.
// for all these reasons, we use heapsort.
// this implementation is a modified version of the one at:
// http://eloquentjavascript.net/1st_edition/appendix2.html
// This code is CC-BY Marijn Haverbeke
// the use of a score function has been replaced with an async compare function
function BinaryHeap(cmpFunction){
this.content = [];
this.cmpFunction = cmpFunction;
}
BinaryHeap.prototype = {
push: async function(element) {
// Add the new element to the end of the array.
this.content.push(element);
// Allow it to bubble up.
return this.bubbleUp(this.content.length - 1);
},
pop: async function() {
// Store the first element so we can return it later.
var result = this.content[0];
// Get the element at the end of the array.
var end = this.content.pop();
// If there are any elements left, put the end element at the
// start, and let it sink down.
if (this.content.length > 0) {
this.content[0] = end;
await this.sinkDown(0);
}
return result;
},
size: function() {
return this.content.length;
},
bubbleUp: async function(n) {
// Fetch the element that has to be moved.
var element = this.content[n];
// When at 0, an element can not go up any further.
while (n > 0) {
// Compute the parent element's index, and fetch it.
var parentN = Math.floor((n + 1) / 2) - 1,
parent = this.content[parentN];
// If the parent has a lesser score, things are in order and we
// are done.
if (await this.cmpFunction(element, parent) > 0)
break;
// Otherwise, swap the parent with the current element and
// continue.
this.content[parentN] = element;
this.content[n] = parent;
n = parentN;
}
},
sinkDown: async function(n) {
// Look up the target element and its score.
var length = this.content.length,
element = this.content[n];
while(true) {
// Compute the indices of the child elements.
var child2N = (n + 1) * 2, child1N = child2N - 1;
// This is used to store the new position of the element,
// if any.
var swap = null;
// If the first child exists (is inside the array)...
if (child1N < length) {
// Look it up and compute its score.
var child1 = this.content[child1N];
// If the child is better than the element, we need to swap
if (await this.cmpFunction(child1, element) < 0)
swap = child1N;
}
// Do the same checks for the other child.
if (child2N < length) {
var child2 = this.content[child2N];
// if the NEW element is in position child2n is better than what's in position
// n, we need to swap
if (await this.cmpFunction(swap == null ? element : child1, child2) > 0)
swap = child2N;
}
// No need to swap further, we are done.
if (swap == null) break;
// Otherwise, swap and continue.
this.content[n] = this.content[swap];
this.content[swap] = element;
n = swap;
}
}
};
var httpRequest = new XMLHttpRequest();
httpRequest.onreadystatechange = handleList;
httpRequest.open('GET', 'filelist.txt');
httpRequest.send();
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment