std/src/sort.nv - main - nv-lang/nova

std/src/sort.nv
397 строк11 KB
Evgeniy Golovin
docs(endocs): root — translate bench, sort, reflect /// docs to English
01 авг 2026, 02:53
01 авг 2026, 02:532d8be0e
// std/sort.nv — sorting / aggregation utilities over `[]int` & `[T]`
// (Plan 91 Ф.4; Plan 153.x consolidation pass).
//
// CANON NOTE (D239 `[]T ≡ Vec[T]`). The canonical, prelude-visible sort/search
// surface is the `collections.vec` family (`@sort`/`@sort_by`/`@sort_by_key`
// merge sort, `@binary_search -> Result`, `@dedup`/`@partition`/
// `@select_nth_unstable`, …). This opt-in module retains the concrete-`[]int`
// and eager-reduce helpers that EITHER have no Vec equivalent OR are still
// required because `[]int.new()`/`with_capacity()` lower to the legacy
// `NovaArray_T` runtime type, on which prelude Vec `mut @`-methods mis-dispatch
// (codegen blocker `[M-153.x-array-new-not-vec]`).
//
// Current surface (Plan 91 §Scope, minus the removed `@binary_search`):
//   - `[]int @sort()` / `[]int @sort_by(cmp)` — in-place insertion sort
//     (stable, O(n²)). KEPT for the `NovaArray` receiver path above.
//   - `[]int @min()` / `@max()` — `Option[int]`, None for empty.
//   - generic `*_of` reduce/query family + `@sum`/`@product`.
//   REMOVED: `[]int @binary_search -> Option` (return-type-conflicted with the
//   prelude Vec `@binary_search -> Result`; see the note above its old slot).
//
// Stability: 0.1 surface stable (the removed `@binary_search` resolves to the
// Vec canon, returning `Result` instead of `Option`).

module std.sort

/// In-place insertion sort for `[]int` (stable, O(n²)).
///
/// Suitable for arrays up to ~1000 elements. For larger sets
/// wait for Plan 91 followup `[sort-pdq]` (pdq-sort) or
/// `[sort-generic-T]` (intro-sort).
///
/// # Examples
/// ```nova
/// let mut xs []int = [3, 1, 4, 1, 5, 9, 2, 6]
/// xs.sort()
/// assert(xs == [1, 1, 2, 3, 4, 5, 6, 9])
/// ```
#stable(since = "0.1")
export fn []int mut @sort() -> @ {
    ro n = @len()
    for i in 1..n {
        ro key = @[i]
        mut j = i - 1
        while j >= 0 && @[j] > key {
            @[j + 1] = @[j]
            j -= 1
        }
        @[j + 1] = key
    }
}

/// In-place insertion sort with a custom comparator `cmp(a, b) -> int`.
///
/// `cmp` returns negative if `a` should come before `b`, 0 if the
/// order does not matter, positive if `a` comes after `b`. The sort is stable —
/// equal-pairs (`cmp == 0`) keep their original order. Compatible with the
/// C `memcmp`/`strcmp` convention (see D183).
///
/// # Examples
/// ```nova
/// let mut xs []int = [3, 1, 4]
/// xs.sort_by(|a, b| b - a)   // descending
/// assert(xs == [4, 3, 1])
/// ```
#stable(since = "0.1")
export fn []int mut @sort_by(cmp fn(int, int) -> int) -> @ {
    ro n = @len()
    for i in 1..n {
        ro key = @[i]
        mut j = i - 1
        while j >= 0 && cmp(@[j], key) > 0 {
            @[j + 1] = @[j]
            j -= 1
        }
        @[j + 1] = key
    }
}

// NOTE (Plan 153.x consolidation): the concrete `[]int @binary_search ->
// Option[int]` that lived here was REMOVED. Under D239 (`[]T ≡ Vec[T]`) it
// became a second `@binary_search` on `[]int` whose RETURN TYPE conflicts
// with the canonical, prelude-visible `[]T Compare @binary_search ->
// Result[int,int]` (std/collections/vec/access.nv). The prelude version wins
// resolution, so a caller writing `xs.binary_search(t) == Some(i)` hit a
// hard C type error (`NovaRes_*` vs `NovaOpt_*`). The canon is the Vec
// `Result` form — `Ok(i)` found / `Err(insertion_point)` not found — richer
// than the old `Option`; comparator / projected-key variants are
// `@binary_search_by` / `@binary_search_by_key`. Migrate call sites to
// `== Ok(i)` / `== Err(i)`.
//
// The OTHER concrete `[]int` ops below (`@sort`/`@sort_by`/`@min`/`@max` and
// the generic `*_of` family) are intentionally KEPT: they do not return-type-
// conflict, and their `[]int`-exact receiver signatures are still REQUIRED for
// correct in-place mutation of arrays built via `[]int.new()` /
// `[]int.with_capacity()`. Those constructors currently lower to the legacy
// `NovaArray_T` runtime type (not `[]T`), and a `mut @`-method call on such
// a receiver mis-dispatches to the erased generic `Nova_Vec_method_*` (element
// width erased to `void*`), so the prelude Vec `@sort`/`@reverse` silently
// no-op on them. Removing the `[]int @sort`/`@sort_by` here would regress every
// `[]int.new()...sort()` site. Tracked as the codegen blocker
// `[M-153.x-array-new-not-vec]` — full consolidation into the Vec family is
// gated on that fix.

