allanlw · January 21, 2017 01:10
diff --git a/index.html b/index.html
 <!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>
	<!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>