datatypes

This module provides implementations of less frequently used, but still common data types.

V's builtin module is imported implicitly, and has implementations for arrays, maps and strings. These are good for many applications, but there are a plethora of other useful data structures/containers, like linked lists, priority queues, trees, etc, that allow for algorithms with different time complexities, which may be more suitable for your specific application.

It is implemented using generics, that you have to specialise for the type of your actual elements. For example:

import datatypes

mut stack := datatypes.Stack[int]{}
stack.push(1)
println(stack)

Currently Implemented Datatypes:

• Linked list
• Doubly linked list
• Stack (LIFO)
• Queue (FIFO)
• Min heap (priority queue)
• Set
• BTree ordered map and BTreeSet ordered set
• Quadtree
• Bloom filter
• CRDT Conflict-free replicated data types (datatypes.crdt)
• ...

heapify(items) builds a minimum heap from a copy of the input. pushpop(item) returns the smallest of the item and heap contents; an empty heap returns the item unchanged. replace(item) removes the existing minimum before inserting the item and errors on an empty heap. nlargest(n, items) and nsmallest(n, items) return sorted copies with at most n elements; nonpositive counts return an empty array.

Directed graphs

new_graph[T]() creates a directed graph with V map keys as nodes. add_node adds an isolated node; add_edge(from, to) adds both endpoints implicitly. Parallel edges are accepted. successors(node) returns an independent array. topo_sort() returns a result containing an ordering where each edge's source precedes its target. has_cycle() detects cycles, including self-loops. An empty graph has an empty ordering. Cycle errors list nodes that could not be ordered, including nodes downstream of a cycle.

Ordered B-trees

new_btree[K, V]() creates an ordered map with logarithmic insert, lookup, and delete. Keys must have consistent equality and a total order; floating-point NaN keys are unsupported. set(key, value) inserts or replaces an entry, get(key) returns an optional value, and delete(key) reports whether it removed an entry. len() and is_empty() describe its size. min_key() and max_key() return optional bounds; keys() returns all keys in ascending order.

range_keys(lo, hi) and iterate(lo, hi) include both bounds. iterate returns BTreeIter[BTreeEntry[K, V]], with next() returning an optional entry. The iterator captures entries when it is created; subsequent insertion or removal does not change that entry list. Values use ordinary V assignment semantics, without deep-cloning references inside them. next() returns none when the captured entries are exhausted.

new_btree_set[T]() creates an ordered set with add, contains, remove, len, is_empty, min, max, and inclusive range(lo, hi) methods. add and remove report whether membership changed.

fn heapify[T](elements []T) MinHeap[T]

heapify builds a MinHeap from elements in O(n) using Floyd's bottom-up heap construction (repeated insert would be O(n log n)). It is the V-idiomatic equivalent of Python's heapq.heapify.

fn new_bloom_filter[T](hash_func fn (T) u32, table_size int, num_functions int) !&BloomFilter[T]

new_bloom_filter creates a new bloom_filter. table_size should be greater than 0, and num_functions should be 1~16.

fn new_bloom_filter_fast[T](hash_func fn (T) u32) &BloomFilter[T]

new_bloom_filter_fast creates a new bloom_filter. table_size is 16384, and num_functions is 4.

fn new_btree[K, V]() &BTree[K, V]

new_btree creates an empty BTree.

fn new_btree_set[V]() &BTreeSet[V]

new_btree_set creates an empty BTreeSet.

fn new_deque[T]() Deque[T]

new_deque creates an empty Deque.

fn new_graph[T]() Graph[T]

new_graph creates an empty Graph.

fn new_ringbuffer[T](s int) RingBuffer[T]

new_ringbuffer creates an empty ring buffer of size s.

fn nlargest[T](n int, items []T) []T

