SHARE
TWEET

Untitled

a guest Aug 12th, 2017 44 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Abstract sort array module.
  3.  * @module sort/abstract
  4.  *
  5.  * @requires module:sort/scope.ScopeArray
  6.  */
  7. import { ScopeArray } from './scope'
  8.  
  9. /**
  10.  * @memberOf module:sort/virtual
  11.  *
  12.  * @class Entry
  13.  *
  14.  * @hideconstructor
  15.  *
  16.  * @extends Array
  17.  *
  18.  * @property {number} 0 - Index.
  19.  * @property {*} 1 - Value.
  20.  */
  21.  
  22. /**
  23.  * Invoked during each interruptable step of AbstractSortArray methods.
  24.  * @memberOf module:sort/virtual
  25.  *
  26.  * @callback interruptCallback
  27.  *
  28.  * @param {Object} step - An object containing information about a generic step interruption.
  29.  * @param {string} step.type - The type of step, e.g. "compare", "swap", "put", "key".
  30.  * @param {module:sort/virtual.Entry[]} entries - An array of index / value pairs of elements involved in the step.
  31.  */
  32.  
  33. /**
  34.  * Base abstract class for arrays that implement sorting algorithms. Do not invoke directly.
  35.  * @abstract
  36.  *
  37.  * @extends module:sort/scope.ScopeArray
  38.  *
  39.  * @param {module:sort/virtual.interruptCallback} interrupt
  40.  *
  41.  * @throws {TypeError} Illegal constructor.
  42.  * @throws {TypeError} `interrupt` must be a function.
  43.  */
  44. export class AbstractSortArray extends ScopeArray {
  45.   constructor (interrupt = () => {}) {
  46.     super()
  47.  
  48.     if (this.constructor === AbstractSortArray) {
  49.       throw new TypeError('Illegal constructor')
  50.     }
  51.  
  52.     if (typeof interrupt === 'function') {
  53.       this.set('interrupt', interrupt)
  54.     } else {
  55.       throw new TypeError('interrupt must be a function')
  56.     }
  57.   }
  58.  
  59.   /**
  60.    * Invoked for each index to generate an element of the array.
  61.    * @callback fillCallback
  62.    *
  63.    * @return {*} element - A generated value with which to populate the array.
  64.    */
  65.  
  66.   /**
  67.    * A method to interruptably populate the array with elements generated from `factory`.
  68.    * @param {module:sort/abstract~fillCallback} factory
  69.    * @param {number} [length=this.length]
  70.    *
  71.    * @throws {TypeError} `factory` must be a function.
  72.    */
  73.   * fill (factory, length = this.length) {
  74.     if (typeof factory !== 'function') {
  75.       throw new TypeError('factory must be a function')
  76.     }
  77.  
  78.     this.length = 0
  79.  
  80.     for (let i = 0; i < length; i++) {
  81.       yield * this.put(i, factory())
  82.     }
  83.   }
  84.  
  85.   /**
  86.    * A method to interruptably randomize the order of elements in the array.
  87.    * Uses the {@link https://en.wikipedia.org/wiki/Fisher–Yates_shuffle|Knuth Fisher Yates} method.
  88.    */
  89.   * shuffle () {
  90.     for (let i = this.length - 1; i > 0; i--) {
  91.       const j = Math.floor(Math.random() * (i + 1))
  92.       yield * this.swap(i, j)
  93.     }
  94.   }
  95.  
  96.   /**
  97.    * A method to interruptably swap two elements in the array.
  98.    * @param {number} i - Index of first element to swap.
  99.    * @param {number} j - Index of second element to swap.
  100.    */
  101.   * swap (i, j) {
  102.     ;[this[i], this[j]] = [this[j], this[i]]
  103.     yield this.get('interrupt')({ type: 'swap', entries: [[i, this[i]], [j, this[j]]] })
  104.   }
  105.  
  106.   /**
  107.    * A method to interruptably put an element in the array.
  108.    * @param {number} index - Index to put element `value`.
  109.    * @param {*} value - Value to put in `index`.
  110.    */
  111.   * put (index, value) {
  112.     this[index] = value
  113.     yield this.get('interrupt')({ type: 'put', entries: [[index, value]] })
  114.   }
  115.  
  116.   /**
  117.    * Abstract method to interruptably sort array of elements.
  118.    * @abstract
  119.    * @throws {TypeError} Illegal invocation.
  120.    */
  121.   * sort () {
  122.     throw new TypeError('Illegal invocation')
  123.   }
  124. }
  125.    
  126. /**
  127.  * Comparative sort array module.
  128.  * @module sort/comparative
  129.  *
  130.  * @requires module:sort/abstract.AbstractSortArray
  131.  */
  132. import { AbstractSortArray } from './abstract'
  133.  
  134. /**
  135.  * Invoked during each compare step of the ComparativeSortArray sort method.
  136.  * @memberOf module:sort/virtual
  137.  *
  138.  * @callback compareCallback
  139.  *
  140.  * @param {*} a - An element to compare on the left-hand side.
  141.  * @param {*} b - An element to compare on the right-hand side.
  142.  *
  143.  * @return {number} result - See {@link https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#Description|`compareFunction`}
  144.  */
  145.  
  146. /**
  147.  * Base abstract class for arrays that implement comparative sorting algorithms.
  148.  * @abstract
  149.  *
  150.  * @extends module:sort/abstract.AbstractSortArray
  151.  *
  152.  * @param {module:sort/virtual.interruptCallback} interrupt
  153.  * @param {module:sort/virtual.compareCallback} compare
  154.  *
  155.  * @throws {TypeError} `compare` must be a function of 2 arguments.
  156.  */
  157. export class ComparativeSortArray extends AbstractSortArray {
  158.   constructor (interrupt, compare = (a, b) => 0) {
  159.     super(interrupt)
  160.  
  161.     if (typeof compare === 'function' && compare.length === 2) {
  162.       this.set('compare', compare)
  163.     } else {
  164.       throw new TypeError('compare must be a function of 2 arguments')
  165.     }
  166.   }
  167.  
  168.   /**
  169.    * A method to interruptably compare two elements in the array.
  170.    * `a` and `b` are optional, since `i` and `j` can sometimes be
  171.    * used to represent indices that are virtual in the comparsion.
  172.    *
  173.    * @param {number} i - Index of left-hand element to compare.
  174.    * @param {number} j - Index of right-hand element to compare.
  175.    * @param {*} [a=this[i]] - Value of left-hand element to compare.
  176.    * @param {*} [b=this[j]] - Value of right-hand element to compare.
  177.    *
  178.    * @return {number} result - See {@link https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#Description|`compareFunction`}
  179.    */
  180.   * compare (i, j, a = this[i], b = this[j]) {
  181.     yield this.get('interrupt')({ type: 'compare', entries: [[i, a], [j, b]] })
  182.     return this.get('compare')(a, b)
  183.   }
  184. }
  185.    
  186. /**
  187.  * Merge sort array module.
  188.  * @module sort/comparative/merge
  189.  *
  190.  * @requires module:sort/comparative.ComparativeSortArray
  191.  */
  192. import { ComparativeSortArray } from '../comparative'
  193.  
  194. /**
  195.  * Base abstract merge sort array.
  196.  * @see {@link https://en.wikipedia.org/wiki/Merge_sort|Merge Sort}
  197.  *
  198.  * @abstract
  199.  *
  200.  * @extends module:sort/comparative.ComparativeSortArray
  201.  */
  202. export class MergeSortArray extends ComparativeSortArray {
  203.   /**
  204.    * @param {number} begin
  205.    * @param {number} middle
  206.    * @param {number} end
  207.    */
  208.   * merge (begin, middle, end) {
  209.     const first = this.slice(begin, middle)
  210.     const last = this.slice(middle, end)
  211.     let index = begin
  212.     let i = 0
  213.     let j = 0
  214.  
  215.     while (index < end) {
  216.       if (j === last.length) {
  217.         yield * this.put(index, first[i++])
  218.       } else if (i === first.length) {
  219.         yield * this.put(index, last[j++])
  220.       } else if ((yield * this.compare(begin + i, middle + j, first[i], last[j])) <= 0) {
  221.         yield * this.put(index, first[i++])
  222.       } else {
  223.         yield * this.put(index, last[j++])
  224.       }
  225.  
  226.       index++
  227.     }
  228.   }
  229. }
  230.    
  231. /**
  232.  * Iterative merge sort array module.
  233.  * @module sort/comparative/merge/iterative
  234.  *
  235.  * @requires module:sort/comparative/merge.MergeSortArray
  236.  */
  237. import { MergeSortArray } from '../merge'
  238.  
  239. /**
  240.  * @see {@link https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation|Bottom-up Merge Sort}
  241.  *
  242.  * @extends module:sort/comparative/merge.MergeSortArray
  243.  */
  244. export class IterativeMergeSortArray extends MergeSortArray {
  245.   /** @override */
  246.   * sort () {
  247.     for (let increment = 1; increment < this.length; increment *= 2) {
  248.       for (let begin = 0; begin < this.length; begin += increment * 2) {
  249.         const middle = begin + increment
  250.         const end = Math.min(begin + increment * 2, this.length)
  251.  
  252.         yield * this.merge(begin, middle, end)
  253.       }
  254.     }
  255.   }
  256. }
RAW Paste Data
Top