Module datatypes stdlib

datatypes
Version:
0.3.3
License:
MIT
Dependencies from vmod:
0
Imports:
0
Imported by:
1
Repository:
OS-specific
Show selected OS-specific symbols.
Backend-specific
Show selected Backend-specific symbols.

Dependencies defined in v.mod

This section is empty.

Imports

This section is empty.

Imported by

Overview

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, tries, 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
  • Quadtree
  • ...

Aliases

This section is empty.

Constants

This section is empty.

Sum types

This section is empty.

Functions

#fn new_ringbuffer[T]

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

new_ringbuffer - creates an empty ringbuffer

Structs

#struct BSTree[T]

pub 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)

#fn (&BSTree[T]) insert

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

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

#fn (&BSTree[T]) insert_helper

fn (mut bst &BSTree[T]) insert_helper(mut node &BSTreeNode[T], value T) bool

insert_helper walks the tree and inserts the given node.

#fn (&BSTree[T]) contains

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

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

#fn (&BSTree[T]) contains_helper

fn (bst &BSTree[T]) contains_helper(node &BSTreeNode[T], value T) bool

contains_helper is a helper function to walk the tree, and return the absence or presence of the value.

#fn (&BSTree[T]) remove

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

remove removes an element with value from the BST.

#fn (&BSTree[T]) remove_helper

fn (mut bst &BSTree[T]) remove_helper(mut node &BSTreeNode[T], value T, left bool) bool

#fn (&BSTree[T]) get_max_from_right

fn (bst &BSTree[T]) get_max_from_right(node &BSTreeNode[T]) &BSTreeNode[T]

get_max_from_right returns the max element of the BST following the right branch.

#fn (&BSTree[T]) get_min_from_left

fn (bst &BSTree[T]) get_min_from_left(node &BSTreeNode[T]) &BSTreeNode[T]

get_min_from_left returns the min element of the BST by following the left branch.

#fn (&BSTree[T]) is_empty

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

is_empty checks if the BST is empty

#fn (&BSTree[T]) in_order_traversal

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

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

#fn (&BSTree[T]) in_order_traversal_helper

fn (bst &BSTree[T]) in_order_traversal_helper(node &BSTreeNode[T], mut result &[]T)

in_order_traversal_helper helps traverse the BST, and accumulates the result in the result array.

#fn (&BSTree[T]) post_order_traversal

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 (&BSTree[T]) post_order_traversal_helper

fn (bst &BSTree[T]) post_order_traversal_helper(node &BSTreeNode[T], mut result &[]T)

post_order_traversal_helper is a helper function that traverses the BST in post order, accumulating the result in an array.

#fn (&BSTree[T]) pre_order_traversal

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 (&BSTree[T]) pre_order_traversal_helper

fn (bst &BSTree[T]) pre_order_traversal_helper(node &BSTreeNode[T], mut result &[]T)

pre_order_traversal_helper is a helper function to traverse the BST in pre order and accumulates the results in an array.

#fn (&BSTree[T]) get_node

fn (bst &BSTree[T]) get_node(node &BSTreeNode[T], value T) &BSTreeNode[T]

get_node is a helper method to ge the internal rapresentation of the node with the value.

#fn (&BSTree[T]) to_left

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, otherwise the a false value is returned.

An example of usage can be the following one

 left_value, exist := bst.to_left(10)

#fn (&BSTree[T]) to_right

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

to_right return the value of the element to the right of the node with value specified, if exist otherwise, the boolean value is false An example of usage can be the following one

 left_value, exist := bst.to_right(10)

#fn (&BSTree[T]) max

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 (&BSTree[T]) min

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

min return the minimum element in the BST.

Time complexity O(N) if the BST is not balanced.

#struct DoublyLinkedList[T]

pub 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 }
	len  int
}

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

#fn (DoublyLinkedList[T]) is_empty

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 (DoublyLinkedList[T]) first

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

first returns the first element of the linked list

#fn (DoublyLinkedList[T]) last

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

last returns the last element of the linked list

#fn (&DoublyLinkedList[T]) push_back

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

push_back adds an element to the end of the linked list

#fn (&DoublyLinkedList[T]) push_front

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

push_front adds an element to the beginning of the linked list

#fn (&DoublyLinkedList[T]) pop_back

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

