import { pipe } from "../prelude/compose"
import { none, type Option, some } from "../prelude/option"

// Phantom property type
declare const __props: unique symbol
type Props<P extends string> = { [__props]?: P }

/**
 * Tracked array with phantom properties.
 * Properties like "Sorted" or "NonEmpty" are tracked at type level.
 */
export type Arr<T, P extends string = never> = readonly T[] & Props<P>

// Property markers
export type Sorted = "Sorted"
export type NonEmpty = "NonEmpty"

// Constructor
export const arr = <T>(xs: readonly T[]): Arr<T> => xs as Arr<T>

// NonEmpty check - returns Option to track the property
export const nonEmpty = <T, P extends string>(
  xs: Arr<T, P>,
): Option<Arr<T, P | NonEmpty>> =>
  xs.length > 0 ? some(xs as Arr<T, P | NonEmpty>) : none

// Safe accessors for NonEmpty arrays
export const head = <T, P extends string>(xs: Arr<T, P | NonEmpty>): T => xs[0]!
export const last = <T, P extends string>(xs: Arr<T, P | NonEmpty>): T =>
  xs[xs.length - 1]!

// Sorting - adds Sorted property
export const sortNum = <P extends string>(
  xs: Arr<number, P>,
): Arr<number, P | Sorted> =>
  [...xs].sort((a, b) => a - b) as Arr<number, P | Sorted>

export const sortBy =
  <T, P extends string>(key: (t: T) => number) =>
  (xs: Arr<T, P>): Arr<T, P | Sorted> =>
    [...xs].sort((a, b) => key(a) - key(b)) as Arr<T, P | Sorted>

// Transformations - preserve properties where valid
export const map =
  <T, U>(f: (t: T) => U) =>
  <P extends string>(xs: Arr<T, P>): Arr<U, Exclude<P, Sorted>> =>
    xs.map(f) as Arr<U, Exclude<P, Sorted>>

export const filter =
  <T>(pred: (t: T) => boolean) =>
  <P extends string>(xs: Arr<T, P>): Arr<T, Exclude<P, NonEmpty>> =>
    xs.filter(pred) as Arr<T, Exclude<P, NonEmpty>>

export const reduce =
  <T, U>(f: (acc: U, t: T) => U, initial: U) =>
  <P extends string>(xs: Arr<T, P>): U =>
    xs.reduce(f, initial)

// Take/drop
export const take =
  (n: number) =>
  <T, P extends string>(xs: Arr<T, P>): Arr<T, Exclude<P, NonEmpty>> =>
    xs.slice(0, n) as Arr<T, Exclude<P, NonEmpty>>

export const drop =
  (n: number) =>
  <T, P extends string>(xs: Arr<T, P>): Arr<T, Exclude<P, NonEmpty>> =>
    xs.slice(n) as Arr<T, Exclude<P, NonEmpty>>

// Generic binary search with comparator
export const binarySearch =
  <T>(compare: (a: T, b: T) => number) =>
  (target: T) =>
  <P extends string>(xs: Arr<T, P | Sorted>): Option<number> => {
    const go = (lo: number, hi: number): Option<number> =>
      lo > hi
        ? none
        : pipe(Math.floor((lo + hi) / 2), (mid) =>
            ((cmp) =>
              cmp === 0
                ? some(mid)
                : cmp < 0
                  ? go(lo, mid - 1)
                  : go(mid + 1, hi))(compare(target, xs[mid]!)),
          )
    return go(0, xs.length - 1)
  }

// Binary search specialized for numbers
export const binarySearchNum = binarySearch<number>((a, b) => a - b)