Summary

Members	Descriptions
namespace utils	namespace with things that doesnt fit in class
class array_container	Interface for structures which uses arrays as base.
class avl_leaf	Tree leaf that is used in avl tree In addition it has height
class avl_tree	Self Balancing Binary Search Tree with sorted_list interface. It's using node like objects.
class bst	Binary Search Tree with sorted_list interface. It's using node like objects.
class container	Basic interface with basic info as size in it, used in all structures.
class heap_node	Element which is used in priority_queue->vector as element
class leaf	Tree leaf that is used in binary tree such as bst.
class link_vector	A class that forms a 2-way linked list using .
class list	Interface for on-list operation with pure virtual methods and protected constructor and destructor
class priority_queue	Priority queue based on heap which is based on vector which holds heap_node* Values don't need to be unique. If no min_heap value is passed to constructor it's made to be min heap
class queue	Basic LIFO structure that uses queue_node
class sorted_list	Only reliable on sorted structures. Interface for on-list operation with pure virtual methods and protected constructor and destructor.
class stack	Basic FIFO structure Uses stack_node (one way node)
class vector	Resizeable array.
struct node	It's 2 way linked list. Stores: value, next node, previous node
struct queue_node	Used only in queue as a (one) element container.
struct stack_node	Used only in stack as a (one) element container.

namespace utils

namespace with things that doesnt fit in class

Summary

Members	Descriptions
public template<> int get_height(avl_leaf< T > * node)	Gets height of leaf, if is not present returns 0
public template<> int calc_balance(avl_leaf< T > * node)	Calculate balance value in node for self balancing avl. If node if nullptr returns 0.
public template<> void update_height(avl_leaf< T > * node)	Updates heights based on subtrees below. It needs to be run with at end.
public template<> void swap_avl_node(avl_leaf< T > * f1,avl_leaf< T > * f2)	Swaps two elements' values in avl tree
public template<> T max(T a1,T a2)

Members

public template<>
int get_height(avl_leaf< T > * node)

Gets height of leaf, if is not present returns 0

Parameters

• node avl_leaf* points to leaf from which height is taken

Returns

int with height of subtree or 0

public template<>
int calc_balance(avl_leaf< T > * node)

Calculate balance value in node for self balancing avl. If node if nullptr returns 0.

Parameters

• node Leaf of which balance value should be calculated

Returns

int with balance

public template<>
void update_height(avl_leaf< T > * node)

Updates heights based on subtrees below. It needs to be run with at end.

Parameters

• T type of objects in avl_leaf

Parameters

• node pointer to avl_leaf of which height will be updated

public template<>
void swap_avl_node(avl_leaf< T > * f1,avl_leaf< T > * f2)

Swaps two elements' values in avl tree

Parameters

• f1 is pointer to first leaf

• f2 is pointer to second leaf

public template<>
T max(T a1,T a2)

class array_container

class array_container
  : public container

Interface for structures which uses arrays as base.

Summary

Members	Descriptions
public virtual bool clear()	Method from 'container' class that deletes every item in container
protected T * tab_	actual array containing data
protected int container_size_	current array size
protected int initial_size_	initial size for array, used for clear method ,from container, as its the initial size after clearing
protected array_container()	Used to make constructor protected.
protected explicit array_container(int initial_size)	Used to make destructor protected.
protected ~array_container()
protected T * rewrite_append(T value)	Method used for rewriting data to a new array and appending value at the end od array
protected T * rewrite(int size,int first_index)	Method used for rewriting into a new size starting from a first_index

Members

public virtual bool clear()

Method from 'container' class that deletes every item in container

Returns

success as true and false otherwise

protected T * tab_

actual array containing data

protected int container_size_

current array size

protected int initial_size_

initial size for array, used for clear method ,from container, as its the initial size after clearing

protected array_container()

Used to make constructor protected.

protected explicit array_container(int initial_size)

Used to make destructor protected.

protected ~array_container()

protected T * rewrite_append(T value)

Method used for rewriting data to a new array and appending value at the end od array

Parameters

• value of type T as what to append to array after rewriting

protected T * rewrite(int size,int first_index)

Method used for rewriting into a new size starting from a first_index

Parameters

• size new size of the container

• first_index from which index to start rewriting

Returns

A pointer to a new array

class avl_leaf

class avl_leaf
  : public leaf< T >

Tree leaf that is used in avl tree In addition it has height

