5
\$\begingroup\$

I would like a review of a library I've recently published. I realize this is a rather large request, but having looked on meta, it seems this is perfectly on-topic. I'll include a few choice samples from the library to demonstrate my approach, as well as a link to the full codebase for anyone interested in giving a full-breadth review.

So to summarize, this library, called sort-viz, is, as the title and tags suggest, an object-oriented approach at designing an educational tool for teaching sorting algorithms, which is why the sorting algorithms use generator functions to introduce interruptions in the control-flow in order to be visualized step-by-step.

Here's a few of the classes needed to implement an iterative (bottom-up) merge sort algorithm:

/**
 * 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[]} step.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.
   * @memberOf module:sort/virtual
   *
   * @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/virtual.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=(a, b) => 0]
 *
 * @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)
      }
    }
  }
}

And as promised, here is the link to the repository, which also contains formatted documentation on the respective github pages, and a full demo on Heroku.

Please be responsible and only make HTTP requests to the Heroku link sparingly, as I have it hosted on a hobbyist plan, which only allows so many hours of uptime a month. I have plans to implement a service worker for it in the future to mitigate this issue.

\$\endgroup\$
  • \$\begingroup\$ I just have to say, this looks incredible. Amazing work! \$\endgroup\$ – Gerrit0 Aug 13 '17 at 0:34
  • \$\begingroup\$ @Gerrit0 thank you, I really appreciate the compliment. I know that having a deep prototypal inheritance and using generator functions isn't exactly performant, but then again, that was never the point to begin with. I was working more towards clean, readable, and maintainable code that tried to avoid "looking asynchronous" as much as possible. \$\endgroup\$ – Patrick Roberts Aug 13 '17 at 0:39
  • \$\begingroup\$ I would take another approach to this, the main class you need to have is a list, and this is already defined in javascript as an array. I would instead define methods to sort the array it instead of defining every operation as a class. Ideally a class should abstract some kind of data and the operations over these data in the form of methods. \$\endgroup\$ – David Lemon Aug 18 '17 at 7:32
  • 1
    \$\begingroup\$ @DavidLemon if you actually look at the repository, the base class of all these algorithms is in fact Array. So, I don't really understand how that isn't already done here. And the operations aren't represented by classes, it's just the hierarchy of inheritance is based on what algorithms use what operations. Of course everything can use swap and put, so that goes in the abstract class. compare is only used by comparative algorithms, so that goes in the next class. merge is used by merge sorts, and then finally the polymorphic sort function overriden for each implementation. \$\endgroup\$ – Patrick Roberts Aug 18 '17 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.