module.ae

// std.sort — in-place ascending sort + binary search over the concrete
// numeric array types (std.intarr / std.longarr / std.floatarr).
//
// 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 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.

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

import std.string

// ---- array externs (bound to the same C the array modules use) -----------
extern intarr_size(arr: ptr) -> int
extern intarr_get_unchecked(arr: ptr, i: int) -> int
extern intarr_set_unchecked(arr: ptr, i: int, value: int)

extern longarr_size(arr: ptr) -> int
extern longarr_get_unchecked(arr: ptr, i: int) -> long
extern longarr_set_unchecked(arr: ptr, i: int, value: long)

extern floatarr_size(arr: ptr) -> int
extern floatarr_get_unchecked(arr: ptr, i: int) -> double
extern floatarr_set_unchecked(arr: ptr, i: int, value: double)

// 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]

// ---- intarr ---------------------------------------------------------------

// Sort an intarr ascending, in place.
ints(arr: ptr) {
    n = intarr_size(arr)
    if n < 2 { return }
    // Build the largest starting gap <= n/2 (Ciura, then *2.25 growth).
    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
    }
    // Shell sort with the descending gap chain.
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = intarr_get_unchecked(arr, i)
            j = i
            while j >= gap && intarr_get_unchecked(arr, j - gap) > tmp {
                intarr_set_unchecked(arr, j, intarr_get_unchecked(arr, j - gap))
                j = j - gap
            }
            intarr_set_unchecked(arr, j, tmp)
            i = i + 1
        }
        if gap == 1 {
            gap = 0
        } else {
            gap = (gap * 4) / 9
            if gap < 1 { gap = 1 }
        }
    }
}

// Binary search a SORTED intarr for `x`. Returns the index of `x` if
// present, otherwise the insertion point (the index where `x` would be
// inserted to keep the array sorted) — matching C3's binarysearch contract.
int_search(arr: ptr, x: int) -> int {
    lo = 0
    hi = intarr_size(arr)
    while lo < hi {
        mid = lo + (hi - lo) / 2
        v = intarr_get_unchecked(arr, mid)
        if v < x { lo = mid + 1 } else { hi = mid }
    }
    return lo
}

// ---- longarr --------------------------------------------------------------

longs(arr: ptr) {
    n = longarr_size(arr)
    if n < 2 { return }
    gap = 1
    idx = 0
    while idx < 8 && CIURA[idx] < n {
        gap = CIURA[idx]
        idx = idx + 1
    }
    while gap < n / 2 {
        gap = (gap * 9) / 4
    }
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = longarr_get_unchecked(arr, i)
            j = i
            while j >= gap && longarr_get_unchecked(arr, j - gap) > tmp {
                longarr_set_unchecked(arr, j, longarr_get_unchecked(arr, j - gap))
                j = j - gap
            }
            longarr_set_unchecked(arr, j, tmp)
            i = i + 1
        }
        if gap == 1 {
            gap = 0
        } else {
            gap = (gap * 4) / 9
            if gap < 1 { gap = 1 }
        }
    }
}

long_search(arr: ptr, x: long) -> int {
    lo = 0
    hi = longarr_size(arr)
    while lo < hi {
        mid = lo + (hi - lo) / 2
        v = longarr_get_unchecked(arr, mid)
        if v < x { lo = mid + 1 } else { hi = mid }
    }
    return lo
}

// ---- floatarr -------------------------------------------------------------

floats(arr: ptr) {
    n = floatarr_size(arr)
    if n < 2 { return }
    gap = 1
    idx = 0
    while idx < 8 && CIURA[idx] < n {
        gap = CIURA[idx]
        idx = idx + 1
    }
    while gap < n / 2 {
        gap = (gap * 9) / 4
    }
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = floatarr_get_unchecked(arr, i)
            j = i
            while j >= gap && floatarr_get_unchecked(arr, j - gap) > tmp {
                floatarr_set_unchecked(arr, j, floatarr_get_unchecked(arr, j - gap))
                j = j - gap
            }
            floatarr_set_unchecked(arr, j, tmp)
            i = i + 1
        }
        if gap == 1 {
            gap = 0
        } else {
            gap = (gap * 4) / 9
            if gap < 1 { gap = 1 }
        }
    }
}

float_search(arr: ptr, x: double) -> int {
    lo = 0
    hi = floatarr_size(arr)
    while lo < hi {
        mid = lo + (hi - lo) / 2
        v = floatarr_get_unchecked(arr, mid)
        if v < x { lo = mid + 1 } else { hi = mid }
    }
    return lo
}

// ---- strings --------------------------------------------------------------
//
// `string[]` is a bare C array with no carried length, unlike the intarr /
// longarr / floatarr handles above, so these take an explicit element count.
// Passing a count larger than the array reads out of bounds exactly as it
// would in C -- the array does not know its own size and cannot check.
//
// Ordering is std.string.compare: lexicographic BYTE order, binary-safe
// (embedded NULs take part). That is the same default C, Go and Zig use.
// Locale-aware collation is a different question and stays in contrib/i18n.