Summary

Members	Descriptions
public int height

Members

public int height

class avl_tree

class avl_tree
  : public bst< T >

Self Balancing Binary Search Tree with sorted_list interface. It's using node like objects.

Summary

Members	Descriptions
public avl_tree() = default
public ~avl_tree()
public virtual void insert(T value)	Inserts element T in tree
public virtual T pop_front()	Removes item from the front of tree
public virtual T pop_back()	Removes item from the back of tree
public bool remove_by_key(T key)	Removes leaf if exists in tree, based on key
public void remove_by_index(int index)	Removes leaf if proper index is present aka index >=0 and index < container size
public inline avl_leaf< T > * get_data_avl()	Simple function to return head of tree

Members

public avl_tree() = default

public ~avl_tree()

public virtual void insert(T value)

Inserts element T in tree

Parameters

• value T type, note it will not be inserted if element with exact same value exists in tree

See also: sorted_list

public virtual T pop_front()

Removes item from the front of tree See also: sorted_list

public virtual T pop_back()

Removes item from the back of tree See also: sorted_list

public bool remove_by_key(T key)

Removes leaf if exists in tree, based on key

Parameters

• key if value which is in tree, type T

Returns

bool informing whether leaf was found and removed

public void remove_by_index(int index)

Removes leaf if proper index is present aka index >=0 and index < container size

Parameters

• index in sorted list

public inline avl_leaf< T > * get_data_avl()

Simple function to return head of tree

Returns

pointer to avl_tree with head of tree

class bst

class bst
  : public sorted_list< T >
  : public container

Binary Search Tree with sorted_list interface. It's using node like objects.

Summary

Members	Descriptions
public bst() = default
public ~bst()
public virtual void insert(T value)	See also: sorted_list
public virtual T pop_front()	See also: sorted_list
public virtual T pop_back()	See also: sorted_list
public virtual T operator[](int index)	See also: sorted_list
public virtual bool find(T value)	See also: sorted_list
public virtual bool clear()	traverses over every element and delete it from memory
public void print()	prints tree
public inline leaf< T > * get_data()
protected leaf< T > * head	Head of the tree.
protected leaf< T > * find_leaf(leaf< T > * curr,T value)	Used to find leaf in tree or check if element is in tree It's recursive so curr has to be in
protected void insert_rec(leaf< T > * curr,T value)	Recursive function for inserting a value at its spot
protected leaf< T > * traverse(leaf< T > * curr,int * curr_idx,int ideal_idx)	Used to go on every element of the tree from left to right
protected void print(leaf< T > * curr)	prints tree in linked-list way
protected bool clear_rec(leaf< T > * curr)	Recursion func used to clear tree

Members

public bst() = default

public ~bst()

public virtual void insert(T value)

See also: sorted_list

public virtual T pop_front()

See also: sorted_list

public virtual T pop_back()

See also: sorted_list

public virtual T operator[](int index)

See also: sorted_list

public virtual bool find(T value)

See also: sorted_list

public virtual bool clear()

traverses over every element and delete it from memory See also: container

public void print()

prints tree

public inline leaf< T > * get_data()

protected leaf< T > * head

Head of the tree.

protected leaf< T > * find_leaf(leaf< T > * curr,T value)

Used to find leaf in tree or check if element is in tree It's recursive so curr has to be in

Parameters

• value of type T self explanatory

• curr pointer of current leaf to be processed

Returns

pointer to the leaf with value or nullptr otherwise

protected void insert_rec(leaf< T > * curr,T value)

Recursive function for inserting a value at its spot

Parameters

• curr currently processed leaf

• value

protected leaf< T > * traverse(leaf< T > * curr,int * curr_idx,int ideal_idx)

Used to go on every element of the tree from left to right

Parameters

• curr as its recursive curr means the elem that it start on the first is head

• curr_idx

• ideal_idx

protected void print(leaf< T > * curr)

prints tree in linked-list way

Parameters

• curr

protected bool clear_rec(leaf< T > * curr)

Recursion func used to clear tree

Parameters

• curr pointer to currently processed leaf

Returns

true if everything go as expected

class container

Basic interface with basic info as size in it, used in all structures.

Summary

Members	Descriptions
public inline int size() const	Method to show how much data it holds
public inline bool empty() const	Check if container is empty
public bool clear()	Used to delete every element in container, is pure-virtual and implemented in child classes
protected int size_	stores how many elements are in container
protected container() = default	Constructor in protected, only for child classes.
protected ~container() = default	Destructor in protected, only for child classes.

