flatten.js

/**
 * ## flatten
 *
 * Flatten an array of integers
 *
 * This is mighty readable, but it won't perform well in a tight
 * loop or with a huge structure.
 *
 * If that's a problem, we could switch to an iterative process,
 * and/or build the output array via mutation. See below.
 */

export const flatten = nestedArr => {
  if (!Array.isArray(nestedArr))
    throw TypeError(`"${nestedArr}" is not an array`)

  return nestedArr.reduce((acc, element) => {
    if (Array.isArray(element)) return [...acc, ...flatten(element)]
    if (Number.isInteger(element)) return [...acc, element]

    throw TypeError(`element "${element}" is not an array or integer`)
  }, [])
}

export const fastFlatten = nestedArr => {
  const input = nestedArr.slice()
  const output = []

  while (input.length > 0) {
    const element = input.pop()

    if (Array.isArray(element)) {
      input.push(...element) // recur
      continue
    }

    if (Number.isInteger(element)) {
      output.push(element)
      continue
    }

    throw TypeError(`element "${element}" is not an array or integer`)
  }
  return output.reverse()
}

flatten.test.js

/* eslint-env jest */

import jasmineCheck from 'jasmine-check'
import performanceNow from 'performance-now'
import { sample } from 'testcheck'

import { flatten, fastFlatten } from './flatten.js'

// polyfill performance.now
const performance = {
  now: performanceNow,
}

// we'll use testcheck for generative testing
jasmineCheck.install()

const testCases = new Map([
  [[1, 2, 3], [1, 2, 3]],
  [[[[[[1, 2, 3], [4, 5, [6, 7]]]]]], [1, 2, 3, 4, 5, 6, 7]],
  [[1, [1]], [1, 1]],
  [[[1, 2, [3]], 4], [1, 2, 3, 4]],
])

const testFlatten = (description, flatten) => {
  describe(description, () => {
    it('should compute the expected result for the test cases', () => {
      for (let [input, output] of testCases.entries()) {
        expect(flatten(input)).toEqual(output)
      }
    })

    check.it(
      'accepts a nested array of ints and returns an array of ints',
      gen.nested(gen.array, gen.int),
      nestedArr => {
        const result = flatten(nestedArr)
        expect(Array.isArray(result)).toBe(true)
        result.forEach(integer => {
          expect(Number.isInteger(integer)).toBe(true)
        })
      },
    )

    it('should throw on non-array input', () => {
      expect(() => flatten(5)).toThrow()
    })

    it('should throw on non-int input', () => {
      expect(() => flatten([1.5, 2, 3])).toThrow()
    })
  })
}

testFlatten('flatten', flatten)
testFlatten('fastFlatten', fastFlatten)

const countTime = fn => input => {
  const start = performance.now()
  fn(input)
  const end = performance.now()
  return end - start
}

describe('performance', () => {
  it('fastFlatten performs at least twice as well as flatten on a bunch of generated data', () => {
    const countFastFlatten = countTime(fastFlatten)
    const countFlatten = countTime(flatten)
    const counters = {
      fast: 0,
      slow: 0,
    }
    const arrs = sample(gen.nested(gen.array, gen.int), 500)
    arrs.forEach(arr => {
      counters.fast += countFastFlatten(arr)
      counters.slow += countFlatten(arr)
    })
    expect(counters.fast / counters.slow).toBeLessThan(1 / 2)
  })
})