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

std/src/collections/vec/sort.nv
404 строки14 KB
Evgeniy Golovin
style(185): дочистка 23 сайтов W_MANUAL_MIN_MAX на @max()/@min()/@clamp() поверх main
20 июл 2026, 02:41
20 июл 2026, 02:41cd165a8
// std.collections.vec (sort) — Plan 153.3 sort family.
//
// Two distinct production algorithms:
//   * STABLE   = bottom-up merge sort (O(n log n) guaranteed, O(n) scratch),
//                preserves equal-element order — `@sort[_by][_by_key]`.
//   * UNSTABLE = pdqsort (pattern-defeating quicksort): median-of-3 pivot +
//                Lomuto partition + insertion-sort (n≤16) + heapsort
//                depth-guard (2·log₂(n)), O(n log n) worst, O(log n) stack —
//                `@sort_unstable[_by][_by_key]`.
// Comparators return int (<0 / 0 / >0); there is no `Ordering` type (D183).
#prelude(core, runtime, collections, protocols)
module collections.vec

// Internal driver: bottom-up STABLE merge sort by `cmp`. Not exported.
// Equal elements keep input order (`cmp(a, b) <= 0` takes the left run first).
fn Vec[T] mut @msort(cmp fn(T, T) -> int) -> @ {
    ro n = @len
    if n < 2 {
        return
    }
    mut buf = Vec[T].new(cap: n)
    mut width = 1
    while width < n {
        buf.clear()
        mut i = 0
        while i < n {
            ro mid = (i + width).min(n)
            ro hi = (i + width + width).min(n)
            mut a = i
            mut b = mid
            while a < mid && b < hi {
                ro ea = unsafe { @data.read_at(a) }
                ro eb = unsafe { @data.read_at(b) }
                if cmp(ea, eb) <= 0 {
                    buf.push(ea)
                    a += 1
                } else {
                    buf.push(eb)
                    b += 1
                }
            }
            while a < mid {
                ro ea = unsafe { @data.read_at(a) }
                buf.push(ea)
                a += 1
            }
            while b < hi {
                ro eb = unsafe { @data.read_at(b) }
                buf.push(eb)
                b += 1
            }
            i = i + width + width
        }
        for j in 0..n {
            ro bj = unsafe { buf.data.read_at(j) }
            unsafe { @data.write_at(j, bj) }
        }
        width += width
    }
}

// Internal: sift element at `root` down a max-heap over [0, end). Iterative.
// Max-heap by `cmp` (`cmp(a,b) < 0` ⇒ a precedes b ⇒ a is "smaller"), so the
// largest element bubbles to index 0.
fn Vec[T] mut @sift_down(root_in int, end int, cmp fn(T, T) -> int) -> @ {
    mut root = root_in
    mut child = root + root + 1
    while child < end {
        mut sel = child
        if child + 1 < end {
            ro lc = unsafe { @data.read_at(child) }
            ro rc = unsafe { @data.read_at(child + 1) }
            if cmp(lc, rc) < 0 {
                sel = child + 1
            }
        }
        ro rootv = unsafe { @data.read_at(root) }
        ro selv = unsafe { @data.read_at(sel) }
        if cmp(rootv, selv) >= 0 {
            return
        }
        @swap(root, sel)
        root = sel
        child = root + root + 1
    }
}

// Internal: in-place UNSTABLE heapsort by `cmp` (ascending). Build a max-heap,
// then pop the max to the shrinking tail. O(n log n) worst, O(1) extra space.
fn Vec[T] mut @heapsort(cmp fn(T, T) -> int) -> @ {
    ro n = @len
    if n < 2 {
        return
    }
    mut start = n / 2
    while start > 0 {
        start -= 1
        @sift_down(start, n, cmp)
    }
    mut end = n
    while end > 1 {
        end -= 1
        @swap(0, end)
        @sift_down(0, end, cmp)
    }
}

// Internal: insertion sort for small slices [lo, hi).
fn Vec[T] mut @ins_sort_range(lo int, hi int, cmp fn(T, T) -> int) -> @ {
    for i in lo + 1..hi {
        ro key = unsafe { @data.read_at(i) }
        mut j = i - 1
        while j >= lo {
            ro ej = unsafe { @data.read_at(j) }
            if cmp(ej, key) <= 0 { break }
            unsafe { @data.write_at(j + 1, ej) }
            j -= 1
        }
        unsafe { @data.write_at(j + 1, key) }
    }
}

// Internal: integer log2 (floor). ilog2(1)=0, ilog2(2)=1, ilog2(4)=2, etc.
fn pdq_ilog2(n int) -> int {
    mut result = 0
    mut m = n
    while m > 1 {
        m /= 2
        result += 1
    }
    result
}