Members

public inline int size() const

Method to show how much data it holds

Returns

integer of size

public inline bool empty() const

Check if container is empty

Returns

bool meaning what the state is

public bool clear()

Used to delete every element in container, is pure-virtual and implemented in child classes

Returns

bool of success

protected int size_

stores how many elements are in container

protected container() = default

Constructor in protected, only for child classes.

protected ~container() = default

Destructor in protected, only for child classes.

class heap_node

Element which is used in priority_queue->vector as element

Parameters

• T type of data stored in value field

Summary

Members	Descriptions
public T value
public int index
public inline heap_node(void * pq,int index,T value)	The only constructor as nodes are created in priority_queue with every field in it names in contructor as used under the same name in class (pq is private)
public T change_priority(T new_value)	Changes value in node and rebalances in heap
public inline int parent()
public inline int left()
public inline int right()
public ~heap_node() = default

Members

public T value

public int index

public inline heap_node(void * pq,int index,T value)

The only constructor as nodes are created in priority_queue with every field in it names in contructor as used under the same name in class (pq is private)

Parameters

• pq pointer to heap in which heap_node is stored

• index on which place element is stored in priority_queue->vector

• value proper value of element

public T change_priority(T new_value)

Changes value in node and rebalances in heap

Parameters

• new_value value that is replacement for previous value

Returns

value that was previously stored in node

public inline int parent()

public inline int left()

public inline int right()

public ~heap_node() = default

class leaf

Tree leaf that is used in binary tree such as bst.

Summary

Members	Descriptions
public T value	Stores value of type T.
public leaf*right	Stores right leaf.
public leaf*left	Stores left leaf.
public leaf*parent	Stores parent leaf;.
public virtual ~leaf() = default

Members

public T value

Stores value of type T.

public leaf*right

Stores right leaf.

public leaf*left

Stores left leaf.

public leaf*parent

Stores parent leaf;.

public virtual ~leaf() = default

class link_vector

class link_vector
  : public list< T >
  : public container

A class that forms a 2-way linked list using .

Summary

Members	Descriptions
public virtual bool clear()	Deletes every node from memory in O(n)
public virtual void insert(int index,T value)	See also: list
public virtual void push_front(T value)	See also: list
public virtual void push_back(T value)	See also: list
public virtual T pop_front()	See also: list
public virtual T pop_back()	See also: list
public virtual T pop(int index)	See also: list
public virtual T operator[](int index)	See also: list
public virtual void replace(int index,T value)	See also: list
public ~link_vector()	Custom destructor for destroying nodes It just starts clear()
protected node< T > * first_	Means first node.
protected node< T > * last_	Means last node.

Members

public virtual bool clear()

Deletes every node from memory in O(n) See also: container

public virtual void insert(int index,T value)

See also: list

public virtual void push_front(T value)

See also: list

public virtual void push_back(T value)

See also: list

public virtual T pop_front()

See also: list

public virtual T pop_back()

See also: list

public virtual T pop(int index)

See also: list

public virtual T operator[](int index)

See also: list

public virtual void replace(int index,T value)

See also: list

public ~link_vector()

Custom destructor for destroying nodes It just starts clear()

protected node< T > * first_

Means first node.

protected node< T > * last_

Means last node.

class list

Interface for on-list operation with pure virtual methods and protected constructor and destructor

Summary

Members	Descriptions
public void insert(int index,T value)	Inserts a value at a certain index
public void push_front(T value)	Puts a value at start of the container
public void push_back(T value)	Puts a value at end of the container
public T pop_front()	Removes value at the beginning of list
public T pop_back()	Removes value at the end of list
public T pop(int index)	Removes value from retain index of the list
public T operator[](int index)	Picks value from desired index
public void replace(int index,T value)	Replacing a value at certain index
protected list() = default	Used to make constructor protected.
protected ~list() = default	Used to make destructor protected.

Members

public void insert(int index,T value)

Inserts a value at a certain index

Parameters

• index at which value has to be assigned

• value self-explanatory

public void push_front(T value)

Puts a value at start of the container

Parameters

• value self-explanatory

public void push_back(T value)

Puts a value at end of the container

Parameters

• value self-explanatory

public T pop_front()

Removes value at the beginning of list

Returns

T value