/// Minimum value in `[]int`. `None` for empty.
///
/// # Examples
/// ```nova
/// assert([3, 1, 4].min() == Some(1))
/// let empty []int = []
/// assert(empty.min() == None)
/// ```
#stable(since = "0.1")
export fn []int @min() -> Option[int] {
    ro n = @len()
    if n == 0 {
        return None
    }
    mut m = @[0]
    for i in 1..n {
        ro v = @[i]
        if v < m {
            m = v
        }
    }
    Some(m)
}

/// Maximum value in `[]int`. `None` for empty.
///
/// # Examples
/// ```nova
/// assert([3, 1, 4].max() == Some(4))
/// let empty []int = []
/// assert(empty.max() == None)
/// ```
#stable(since = "0.1")
export fn []int @max() -> Option[int] {
    ro n = @len()
    if n == 0 {
        return None
    }
    mut m = @[0]
    for i in 1..n {
        ro v = @[i]
        if v > m {
            m = v
        }
    }
    Some(m)
}

// ──────────────────────────────────────────────────────────────────────────
// Plan 91.8c: Generic [T Compare] versions (D185)
//
// Любой тип satisfying Compare (имеет @compare(other Self) -> int)
// автоматически получает min_of/max_of через mono pass + synthesis.
// Concrete []int @min/@max выше остаются как fast-path для int (без mono overhead).
// ──────────────────────────────────────────────────────────────────────────

/// Generic min for any `[T Compare]`. `None` for empty.
///
/// # Examples
/// ```nova
/// assert([3, 1, 4].min_of() == Some(1))
/// assert(["zebra", "apple", "mango"].min_of() == Some("apple"))
/// ```
#stable(since = "0.1")
export fn[T Compare] []T @min_of() -> Option[T] {
    ro n = @len()
    if n == 0 { return None }
    mut m = @[0]
    for i in 1..n {
        ro v = @[i]
        if v.compare(m) < 0 { m = v }
    }
    Some(m)
}

/// Generic max for any `[T Compare]`. `None` for empty.
#stable(since = "0.1")
export fn[T Compare] []T @max_of() -> Option[T] {
    ro n = @len()
    if n == 0 { return None }
    mut m = @[0]
    for i in 1..n {
        ro v = @[i]
        if v.compare(m) > 0 { m = v }
    }
    Some(m)
}

/// Generic insertion sort for `[T Compare]` (stable, O(n²)).
///
/// # Examples
/// ```nova
/// let mut xs []str = ["zebra", "apple", "mango"]
/// xs.sort_of()
/// assert(xs == ["apple", "mango", "zebra"])
/// ```
#stable(since = "0.1")
export fn[T Compare] []T mut @sort_of() -> @ {
    ro n = @len()
    for i in 1..n {
        ro key = @[i]
        mut j = i - 1
        mut cur = @[j]
        while j >= 0 && cur > key {
            @[j + 1] = cur
            j -= 1
            if j >= 0 { cur = @[j] }
        }
        @[j + 1] = key
    }
}

/// Generic min_by with a custom comparator. T does not have to satisfy Compare.
/// `None` for empty.
///
/// # Examples
/// ```nova
/// // Pick word with shortest length
/// let words []str = ["apple", "kiwi", "banana"]
/// match words.min_by_of(|a, b| a.len() - b.len()) {
///     Some(w) => assert(w == "kiwi")
///     _       => assert(false)
/// }
/// ```
#stable(since = "0.1")
export fn[T] []T @min_by_of(cmp fn(T, T) -> int) -> Option[T] {
    ro n = @len()
    if n == 0 { return None }
    mut m = @[0]
    for i in 1..n {
        ro v = @[i]
        if cmp(v, m) < 0 { m = v }
    }
    Some(m)
}