pop_back removes the last element of the linked list

#fn (&DoublyLinkedList[T]) pop_front

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

pop_front removes the last element of the linked list

#fn (&DoublyLinkedList[T]) insert

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

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

#fn (&DoublyLinkedList[T]) insert_back

fn (mut list &DoublyLinkedList[T]) insert_back(idx int, item T)

insert_back walks from the tail and inserts a new item at index idx (determined from the forward index). This function should be called when idx > list.len/2. This helper function assumes idx bounds have already been checked and idx is not at the edges.

#fn (&DoublyLinkedList[T]) insert_front

fn (mut list &DoublyLinkedList[T]) insert_front(idx int, item T)

insert_front walks from the head and inserts a new item at index idx (determined from the forward index). This function should be called when idx <= list.len/2. This helper function assumes idx bounds have already been checked and idx is not at the edges.

#fn (&DoublyLinkedList[T]) node

fn (list &DoublyLinkedList[T]) node(idx int) &DoublyListNode[T]

node walks from the head or tail and finds the node at index idx.

This helper function assumes the list is not empty and idx is in bounds.

#fn (&DoublyLinkedList[T]) 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 (&DoublyLinkedList[T]) delete

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 (DoublyLinkedList[T]) array

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

array returns a array representation of the linked list

#fn (&DoublyLinkedList[T]) next

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 (&DoublyLinkedList[T]) iterator

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

iterator returns a new iterator instance for the list.

#fn (&DoublyLinkedList[T]) back_iterator

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

back_iterator returns a new backwards iterator instance for the list.

#struct DoublyListIter[T]

pub 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.

#fn (&DoublyListIter[T]) next

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.

#struct DoublyListIterBack[T]

pub 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.

#fn (&DoublyListIterBack[T]) next

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.

#struct MinHeap[T]

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

MinHeap is a binary minimum heap data structure.

#fn (&MinHeap[T]) insert

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

insert adds an element to the heap.

#fn (&MinHeap[T]) pop

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

pop removes the top-most element from the heap.

#fn (MinHeap[T]) peek

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

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

#fn (MinHeap[T]) len

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

len returns the number of elements in the heap.

#fn (MinHeap[T]) left_child

fn (heap MinHeap[T]) left_child(idx int) !int

left_child is a helper function that returns the index of the left child given a parent idx, or none if there is no left child.

#fn (MinHeap[T]) right_child

fn (heap MinHeap[T]) right_child(idx int) !int

right_child is a helper function that returns the index of the right child given a parent idx, or none if there is no right child.

#fn (MinHeap[T]) parent

fn (heap MinHeap[T]) parent(idx int) int

parent is a helper function that returns the parent index of the child.

#struct ListNode[T]

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

#struct LinkedList[T]

pub struct LinkedList[T] {
mut:
	head &ListNode[T] = unsafe { 0 }
	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 { 0 }
}

#fn (LinkedList[T]) is_empty

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

is_empty checks if the linked list is empty

#fn (LinkedList[T]) len

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

len returns the length of the linked list

#fn (LinkedList[T]) first

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

first returns the first element of the linked list

#fn (LinkedList[T]) last

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

last returns the last element of the linked list

#fn (LinkedList[T]) index

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

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

#fn (&LinkedList[T]) push

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

push adds an element to the end of the linked list

#fn (&LinkedList[T]) pop

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

pop removes the last element of the linked list

#fn (&LinkedList[T]) shift

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

shift removes the first element of the linked list

#fn (&LinkedList[T]) insert

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

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

#fn (&LinkedList[T]) prepend

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 (LinkedList[T]) str

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

str returns a string representation of the linked list

#fn (LinkedList[T]) array

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

array returns a array representation of the linked list

#fn (&LinkedList[T]) next

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

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

#fn (&LinkedList[T]) iterator

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

iterator returns a new iterator instance for the list.

#struct ListIter[T]

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

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.

#fn (&ListIter[T]) next

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.

#struct AABB

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

#struct Quadtree

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

#fn (&Quadtree) create

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 (&Quadtree) insert

fn (mut q &Quadtree) insert(p AABB)

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

#fn (&Quadtree) retrieve

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

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

#fn (&Quadtree) clear

fn (mut q &Quadtree) clear()