strings(arr: string[], n: int) {
    if n < 2 { return }
    gap = 1
    idx = 0
    while idx < 8 && CIURA[idx] < n {
        gap = CIURA[idx]
        idx = idx + 1
    }
    while gap < n / 2 {
        gap = (gap * 9) / 4
    }
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = arr[i]
            j = i
            while j >= gap && string.compare(arr[j - gap], tmp) > 0 {
                arr[j] = arr[j - gap]
                j = j - gap
            }
            arr[j] = tmp
            i = i + 1
        }
        if gap == 1 {
            gap = 0
        } else {
            gap = (gap * 4) / 9
            if gap < 1 { gap = 1 }
        }
    }
}

// Lower bound: the index of the first element not ordered before `x`, which
// is where `x` would be inserted to keep the array sorted. Equal to `n` when
// every element sorts before `x`. Same contract as int_search.
string_search(arr: string[], n: int, x: string) -> int {
    lo = 0
    hi = n
    while lo < hi {
        mid = lo + (hi - lo) / 2
        if string.compare(arr[mid], x) < 0 { lo = mid + 1 } else { hi = mid }
    }
    return lo
}

// ---- comparator forms -----------------------------------------------------
//
// `cmp(a, b)` returns <0 when a sorts before b, 0 when they tie, >0 when a
// sorts after. It must be a strict weak ordering: an inconsistent comparator
// gives an unspecified permutation, not a crash, but not a sorted array
// either.
//
// Separate names rather than an optional argument on `ints`/`strings` 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.

ints_by(arr: ptr, cmp: fn(int, int) -> int) {
    n = intarr_size(arr)
    if n < 2 { return }
    gap = 1
    idx = 0
    while idx < 8 && CIURA[idx] < n {
        gap = CIURA[idx]
        idx = idx + 1
    }
    while gap < n / 2 {
        gap = (gap * 9) / 4
    }
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = intarr_get_unchecked(arr, i)
            j = i
            while j >= gap && cmp(intarr_get_unchecked(arr, j - gap), tmp) > 0 {
                intarr_set_unchecked(arr, j, intarr_get_unchecked(arr, j - gap))
                j = j - gap
            }
            intarr_set_unchecked(arr, j, tmp)
            i = i + 1
        }
        if gap == 1 {
            gap = 0
        } else {
            gap = (gap * 4) / 9
            if gap < 1 { gap = 1 }
        }
    }
}

longs_by(arr: ptr, cmp: fn(long, long) -> int) {
    n = longarr_size(arr)
    if n < 2 { return }
    gap = 1
    idx = 0
    while idx < 8 && CIURA[idx] < n {
        gap = CIURA[idx]
        idx = idx + 1
    }
    while gap < n / 2 {
        gap = (gap * 9) / 4
    }
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = longarr_get_unchecked(arr, i)
            j = i
            while j >= gap && cmp(longarr_get_unchecked(arr, j - gap), tmp) > 0 {
                longarr_set_unchecked(arr, j, longarr_get_unchecked(arr, j - gap))
                j = j - gap
            }
            longarr_set_unchecked(arr, j, tmp)
            i = i + 1
        }
        if gap == 1 {
            gap = 0
        } else {
            gap = (gap * 4) / 9
            if gap < 1 { gap = 1 }
        }
    }
}

floats_by(arr: ptr, cmp: fn(double, double) -> int) {
    n = floatarr_size(arr)
    if n < 2 { return }
    gap = 1
    idx = 0
    while idx < 8 && CIURA[idx] < n {
        gap = CIURA[idx]
        idx = idx + 1
    }
    while gap < n / 2 {
        gap = (gap * 9) / 4
    }
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = floatarr_get_unchecked(arr, i)
            j = i
            while j >= gap && cmp(floatarr_get_unchecked(arr, j - gap), tmp) > 0 {
                floatarr_set_unchecked(arr, j, floatarr_get_unchecked(arr, j - gap))
                j = j - gap
            }
            floatarr_set_unchecked(arr, j, tmp)
            i = i + 1
        }
        if gap == 1 {
            gap = 0
        } else {
            gap = (gap * 4) / 9
            if gap < 1 { gap = 1 }
        }
    }
}

strings_by(arr: string[], n: int, cmp: fn(string, string) -> int) {
    if n < 2 { return }
    gap = 1
    idx = 0
    while idx < 8 && CIURA[idx] < n {
        gap = CIURA[idx]
        idx = idx + 1
    }
    while gap < n / 2 {
        gap = (gap * 9) / 4
    }
    while gap >= 1 {
        i = gap
        while i < n {
            tmp = arr[i]
            j = i
            while j >= gap && cmp(arr[j - gap], tmp) > 0 {
                arr[j] = arr[j - gap]
                j = j - gap
            }
            arr[j] = tmp
            i = i + 1
        }
        if gap == 1 {
            gap = 0
        } else {
            gap = (gap * 4) / 9
            if gap < 1 { gap = 1 }
        }
    }
}