// Returns the greatest common denominator of
// a and b, where a is greater than or equal to b.
// The given pair a, b must have a common divisor.
// The actions array is populated with a history of
// objects representing actions along with snapshots
// of the state of the algorithm throughout the procedure.
function gcd(a, b, actions) {
  function _gcd(a, b) {
    while (a !== b) {
      a = remainder(a, b);
      actions.push(reset(a, b));
      [a, b] = [b, a];
      actions.push(swap(a, b));
    }
    actions.push(end(a));
    return a;
  }

  // a is greater than or equal to b
  function remainder(a, b) {
    if (a <= b) return a;
    if (a - b <= b) {
      actions.push(shorten(a - b, b));
      return a - b;
    }
    actions.push(lengthen(a, b + b));
    a = remainder(a, b + b);
    if (a <= b) return a;
    actions.push(reset(a, b));
    actions.push(shorten(a - b, b));
    return a - b;
  }

  function swap(a, b) {
    return { type: "swap", a: a, b: b};
  }

  function shorten(a, b) {
    return { type: "shorten", a: a, b: b };
  }

  function end(a) {
    return { type: "end", a: a };
  }

  function lengthen(a, b) {
    return { type: "lengthen", a: a, b: b };
  }

  function reset(a, b) {
    return { type: "reset", a: a, b: b };
  }

  return _gcd(a, b);
}