Search results

std.deque.Deque

type pub Deque[T]

A double-ended queue (= "deque").

This type is implemented as a growable ring buffer, and supports fast inserts and removals at the head and tail of the queue.

The implementation is currently based on Rust's VecDeque type, which in turn is based on a comment by dizzy57 on this article.

Static methods

new

Show source code

fn pub static new -> Deque[T] {
  with_capacity(0)
}

fn pub static new -> Deque[T]

Returns a Deque with a capacity of zero.

See Deque.with_capacity for more details.

Examples

import std.deque (Deque)

Deque.new

with_capacity

Show source code

fn pub static with_capacity(size: Int) -> Deque[T] {
  if size < 0 { invalid_capacity(size) }

  Deque(
    size: 0,
    capacity: size,
    head: 0,
    buffer: alloc.resize(0 as Pointer[T], size),
  )
}

fn pub static with_capacity(size: Int) -> Deque[T]

Returns a Deque with enough space for at least size values.

Panics

This method panics of size if less than zero.

Examples

import std.deque (Deque)

Deque.with_capacity(42)

Instance methods

capacity

Show source code

fn pub capacity -> Int {
  @capacity
}

fn pub capacity -> Int

Returns the number of values that can be stored in self before self needs to be resized.

Examples

import std.deque (Deque)

let q = Deque.with_capacity(4)

q.capacity # => 4
q.push_back(10)
q.capacity # => 4

clear

Show source code

fn pub mut clear {
  while @size > 0 {
    drop_value(read_from(@head := to_buffer_index(1)))
    @size -= 1
  }

  @head = 0
}

fn pub mut clear

Removes all values in self.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_back(10)
q.push_back(20)
q.clear
q.size # => 0

get

Show source code

fn pub get(index: Int) -> Result[ref T, OutOfBounds] {
  try check_bounds(index, @size)
  Result.Ok(get_unchecked(to_buffer_index(index)))
}

fn pub get(index: Int) -> Result[ref T, OutOfBounds]

Returns an immutable borrow of the value at the given index.

If the index is out of bounds, a std.bounds.OutOfBounds error is returned.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_front(10)
q.push_front(20)
q.get(0) # => Result.Ok(20)
q.get(1) # => Result.Ok(10)

get_mut

Show source code

fn pub mut get_mut(index: Int) -> Result[mut T, OutOfBounds] {
  try check_bounds(index, @size)
  Result.Ok(get_unchecked_mut(to_buffer_index(index)))
}

fn pub mut get_mut(index: Int) -> Result[mut T: mut, OutOfBounds]
if
  T: mut

Returns a mutable borrow of the value at the given index.

If the index is out of bounds, a std.bounds.OutOfBounds error is returned.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_front(10)
q.push_front(20)
q.get_mut(0) # => Result.Ok(20)
q.get_mut(1) # => Result.Ok(10)

into_iter

Show source code

fn pub move into_iter -> IntoIter[T] {
  IntoIter(deque: self, index: 0)
}

fn pub move into_iter -> IntoIter[T]

Returns an iterator that moves the values out of self, yielding from the front to the back of the deque.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_back(10)
q.push_back(20)
q.into_iter.to_array # => [10, 20]

iter

Show source code

fn pub iter -> Stream[ref T] {
  let mut idx = 0

  Stream.new(fn move {
    if idx < @size {
      Option.Some(get_unchecked(to_buffer_index(idx := idx + 1)))
    } else {
      Option.None
    }
  })
}

fn pub iter -> Stream[ref T]

Returns an iterator that yields immutable borrows of the values in self.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_back(10)
q.push_front(20)
q.push_back(30)

q.iter.to_array # => [20, 10, 30]

iter_mut

Show source code

fn pub mut iter_mut -> Stream[mut T] {
  let mut idx = 0

  Stream.new(fn move {
    if idx < @size {
      Option.Some(get_unchecked_mut(to_buffer_index(idx := idx + 1)))
    } else {
      Option.None
    }
  })
}

fn pub mut iter_mut -> Stream[mut T: mut]
if
  T: mut

Returns an iterator that yields mutable borrows of the values in self.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_back(10)
q.push_front(20)
q.push_back(30)

q.iter_mut.to_array # => [20, 10, 30]

pop_back

Show source code

fn pub mut pop_back -> Option[T] {
  if @size == 0 { return Option.None }

  @size -= 1
  Option.Some(read_from(to_buffer_index(@size)))
}

fn pub mut pop_back -> Option[T]

Removes a value from the back of self, returning the removed value.

If no value was found, a None is returned.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_back(10)
q.push_back(20)

q.pop_back # => Option.Some(20)
q.pop_back # => Option.Some(10)
q.pop_back # => Option.None

pop_front

Show source code

fn pub mut pop_front -> Option[T] {
  if @size == 0 { return Option.None }

  @size -= 1
  Option.Some(read_from(@head := to_buffer_index(1)))
}

fn pub mut pop_front -> Option[T]

Removes a value from the front of self, returning the removed value.

If no value was found, a None is returned.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_front(10)
q.push_front(20)

q.pop_front # => Option.Some(20)
q.pop_front # => Option.Some(10)
q.pop_front # => Option.None

push_back

Show source code

fn pub mut push_back(value: T) {
  reserve(1)
  write_to(to_buffer_index(@size), value)
  @size += 1
}

fn pub mut push_back(value: T)

Pushes a value to the back of self.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_back(42)

push_front

Show source code

fn pub mut push_front(value: T) {
  reserve(1)
  @head = @head.wrapping_sub(1).wrapping_add(@capacity) % @capacity
  @size += 1
  write_to(@head, value)
}

fn pub mut push_front(value: T)

Pushes a value to the front of self.

Examples

import std.deque (Deque)

let q = Deque.new

q.push_front(42)

reserve

Show source code

fn pub mut reserve(size: Int) {
  if @capacity - @size >= size { return }

  let old_cap = @capacity

  @capacity = max(@capacity * 2, @capacity + size)
  @buffer = alloc.resize(@buffer, @capacity)
  handle_increase(old_cap)
}

fn pub mut reserve(size: Int)

Reserves space for size additional values.

The actual space reserved may be greater to prevent frequent reallocations. After calling this method, the capacity will be greater than or equal to self.size + size.

If the capacity is great enough or the given size is less than zero, this method does nothing.

size

Show source code

fn pub size -> Int {
  @size
}

fn pub size -> Int

Returns the number of values in self.

Examples

import std.deque (Deque)

let q = Deque.new

q.size # => 0
q.push_back(10)
q.size # => 1

Implemented traits

std.drop.

Drop

impl Drop for Deque