public T pop_back()

Removes value at the end of list

Returns

T value

public T pop(int index)

Removes value from retain index of the list

Parameters

• index integer from which spot value will be picked

Returns

T value

public T operator[](int index)

Picks value from desired index

Parameters

• index

Returns

T value

public void replace(int index,T value)

Replacing a value at certain index

Parameters

• index integer for place in list

• value for what this should be replaced

protected list() = default

Used to make constructor protected.

protected ~list() = default

Used to make destructor protected.

class priority_queue

class priority_queue
  : private vector< heap_node< T > * >
  : public container

Priority queue based on heap which is based on vector which holds heap_node* Values don't need to be unique. If no min_heap value is passed to constructor it's made to be min heap See also: heap_node

See also: vector

Parameters

• T type of stored elements it needs to implements operator<() and operator>()

Summary

Members	Descriptions
public priority_queue() = default	Default constructor.
public inline explicit priority_queue(int initial_size)	Constructor with initial_size of array containing elements
public inline priority_queue(int initial_size,bool min_heap)	Constructor with both arguments initial_size and min_heap
public inline explicit priority_queue(bool min_heap)	Constructor with one bool information
public inline ~priority_queue()
public void insert(T value)	Inserts element in heap
public T pop()	pops element that is on top of heap
public inline int size()	Checks for size of data
public inline bool empty()	Checks whether heap is empty
public inline virtual bool clear()	Removes every node from tab.
public inline heap_node< T > ** raw_data()	Function for having data from heap in an array
public inline void rebalance(int index)	Balances heap from point given - used when element changes in heap and when you insert or pop and element
public inline T top()	Function for taking top element without having to pop it
protected bool min_heap	value in which information on relation is stored (whether it's min heap(true) or max heap(max))
protected inline void swap_heap_nodes(int f1,int f2)	Swaps elements in heap from 2 indexes
protected void balance_up(heap_node< T > * node)	Balances the heap from index going thru parents
protected void balance_down(heap_node< T > * node)	Balances the heap from index going thru childs

Members

public priority_queue() = default

Default constructor.

public inline explicit priority_queue(int initial_size)

Constructor with initial_size of array containing elements

Parameters

• initial_size int with size of array at start

public inline priority_queue(int initial_size,bool min_heap)

Constructor with both arguments initial_size and min_heap

Parameters

• initial_size int with size of array at start

• min_heap bool whether this should be min heap (true) or max heap (false)

public inline explicit priority_queue(bool min_heap)

Constructor with one bool information

Parameters

• min_heap bool whether this should be min heap (true) or max heap (false)

public inline ~priority_queue()

public void insert(T value)

Inserts element in heap

Parameters

• value value that has to be inserted

public T pop()

pops element that is on top of heap

Returns

value of type T

public inline int size()

Checks for size of data

Returns

number of records in container

public inline bool empty()

Checks whether heap is empty

Returns

bool with certain information

public inline virtual bool clear()

Removes every node from tab.

public inline heap_node< T > ** raw_data()

Function for having data from heap in an array

Returns

whole array with heap

public inline void rebalance(int index)

Balances heap from point given - used when element changes in heap and when you insert or pop and element

Parameters

• index where to start balancing

public inline T top()

Function for taking top element without having to pop it

Returns

minimal(min heap)/maximal(max heap) element in heap

protected bool min_heap

value in which information on relation is stored (whether it's min heap(true) or max heap(max))

protected inline void swap_heap_nodes(int f1,int f2)

Swaps elements in heap from 2 indexes

Parameters

• f1 index of first element

• f2 index of second element

protected void balance_up(heap_node< T > * node)

Balances the heap from index going thru parents

Parameters

• node from which should balancing start

protected void balance_down(heap_node< T > * node)

Balances the heap from index going thru childs

Parameters

• node from which should balancing strart

class queue

class queue
  : public container

Basic LIFO structure that uses queue_node

Summary

Members	Descriptions
public bool enqueue(T value)	Puts element on the back of the queue
public T dequeue()	Removes element from the front
public T peek()	Peeks at the first element and dont remove it from queue
public virtual bool clear()	Pops every element in queue , it's O(n)
protected queue_node< T > * first_	First element in queue.
protected queue_node< T > * last_	Last element in queue.

Members

public bool enqueue(T value)

Puts element on the back of the queue

Parameters

• value of type T is put on back

Returns

bool of success

public T dequeue()

Removes element from the front

Returns

T value

public T peek()

Peeks at the first element and dont remove it from queue

Returns

T value

public virtual bool clear()

Pops every element in queue , it's O(n) See also: container

protected queue_node< T > * first_

First element in queue.

protected queue_node< T > * last_

Last element in queue.

class sorted_list

Only reliable on sorted structures. Interface for on-list operation with pure virtual methods and protected constructor and destructor.

Summary

Members	Descriptions
public void insert(T value)	Insert a value at its spot
public T pop_front()	Removes value at the beginning of list
public T pop_back()	Removes value at the end of list
public T operator[](int index)	Picks value from desired index
public bool find(T value)	Check if value is in list
protected sorted_list() = default	Used to make constructor protected.
protected ~sorted_list() = default	Used to make destructor protected.

Members

public void insert(T value)

Insert a value at its spot

Parameters

• value self-explanatory

public T pop_front()

Removes value at the beginning of list

Returns

T value

public T pop_back()

Removes value at the end of list

Returns

T value

public T operator[](int index)

Picks value from desired index

Parameters

• index

Returns

T value

public bool find(T value)

Check if value is in list

Parameters

• value of type T for search

Returns

bool true if element is in list

protected sorted_list() = default

Used to make constructor protected.

protected ~sorted_list() = default

Used to make destructor protected.

class stack

class stack
  : public container

Basic FIFO structure Uses stack_node (one way node)

Summary

Members	Descriptions
public bool push(T value)	Pushes value on top of the stack
public T pop()	Pops the top value from the stack
public T peek()	Peeks the top value from the stack
public ~stack()	Destructor for removing all nodes from memory.
public virtual bool clear()	Pops every element in stack

Members

public bool push(T value)

Pushes value on top of the stack

Parameters

• value of type T to be pushed on top

Returns

bool of success

public T pop()

Pops the top value from the stack

Returns

T value

public T peek()

Peeks the top value from the stack

Returns

T value of the top value

public ~stack()

Destructor for removing all nodes from memory.

public virtual bool clear()

Pops every element in stack See also: container

class vector

class vector
  : public list< T >
  : public array_container< T >

Resizeable array.

Summary

Members	Descriptions
public vector()	Default constructor.
public vector(int initial_size)	Constructor with possibility
public virtual void insert(int index,T value)	Inserts a value at a certain index
public virtual void push_back(T value)	Puts a value at end of the container
public virtual void push_front(T value)	Puts a value at start of the container
public virtual T pop_front()	Removes value at the beginning of list
public virtual T pop_back()	Removes value at the end of list
public virtual T pop(int index)	Removes value from retain index of the list
public virtual T operator[](int index)	Picks value from desired index
public virtual void replace(int index,T value)	Replacing a value at certain index

Members

public vector()

Default constructor.

public vector(int initial_size)

Constructor with possibility

Parameters

• initial_size for container

public virtual void insert(int index,T value)

Inserts a value at a certain index

Parameters

• index at which value has to be assigned

• value self-explanatory

public virtual void push_back(T value)

Puts a value at end of the container

Parameters

• value self-explanatory

public virtual void push_front(T value)

Puts a value at start of the container

Parameters

• value self-explanatory

public virtual T pop_front()

Removes value at the beginning of list

Returns

T value

public virtual T pop_back()

Removes value at the end of list

Returns

T value

public virtual T pop(int index)

Removes value from retain index of the list

Parameters

• index integer from which spot value will be picked

Returns

T value

public virtual T operator[](int index)

Picks value from desired index

Parameters

• index

Returns

T value

public virtual void replace(int index,T value)

Replacing a value at certain index

Parameters

• index integer for place in list

• value for what this should be replaced

struct node

It's 2 way linked list. Stores: value, next node, previous node

Summary

Members	Descriptions
public T value	Stores value of type T.
public node*next	Stores next node.
public node*previous	Stores previous node.

Members

public T value

Stores value of type T.

public node*next

Stores next node.

public node*previous

Stores previous node.

struct queue_node

Used only in queue as a (one) element container.

Summary

Members	Descriptions
public T value
public queue_node< T > * next

Members

public T value

public queue_node< T > * next

struct stack_node

Used only in stack as a (one) element container.

Summary

Members	Descriptions
public T value
public stack_node< T > * previous

Members

public T value

public stack_node< T > * previous

Generated by Moxygen