var gIntervalTimeout = 10;  // milli seoncnds
var gInitialTimeout = 300;
var gBackgroundColor = "pink";

function swap(array, i, j) {
  var tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
}

function partition(data, offset, length) {
  var pivot = data[offset];
  var pivotPos = offset;
  for (var i = offset + 1; i < offset + length; ++i) {
    if (data[i] < pivot) {
      swap(data, pivotPos, i);
      ++pivotPos;
      swap(data, pivotPos, i);
    }
  }
  return pivotPos;
}

function quickSort(data) {
  // For the sake of redrawing, we need to break down the
  // recursive calls into a loop using setTimeout().
  var stack = [];
  stack.push([0, data.length]);
  var loop = function() {
    if (stack.length > 0) {
      var top = stack.pop();
      var offset = top[0];
      var length = top[1];
      if (length > 1) {
        var middlePos = partition(data, offset, length);
        stack.push([middlePos + 1, offset + length - middlePos - 1]);
        stack.push([offset, middlePos - offset]);
        showData(data);
      }
      setTimeout(loop, gIntervalTimeout);
    }
  }
  showData(data);
  setTimeout(loop, gInitialTimeout);
}

function bubbleSort(data) {
  var i = 0;
  var loop = function() {
    if (i < data.length - 1) {
      for (var j = data.length - 1; j > i; j--) {
        if (data[j - 1] > data[j]) {
          swap(data, j -1, j);
        }
      }
      ++i;
      showData(data);
      setTimeout(loop, gIntervalTimeout);
    }
  }
  showData(data);
  setTimeout(loop, gInitialTimeout);
}

function insertionSort(data) {
  var i = 0;
  var loop = function() {
    if (i < data.length) {
      var j = i;
      while (j >= 1 && data[j - 1] > data[j]) {
        swap(data, j, j - 1);
        --j;
      }
      ++i;
      showData(data);
      setTimeout(loop, gIntervalTimeout);
    }
  }
  showData(data);
  setTimeout(loop, gInitialTimeout);
}

function selectionSort(data) {
  var i = 0;
  var loop = function() {
    if (i < data.length - 1) {
      var indexOfSmallestValue = i;
      for (var j = i; j < data.length; ++j) {
        if (data[j] < data[indexOfSmallestValue]) {
          indexOfSmallestValue = j;
        }
      }
      swap(data, i, indexOfSmallestValue);
      ++i;
      showData(data);
      setTimeout(loop, gIntervalTimeout);
    }
  }
  showData(data);
  setTimeout(loop, gInitialTimeout);
}

function shellSort(data) {
  var h;
  for (h = 1; h < Math.floor(data.length / 9);  h = h * 3 + 1) {
  }

  // It's a pain to transform nested two "for" loops into
  // setTimeout equivalents.
  var loop = function() {
    if (h > 0) {
      var i = h;
      var loop2 = function() {
        if (i < data.length) {
          var j = i;
          while (j >= h && data[j - h] > data[j]) {
            swap(data, j, j - h);
            j -= h;
          }
          ++i;
          showData(data);
          setTimeout(loop2, gIntervalTimeout);
        } else {
          h = Math.floor(h / 3);
          setTimeout(loop, gIntervalTimeout);
        }
      }
      setTimeout(loop2, gIntervalTimeout);
    }
  }
  showData(data);
  setTimeout(loop, gInitialTimeout);
}

function heapSortInternalOrig(data) {
  var n = data.length - 1;
  for (var i = Math.floor(n / 2); i >= 1; --i) {
    downHeap(data, n, i);
  }
  while (n > 1) {
    swap(data, n, 1);
    --n;
    downHeap(data, n, 1);
  }
  showData(data);
}

function heapSortInternal(data) {
  var n = data.length - 1;
  var i = Math.floor(n / 2);
  var loop = function() {
    if (i >= 1) {
      downHeap(data, n, i);
      --i;
      showData(data);
      setTimeout(loop, gIntervalTimeout);
    } else {
      setTimeout(loop2, gIntervalTimeout);  // Jump to loop2.
    }
  }

  var loop2 = function() {
    if (n > 1) {
      swap(data, n, 1);
      --n;
      downHeap(data, n, 1);
      showData(data);
      setTimeout(loop2, gIntervalTimeout);
    }
  }

  showData(data);
  setTimeout(loop, gInitialTimeout);
}

function heapSort(data) {
  // We first move the element with the value zero to the
  // beginning of the array since heapSort() ignores the
  // first element.
  for (var i = 0; i < data.length; ++i) {
    if (data[i] == 0) {
      swap(data, 0, i);
    }
  }
  heapSortInternal(data);
}

function mergeSortInternal(data, first, last) {
  if (last - first <= 1) {
    return;
  }
  var middle = Math.floor((first + last) / 2);
  mergeSortInternal(data, first, middle);
  mergeSortInternal(data, middle, last);

  var work = [];
  for (var i = first; i < middle; ++i) {
    work.push(data[i]);
  }

  var i = first;
  var j = 0;
  var k = middle;
  while (j < middle - first && k < last) {
    if (work[j] <= data[k]) {
      data[i] = work[j];
      ++i;
      ++j;
    } else {
      data[i] = data[k];
      ++i;
      ++k;
    }
  }
  while (j < middle - first) {
    data[i] = work[j];
    ++i;
    ++j;
  }
}

