partition_utils.ts

import { assertEquals } from "https://deno.land/std@0.177.0/testing/asserts.ts"

/** @example
 * const input = [1, 1, -1, 1, -1, 1]
 * assertEquals(span(input, (x) => x > 0), [[1, 1], [-1, 1, -1, 1]])
 */
export const span = <T>(array: T[], predicate: (line: T) => boolean): [T[], T[]] => {
  const index = array.findIndex((line) => !predicate(line))
  const before = index === -1 ? array : array.slice(0, index)
  const after = index === -1 ? [] : array.slice(index)

  return [before, after]
}

const cases = [
  [[1, 1, -1, 1, -1, 1], (x) => x > 0, [[1, 1], [-1, 1, -1, 1]]],
  [[1, 2, 3, 4, 1, 2, 3, 4], (x) => x < 3, [[1, 2], [3, 4, 1, 2, 3, 4]]],
  [[1, 2, 3], (x) => x < 9, [[1, 2, 3], []]],
  [[1, 2, 3], (x) => x < 0, [[], [1, 2, 3]]],
] satisfies [input: number[], predicate: (x: number) => boolean, expected: [number[], number[]]][]

for (const [input, predicate, expected] of cases) {
  Deno.test(`span(${input}, ${predicate})`, () => {
    assertEquals(span(input, predicate), expected)
  })
}

/** @example
 * const input = [1, 2, 3, 4, 5, 6]
 * assertEquals(cutHalf(input, 2), [[1, 2], [3, 4, 5, 6]])
 */
export const cutHalf = <T>(
  array: T[],
  size = Math.floor(array.length / 2),
): [T[], T[]] => [array.slice(0, size), array.slice(size)]

Deno.test("cutHalf", () => {
  const input = [1, 2, 3, 4, 5, 6]

  assertEquals(cutHalf(input), [[1, 2, 3], [4, 5, 6]])
  assertEquals(cutHalf(input, 3), [[1, 2, 3], [4, 5, 6]])
  assertEquals(cutHalf(input, 10), [input, []])
  assertEquals(cutHalf(input, 0), [[], input])
})

/**
 * pluck first consecutive elements that satisfy predicate among array.
 *
 * @example
 * const input = [1, 2, 3, 10, 11, 12, 4, 5, 6, 13, 14]
 * const output = [[1, 2, 3], [10, 11, 12], [4, 5, 6, 13, 14]]
 * assertEquals(trisection(input, (x) => x >= 10), output)
 */
export const trisection = <T>(array: T[], predicate: (line: T) => boolean): [T[], T[], T[]] => {
  const firstSatisfying = array.findIndex(predicate)
  const [before, rest] = cutHalf(array, firstSatisfying)

  const firstNotSatisfying = rest.findIndex((line) => !predicate(line))
  const [middle, after] = cutHalf(rest, firstNotSatisfying)

  return [before, middle, after]
}

Deno.test("trisection", () => {
  const input = [1, 2, 3, 10, 11, 12, 4, 5, 6, 13, 14]
  assertEquals(trisection(input, (x) => x >= 10), [[1, 2, 3], [10, 11, 12], [4, 5, 6, 13, 14]])
})