module.ae

// std.sort — in-place ascending sort and binary search over slices:
// `int[]`, `long[]`, `float[]` and `string[]`.
//
// Every entry point takes a slice, so the length travels with the elements
// and no call takes a separate count: a whole array sorts as `sort.ints(a)`,
// a prefix as `sort.ints(a[..n])`, any run as `sort.ints(a[lo..hi])`. The
// packed-array handles give their elements as a slice (`intarr.array(h)`,
// `longarr.array(h)`, `floatarr.array(h)`, `strarr.array(h)`), as do a
// `T[N]` array, a `make([]T, n)` buffer and a bounded view of C memory
// (`(p as int[])[0..n]`). A view with no bound (`p as int[]`, `.len` -1)
// has no length to sort and panics.
//
// Scoped to concrete types by design (see docs/cross-references/
// c3-stdlib-gaps.md §2.3): C3's `std::sort` is generics-first, which
// Aether lowers differently; here each element type gets a direct sort so
// there is no generic machinery to reason about. The default order is
// ascending. Sorts are IN PLACE and stable is not guaranteed (shell sort).
// The slice's bound is checked once, on entry; the loops index an unchecked
// view of the same elements, so a sort costs what it did over the raw
// buffer.
//
// The algorithm choice (shell sort with the Ciura gap sequence) and the
// binary-search contract follow C3's `std::sort` at the capability level
// (MIT, Copyright (c) 2022-2026 Christoffer Lernö and contributors),
// re-expressed for Aether's concrete array types.
//
// Ordering: numbers by `<`; strings by std.string.compare, lexicographic
// BYTE order, binary-safe (embedded NULs take part), the default C, Go and
// Zig use. Locale-aware collation is a different question and stays in
// contrib/i18n.

exports(
    ints, longs, floats, strings,
    int_search, long_search, float_search, string_search,
    ints_by, longs_by, floats_by, strings_by
)

import std.string
import std.mem

// Ciura's gap sequence, extended by *2.25 for larger n. A module-level
// const array of the fixed prefix; larger gaps are computed on the fly.
const CIURA[] = [1, 4, 10, 23, 57, 132, 301, 701]

// The largest starting gap <= n/2: Ciura's, then *2.25 growth.
fn first_gap(n: int) -> int {
    gap = 1
    idx = 0
    while idx < 8 && CIURA[idx] < n {
        gap = CIURA[idx]
        idx = idx + 1
    }
    while gap < n / 2 {
        gap = (gap * 9) / 4 // ~*2.25
    }
    return gap
}

// The next gap down the chain; 0 after the final gap-1 pass.
fn next_gap(gap: int) -> int {
    if gap == 1 {
        return 0
    }
    next = (gap * 4) / 9
    if next < 1 {
        return 1
    }
    return next
}

// A view with no bound (`p as T[]`) has no length to sort or search.
fn unbounded(fname: string) {
    panic("sort.${fname}: the slice has no bound (.len -1); give it one, as `(p as T[])[0..n]`")
}

// The comparator forms (`*_by`): `cmp` must be a strict weak ordering. An
// inconsistent comparator gives an unspecified permutation, not a crash, but
// not a sorted slice either. They are separate names rather than an optional
// argument so the default path keeps a direct comparison instead of an
// indirect call per element: these sorts are in place and hot, and the
// natural order is what almost every caller wants. Not stable, like every
// sort in this module.

// ---- int[] -------------------------------------------------------------------

// Sort `xs` ascending, in place.
ints(xs: int[]) {
    n = xs.len
    if n < 0 {
        unbounded("ints")
    }
    if n < 2 {
        return
    }
    v = xs as ptr as int[] // bound checked above; the loops index unchecked
    gap = first_gap(n)
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = v[i]
            j = i
            while j >= gap && v[j - gap] > tmp {
                v[j] = v[j - gap]
                j = j - gap
            }
            v[j] = tmp
            i = i + 1
        }
        gap = next_gap(gap)
    }
}

// Binary search a SORTED `xs` for `x`: the index of the first element not
// ordered before `x`, which is `x`'s index when present and otherwise where
// it would be inserted to keep `xs` sorted (`xs.len` when every element
// sorts before it). C3's binarysearch contract.
int_search(xs: int[], x: int) -> int {
    if xs.len < 0 {
        unbounded("int_search")
    }
    v = xs as ptr as int[]
    lo = 0
    hi = xs.len
    while lo < hi {
        mid = lo + (hi - lo) / 2
        if v[mid] < x {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

// Sort `xs` in place by `cmp`, which returns <0 when its first argument
// sorts before its second, 0 when they tie, >0 when it sorts after.
ints_by(xs: int[], cmp: fn(int, int) -> int) {
    n = xs.len
    if n < 0 {
        unbounded("ints_by")
    }
    if n < 2 {
        return
    }
    v = xs as ptr as int[]
    gap = first_gap(n)
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = v[i]
            j = i
            while j >= gap && cmp(v[j - gap], tmp) > 0 {
                v[j] = v[j - gap]
                j = j - gap
            }
            v[j] = tmp
            i = i + 1
        }
        gap = next_gap(gap)
    }
}

// ---- long[] ------------------------------------------------------------------

// Sort `xs` ascending, in place.
longs(xs: long[]) {
    n = xs.len
    if n < 0 {
        unbounded("longs")
    }
    if n < 2 {
        return
    }
    v = xs as ptr as long[] // bound checked above; the loops index unchecked
    gap = first_gap(n)
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = v[i]
            j = i
            while j >= gap && v[j - gap] > tmp {
                v[j] = v[j - gap]
                j = j - gap
            }
            v[j] = tmp
            i = i + 1
        }
        gap = next_gap(gap)
    }
}