/// Generic max_by with a custom comparator.
#stable(since = "0.1")
export fn[T] []T @max_by_of(cmp fn(T, T) -> int) -> Option[T] {
    ro n = @len()
    if n == 0 { return None }
    mut m = @[0]
    for i in 1..n {
        ro v = @[i]
        if cmp(v, m) > 0 { m = v }
    }
    Some(m)
}

/// Generic in-place reverse for any `[T]`. Returns `@` for fluent chaining.
///
/// # Examples
/// ```nova
/// let mut xs []int = [1, 2, 3, 4, 5]
/// xs.reverse_of()
/// assert(xs == [5, 4, 3, 2, 1])
/// ```
#stable(since = "0.1")
export fn[T] []T mut @reverse_of() -> @ {
    ro n = @len()
    mut i = 0
    mut j = n - 1
    while i < j {
        ro tmp = @[i]
        @[i] = @[j]
        @[j] = tmp
        i += 1
        j -= 1
    }
}

/// Sum for `[]int`. Returns 0 for empty.
///
/// # Examples
/// ```nova
/// assert([1, 2, 3, 4, 5].sum() == 15)
/// let empty []int = []
/// assert(empty.sum() == 0)
/// ```
#stable(since = "0.1")
export fn []int @sum() -> int {
    ro n = @len()
    mut s = 0
    for i in 0..n {
        s += @[i]
    }
    s
}

/// Product for `[]int`. Returns 1 for empty (multiplicative identity).
#stable(since = "0.1")
export fn []int @product() -> int {
    ro n = @len()
    mut p = 1
    for i in 0..n {
        p *= @[i]
    }
    p
}

/// Generic position_of — index of the first element satisfying the predicate.
/// `None` if none match.
///
/// # Examples
/// ```nova
/// let xs []int = [1, 3, 4, 7, 8]
/// assert(xs.position_of(|x| x > 3) == Some(2))
/// assert(xs.position_of(|x| x > 100) == None)
/// ```
#stable(since = "0.1")
export fn[T] []T @position_of(pred fn(T) -> bool) -> Option[int] {
    ro n = @len()
    for i in 0..n {
        ro v = @[i]
        if pred(v) { return Some(i) }
    }
    None
}

/// Generic count_of — how many elements satisfy the predicate.
///
/// # Examples
/// ```nova
/// let xs []int = [1, 3, 4, 7, 8]
/// assert(xs.count_of(|x| x > 3) == 3)   // 4, 7, 8
/// ```
#stable(since = "0.1")
export fn[T] []T @count_of(pred fn(T) -> bool) -> int {
    ro n = @len()
    mut count = 0
    for i in 0..n {
        ro v = @[i]
        if pred(v) { count += 1 }
    }
    count
}

/// Generic find_of — the first element satisfying the predicate. `None` if none.
///
/// # Examples
/// ```nova
/// let xs []int = [1, 3, 4, 7, 8]
/// assert(xs.find_of(|x| x > 3) == Some(4))
/// ```
#stable(since = "0.1")
export fn[T] []T @find_of(pred fn(T) -> bool) -> Option[T] {
    ro n = @len()
    for i in 0..n {
        ro v = @[i]
        if pred(v) { return Some(v) }
    }
    None
}

/// Generic sort_by with a custom comparator. T does not have to satisfy Compare —
/// the order is defined via `cmp(a, b) -> int` (negative/0/positive convention).
///
/// # Examples
/// ```nova
/// let mut xs []int = [3, 1, 4, 1, 5]
/// xs.sort_by_of(|a, b| b - a)    // descending
/// ```
#stable(since = "0.1")
export fn[T] []T mut @sort_by_of(cmp fn(T, T) -> int) -> @ {
    ro n = @len()
    for i in 1..n {
        ro key = @[i]
        mut j = i - 1
        mut cur = @[j]
        while j >= 0 && cmp(cur, key) > 0 {
            @[j + 1] = cur
            j -= 1
            if j >= 0 { cur = @[j] }
        }
        @[j + 1] = key
    }
}

/// Generic binary_search for a sorted `[T Compare]`.
/// Returns `Some(idx)` where `@[idx] == target` (via @compare == 0), or `None`.
#stable(since = "0.1")
export fn[T Compare] []T @binary_search_of(target T) -> Option[int] {
    mut lo = 0
    mut hi = @len() - 1
    while lo <= hi {
        ro mid = (lo + hi) / 2
        ro v = @[mid]
        ro cmp = v.compare(target)
        if cmp == 0 { return Some(mid) }
        if cmp < 0 { lo = mid + 1 }
        else       { hi = mid - 1 }
    }
    None
}