clear flushes out nodes and partcles from the tree.

#fn (Quadtree) get_nodes

fn (q Quadtree) get_nodes() []Quadtree

get_nodes recursevely returns the subdivisions the tree has.

#fn (&Quadtree) split

fn (mut q &Quadtree) split()

#fn (&Quadtree) get_index

fn (mut q &Quadtree) get_index(p AABB) []int

#struct Queue[T]

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

#fn (Queue[T]) is_empty

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

is_empty checks if the queue is empty

#fn (Queue[T]) len

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

len returns the length of the queue

#fn (Queue[T]) peek

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

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

#fn (Queue[T]) last

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

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

#fn (Queue[T]) index

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

index returns the element at the given index of the queue

#fn (&Queue[T]) push

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

push adds an element to the tail of the queue

#fn (&Queue[T]) pop

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

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

#fn (Queue[T]) str

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

str returns a string representation of the queue

#fn (Queue[T]) array

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

array returns a array representation of the queue

#struct RingBuffer[T]

pub 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 - public struct that represents the ringbuffer

#fn (&RingBuffer[T]) push

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

push - adds an element to the ringbuffer

#fn (&RingBuffer[T]) pop

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

pop - returns the oldest element of the buffer

#fn (&RingBuffer[T]) push_many

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

push_many - pushes an array to the buffer

#fn (&RingBuffer[T]) pop_many

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

pop_many - returns a given number(n) of elements of the buffer starting with the oldest one

#fn (RingBuffer[T]) is_empty

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

is_empty - checks if the ringbuffer is empty

#fn (RingBuffer[T]) is_full

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

is_full - checks if the ringbuffer is full

#fn (RingBuffer[T]) capacity

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

capacity - returns the capacity of the ringbuffer

#fn (&RingBuffer[T]) clear

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

clear - emptys the ringbuffer and all pushed elements

#fn (RingBuffer[T]) occupied

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

occupied - returns occupied capacity of the buffer.

#fn (RingBuffer[T]) remaining

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

remaining - returns remaining capacity of the buffer

#fn (&RingBuffer[T]) move_reader

fn (mut rb &RingBuffer[T]) move_reader()

head an tail-pointer move methods these methods are not public, they are just an eneasement for handling the pointer-movement process.

#fn (&RingBuffer[T]) move_writer

fn (mut rb &RingBuffer[T]) move_writer()

#struct Set[T]

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

#fn (Set[T]) exists

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

checks the element is exists.

#fn (&Set[T]) add

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

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

#fn (&Set[T]) remove

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

removes the element from set.

#fn (Set[T]) pick

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

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

#fn (&Set[T]) rest

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

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

#fn (&Set[T]) pop

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

pop returns an arbitrary element and deleting it from set.

#fn (&Set[T]) clear

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

delete all elements of set.

#fn (Set[T]) equal

deprecated:use set1[T] == set2[T] instead
fn (l Set[T]) equal(r Set[T]) bool

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

#fn (Set[T]) operator==

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[T]) is_empty

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

is_empty checks whether the set is empty or not.

#fn (Set[T]) size

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

size returns the number of elements in the set.

#fn (Set[T]) copy

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

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

#fn (&Set[T]) add_all

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

add_all adds the whole elements array to the set

#fn (Set[T]) @union

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

@union returns the union of the two sets.

#fn (Set[T]) intersection

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

intersection returns the intersection of sets.

#fn (Set[T]) difference

deprecated:use set1[T] - set2[T] instead
fn (l Set[T]) difference(r Set[T]) Set[T]

difference returns the difference of sets.

#fn (Set[T]) operator-

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

- returns the difference of sets.

#fn (Set[T]) subset

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

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

#struct Stack[T]

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

#fn (Stack[T]) is_empty

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

is_empty checks if the stack is empty

#fn (Stack[T]) len

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

len returns the length of the stack

#fn (Stack[T]) peek

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

peek returns the top of the stack

#fn (&Stack[T]) push

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

push adds an element to the top of the stack

#fn (&Stack[T]) pop

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

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

#fn (Stack[T]) str

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

str returns a string representation of the stack

#fn (Stack[T]) array

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

array returns a array representation of the stack

Interfaces

This section is empty.

Enums

This section is empty.