vector

Module

Defines several vector-like classes.

You can import these APIs from the utils package. For example:

from utils.vector import InlinedFixedVector

InlinedFixedVector

The InlinedFixedVector type is a dynamically-allocated vector with small- vector optimization.

The InlinedFixedVector does not resize or implement bounds checks, it is initialized with both a small-vector size (statically known) and a dynamic (not known at compile time) number of slots, and when it is deallocated, it frees its memory.

TODO: It should call its element destructors once we have traits.

This data structure is useful for applications where the number of required elements is not known at compile time, but once known at runtime, is guaranteed to be equal to or less than a certain capacity.

Parameters:

• size (Int): The statically know-small vector size.
• type (AnyType): The type of the elements.

Aliases:

• static_size = _26x27_size

• static_data_type = StaticTuple[size, *"type"]

Fields:

• static_data (StaticTuple[size, *"type"]): The underlying static storage, used for small vectors.

• dynamic_data (Pointer[*"type"]): The underlying dynamic storage, used to grow large vectors.

• current_size (Int): The number of elements in the vector.

• capacity (Int): The amount of elements that can fit in the vector without resizing it.

Functions:

__init__

__init__(inout self: Self, capacity: Int)

Constructs InlinedFixedVector with the given capacity.

The dynamically allocated portion is capacity - size.

Args:

• capacity (Int): The requested capacity of the vector.

__copyinit__

__copyinit__(inout self: Self, existing: Self)

Creates a shallow copy (it doesn’t copy the data).

Args:

• existing (Self): The InlinedFixedVector to copy.

__getitem__

__getitem__(self: Self, i: Int) -> *"type"

Gets a vector element at the given index.

Args:

• i (Int): The index of the element.

Returns:

The element at the given index.

__setitem__

__setitem__(inout self: Self, i: Int, *value: "type")

Sets a vector element at the given index.

Args:

• i (Int): The index of the element.
• value (*"type"): The value to assign.

deepcopy

deepcopy(self: Self) -> Self

Creates a deepcopy of this vector.

Returns:

The created copy of this vector.

append

append(inout self: Self, *value: "type")

Appends a value to this vector.

Args:

• value (*"type"): The value to append.

__len__

__len__(self: Self) -> Int

Gets the number of elements in the vector.

Returns:

The number of elements in the vector.

clear

clear(inout self: Self)

Clears the elements in the vector.

UnsafeFixedVector

The UnsafeFixedVector type is a dynamically-allocated vector that does not resize or implement bounds checks.

It is initialized with a dynamic (not known at compile time) number of slots, and when it is deallocated, it frees its memory.

TODO: It should call its element destructors once we have traits.

This data structure is useful for applications where the number of required elements is not known at compile time, but once known at runtime, is guaranteed to be equal to or less than a certain capacity.

Parameters:

• type (AnyType): The type of the elements.

Fields:

• data (Pointer[*"type"]): The underlying storage for the vector.

• size (Int): The number of elements in the vector.

• capacity (Int): The amount of elements that can fit in the vector.

Functions:

__init__

__init__(inout self: Self, capacity: Int)

Constructs UnsafeFixedVector with the given capacity.

Args:

• capacity (Int): The requested capacity of the vector.

__copyinit__

__copyinit__(inout self: Self, existing: Self)

Creates a shallow copy (it doesn’t copy the data).

Args:

• existing (Self): The UnsafeFixedVector to copy.

__getitem__

__getitem__(self: Self, i: Int) -> *"type"

Gets a vector element at the given index.

Args:

• i (Int): The index of the element.

Returns:

The element at the given index.

__setitem__

__setitem__(self: Self, i: Int, *value: "type")

Sets a vector element at the given index.

Args:

• i (Int): The index of the element.
• value (*"type"): The value to assign.

__len__

__len__(self: Self) -> Int

Gets the number of elements in the vector.

Returns:

The number of elements in the vector.

append

append(inout self: Self, *value: "type")

Appends a value to this vector.

Args:

• value (*"type"): The value to append.

clear

clear(inout self: Self)

Clears the elements in the vector.

DynamicVector

The DynamicVector type is a dynamically-allocated vector.

It supports pushing and popping from the back resizing the underlying storage as needed. When it is deallocated, it frees its memory.

TODO: It should call its element destructors once we have traits. TODO: It should perform bound checks.

Parameters:

• type (AnyType): The type of the elements.

Fields:

• data (Pointer[*"type"]): The underlying storage for the vector.

• size (Int): The number of elements in the vector.

• capacity (Int): The amount of elements that can fit in the vector without resizing it.

Functions:

__init__

__init__(inout self: Self)

Constructs an empty vector.

__init__(inout self: Self, capacity: Int)

Constructs a vector with the given capacity.

Args:

• capacity (Int): The requested capacity of the vector.

__init__(inout self: Self, pointer: Pointer[*"type"], size: Int)

Constructs a vector with the given pointer and size.

Args:

• pointer (Pointer[*"type"]): The pointer to the buffer.
• size (Int): The size of the buffer.

__copyinit__

__copyinit__(inout self: Self, existing: Self)

Creates a shallow copy (it doesn’t copy the data).

Args:

• existing (Self): The DynamicVector to copy.

__getitem__

__getitem__(self: Self, i: Int) -> *"type"

Gets a vector element at the given index.

Args:

• i (Int): The index of the element.

Returns:

The element at the given index.

__setitem__

__setitem__(inout self: Self, i: Int, *value: "type")

Sets a vector element at the given index.

Args:

• i (Int): The index of the element.
• value (*"type"): The value to assign.

__len__

__len__(self: Self) -> Int

Gets the number of elements in the vector.

Returns:

The number of elements in the vector.

resize

resize(inout self: Self, size: Int)

Resizes the vector to the given new size.

If the new size is smaller than the current one, elements at the end are discarded. If the new size is larger than the current one, the vector is appended with non-initialized elements up to the requested size.

Args:

• size (Int): The new size.

deepcopy

deepcopy(self: Self) -> Self

Creates a deepcopy of this vector.

Returns:

The created copy of this vector.

reserve

reserve(inout self: Self, new_capacity: Int)

Reserves the requested capacity.

If the current capacity is greater or equal, this is a no-op. Otherwise, the storage is reallocated and the date is moved.

Args:

• new_capacity (Int): The new capacity.

push_back

push_back(inout self: Self, *value: "type")

Appends a value to this vector.

Args:

• value (*"type"): The value to append.

pop_back

pop_back(inout self: Self) -> *"type"

Pops a value from the back of this vector.

Returns:

The popped value.

clear

clear(inout self: Self)

Clears the elements in the vector.