// Internal: iterative pdqsort over the full Vec by `cmp`.
// Uses an explicit work-stack (Vec of int pairs lo/hi) to avoid recursion.
// Threshold PDQ_SMALL=16 for insertion sort; depth_limit=2*ilog2(n) for heapsort fallback.
fn Vec[T] mut @pdqsort(cmp fn(T, T) -> int) -> @ {
    ro n = @len
    if n < 2 {
        return
    }
    ro depth_limit = pdq_ilog2(n) + pdq_ilog2(n) + 2
    mut stack = Vec[int].new()
    stack.push(0)
    stack.push(n)
    while stack.len > 0 {
        ro hi_val = stack.pop()
        match hi_val {
            None => { break }
            Some(hi) => {
                ro lo_val = stack.pop()
                match lo_val {
                    None => { break }
                    Some(lo) => {
                        ro size = hi - lo
                        if size <= 1 {
                            // nothing to do
                        } else if size <= 16 {
                            @ins_sort_range(lo, hi, cmp)
                        } else if stack.len >= depth_limit {
                            // depth guard: heapsort this range via temp Vec
                            mut tmp = Vec[T].new(cap: size)
                            for ci in lo..hi {
                                tmp.push(unsafe { @data.read_at(ci) })
                            }
                            tmp.heapsort(cmp)
                            mut wi = lo
                            mut ti = 0
                            while wi < hi {
                                ro tv = unsafe { tmp.data.read_at(ti) }
                                unsafe { @data.write_at(wi, tv) }
                                wi += 1
                                ti += 1
                            }
                        } else {
                            // median-of-3 pivot to position hi-1
                            ro mid = lo + size / 2
                            @median3_to_end(lo, mid, hi - 1, cmp)
                            ro pivot = unsafe { @data.read_at(hi - 1) }
                            // Lomuto partition [lo, hi-1) around pivot
                            mut i = lo
                            mut j = lo
                            while j < hi - 1 {
                                ro ej = unsafe { @data.read_at(j) }
                                if cmp(ej, pivot) < 0 {
                                    if i != j {
                                        @swap(i, j)
                                    }
                                    i += 1
                                }
                                j += 1
                            }
                            @swap(i, hi - 1)
                            ro p = i
                            // push the larger partition first
                            ro left_size = p - lo
                            ro right_size = hi - (p + 1)
                            if left_size >= right_size {
                                if p - lo > 1 {
                                    stack.push(lo)
                                    stack.push(p)
                                }
                                if hi - (p + 1) > 1 {
                                    stack.push(p + 1)
                                    stack.push(hi)
                                }
                            } else {
                                if hi - (p + 1) > 1 {
                                    stack.push(p + 1)
                                    stack.push(hi)
                                }
                                if p - lo > 1 {
                                    stack.push(lo)
                                    stack.push(p)
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

/// Sort in place ascending by the element's own `Compare` (stable). O(n log n).
export fn Vec[T Compare] mut @sort() -> @ => @msort(|a, b| a.compare(b))

/// Sort in place by a custom comparator `cmp(a, b)` (`<0`/`0`/`>0`), stable.
export fn Vec[T] mut @sort_by(cmp fn(T, T) -> int) -> @ => @msort(cmp)

/// Sort in place by a projected key, ordered by the key type's `Compare`, stable.
export fn Vec[T] mut @sort_by_key[K Compare](key fn(T) -> K) -> @ => @msort(|a, b| key(a).compare(key(b)))

/// Unstable in-place sort by the element's own `Compare` — pdqsort, O(n log n),
/// O(log n) stack (no scratch buffer, unlike `@sort`). No equal-order guarantee.
export fn Vec[T Compare] mut @sort_unstable() -> @ => @pdqsort(|a, b| a.compare(b))

/// Unstable in-place sort by comparator `cmp(a, b)` (`<0`/`0`/`>0`) — pdqsort.
export fn Vec[T] mut @sort_unstable_by(cmp fn(T, T) -> int) -> @ => @pdqsort(cmp)

/// Unstable in-place sort by projected key — pdqsort.
export fn Vec[T] mut @sort_unstable_by_key[K Compare](key fn(T) -> K) -> @ => @pdqsort(|a, b| key(a).compare(key(b)))

// ─── dedup + partition (Plan 153.3 reordering) ────────────────────────

/// Remove CONSECUTIVE equal elements in place (each compared with the last
/// kept via `==`), preserving order. O(n). Pair with `@sort()` to drop *all*
/// duplicates (`v.sort().dedup()`). Returns `@`.
export fn Vec[T] mut @dedup() -> @ {
    if @len < 2 {
        return
    }
    mut write = 1
    for read in 1..@len {
        ro cur = unsafe { @data.read_at(read) }
        ro prev = unsafe { @data.read_at(write - 1) }
        if !(cur == prev) {
            if write != read {
                unsafe { @data.write_at(write, cur) }
            }
            write += 1
        }
    }
    @len = write
}

/// Remove consecutive elements considered equal by `eq(prev, cur)`. O(n).
export fn Vec[T] mut @dedup_by(eq fn(T, T) -> bool) -> @ {
    if @len < 2 {
        return
    }
    mut write = 1
    for read in 1..@len {
        ro cur = unsafe { @data.read_at(read) }
        ro prev = unsafe { @data.read_at(write - 1) }
        if !eq(prev, cur) {
            if write != read {
                unsafe { @data.write_at(write, cur) }
            }
            write += 1
        }
    }
    @len = write
}

/// Remove consecutive elements with equal projected key (`key(x)` via `==`). O(n).
export fn Vec[T] mut @dedup_by_key[K Equal](key fn(T) -> K) -> @ {
    if @len < 2 {
        return
    }
    mut write = 1
    for read in 1..@len {
        ro cur = unsafe { @data.read_at(read) }
        ro prev = unsafe { @data.read_at(write - 1) }
        ro kc = key(cur)
        ro kp = key(prev)
        if !(kc == kp) {
            if write != read {
                unsafe { @data.write_at(write, cur) }
            }
            write += 1
        }
    }
    @len = write
}

/// Reorder in place so every element satisfying `pred` precedes those that do
/// not; returns the partition point (the count of satisfying elements).
/// UNSTABLE (swap-based; does not preserve relative order). O(n).
export fn Vec[T] mut @partition(pred fn(T) -> bool) -> int {
    mut i = 0
    for j in 0..@len {
        ro ej = unsafe { @data.read_at(j) }
        if pred(ej) {
            if i != j {
                @swap(i, j)
            }
            i += 1
        }
    }
    i
}

// ─── select_nth (introselect, Plan 153.3) ─────────────────────────────

// Internal: move the median of @data[a]/@data[b]/@data[c] to index `c`
// (median-of-three pivot — kills the sorted/reverse O(n²) quickselect case).
fn Vec[T] mut @median3_to_end(a int, b int, c int, cmp fn(T, T) -> int) -> @ {
    ro va = unsafe { @data.read_at(a) }
    ro vb = unsafe { @data.read_at(b) }
    ro vc = unsafe { @data.read_at(c) }
    ro med = if cmp(va, vb) < 0 {
        if cmp(vb, vc) < 0 { b } else { if cmp(va, vc) < 0 { c } else { a } }
    } else {
        if cmp(va, vc) < 0 { a } else { if cmp(vb, vc) < 0 { c } else { b } }
    }
    if med != c {
        @swap(med, c)
    }
}

// Internal: Lomuto partition of [lo, hi) around a median-of-three pivot.
// Returns the pivot's final index `p`; [lo, p) < pivot ≤ [p, hi).
fn Vec[T] mut @partition_range(lo int, hi int, cmp fn(T, T) -> int) -> int {
    ro mid = lo + (hi - lo) / 2
    @median3_to_end(lo, mid, hi - 1, cmp)
    ro pivot = unsafe { @data.read_at(hi - 1) }
    mut i = lo
    for j in lo..hi - 1 {
        ro ej = unsafe { @data.read_at(j) }
        if cmp(ej, pivot) < 0 {
            if i != j {
                @swap(i, j)
            }
            i += 1
        }
    }
    @swap(i, hi - 1)
    i
}

// Internal: introselect over [lo, hi) for global index `k`. Quickselect with a
// depth guard: on exhaustion fall back to the O(n log n) heapsort (after a full
// sort the k-th order statistic sits at index k). Average O(n), worst O(n log n).
fn Vec[T] mut @qselect(lo_in int, hi_in int, k int, depth_in int, cmp fn(T, T) -> int) -> @ {
    mut lo = lo_in
    mut hi = hi_in
    mut depth = depth_in
    while hi - lo > 1 {
        if depth == 0 {
            @heapsort(cmp)
            return
        }
        depth -= 1
        ro p = @partition_range(lo, hi, cmp)
        if k == p {
            return
        }
        if k < p {
            hi = p
        } else {
            lo = p + 1
        }
    }
}

/// Partition in place so the element at sorted position `k` lands at `self[k]`,
/// every earlier element ≤ it and every later element ≥ it (UNSTABLE). Returns
/// that k-th-smallest value. Introselect: O(n) average, O(n log n) worst
/// (heapsort guard — no quickselect O(n²) cliff). Panics if `k` is out of bounds.
export fn Vec[T Compare] mut @select_nth_unstable(k int) -> T
    requires k >= 0 && k < @len
{
    ro n = @len
    mut lim = 0
    mut m = n
    while m > 1 {
        m /= 2
        lim += 1
    }
    lim = lim + lim + 2
    @qselect(0, n, k, lim, |a, b| a.compare(b))
    unsafe { @data.read_at(k) }
}