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

std/src/collections/vec/restructure.nv
268 строк12 KB
Evgeniy Golovin
docs(std/src): clean comments batch 19 — tail of /// internal-ref sweep
01 авг 2026, 16:48
01 авг 2026, 16:481b14c02
// std.collections.vec (restructure) — restructure-ops.
//
// Operations that build a NEW vector from existing data, or reshape a vector
// in place by moving whole runs of elements:
//
//   @concat(other) -> Vec[T]   — non-mutating join `self ++ other` (new buffer).
//   `+` operator    -> @plus    — `a + b` is a new Vec (≡ @concat); operands
//                                 are unchanged. `a += b` lowers to `a = a + b`
//                                 (a fresh concat Vec).
//   [][]T.@flatten() -> []T     — concatenate every inner `Vec[T]` of a
//                                 `Vec[Vec[T]]` into one flat `Vec[T]` (new
//                                 buffer), in order. `T` = innermost element.
//   mut @rotate_left(n)         — cyclic shift left by `n` (in place).
//   mut @rotate_right(n)        — cyclic shift right by `n` (in place).
//   mut @drain(range) -> Vec[T] — cut out `[range)`, RETURN the removed run as
//                                 an owned Vec; the receiver is shortened.
//   mut @insert_slice(i, sl)    — splice a slice `sl` in at index `i`.
//
// extend/append/retain/splice already live in mutate.nv (audited — NOT
// duplicated): `@append(Vec[T])` is the in-place bulk merge, `@splice(i, other)`
// is the in-place bulk insert. The new ops here are the *non-mutating* join
// (`@concat`/`+`) plus the move-runs reshapers (rotate/drain) and the
// slice-flavoured insert (`@insert_slice`, an `@splice` alias taking a `[]T`).
#prelude(core, runtime, collections, protocols)
module collections.vec

import std.runtime.raw_mem.{RawMem}
import std.collections.range.{Range}

// ──────────────────────────────────────────────────────────────────────────
// Concat / operator `+`
// ──────────────────────────────────────────────────────────────────────────

/// Build a NEW `Vec[T]` that is `self` followed by `other`. Neither operand is
/// mutated (unlike `@append`, which grows `self` in place). O(self + other) — one
/// allocation sized exactly for both runs, then two bulk `RawMem.copy` passes.
///
/// This is the non-mutating join and the body of the `+` operator (`@plus`).
/// Matches Kotlin/Python `+` and Rust `[a, b].concat()` semantics.
///
/// # Examples
///
/// ```nova
/// ro a = Vec[int].of(1, 2, 3)
/// ro b = Vec[int].of(4, 5)
/// ro c = a.concat(b)
/// assert(c.equal(Vec[int].of(1, 2, 3, 4, 5)))
/// assert(a.len() == 3)   // operands untouched
/// assert(b.len() == 2)
/// ```
export fn Vec[T] @concat(other Vec[T]) -> Vec[T] {
    ro a = @len
    ro b = other.len()
    mut out = Vec[T].new(cap: a + b)
    if a > 0 {
        unsafe {
            RawMem.copy(@data as *u8, out.data as *mut u8, a * size_of[T]())
        }
    }
    if b > 0 {
        unsafe {
            RawMem.copy(other.data as *u8, out.data.offset(a) as *mut u8, b * size_of[T]())
        }
    }
    // `out` was built with exact capacity `a + b`; set its live length to match
    // the two bulk copies above (the buffer slots are now initialised). `len`
    // is a `priv` field of the same `Vec` type, so a co-module type-method may
    // write it directly on another instance (same idiom as `other.data` reads).
    out.len = a + b
    out
}

/// Operator `+`: `a + b == a.@plus(b)` → `@concat`, resolved by operator overloading.
/// Produces a NEW `Vec[T]`; the operands are unchanged. `a += b` lowers to
/// `a = a + b` (a fresh Vec) — to grow `a` in place use `a.append(b)`.
///
/// # Examples
///
/// ```nova
/// ro a = Vec[int].of(1, 2)
/// ro b = Vec[int].of(3, 4)
/// ro c = a + b
/// assert(c.equal(Vec[int].of(1, 2, 3, 4)))
/// ```
export fn Vec[T] @plus(other Vec[T]) -> Vec[T] => @concat(other)

