std/src/collections/queue.nv - main - nv-lang/nova

std/src/collections/queue.nv
141 строка6 KB
Evgeniy Golovin
docs(endocs): перевод ///-комментариев collections на английский
01 авг 2026, 01:19
01 авг 2026, 01:196b13a19
// stdlib_queue.nv — FIFO-очередь через два массива.
//
// Демонстрирует **composability** базовых контейнеров: Queue не имеет
// собственной структуры данных, она составлена из двух массивов
// ([stdlib_vec.nv](stdlib_vec.nv)) — `in` (вход) и `out` (выход).
//
// Алгоритм классический ("amortized O(1) queue из двух стеков"):
// push кладёт в `in`. pop забирает из `out`; если `out` пуст —
// разворачивает `in` в `out` (O(n) реверс, но амортизированно
// каждая операция O(1)).
//
// Без специальной поддержки циркулярного буфера, без unsafe — просто
// два массива и pattern-match на пустоту.

module collections.queue

// ──────────────────────────────────────────────────────────────────────────
// Тип
// ──────────────────────────────────────────────────────────────────────────

/// A FIFO queue over two arrays with O(1) amortized push/pop.
///
/// Algorithm: `push` puts into the inbox, `pop` takes from the outbox.
/// When the outbox is empty, the inbox is poured into the outbox in reverse order (O(n), but O(1) amortized).
///
/// # Examples
///
/// ```nova
/// let mut q = Queue[int].new()
/// q.push(1)
/// q.push(2)
/// q.push(3)
/// assert(q.pop() == Some(1))
/// assert(q.pop() == Some(2))
/// ```
///
/// # See Also
///
/// - `[Deque]` — a double-ended queue
#stable(since = "0.1")
export type Queue[T] {
    mut inbox  []T   // internal: входная сторона FIFO
    mut outbox []T   // internal: выходная сторона FIFO (reversed in)
}

// ──────────────────────────────────────────────────────────────────────────
// Конструкторы
// ──────────────────────────────────────────────────────────────────────────

/// Create an empty queue.
#stable(since = "0.1")
export fn Queue[T].new(cap int = 0) -> Self
    requires cap >= 0
    => { inbox: []T.new(cap: cap), outbox: [] }

// ──────────────────────────────────────────────────────────────────────────
// Базовые операции
// ──────────────────────────────────────────────────────────────────────────

/// Number of elements in the queue.
#stable(since = "0.1")
export fn Queue[T] @len() -> int =>
    @inbox.len() + @outbox.len()

/// Returns `true` if the queue is empty.
#stable(since = "0.1")
export fn Queue[T] @is_empty() -> bool =>
    @inbox.is_empty() && @outbox.is_empty()

// D117 AMEND accessor-pair (vec-sweep, 2026-07-06): 0-arg getter half of the
// `cap`/`cap(n)` property pair. Reports the inbox side's capacity (the two
// backing arrays are sized identically by `cap(n)` below).
#stable(since = "0.1")
export fn Queue[T] @cap() -> int => @inbox.cap()

/// Reserve capacity `n` on BOTH backing arrays (replacement for the removed
/// `Queue[T].with_capacity` static constructor: `Queue[T].new(cap: n)`).
#stable(since = "0.1")
export fn Queue[T] mut @cap(n int) -> @
    requires n >= 0
{
    @inbox.cap(n)
    @outbox.cap(n)
}

// ──────────────────────────────────────────────────────────────────────────
// FIFO-операции
// ──────────────────────────────────────────────────────────────────────────

/// Append an element to the end of the queue. O(1).
#stable(since = "0.1")
export fn Queue[T] mut @push(item T) -> () =>
    @inbox.push(item)

/// Pop an element from the front of the queue (FIFO). O(1) amortized.
///
/// # Examples
///
/// ```nova
/// let mut q = Queue[str].new()
/// q.push("first")
/// q.push("second")
/// assert(q.pop() == Some("first"))
/// ```
#stable(since = "0.1")
export fn Queue[T] mut @pop() -> Option[T] {
    if @outbox.is_empty() {
        // Перелить `in` в `out` в обратном порядке.
        loop {
            match @inbox.pop() {
                Some(x) => @outbox.push(x)
                None    => break
            }
        }
    }
    @outbox.pop()
}

/// Peek the first element without removing it. `None` if empty.
#stable(since = "0.1")
export fn Queue[T] @peek() -> Option[T] {
    if !@outbox.is_empty() {
        // Голова outbox — последний элемент (pop забирает с конца).
        Some(@outbox[@outbox.len() - 1])
    } else if !@inbox.is_empty() {
        // Голова находится в `in[0]` (она «дальше всего» от выхода
        // тоже, но ещё не перелита).
        Some(@inbox[0])
    } else {
        None
    }
}

/// Clear the queue.
#stable(since = "0.1")
export fn Queue[T] mut @clear() -> () {
    @inbox.clear()
    @outbox.clear()
}

// Тесты — см. peer-файл queue_test.nv (module collections.queue_test).