nlargest returns the n largest elements of items in descending order (Python's heapq.nlargest). k <= 0 yields an empty array; the input is not modified. A min-heap of size k is maintained, so the cost is O(len * log k).

fn nsmallest[T](n int, items []T) []T

nsmallest returns the n smallest elements of items in ascending order (Python's heapq.nsmallest).

fn Direction.from[W](input W) !Direction

from returns the Direction value of an integer or of a field name, or an error if there is none.

fn (mut bst BSTree[T]) insert(value T) bool

insert give the possibility to insert an element in the BST.

fn (bst &BSTree[T]) contains(value T) bool

contains checks if an element with a given value is inside the BST.

fn (mut bst BSTree[T]) remove(value T) bool

remove removes an element with value from the BST.

fn (bst &BSTree[T]) is_empty() bool

is_empty checks if the BST is empty

fn (bst &BSTree[T]) in_order_traversal() []T

in_order_traversal traverses the BST in order, and returns the result as an array.

fn (bst &BSTree[T]) post_order_traversal() []T

post_order_traversal traverses the BST in post order, and returns the result in an array.

fn (bst &BSTree[T]) pre_order_traversal() []T

pre_order_traversal traverses the BST in pre order, and returns the result as an array.

fn (bst &BSTree[T]) to_left(value T) !T

to_left returns the value of the node to the left of the node with value specified if it exists

fn (bst &BSTree[T]) to_right(value T) !T

to_right returns the value of the node to the right of the node with value specified if it exists

fn (bst &BSTree[T]) max() !T

max return the max element inside the BST. Time complexity O(N) if the BST is not balanced

fn (bst &BSTree[T]) min() !T

min return the minimum element in the BST. Time complexity O(N) if the BST is not balanced.

fn (mut it BTreeIter[E]) next() ?E

next returns the next entry, or none when exhausted.

fn (mut s BTreeSet[V]) add(value V) bool

add inserts value, returning false if it was already present.

fn (s &BTreeSet[V]) contains(value V) bool

contains reports whether value is present.

fn (mut s BTreeSet[V]) remove(value V) bool

remove deletes value, returning false if it was absent.

fn (s &BTreeSet[V]) len() int

len returns the number of elements.

fn (s &BTreeSet[V]) is_empty() bool

is_empty reports whether the set holds no elements.

fn (s &BTreeSet[V]) min() ?V

min returns the smallest element, or none if empty.

fn (s &BTreeSet[V]) max() ?V

max returns the largest element, or none if empty.

fn (s &BTreeSet[V]) range(lo V, hi V) []V

range returns the elements v with lo <= v <= hi, in ascending order.

fn (m &BTree[K, V]) len() int

len returns the number of entries.

fn (m &BTree[K, V]) is_empty() bool

is_empty reports whether the tree holds no entries.

fn (m &BTree[K, V]) get(key K) ?V

get returns the value for key, or none if absent.

fn (m &BTree[K, V]) exists(key K) bool

exists reports whether key is present.

fn (mut m BTree[K, V]) set(key K, value V)

set inserts or replaces key with value.

fn (mut m BTree[K, V]) delete(key K) bool

delete removes key, returning false if it was absent.

fn (m &BTree[K, V]) min_key() ?K

min_key returns the smallest key, or none if empty.

fn (m &BTree[K, V]) max_key() ?K

max_key returns the largest key, or none if empty.

fn (m &BTree[K, V]) keys() []K

keys returns all keys in ascending order.

fn (m &BTree[K, V]) range_keys(lo K, hi K) []K

range_keys returns the keys k with lo <= k <= hi, in ascending order.

fn (m &BTree[K, V]) iterate(lo K, hi K) BTreeIter[BTreeEntry[K, V]]

iterate returns an entry iterator over lo <= k <= hi (snapshot semantics).

fn (mut b BloomFilter[T]) add(element T)

adds the element to bloom filter.

fn (b &BloomFilter[T]) exists(element T) bool

checks the element is exists.

fn (l &BloomFilter[T]) @union(r &BloomFilter[T]) !&BloomFilter[T]

@union returns the union of the two bloom filters.

fn (l &BloomFilter[T]) intersection(r &BloomFilter[T]) !&BloomFilter[T]

intersection returns the intersection of bloom filters.

fn (d &Deque[T]) len() int

len returns the number of elements.

fn (d &Deque[T]) is_empty() bool

is_empty reports whether the deque holds no elements.

fn (d &Deque[T]) cap() int

cap returns the current ring capacity (for tests and tuning).

fn (mut d Deque[T]) push_back(item T)

push_back appends item at the back.

fn (mut d Deque[T]) push_front(item T)

push_front prepends item at the front.

fn (mut d Deque[T]) pop_front() !T

pop_front removes and returns the front element, or an error if empty. The vacated slot no longer retains the removed value.

fn (mut d Deque[T]) pop_back() !T

pop_back removes and returns the back element, or an error if empty. The vacated slot no longer retains the removed value.

fn (d &Deque[T]) peek_front() !T

peek_front returns the front element without removing it.

fn (d &Deque[T]) peek_back() !T

peek_back returns the back element without removing it.

fn (d &Deque[T]) array() []T

array returns the elements in front-to-back order.

fn (list DoublyLinkedList[T]) is_empty() bool

is_empty checks if the linked list is empty

fn (list DoublyLinkedList[T]) len() int

len returns the length of the linked list

fn (list DoublyLinkedList[T]) first() !T

first returns the first element of the linked list

fn (list DoublyLinkedList[T]) last() !T

last returns the last element of the linked list

fn (mut list DoublyLinkedList[T]) push_back(item T)

push_back adds an element to the end of the linked list

fn (mut list DoublyLinkedList[T]) push_front(item T)

push_front adds an element to the beginning of the linked list

fn (mut list DoublyLinkedList[T]) push_many(elements []T, direction Direction)

push_many adds array of elements to the beginning of the linked list

fn (mut list DoublyLinkedList[T]) pop_back() !T

pop_back removes the last element of the linked list

fn (mut list DoublyLinkedList[T]) pop_front() !T

pop_front removes the last element of the linked list

fn (mut list DoublyLinkedList[T]) insert(idx int, item T) !

insert adds an element to the linked list at the given index

fn (list &DoublyLinkedList[T]) index(item T) !int

index searches the linked list for item and returns the forward index or none if not found.

fn (mut list DoublyLinkedList[T]) delete(idx int)

delete removes index idx from the linked list and is safe to call for any idx.

fn (list DoublyLinkedList[T]) str() string

str returns a string representation of the linked list

fn (list DoublyLinkedList[T]) array() []T

array returns a array representation of the linked list

fn (mut list DoublyLinkedList[T]) next() ?T

next implements the iter interface to use DoublyLinkedList with V's for x in list { loop syntax.

fn (mut list DoublyLinkedList[T]) iterator() DoublyListIter[T]

iterator returns a new iterator instance for the list.

fn (mut list DoublyLinkedList[T]) back_iterator() DoublyListIterBack[T]

back_iterator returns a new backwards iterator instance for the list.

fn (mut iter DoublyListIterBack[T]) next() ?T

next returns the previous element of the list, or none when the start of the list is reached. It is called by V's for x in iter{ on each iteration.

fn (mut iter DoublyListIter[T]) next() ?T

next returns the next element of the list, or none when the end of the list is reached. It is called by V's for x in iter{ on each iteration.

fn (mut g Graph[T]) add_node(v T)

add_node ensures v exists (isolated nodes need this; edge endpoints are added implicitly).

fn (mut g Graph[T]) add_edge(from T, to T)

add_edge adds the directed edge from -> to (creating both endpoints). Parallel edges are tolerated.

fn (g &Graph[T]) successors(v T) []T

successors returns an independent array of direct successors of v (empty if none).

fn (g &Graph[T]) has_cycle() bool

has_cycle reports whether the graph contains a directed cycle (a self-loop counts).

fn (g &Graph[T]) topo_sort() ![]T

topo_sort returns the nodes in dependency order (dependencies first). Cyclic graphs are an error naming nodes that could not be ordered, including successors blocked by a cycle.

fn (list LinkedList[T]) is_empty() bool

is_empty checks if the linked list is empty

fn (list LinkedList[T]) len() int

len returns the length of the linked list

fn (list LinkedList[T]) first() !T

first returns the first element of the linked list

fn (list LinkedList[T]) last() !T

last returns the last element of the linked list

fn (list LinkedList[T]) index(idx int) !T

index returns the element at the given index of the linked list

fn (mut list LinkedList[T]) push(item T)

push adds an element to the end of the linked list

fn (mut list LinkedList[T]) push_many(elements []T)

push adds an array of elements to the end of the linked list

fn (mut list LinkedList[T]) pop() !T

pop removes the last element of the linked list

fn (mut list LinkedList[T]) shift() !T

shift removes the first element of the linked list

fn (mut list LinkedList[T]) insert(idx int, item T) !

insert adds an element to the linked list at the given index

fn (mut list LinkedList[T]) prepend(item T)

prepend adds an element to the beginning of the linked list (equivalent to insert(0, item))

fn (list LinkedList[T]) str() string

str returns a string representation of the linked list

fn (list LinkedList[T]) array() []T

array returns a array representation of the linked list

fn (mut list LinkedList[T]) next() ?T

next implements the iteration interface to use LinkedList with V's for loop syntax.

fn (mut list LinkedList[T]) iterator() ListIter[T]

iterator returns a new iterator instance for the list.

fn (mut iter ListIter[T]) next() ?T

next returns the next element of the list, or none when the end of the list is reached. It is called by V's for x in iter{ on each iteration.

fn (mut heap MinHeap[T]) insert(item T)

insert adds an element to the heap.

fn (mut heap MinHeap[T]) insert_many(elements []T)

insert array of elements to the heap.

fn (mut heap MinHeap[T]) pop() !T

pop removes the top-most element from the heap.

fn (heap MinHeap[T]) peek() !T

peek gets the top-most element from the heap without removing it.

fn (heap MinHeap[T]) len() int

len returns the number of elements in the heap.

fn (mut h MinHeap[T]) pushpop(item T) !T

pushpop pushes item and pops the smallest element (Python's heapq.heappushpop). When item is the smallest, the heap is left untouched and item is returned, so no sift work is needed; otherwise the old root is returned and item takes its place.

fn (mut h MinHeap[T]) replace(item T) !T

replace pops the smallest element and pushes item afterwards (the reverse order of pushpop, matching Python's heapq.heapreplace).

fn (queue Queue[T]) is_empty() bool

is_empty checks if the queue is empty

fn (queue Queue[T]) len() int

len returns the length of the queue

fn (queue Queue[T]) peek() !T

peek returns the head of the queue (first element added)

fn (queue Queue[T]) last() !T

last returns the tail of the queue (last element added)

fn (queue Queue[T]) index(idx int) !T

index returns the element at the given index of the queue

fn (mut queue Queue[T]) push(item T)

push adds an element to the tail of the queue

fn (mut queue Queue[T]) pop() !T

pop removes the element at the head of the queue and returns it

fn (queue Queue[T]) str() string

str returns a string representation of the queue

fn (queue Queue[T]) array() []T

array returns a array representation of the queue

fn (mut rb RingBuffer[T]) push(element T) !

push adds an element to the ring buffer.

fn (mut rb RingBuffer[T]) pop() !T

pop returns the oldest element in the buffer.

fn (mut rb RingBuffer[T]) push_many(elements []T) !

push_many pushes an array to the buffer.

fn (mut rb RingBuffer[T]) pop_many(n u64) ![]T

pop_many returns n elements of the buffer starting with the oldest one.

fn (rb RingBuffer[T]) is_empty() bool

is_empty returns true if the ring buffer is empty, false otherwise.

fn (rb RingBuffer[T]) is_full() bool

is_full returns true if the ring buffer is full, false otherwise.

fn (rb RingBuffer[T]) capacity() int

capacity returns the capacity of the ring buffer.

fn (mut rb RingBuffer[T]) clear()

clear empties the ring buffer and all pushed elements.

fn (rb RingBuffer[T]) occupied() int

occupied returns the occupied capacity of the buffer.

fn (rb RingBuffer[T]) remaining() int

remaining returns the remaining capacity of the buffer.

fn (set Set[T]) exists(element T) bool

checks the element is exists.

fn (mut set Set[T]) add(element T)

adds the element to set, if it is not present already.

fn (mut set Set[T]) remove(element T)

removes the element from set.

fn (set Set[T]) pick() !T

pick returns an arbitrary element of set, if set is not empty.

fn (mut set Set[T]) rest() ![]T

rest returns the set consisting of all elements except for the arbitrary element.

fn (mut set Set[T]) pop() !T

pop returns an arbitrary element and deleting it from set.

fn (mut set Set[T]) clear()

delete all elements of set.

fn (l Set[T]) == (r Set[T]) bool

== checks whether the two given sets are equal (i.e. contain all and only the same elements).

fn (set Set[T]) is_empty() bool

is_empty checks whether the set is empty or not.

fn (set Set[T]) size() int

size returns the number of elements in the set.

fn (set Set[T]) copy() Set[T]

copy returns a copy of all the elements in the set.

fn (mut set Set[T]) add_all(elements []T)

add_all adds the whole elements array to the set

fn (l Set[T]) @union(r Set[T]) Set[T]

@union returns the union of the two sets.

fn (l Set[T]) intersection(r Set[T]) Set[T]

intersection returns the intersection of sets.

fn (l Set[T]) - (r Set[T]) Set[T]

• returns the difference of sets.

fn (l Set[T]) subset(r Set[T]) bool

subset returns true if the set r is a subset of the set l.

fn (l Set[T]) array() []T

array returns an array representation of the set

fn (stack Stack[T]) is_empty() bool

is_empty checks if the stack is empty

fn (stack Stack[T]) len() int

len returns the length of the stack

fn (stack Stack[T]) peek() !T

peek returns the top of the stack

fn (mut stack Stack[T]) push(item T)

push adds an element to the top of the stack

fn (mut stack Stack[T]) pop() !T

pop removes the element at the top of the stack and returns it

fn (stack Stack[T]) str() string

str returns a string representation of the stack

fn (stack Stack[T]) array() []T

array returns a array representation of the stack

enum Direction {
	front
	back
}

struct AABB {
pub mut:
	x      f64
	y      f64
	width  f64
	height f64
}

struct BSTree[T] {
mut:
	root &BSTreeNode[T] = unsafe { 0 }
}

Pure Binary Seach Tree implementation

Pure V implementation of the Binary Search Tree Time complexity of main operation O(log N) Space complexity O(N)

struct BTree[K, V] {
mut:
	root &BTreeNode[K, V]
	len  int
}

BTree is an ordered map with logarithmic insert, lookup and delete. Keys must have a total order consistent with < and ==; floating-point NaN keys are unsupported. Integer, other float and string keys work. It is the V-idiomatic equivalent of Rust's std::collections::BTreeMap, complementing the string-only builtin SortedMap and the unordered builtin map and datatypes.Set.

struct BTreeEntry[K, V] {
pub:
	key   K
	value V
}

BTreeEntry is one key/value pair yielded by BTree iteration.

struct BTreeIter[E] {
mut:
	entries []E
	pos     int
}

BTreeIter iterates over BTree entries in ascending order.

struct BTreeSet[V] {
mut:
	tree &BTree[V, bool]
}

BTreeSet is an ordered set built on BTree.

struct Deque[T] {
mut:
	buf  []T
	head int // index of the front element
	len  int
}

Deque is a double-ended queue: both ends support push and pop in amortized O(1). It is ring-buffer backed, so unlike Queue it is also usable as a stack or a palindrome buffer. Like Queue, it requires external synchronization when shared between threads.

struct DoublyLinkedList[T] {
mut:
	head &DoublyListNode[T] = unsafe { 0 }
	tail &DoublyListNode[T] = unsafe { 0 }
	// Internal iter pointer for allowing safe modification
	// of the list while iterating. TODO: use an option
	// instead of a pointer to determine it is initialized.
	iter &DoublyListIter[T] = unsafe { 0 }
pub mut:
	len int
}

DoublyLinkedList[T] represents a generic doubly linked list of elements, each of type T.

struct DoublyListIter[T] {
mut:
	node &DoublyListNode[T] = unsafe { 0 }
}

DoublyListIter[T] is an iterator for DoublyLinkedList. It starts from the start and moves forwards to the end of the list. It can be used with V's for x in iter { construct. One list can have multiple independent iterators, pointing to different positions/places in the list. A DoublyListIter iterator instance always traverses the list from start to finish.

struct DoublyListIterBack[T] {
mut:
	node &DoublyListNode[T] = unsafe { 0 }
}

DoublyListIterBack[T] is an iterator for DoublyLinkedList. It starts from the end and moves backwards to the start of the list. It can be used with V's for x in iter { construct. One list can have multiple independent iterators, pointing to different positions/places in the list. A DoublyListIterBack iterator instance always traverses the list from finish to start.

struct Graph[T] {
mut:
	nodes map[T]bool
	succ  map[T][]T
}

Graph is a directed graph with topological sorting (Kahn's algorithm). It is the V-idiomatic equivalent of Python's graphlib: the core of build systems, DI containers and task schedulers. Node keys must be supported V map key types.

struct LinkedList[T] {
mut:
	head &ListNode[T] = unsafe { nil }
	tail &ListNode[T] = unsafe { nil }
	len  int
	// Internal iter pointer for allowing safe modification
	// of the list while iterating. TODO: use an option
	// instead of a pointer to determine if it is initialized.
	iter &ListIter[T] = unsafe { nil }
}

struct ListIter[T] {
mut:
	node &ListNode[T] = unsafe { nil }
}

ListIter[T] is an iterator for LinkedList. It can be used with V's for x in iter { construct. One list can have multiple independent iterators, pointing to different positions/places in the list. An iterator instance always traverses the list from start to finish.

struct ListNode[T] {
mut:
	data T
	next &ListNode[T] = unsafe { nil }
}

struct MinHeap[T] {
mut:
	data []T
}

MinHeap is a binary minimum heap data structure.

struct Quadtree {
pub mut:
	perimeter AABB
	capacity  int
	depth     int
	level     int
	particles []AABB
	nodes     []Quadtree
}

fn (mut q Quadtree) create(x f64, y f64, width f64, height f64, capacity int, depth int, level int) Quadtree

create returns a new configurable root node for the tree.

fn (mut q Quadtree) insert(p AABB)

insert recursively adds a particle in the correct index of the tree.

fn (mut q Quadtree) retrieve(p AABB) []AABB

retrieve recursively checks if a particle is in a specific index of the tree.

fn (mut q Quadtree) clear()

clear flushes out nodes and particles from the tree.

fn (q Quadtree) get_nodes() []Quadtree

get_nodes recursively returns the subdivisions the tree has.

struct Queue[T] {
mut:
	elements LinkedList[T]
}

struct RingBuffer[T] {
mut:
	reader  int // index of the tail where data is going to be read
	writer  int // index of the head where data is going to be written
	content []T
}

RingBuffer represents a ring buffer also known as a circular buffer.

struct Set[T] {
pub mut:
	elements map[T]u8
}

struct Stack[T] {
mut:
	elements []T
}