// ──────────────────────────────────────────────────────────────────────────
// Flatten (vector-of-vectors)
// ──────────────────────────────────────────────────────────────────────────
//
/// Concatenate every inner `Vec[T]` of a `Vec[Vec[T]]` into one flat `Vec[T]`,
/// in order — `[[1, 2], [3], [4, 5]].flatten() == [1, 2, 3, 4, 5]`. A NEW buffer
/// is built; neither the outer vector nor any inner row is mutated. Empty inner
/// rows contribute nothing; an empty outer vector flattens to an empty `Vec[T]`
/// (Rust `[[T]].concat()` / Kotlin `flatten()`). O(N) where N is the total inner
/// element count — one exact allocation plus a bulk `RawMem.copy` per inner row.
///
/// The receiver is a **nested generic carrier** `Vec[Vec[T]]`: structural
/// typevar unification binds `T` to the innermost element (`int` for
/// `Vec[Vec[int]]`), so the result is `Vec[T]`, not `Vec[Vec[T]]`. Flatten more
/// than one level by flattening repeatedly: a `Vec[Vec[Vec[T]]]` becomes a flat
/// `Vec[T]` via `nested.flatten().flatten()`.
///
/// # Examples
///
/// ```nova
/// mut nested = Vec[Vec[int]].new()
/// nested.push(Vec[int].of(1, 2))
/// nested.push(Vec[int].of(3))
/// nested.push(Vec[int].of(4, 5))
/// ro flat = nested.flatten()
/// assert(flat.equal(Vec[int].of(1, 2, 3, 4, 5)))
/// ```
export fn Vec[Vec[T]] @flatten() -> Vec[T] {
    // Pre-size the output to the exact total element count so the per-row bulk
    // appends below never reallocate (each `@append` would otherwise ×2-grow).
    mut total = 0
    for inner in @ {
        total += inner.len()
    }
    mut out = Vec[T].new(cap: total)
    // Bulk-copy each inner row onto the end of `out` (the `@append(Vec[T])`
    // fast path, mutate.nv — one `RawMem.copy` per row, COPY not move so the
    // inner rows are left unchanged). Empty rows are no-ops inside `@append`.
    for inner in @ {
        out.append(inner)
    }
    out
}

// ──────────────────────────────────────────────────────────────────────────
// Rotate (cyclic shift, in place)
// ──────────────────────────────────────────────────────────────────────────

/// Rotate the live elements left by `n` positions, in place. Element at index
/// `i` moves to `(i - n) mod len`; the first `n` elements wrap to the end.
/// `n` is reduced mod `len`, so any `n >= 0` is valid (a full or multi-turn
/// rotation is the identity). O(len) time, O(min(n, len-n)) scratch.
///
/// Empty / single-element vectors are unchanged. Returns `@` for chaining.
///
/// # Examples
///
/// ```nova
/// mut v = Vec[int].of(1, 2, 3, 4, 5)
/// v.rotate_left(2)
/// assert(v.equal(Vec[int].of(3, 4, 5, 1, 2)))
/// ```
export fn Vec[T] mut @rotate_left(n int) -> @
    requires n >= 0
{
    if @len < 2 {
        return
    }
    ro k = n % @len
    if k == 0 {
        return
    }
    // Save the leading `k` elements, shift the suffix `[k, len)` down to the
    // front (overlap-safe memmove), then drop the saved prefix into the tail.
    mut head = Vec[T].new(cap: k)
    unsafe {
        RawMem.copy(@data as *u8, head.data as *mut u8, k * size_of[T]())
    }
    head.len = k
    unsafe {
        RawMem.copy(@data.offset(k) as *u8, @data as *mut u8, (@len - k) * size_of[T]())
        RawMem.copy(head.data as *u8, @data.offset(@len - k) as *mut u8, k * size_of[T]())
    }
}