// Binary search a SORTED `xs` for `x`: the index of the first element not
// ordered before `x`, which is `x`'s index when present and otherwise where
// it would be inserted to keep `xs` sorted (`xs.len` when every element
// sorts before it). C3's binarysearch contract.
long_search(xs: long[], x: long) -> int {
    if xs.len < 0 {
        unbounded("long_search")
    }
    v = xs as ptr as long[]
    lo = 0
    hi = xs.len
    while lo < hi {
        mid = lo + (hi - lo) / 2
        if v[mid] < x {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

// Sort `xs` in place by `cmp`, which returns <0 when its first argument
// sorts before its second, 0 when they tie, >0 when it sorts after.
longs_by(xs: long[], cmp: fn(long, long) -> int) {
    n = xs.len
    if n < 0 {
        unbounded("longs_by")
    }
    if n < 2 {
        return
    }
    v = xs as ptr as long[]
    gap = first_gap(n)
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = v[i]
            j = i
            while j >= gap && cmp(v[j - gap], tmp) > 0 {
                v[j] = v[j - gap]
                j = j - gap
            }
            v[j] = tmp
            i = i + 1
        }
        gap = next_gap(gap)
    }
}

// ---- float[] -----------------------------------------------------------------

// Sort `xs` ascending, in place.
floats(xs: float[]) {
    n = xs.len
    if n < 0 {
        unbounded("floats")
    }
    if n < 2 {
        return
    }
    v = xs as ptr as float[] // bound checked above; the loops index unchecked
    gap = first_gap(n)
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = v[i]
            j = i
            while j >= gap && v[j - gap] > tmp {
                v[j] = v[j - gap]
                j = j - gap
            }
            v[j] = tmp
            i = i + 1
        }
        gap = next_gap(gap)
    }
}

// Binary search a SORTED `xs` for `x`: the index of the first element not
// ordered before `x`, which is `x`'s index when present and otherwise where
// it would be inserted to keep `xs` sorted (`xs.len` when every element
// sorts before it). C3's binarysearch contract.
float_search(xs: float[], x: float) -> int {
    if xs.len < 0 {
        unbounded("float_search")
    }
    v = xs as ptr as float[]
    lo = 0
    hi = xs.len
    while lo < hi {
        mid = lo + (hi - lo) / 2
        if v[mid] < x {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

// Sort `xs` in place by `cmp`, which returns <0 when its first argument
// sorts before its second, 0 when they tie, >0 when it sorts after.
floats_by(xs: float[], cmp: fn(float, float) -> int) {
    n = xs.len
    if n < 0 {
        unbounded("floats_by")
    }
    if n < 2 {
        return
    }
    v = xs as ptr as float[]
    gap = first_gap(n)
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = v[i]
            j = i
            while j >= gap && cmp(v[j - gap], tmp) > 0 {
                v[j] = v[j - gap]
                j = j - gap
            }
            v[j] = tmp
            i = i + 1
        }
        gap = next_gap(gap)
    }
}

// ---- string[] ----------------------------------------------------------------

// Sort `xs` ascending, in place.
strings(xs: string[]) {
    n = xs.len
    if n < 0 {
        unbounded("strings")
    }
    if n < 2 {
        return
    }
    // A permutation: the elements' pointers are exchanged, taking and
    // releasing nothing, so the array may be Aether's or C's (a strarr).
    base = xs as ptr
    gap = first_gap(n)
    while gap >= 1 {
        i = gap
        while i < n {
            j = i
            while j >= gap && string.compare(xs[j - gap], xs[j]) > 0 {
                mem.swap_ptrs(base, j - gap, j)
                j = j - gap
            }
            i = i + 1
        }
        gap = next_gap(gap)
    }
}

// Binary search a SORTED `xs` for `x`: the index of the first element not
// ordered before `x`, which is `x`'s index when present and otherwise where
// it would be inserted to keep `xs` sorted (`xs.len` when every element
// sorts before it). C3's binarysearch contract.
string_search(xs: string[], x: string) -> int {
    if xs.len < 0 {
        unbounded("string_search")
    }
    v = xs as ptr as string[]
    lo = 0
    hi = xs.len
    while lo < hi {
        mid = lo + (hi - lo) / 2
        if string.compare(v[mid], x) < 0 {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

// Sort `xs` in place by `cmp`, which returns <0 when its first argument
// sorts before its second, 0 when they tie, >0 when it sorts after.
strings_by(xs: string[], cmp: fn(string, string) -> int) {
    n = xs.len
    if n < 0 {
        unbounded("strings_by")
    }
    if n < 2 {
        return
    }
    base = xs as ptr
    gap = first_gap(n)
    while gap >= 1 {
        i = gap
        while i < n {
            j = i
            while j >= gap && cmp(xs[j - gap], xs[j]) > 0 {
                mem.swap_ptrs(base, j - gap, j)
                j = j - gap
            }
            i = i + 1
        }
        gap = next_gap(gap)
    }
}