function mergeSortOrig(data) {
  mergeSortInternal(data, 0, data.length);
  showData(data);
}

function mergeSort(data) {
  var regions = [];
  var stack = [];
  stack.push([0, data.length]);
  while (stack.length > 0) {
    var top = stack.pop();
    var first = top[0];
    var last = top[1];
    var middle = Math.floor((first + last) / 2);
    if (last - first <= 1) {
      continue;
    }
    stack.push([first, middle]);
    stack.push([middle, last]);
    regions.push([first, last]);
  }

  var loop = function() {
    if (regions.length > 0) {
      var top = regions.pop();
      var first = top[0];
      var last = top[1];
      var middle = Math.floor((first + last) / 2);

      var work = [];
      for (var i = first; i < middle; ++i) {
        work.push(data[i]);
      }

      var i = first;
      var j = 0;
      var k = middle;
      while (j < middle - first && k < last) {
        if (work[j] <= data[k]) {
          data[i++] = work[j++];
        } else {
          data[i++] = data[k++];
        }
      }
      while (j < middle - first) {
        data[i++] = work[j++];
      }
      showData(data);
      setTimeout(loop, gIntervalTimeout);
    }
  }
  showData(data);
  setTimeout(loop, gInitialTimeout);
}


function downHeap(data, n, i) {
  var j;
  var x = data[i];
  while ((j = i * 2) <= n) {
    if (j + 1 <= n && data[j] < data[j + 1]) {
      ++j;
    }
    if (data[j] <= x) {
      break;
    }
    data[i] = data[j];
    i = j;
  }
  data[i] = x;
}

function shuffle(array) {
  for (var i = 0; i < array.length; ++i) {
    var pos = Math.floor(Math.random() * (array.length - i)  + i);
    swap(array, i, pos);
  }
}

function generateData(num) {
  var data = [];
  for (var i = 0; i < num; ++i) {
    data[i] = i;
  }
  shuffle(data);
  return data;
}

function showData(data) {
  clearCanvas();
  var matrix = document.getElementById("matrix");
  // Keep track of dots shown so that we can clear them
  // later easily.
  matrix.shownDots = [];
  for (var i = 0; i < data.length; ++i) {
    var y = data.length - data[i] - 1
    var dot = matrix.matrix[y][i];
    dot.style.backgroundColor = "black";
    matrix.shownDots.push(dot);
  }
}

function clearCanvas() {
  var matrix = document.getElementById("matrix");
  var shownDots = matrix.shownDots;
  if (shownDots) {
    for (var i = 0; i < shownDots.length; ++i) {
      shownDots[i].style.backgroundColor = gBackgroundColor;
    }
    matrix.shownDots = null;
  }
}

function makeCanvas(numElements) {
  var canvas = document.getElementById("canvas");
  var matrix = document.getElementById("matrix");
  // Reuse the old matrix if the size matches.
  if (matrix && matrix.matrix && matrix.matrix.length == numElements) {
    return;
  }
  if (matrix) {
    canvas.removeChild(matrix);
  }

  var dotWidthPx = Math.floor(canvas.clientWidth / numElements).toString() +
    "px";
  var dotHeightPx = Math.floor(canvas.clientHeight / numElements).toString() +
    "px";

  var table = document.createElement("table");
  table.id = "matrix";
  table.style.borderCollapse = "collapse";
  table.style.margin = "0px";
  table.style.padding = "0px";
  var tbody = document.createElement("tbody");
  // For easier access, we keep cells in this value as array
  // of array.
  var matrix = [];
  for (var i = 0; i < numElements; ++i) {
    matrix.push([]);
    var tr = document.createElement("tr");
    for (var j = 0; j < numElements; ++j) {
      var td = document.createElement("td");
      td.style.width = dotWidthPx;
      td.style.height = dotHeightPx;
      td.style.backgroundColor = gBackgroundColor;
      td.style.padding = "0px";
      tr.appendChild(td);
      matrix[i][j] = td;
    }
    tbody.appendChild(tr);
  }
  table.appendChild(tbody);
  table.matrix = matrix;
  canvas.appendChild(table);
}

function startAnimation() {
  var form = document.getElementById("sort-animation");
  if (!form) {
    return;
  }
  var num = parseInt(form.elements["num"].value);
  var sortName = form.elements["method"].value;
  var data = generateData(num);
  makeCanvas(data.length);

  var sortTable = {
    quick: quickSort,
    bubble: bubbleSort,
    selection: selectionSort,
    insertion: insertionSort,
    shell: shellSort,
    heap: heapSort,
    merge: mergeSort
  };
  var sortFunction = sortTable[sortName];
  if (sortFunction) {
    sortFunction(data);
  } else {
    alert("Unsupported sort method: " + sortName);
  }
}