/**
 * Abstract sort array module.
 * @module sort/abstract
 *
 * @requires module:sort/scope.ScopeArray
 */
import { ScopeArray } from './scope'

/**
 * @memberOf module:sort/virtual
 *
 * @class Entry
 *
 * @hideconstructor
 *
 * @extends Array
 *
 * @property {number} 0 - Index.
 * @property {*} 1 - Value.
 */

/**
 * Invoked during each interruptable step of AbstractSortArray methods.
 * @memberOf module:sort/virtual
 *
 * @callback interruptCallback
 *
 * @param {Object} step - An object containing information about a generic step interruption.
 * @param {string} step.type - The type of step, e.g. "compare", "swap", "put", "key".
 * @param {module:sort/virtual.Entry[]} entries - An array of index / value pairs of elements involved in the step.
 */

/**
 * Base abstract class for arrays that implement sorting algorithms. Do not invoke directly.
 * @abstract
 *
 * @extends module:sort/scope.ScopeArray
 *
 * @param {module:sort/virtual.interruptCallback} interrupt
 *
 * @throws {TypeError} Illegal constructor.
 * @throws {TypeError} `interrupt` must be a function.
 */
export class AbstractSortArray extends ScopeArray {
  constructor (interrupt = () => {}) {
    super()

    if (this.constructor === AbstractSortArray) {
      throw new TypeError('Illegal constructor')
    }

    if (typeof interrupt === 'function') {
      this.set('interrupt', interrupt)
    } else {
      throw new TypeError('interrupt must be a function')
    }
  }

  /**
   * Invoked for each index to generate an element of the array.
   * @callback fillCallback
   *
   * @return {*} element - A generated value with which to populate the array.
   */

  /**
   * A method to interruptably populate the array with elements generated from `factory`.
   * @param {module:sort/abstract~fillCallback} factory
   * @param {number} [length=this.length]
   *
   * @throws {TypeError} `factory` must be a function.
   */
  * fill (factory, length = this.length) {
    if (typeof factory !== 'function') {
      throw new TypeError('factory must be a function')
    }

    this.length = 0

    for (let i = 0; i < length; i++) {
      yield * this.put(i, factory())
    }
  }

  /**
   * A method to interruptably randomize the order of elements in the array.
   * Uses the {@link https://en.wikipedia.org/wiki/Fisher–Yates_shuffle|Knuth Fisher Yates} method.
   */
  * shuffle () {
    for (let i = this.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1))
      yield * this.swap(i, j)
    }
  }

  /**
   * A method to interruptably swap two elements in the array.
   * @param {number} i - Index of first element to swap.
   * @param {number} j - Index of second element to swap.
   */
  * swap (i, j) {
    ;[this[i], this[j]] = [this[j], this[i]]
    yield this.get('interrupt')({ type: 'swap', entries: [[i, this[i]], [j, this[j]]] })
  }

  /**
   * A method to interruptably put an element in the array.
   * @param {number} index - Index to put element `value`.
   * @param {*} value - Value to put in `index`.
   */
  * put (index, value) {
    this[index] = value
    yield this.get('interrupt')({ type: 'put', entries: [[index, value]] })
  }

  /**
   * Abstract method to interruptably sort array of elements.
   * @abstract
   * @throws {TypeError} Illegal invocation.
   */
  * sort () {
    throw new TypeError('Illegal invocation')
  }
}

/**
 * Comparative sort array module.
 * @module sort/comparative
 *
 * @requires module:sort/abstract.AbstractSortArray
 */
import { AbstractSortArray } from './abstract'

/**
 * Invoked during each compare step of the ComparativeSortArray sort method.
 * @memberOf module:sort/virtual
 *
 * @callback compareCallback
 *
 * @param {*} a - An element to compare on the left-hand side.
 * @param {*} b - An element to compare on the right-hand side.
 *
 * @return {number} result - See {@link https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#Description|`compareFunction`}
 */

/**
 * Base abstract class for arrays that implement comparative sorting algorithms.
 * @abstract
 *
 * @extends module:sort/abstract.AbstractSortArray
 *
 * @param {module:sort/virtual.interruptCallback} interrupt
 * @param {module:sort/virtual.compareCallback} compare
 *
 * @throws {TypeError} `compare` must be a function of 2 arguments.
 */
export class ComparativeSortArray extends AbstractSortArray {
  constructor (interrupt, compare = (a, b) => 0) {
    super(interrupt)

    if (typeof compare === 'function' && compare.length === 2) {
      this.set('compare', compare)
    } else {
      throw new TypeError('compare must be a function of 2 arguments')
    }
  }

  /**
   * A method to interruptably compare two elements in the array.
   * `a` and `b` are optional, since `i` and `j` can sometimes be
   * used to represent indices that are virtual in the comparsion.
   *
   * @param {number} i - Index of left-hand element to compare.
   * @param {number} j - Index of right-hand element to compare.
   * @param {*} [a=this[i]] - Value of left-hand element to compare.
   * @param {*} [b=this[j]] - Value of right-hand element to compare.
   *
   * @return {number} result - See {@link https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#Description|`compareFunction`}
   */
  * compare (i, j, a = this[i], b = this[j]) {
    yield this.get('interrupt')({ type: 'compare', entries: [[i, a], [j, b]] })
    return this.get('compare')(a, b)
  }
}

/**
 * Merge sort array module.
 * @module sort/comparative/merge
 *
 * @requires module:sort/comparative.ComparativeSortArray
 */
import { ComparativeSortArray } from '../comparative'

/**
 * Base abstract merge sort array.
 * @see {@link https://en.wikipedia.org/wiki/Merge_sort|Merge Sort}
 *
 * @abstract
 *
 * @extends module:sort/comparative.ComparativeSortArray
 */
export class MergeSortArray extends ComparativeSortArray {
  /**
   * @param {number} begin
   * @param {number} middle
   * @param {number} end
   */
  * merge (begin, middle, end) {
    const first = this.slice(begin, middle)
    const last = this.slice(middle, end)
    let index = begin
    let i = 0
    let j = 0

    while (index < end) {
      if (j === last.length) {
        yield * this.put(index, first[i++])
      } else if (i === first.length) {
        yield * this.put(index, last[j++])
      } else if ((yield * this.compare(begin + i, middle + j, first[i], last[j])) <= 0) {
        yield * this.put(index, first[i++])
      } else {
        yield * this.put(index, last[j++])
      }

      index++
    }
  }
}

/**
 * Iterative merge sort array module.
 * @module sort/comparative/merge/iterative
 *
 * @requires module:sort/comparative/merge.MergeSortArray
 */
import { MergeSortArray } from '../merge'

/**
 * @see {@link https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation|Bottom-up Merge Sort}
 *
 * @extends module:sort/comparative/merge.MergeSortArray
 */
export class IterativeMergeSortArray extends MergeSortArray {
  /** @override */
  * sort () {
    for (let increment = 1; increment < this.length; increment *= 2) {
      for (let begin = 0; begin < this.length; begin += increment * 2) {
        const middle = begin + increment
        const end = Math.min(begin + increment * 2, this.length)

        yield * this.merge(begin, middle, end)
      }
    }
  }
}