// missing from JS stdlib

// return an array of numbers starting at `start`, not reaching `end`, incrementing by `step`.
export function range(start: number, end: number, step: number = 1): number[] {
  return [...Array(Math.ceil((end - start) / step)).keys()].map(i => i * step + start);
}

// return the average of an array of numbers.
export function average(array: number[]): number {
  return array.reduce((sum, n) => sum + n) / array.length;
}


// ----- arrays

// this is really just a trick to make typescript happy.
export function removeMissing<A>(list: (A | undefined)[]): A[] {
  return list.filter(x => x !== undefined) as A[];
}

// remove an item discovered via `indexOf`.
export function arrayRemove<A>(array: Array<A>, item: A) {
  const index = array.indexOf(item);
  if (index >= 0) array.splice(index, 1);
}

// call `f` on each item of the array, and return a new array containing only the results that were not undefined.
export function filterMap<A, B>(list: A[], f: (item: A, index: number) => B | undefined): B[] {
  return list.reduce<B[]>((rv, item, i) => {
    const b = f(item, i);
    if (b !== undefined) rv.push(b);
    return rv;
  }, []);
}

// return the index of the first element where test returns true. if none did, return the array length.
export function binarySearch<A>(array: A[], test: (item: A) => boolean): number {
  let lo = -1, hi = array.length;
  while (lo + 1 < hi) {
    const m = lo + ((hi - lo) >> 1);
    if (test(array[m])) {
      hi = m;
    } else {
      lo = m;
    }
  }
  return hi;
}

// break an array into a list of arrays where each new array's size is `maxSize` except (possibly) the last one.
export function arraySlice<A>(array: A[], maxSize: number): A[][] {
  return range(0, array.length, maxSize).map(i => array.slice(i, i + maxSize));
}

export function groupBy<A>(array: A[], grouper: (a: A) => string): { [key: string]: A[] } {
  const rv: { [key: string]: A[] } = {};
  array.forEach(a => {
    const key = grouper(a);
    if (rv[key] === undefined) rv[key] = [];
    rv[key].push(a);
  });
  return rv;
}

// return a list that only contains each item once, based on a lookup per item.
export function uniqueBy<A>(list: A[], getKey: (item: A) => string): A[] {
  const seenKeys = new Set<string>();
  return list.filter(x => {
    const key = getKey(x);
    if (seenKeys.has(key)) return false;
    seenKeys.add(key);
    return true;
  });
}

// return two lists: the first is every item where `f` returned true, the second is every item where `f` returned false.
export function partition<A>(array: A[], f: (item: A) => boolean): [ A[], A[] ] {
  const left: A[] = [];
  const right: A[] = [];
  array.forEach(item => (f(item) ? left : right).push(item));
  return [ left, right ];
}

// return the most popular item from a list.
export function consensus<A>(
  array: Array<A>,
  comparer: (a: A, b: A) => number
): A | undefined {
  const sorted: Array<[ A, number ]> = array.sort(comparer).map(item => [ item, 1 ] as [ A, number ]);
  if (sorted.length == 0) return undefined;

  let i = 1;
  while (i < sorted.length) {
    if (comparer(sorted[i - 1][0], sorted[i][0]) == 0) {
      sorted[i - 1][1]++;
      sorted.splice(i, 1);
    } else {
      i++;
    }
  }
  return sorted.sort((a, b) => b[1] - a[1])[0][0];
}


// ----- iterators

// generate a list of numbers starting at `start`. each subsequent item is
// supplied by `next`, until `condition` returns false.
export function generate(
  start: number,
  next: (n: number) => number,
  condition: (n: number, len: number) => boolean
): number[] {
  const rv: number[] = [];
  let current = start;
  do {
    rv.push(current);
    current = next(current);
  } while (condition(current, rv.length));
  return rv;
}

// make an iterator that yields the first `max` items.
export function* iterTake<A>(iterable: Iterable<A>, max: number): Iterable<A> {
  const iter = iterable[Symbol.iterator]();
  for (let i = 0; i < max; i++) {
    const item = iter.next();
    if (item.done) return;
    yield item.value;
  }
}

// return an iterable that concatenates all the iterables in `array`.
export function *iterFlatten<A>(array: Iterable<A>[]): Iterable<A> {
  for (const x of array) yield* x;
}


// ----- maps

// like `map`, but applying only to the keys of a Map.
export function mapKeys<A, B, V>(inMap: Map<A, V>, f: (key: A) => B): Map<B, V> {
  return new Map([...inMap].map(([ k, v ]) => [ f(k), v ]));
}

// like `filterMap`, but applying only to the keys of a Map.
export function filterMapKeys<A, B, V>(inMap: Map<A, V>, f: (key: A) => (B | undefined)): Map<B, V> {
  return new Map(removeMissing([...inMap].map(([ k, v ]) => {
    const newKey = f(k);
    return newKey === undefined ? undefined : [ newKey, v ];
  })));
}


// ----- promises

// like `filter`, for a list of promises.
export async function asyncFilter<A>(list: A[], f: (item: A) => Promise<boolean>): Promise<A[]> {
  const allowed = await Promise.all(list.map(f));
  return list.filter((x, i) => allowed[i]);
}

// return true if any of the promises returned true.
export async function asyncSome<A>(list: A[], f: (item: A) => Promise<boolean>): Promise<boolean> {
  return (await Promise.all(list.map(f))).some(x => x);
}