/// Rotate the live elements right by `n` positions, in place. Element at index
/// `i` moves to `(i + n) mod len`; the last `n` elements wrap to the front.
/// `n` is reduced mod `len`. O(len) time. Empty / single-element vectors are
/// unchanged. Returns `@` for chaining.
///
/// # Examples
///
/// ```nova
/// mut v = Vec[int].of(1, 2, 3, 4, 5)
/// v.rotate_right(2)
/// assert(v.equal(Vec[int].of(4, 5, 1, 2, 3)))
/// ```
export fn Vec[T] mut @rotate_right(n int) -> @
    requires n >= 0
{
    if @len < 2 {
        return
    }
    ro k = n % @len
    if k == 0 {
        return
    }
    // Rotating right by `k` is rotating left by `len - k`.
    @rotate_left(@len - k)
}

// ──────────────────────────────────────────────────────────────────────────
// Drain (cut out a range, return it owned)
// ──────────────────────────────────────────────────────────────────────────

/// Remove the half-open range `[range.start, range.end)` from `self` and return
/// the removed elements as a NEW owned `Vec[T]`. The suffix after the range is
/// shifted down to close the gap, so `self` is shortened by `range.len()`.
/// O(len) — one bulk copy out + one bulk shift down.
///
/// Panics if the range is out of bounds (`start < 0`, `end < start`, or
/// `end > len`). An empty range drains nothing and returns an empty `Vec`.
///
/// # Examples
///
/// ```nova
/// mut v = Vec[int].of(1, 2, 3, 4, 5)
/// ro cut = v.drain(1..4)
/// assert(cut.equal(Vec[int].of(2, 3, 4)))
/// assert(v.equal(Vec[int].of(1, 5)))
/// ```
export fn Vec[T] mut @drain(range Range) -> Vec[T]
    requires range.start >= 0 && range.end >= range.start && range.end <= @len
{
    ro { start, end } = range
    ro count = end - start
    mut out = Vec[T].new(cap: count)
    if count == 0 {
        return out
    }
    // Copy the drained run out, then shift the suffix `[end, len)` left into the
    // hole at `start` (overlap-safe memmove), and shorten `self`.
    unsafe {
        RawMem.copy(@data.offset(start) as *u8, out.data as *mut u8, count * size_of[T]())
    }
    out.len = count
    ro tail = @len - end
    if tail > 0 {
        unsafe {
            RawMem.copy(@data.offset(end) as *u8, @data.offset(start) as *mut u8, tail * size_of[T]())
        }
    }
    @len -= count
    out
}

// ──────────────────────────────────────────────────────────────────────────
// Insert a slice
// ──────────────────────────────────────────────────────────────────────────

/// Insert every element of slice `sl` at index `i`, shifting the existing suffix
/// `[i, len)` right by `sl.len()` slots. Panics if `i > len` (`i == len` is a
/// bulk append). Overlap-safe (memmove), so a self-insert
/// (`v.insert_slice(i, v[a..b])`) is correct. O(len + sl.len()).
///
/// This is the slice-flavoured bulk insert — the `[]T` counterpart of `@splice`
/// (which takes a `Vec[T]`). A `[]T` IS a `Vec[T]`, so this delegates
/// straight to `@splice`; the distinct name documents the slice-argument intent
/// (Rust `Vec::splice` / Go `slices.Insert`). Returns `@` for chaining.
///
/// # Examples
///
/// ```nova
/// mut v = Vec[int].of(1, 2, 5, 6)
/// v.insert_slice(2, Vec[int].of(3, 4))
/// assert(v.equal(Vec[int].of(1, 2, 3, 4, 5, 6)))
/// ```
export fn Vec[T] mut @insert_slice(i int, sl []T) -> @
    requires 0 <= i && i <= @len
{
    @splice(i, sl)
}