aboutsummaryrefslogtreecommitdiff
path: root/sem3/algo
diff options
context:
space:
mode:
Diffstat (limited to 'sem3/algo')
-rw-r--r--sem3/algo/lek1/merge.c32
-rw-r--r--sem3/algo/mm10/bfs.c46
-rw-r--r--sem3/algo/mm12/dijkstra.c33
-rw-r--r--sem3/algo/mm12/graph.c47
-rw-r--r--sem3/algo/mm2/linked/llist.c29
-rw-r--r--sem3/algo/mm2/linked/main.c10
-rw-r--r--sem3/algo/mm2/linked/node.c16
-rw-r--r--sem3/algo/mm2/queue.c31
-rw-r--r--sem3/algo/mm3/multiply.c10
-rw-r--r--sem3/algo/mm6/main.c3
-rw-r--r--sem3/algo/mm6/tree.c61
-rw-r--r--sem3/algo/workshop2/dfs/dfs.c21
-rw-r--r--sem3/algo/workshop2/dfs/graph.c64
-rw-r--r--sem3/algo/workshop2/dijkstra/dijkstra.c36
-rw-r--r--sem3/algo/workshop2/dijkstra/graph.c76
15 files changed, 300 insertions, 215 deletions
diff --git a/sem3/algo/lek1/merge.c b/sem3/algo/lek1/merge.c
index 997bcb8..945b86a 100644
--- a/sem3/algo/lek1/merge.c
+++ b/sem3/algo/lek1/merge.c
@@ -6,24 +6,26 @@
#define DO_PRINT 0
-void printArr(int *arr, size_t len) {
+void printArr(int *arr, size_t len)
+{
printf("{");
- for(int i = 0; i < len; i++) {
+ for (int i = 0; i < len; i++) {
printf(" %d%s", arr[i], i+1 == len ? " " : ",");
}
printf("}\n");
}
-int *genArr(size_t len, int div) {
+int *genArr(size_t len, int div)
+{
/* Make array */
int *arr = (int *) malloc(len * sizeof(int));
- if( arr == NULL) {
+ if (arr == NULL) {
return NULL;
}
/* Fill it with random */
- while( len-- ) {
+ while (len--) {
arr[len] = div - (rand() % (div*2));
}
@@ -31,7 +33,8 @@ int *genArr(size_t len, int div) {
}
-int mergeSort(int *arr, size_t len) {
+int mergeSort(int *arr, size_t len)
+{
/* Check if len is one(then it's sorted */
if (len <= 1) {
return 0;
@@ -42,11 +45,11 @@ int mergeSort(int *arr, size_t len) {
/* Make arrays */
int *left = (int *) malloc(q * sizeof(int));
- if( left == NULL ) {
+ if (left == NULL) {
return 1;
}
int *right = (int *) malloc(rl * sizeof(int));
- if( right == NULL ) {
+ if (right == NULL) {
return 1;
}
@@ -59,8 +62,8 @@ int mergeSort(int *arr, size_t len) {
mergeSort(right, rl);
/* Merge them into arr */
- for(int i=0, j=0, k = 0; k < len; k++) {
- if( i < q && ( j == rl || left[i] <= right[j] ) ) {
+ for (int i=0, j=0, k = 0; k < len; k++) {
+ if ( i < q && ( j == rl || left[i] <= right[j] ) ) {
arr[k] = left[ i++ ];
} else {
arr[k] = right[ j++ ];
@@ -74,7 +77,8 @@ int mergeSort(int *arr, size_t len) {
return 0;
}
-void test(size_t len) {
+void test(size_t len)
+{
int *a = genArr(len, len);
@@ -97,7 +101,8 @@ void test(size_t len) {
free(a);
}
-void bench() {
+void bench()
+{
size_t len = SIZE_MAX;
@@ -107,7 +112,8 @@ void bench() {
}
}
-int main(void) {
+int main(void)
+{
bench();
diff --git a/sem3/algo/mm10/bfs.c b/sem3/algo/mm10/bfs.c
index 982ecef..6f699f0 100644
--- a/sem3/algo/mm10/bfs.c
+++ b/sem3/algo/mm10/bfs.c
@@ -18,7 +18,8 @@ typedef struct vertex_struct {
list_node_t *adj;
} vertex_t;
-vertex_t *create_vertex(char ref) {
+vertex_t *create_vertex(char ref)
+{
// Get some space TODO check for null
vertex_t *v = malloc(sizeof(vertex_t));
@@ -30,7 +31,8 @@ vertex_t *create_vertex(char ref) {
v->adj = NULL;
}
-vertex_t *add_adj(vertex_t *v, vertex_t *add) {
+vertex_t *add_adj(vertex_t *v, vertex_t *add)
+{
list_node_t *oldN = v->adj;
// Create new list node
@@ -43,10 +45,11 @@ vertex_t *add_adj(vertex_t *v, vertex_t *add) {
return add;
}
-void print_adj(vertex_t *v) {
+void print_adj(vertex_t *v)
+{
list_node_t *n = v->adj;
printf("[ ");
- while(n) {
+ while (n) {
printf("%c ", *((char *)n->val));
n = n->next;
}
@@ -55,13 +58,14 @@ void print_adj(vertex_t *v) {
vertex_t *vertexes[128];
-void add_edge(char a, char b) {
+void add_edge(char a, char b)
+{
// Does a exists
- if( vertexes[a] == NULL ) {
+ if ( vertexes[a] == NULL ) {
vertexes[a] = create_vertex(a);
}
// What about b
- if( vertexes[b] == NULL ) {
+ if ( vertexes[b] == NULL ) {
vertexes[b] = create_vertex(b);
}
@@ -75,28 +79,30 @@ typedef struct {
list_node_t *out;
} queue_t;
-void enqueue(queue_t *q, vertex_t *v) {
+void enqueue(queue_t *q, vertex_t *v)
+{
list_node_t *n = malloc(sizeof(list_node_t));
n->val = v;
// Add at end
list_node_t *old = q->in;
q->in = n;
- if( old ) {
+ if ( old ) {
old->next = n;
}
// Make sure we have an out
- if( q->out == NULL ) {
+ if ( q->out == NULL ) {
q->out = n;
}
q->len++;
}
-vertex_t *dequeue(queue_t *q) {
+vertex_t *dequeue(queue_t *q)
+{
list_node_t *n = q->out;
- if( n == NULL ) {
+ if ( n == NULL ) {
return NULL;
}
vertex_t *v = (vertex_t *)n->val;
@@ -110,17 +116,18 @@ vertex_t *dequeue(queue_t *q) {
return v;
}
-void bfs(vertex_t *s) {
+void bfs(vertex_t *s)
+{
queue_t q = {0, NULL, NULL };
enqueue(&q, s);
s->dist = 0;
- while( q.len ) {
+ while ( q.len ) {
vertex_t *u = dequeue(&q);
list_node_t *n = u->adj;
- while( n ) {
+ while ( n ) {
vertex_t *v = (vertex_t *)n->val;
- if( v->color == COL_WHITE ) {
+ if ( v->color == COL_WHITE ) {
v->color = COL_GRAY;
v->dist = u->dist + 1;
v->p = u;
@@ -133,7 +140,8 @@ void bfs(vertex_t *s) {
}
-int main() {
+int main()
+{
add_edge('s', 'd'); // S
add_edge('s', 'c');
add_edge('s', 'a');
@@ -149,8 +157,8 @@ int main() {
bfs(vertexes['s']);
char c;
- while( (c = getchar()) != EOF) {
- if( vertexes[c] != NULL ) {
+ while ( (c = getchar()) != EOF) {
+ if ( vertexes[c] != NULL ) {
print_adj(vertexes[c]);
printf("%d\n", vertexes[c]->dist);
} else if (c == 10) {
diff --git a/sem3/algo/mm12/dijkstra.c b/sem3/algo/mm12/dijkstra.c
index 103c700..b4f0f94 100644
--- a/sem3/algo/mm12/dijkstra.c
+++ b/sem3/algo/mm12/dijkstra.c
@@ -14,7 +14,8 @@ typedef struct {
struct list_item *end;
} list_t;
-void list_push(list_t *s, vertex_t *v) {
+void list_push(list_t *s, vertex_t *v)
+{
// Create
list_item_t *i = malloc(sizeof(list_item_t));
i->next = NULL;
@@ -22,7 +23,7 @@ void list_push(list_t *s, vertex_t *v) {
i->v = v;
// Link
- if( s->len == 0 ) {
+ if ( s->len == 0 ) {
s->begin = i;
} else {
s->end->next = i;
@@ -33,25 +34,26 @@ void list_push(list_t *s, vertex_t *v) {
s->len++;
}
-vertex_t *list_pop_smallest(list_t *s) {
+vertex_t *list_pop_smallest(list_t *s)
+{
list_item_t *smallest = s->begin;
// Search
list_item_t *i = s->begin;
- while( i ) {
- if( i->v->dist != -1 && i->v->dist < smallest->v->dist ) {
+ while ( i ) {
+ if ( i->v->dist != -1 && i->v->dist < smallest->v->dist ) {
smallest = i;
}
i = i->next;
}
- if( smallest == s->begin ) {
+ if ( smallest == s->begin ) {
s->begin = smallest->next;
} else {
smallest->prev->next = smallest->next;
}
- if( smallest == s->end ) {
+ if ( smallest == s->end ) {
s->end = smallest->prev;
} else {
smallest->next->prev = smallest->prev;
@@ -68,20 +70,22 @@ vertex_t *list_pop_smallest(list_t *s) {
graph_t g;
// Assumes u has an edge to v
-void relax(vertex_t *u, vertex_t *v) {
+void relax(vertex_t *u, vertex_t *v)
+{
// Get edge between these two guys
edge_t *e = u->adj;
- while(e && e->next && e->to->ref != v->ref) {
+ while (e && e->next && e->to->ref != v->ref) {
e = e->next;
}
- if( v->dist == -1 || v->dist > (u->dist + e->weight) ) {
+ if ( v->dist == -1 || v->dist > (u->dist + e->weight) ) {
v->dist = u->dist + e->weight;
v->p = u;
}
}
-void dijkstra(graph_t *g, vertex_t *s) {
+void dijkstra(graph_t *g, vertex_t *s)
+{
list_t list;
list.len = 0;
list.end = list.begin = 0;
@@ -90,13 +94,13 @@ void dijkstra(graph_t *g, vertex_t *s) {
{
vertex_t *v = vertex_next(g, NULL);
- while( v ) {
+ while ( v ) {
list_push(&list, v);
v = vertex_next(g, v);
}
}
- while( list.len ) {
+ while ( list.len ) {
vertex_t *u = list_pop_smallest(&list);
edge_t *e = u->adj;
while( e ) {
@@ -106,7 +110,8 @@ void dijkstra(graph_t *g, vertex_t *s) {
}
}
-int main() {
+int main()
+{
graph_edge(&g, 'a', 'b', 2);
graph_edge(&g, 'a', 'f', 1);
diff --git a/sem3/algo/mm12/graph.c b/sem3/algo/mm12/graph.c
index 299ea24..e478103 100644
--- a/sem3/algo/mm12/graph.c
+++ b/sem3/algo/mm12/graph.c
@@ -2,7 +2,8 @@
#include <stdlib.h>
#include "graph.h"
-static vertex_t *create_vertex(char ref) {
+static vertex_t *create_vertex(char ref)
+{
// Get some space TODO check for null
vertex_t *v = malloc(sizeof(vertex_t));
@@ -14,7 +15,8 @@ static vertex_t *create_vertex(char ref) {
return v;
}
-static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
+static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight)
+{
edge_t *old = from->adj;
// Create new list node
@@ -25,12 +27,12 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
// Do new link
e->next = old;
- if( old ) {
+ if ( old ) {
e->prev = old->prev;
old->prev = e;
} else { e->prev = NULL; }
- if( e->prev ) {
+ if ( e->prev ) {
e->prev->next = e;
}
@@ -40,14 +42,15 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
}
// For iterating edges
-edge_t *edge_next(graph_t *g, edge_t *e) {
- if(e == NULL || e->next == NULL ) {
+edge_t *edge_next(graph_t *g, edge_t *e)
+{
+ if (e == NULL || e->next == NULL ) {
// Find next index
// Chose starting index 0 if NULL e
unsigned char i = e ? e->from->ref+1 : 0;
- for( ; i < 128; i++ ) {
- if( g->vertexes[i] && g->vertexes[i]->adj ) {
+ for ( ; i < 128; i++ ) {
+ if ( g->vertexes[i] && g->vertexes[i]->adj ) {
return g->vertexes[i]->adj;
}
}
@@ -59,10 +62,11 @@ edge_t *edge_next(graph_t *g, edge_t *e) {
return e->next;
}
-vertex_t *vertex_next(graph_t *g, vertex_t *v) {
+vertex_t *vertex_next(graph_t *g, vertex_t *v)
+{
unsigned char ref = v ? v->ref+1 : 0;
- for( ; ref < 128; ref++ ) {
- if( g->vertexes[ref] ) {
+ for ( ; ref < 128; ref++ ) {
+ if ( g->vertexes[ref] ) {
return g->vertexes[ref];
}
}
@@ -70,13 +74,14 @@ vertex_t *vertex_next(graph_t *g, vertex_t *v) {
return NULL;
}
-void graph_edge(graph_t *g, char from, char to, int weight) {
+void graph_edge(graph_t *g, char from, char to, int weight)
+{
// Does a exists
- if( g->vertexes[from] == NULL ) {
+ if ( g->vertexes[from] == NULL ) {
g->vertexes[from] = create_vertex(from);
}
// What about b
- if( g->vertexes[to] == NULL ) {
+ if ( g->vertexes[to] == NULL ) {
g->vertexes[to] = create_vertex(to);
}
@@ -84,14 +89,15 @@ void graph_edge(graph_t *g, char from, char to, int weight) {
create_edge(g->vertexes[from], g->vertexes[to], weight);
}
-int graph_print_adj(graph_t *g, char ref) {
- if( g->vertexes[ref] == NULL ) {
+int graph_print_adj(graph_t *g, char ref)
+{
+ if ( g->vertexes[ref] == NULL ) {
return 1;
}
edge_t *e = g->vertexes[ref]->adj;
printf("[ ");
- while(e && e->from->ref == ref) {
+ while (e && e->from->ref == ref) {
printf("%c[%d] ", e->to->ref, e->weight);
e = e->next;
}
@@ -100,19 +106,20 @@ int graph_print_adj(graph_t *g, char ref) {
return 0;
}
-int graph_to_dot(FILE *f, graph_t *g) {
+int graph_to_dot(FILE *f, graph_t *g)
+{
// print pre stuff
fprintf(f, "digraph coolgraph {\n");
// Label all nodes
vertex_t *v = vertex_next(g, NULL);
- while( v ) {
+ while ( v ) {
fprintf(f, "%c [label=\"%c(%d)\"];\n", v->ref, v->ref, v->dist);
v = vertex_next(g, v);
}
// Print all the edges
edge_t *e = edge_next(g, NULL);
- while( e ) {
+ while ( e ) {
fprintf(f, "%c -> %c [label = %d%s];\n", e->from->ref, e->to->ref, e->weight, e->to->p == e->from ? " color=blue" : "");
e = edge_next(g, e);
}
diff --git a/sem3/algo/mm2/linked/llist.c b/sem3/algo/mm2/linked/llist.c
index 41ab892..8044e0b 100644
--- a/sem3/algo/mm2/linked/llist.c
+++ b/sem3/algo/mm2/linked/llist.c
@@ -6,7 +6,8 @@
#define OUT_OFF_BOUNDS 2
-void llist_init(llist_t *list) {
+void llist_init(llist_t *list)
+{
/* Zero out structure */
list->head = list->root = NULL;
@@ -14,12 +15,13 @@ void llist_init(llist_t *list) {
}
-void llist_append(llist_t *list, int val) {
+void llist_append(llist_t *list, int val)
+{
/* Insert node after HEAD */
list->head = node_insert(list->head, val);
/* Check if was list is empty */
- if( list->len == 0 ) {
+ if ( list->len == 0 ) {
/* Set root */
list->root = list->head;
}
@@ -28,9 +30,10 @@ void llist_append(llist_t *list, int val) {
list->len++;
}
-node_t *llist_get_node(llist_t *list, unsigned int index) {
+node_t *llist_get_node(llist_t *list, unsigned int index)
+{
/* Check if we have it */
- if( index >= list->len ) {
+ if ( index >= list->len ) {
return NULL;
}
@@ -42,7 +45,7 @@ node_t *llist_get_node(llist_t *list, unsigned int index) {
node_t *node = direc > 0 ? list->root : list->head;
/* Go to index */
- while( pos != index ) {
+ while ( pos != index ) {
/* TODO kinda risky, we trust our math and len */
node = direc > 0 ? node->next : node->prev;
@@ -52,10 +55,11 @@ node_t *llist_get_node(llist_t *list, unsigned int index) {
return node;
}
-int llist_get(llist_t *list, unsigned int index) {
+int llist_get(llist_t *list, unsigned int index)
+{
/* Get node */
node_t *node = llist_get_node(list, index);
- if( node == NULL ) {
+ if ( node == NULL ) {
/* Yes i know this is stupid */
return -1;
}
@@ -65,19 +69,20 @@ int llist_get(llist_t *list, unsigned int index) {
}
-int llist_pop(llist_t *list, unsigned int index) {
+int llist_pop(llist_t *list, unsigned int index)
+{
/* Get node */
node_t *node = llist_get_node(list, index);
- if( node == NULL ) {
+ if ( node == NULL ) {
/* Yes i know this is stupid */
return -1;
}
/* Update root and head if we delete it */
- if( node == list->root ) {
+ if ( node == list->root ) {
list->root = node->next;
}
- if( node == list->head ) {
+ if ( node == list->head ) {
list->head = node->prev;
}
diff --git a/sem3/algo/mm2/linked/main.c b/sem3/algo/mm2/linked/main.c
index 72b62cc..6f4eb6a 100644
--- a/sem3/algo/mm2/linked/main.c
+++ b/sem3/algo/mm2/linked/main.c
@@ -2,10 +2,11 @@
#include "node.h"
#include "llist.h"
-void list_print(node_t *root) {
+void list_print(node_t *root)
+{
int index = 0;
/* Loop through notes and print them */
- while( root != NULL ) {
+ while ( root != NULL ) {
/* Print a value */
printf("%d: %d\n", index++, root->val);
@@ -15,7 +16,8 @@ void list_print(node_t *root) {
}
/* Remove node */
-int main() {
+int main()
+{
/* Do some stuff */
llist_t list;
@@ -39,7 +41,7 @@ int main() {
list_print(list.root);
- while( list.len ) {
+ while ( list.len ) {
printf("Popped %d\n", llist_pop(&list, 0));
}
}
diff --git a/sem3/algo/mm2/linked/node.c b/sem3/algo/mm2/linked/node.c
index cce1be0..21f0993 100644
--- a/sem3/algo/mm2/linked/node.c
+++ b/sem3/algo/mm2/linked/node.c
@@ -4,10 +4,11 @@
#include <stdlib.h>
/* Insert after node */
-node_t *node_insert(node_t *node, int val) {
+node_t *node_insert(node_t *node, int val)
+{
/* Create new node */
node_t *newNode = (node_t *) malloc( sizeof(node_t) );
- if( newNode == NULL ) {
+ if ( newNode == NULL ) {
return NULL;
}
@@ -16,7 +17,7 @@ node_t *node_insert(node_t *node, int val) {
newNode->prev = node;
/* Check if there is node before */
- if( node == NULL ) {
+ if ( node == NULL ) {
/* If not then there is no after */
newNode->next = NULL;
return newNode;
@@ -27,7 +28,7 @@ node_t *node_insert(node_t *node, int val) {
node->next = newNode;
/* Check node after */
- if( newNode->next != NULL ) {
+ if ( newNode->next != NULL ) {
/* Backlink next node */
newNode->next->prev = newNode;
}
@@ -36,17 +37,18 @@ node_t *node_insert(node_t *node, int val) {
}
/* Pop node */
-int node_pop(node_t *node) {
+int node_pop(node_t *node)
+{
int val = node->val;
/* Check prev */
- if( node->prev != NULL ) {
+ if ( node->prev != NULL ) {
/* Point last node to next node */
node->prev->next = node->next;
}
/* Check next */
- if( node->next != NULL ) {
+ if ( node->next != NULL ) {
node->next->prev = node->prev;
}
diff --git a/sem3/algo/mm2/queue.c b/sem3/algo/mm2/queue.c
index a93f76a..a574acb 100644
--- a/sem3/algo/mm2/queue.c
+++ b/sem3/algo/mm2/queue.c
@@ -15,13 +15,14 @@ typedef struct {
} queue_t;
/* Queue functions */
-int queue_init(queue_t *q, size_t cap) {
+int queue_init(queue_t *q, size_t cap)
+{
/* Make the struct and set i to zero */
memset(q, 0, sizeof(queue_t));
/* Allocate the buffer */
q->buff = (int *) malloc(cap * sizeof(int));
- if( q->buff == NULL ) {
+ if ( q->buff == NULL ) {
return 1;
}
@@ -30,15 +31,17 @@ int queue_init(queue_t *q, size_t cap) {
return 0;
}
-void queue_free(queue_t *q) {
+void queue_free(queue_t *q)
+{
/* Free the heap buffer */
free(q->buff);
}
-int queue_place(queue_t *q, int val) {
+int queue_place(queue_t *q, int val)
+{
/* Check if full */
printf("len: %d\n", q->len);
- if( q->len >= q->cap) {
+ if ( q->len >= q->cap) {
printf("ERR: Full\n");
return EFULL;
}
@@ -53,15 +56,16 @@ int queue_place(queue_t *q, int val) {
return 0;
}
-int queue_get(queue_t *q, int *val) {
+int queue_get(queue_t *q, int *val)
+{
/* Check if empty */
- if( !q->len ) {
+ if ( !q->len ) {
printf("ERR: Empty\n");
return EMPTY;
}
/* Read value */
- if( val != NULL ){
+ if ( val != NULL ){
*val = q->buff[q->tail];
}
@@ -72,25 +76,26 @@ int queue_get(queue_t *q, int *val) {
return 0;
}
-int main(void) {
+int main(void)
+{
int in;
char com;
queue_t q;
queue_init(&q, 16);
- for(;;) {
+ for (;;) {
/* Read a command */
scanf("%c", &com);
- if( com == 'w') {
+ if ( com == 'w') {
printf("> ");
scanf("%d", &in);
queue_place(&q, in);
- } else if( com == 'r' ) {
+ } else if ( com == 'r' ) {
queue_get(&q, &in);
printf("%d\n", in);
- } else if( com == 'q' ) {
+ } else if ( com == 'q' ) {
break;
}
}
diff --git a/sem3/algo/mm3/multiply.c b/sem3/algo/mm3/multiply.c
index e454de3..da8068c 100644
--- a/sem3/algo/mm3/multiply.c
+++ b/sem3/algo/mm3/multiply.c
@@ -3,12 +3,13 @@
#include <stdint.h>
#include <time.h>
-uint64_t mult(uint64_t x, uint64_t y, unsigned int bits) {
+uint64_t mult(uint64_t x, uint64_t y, unsigned int bits)
+{
/* Check if they expect more than 64 bits. */
- if( bits > 64 ) {
+ if ( bits > 64 ) {
printf("Sorry we cant handle higher than 64 bits\n");
exit(1);
- } else if(bits <= 1) {
+ } else if (bits <= 1) {
return x && y;
}
@@ -37,7 +38,8 @@ uint64_t mult(uint64_t x, uint64_t y, unsigned int bits) {
}
-int main(void) {
+int main(void)
+{
uint32_t a = 0xFFFFFF;
uint8_t b = 55;
diff --git a/sem3/algo/mm6/main.c b/sem3/algo/mm6/main.c
index abc8d02..a93571e 100644
--- a/sem3/algo/mm6/main.c
+++ b/sem3/algo/mm6/main.c
@@ -2,7 +2,8 @@
#include "tree.h"
-int main() {
+int main()
+{
tree_t t;
t.root = 0;
diff --git a/sem3/algo/mm6/tree.c b/sem3/algo/mm6/tree.c
index 47378f3..4d58309 100644
--- a/sem3/algo/mm6/tree.c
+++ b/sem3/algo/mm6/tree.c
@@ -4,7 +4,8 @@
#include "tree.h"
-static node_t *create_node(unsigned int index, char *val) {
+static node_t *create_node(unsigned int index, char *val)
+{
node_t *node = malloc( sizeof(node_t) );
memset(node, 0, sizeof(node_t));
@@ -13,7 +14,8 @@ static node_t *create_node(unsigned int index, char *val) {
}
/* Comments are based of dir = CHILD_LEFT */
-void node_rotate(tree_t *tree, node_t *x, int dir) {
+void node_rotate(tree_t *tree, node_t *x, int dir)
+{
/* Node below which we should rotate with */
node_t *y = x->children[!dir];
@@ -21,7 +23,7 @@ void node_rotate(tree_t *tree, node_t *x, int dir) {
x->children[!dir] = y->children[dir];
/* Update parent */
- if( y->children[dir] ) {
+ if ( y->children[dir] ) {
y->children[dir]->p = x;
}
@@ -29,9 +31,9 @@ void node_rotate(tree_t *tree, node_t *x, int dir) {
y->p = x->p;
/* Check if y is new root if not update x's parent */
- if( !y->p ) {
+ if ( !y->p ) {
tree->root = y;
- } else if( x == x->p->children[CHILD_LEFT]) {
+ } else if ( x == x->p->children[CHILD_LEFT]) {
x->p->children[CHILD_LEFT] = y;
} else {
x->p->children[CHILD_RIGHT] = y;
@@ -43,21 +45,22 @@ void node_rotate(tree_t *tree, node_t *x, int dir) {
}
-static void insert_fixup(tree_t *tree, node_t *z) {
- while( z->p && z->p->black == false ) {
+static void insert_fixup(tree_t *tree, node_t *z)
+{
+ while ( z->p && z->p->black == false ) {
/* Set the right direction */
int dir = (z->p == z->p->p->children[CHILD_LEFT]) ? CHILD_RIGHT : CHILD_LEFT;
/* Get uncle */
node_t *y = z->p->p->children[dir];
- if( y && !y->black ) {
+ if ( y && !y->black ) {
/* Case 1 */
z->p->black = true;
y->black = true;
z->p->p->black = false;
z = z->p->p;
- } else if( z == z->p->children[dir] ) {
+ } else if ( z == z->p->children[dir] ) {
/* Case 2 */
z = z->p;
node_rotate(tree, z, !dir);
@@ -73,10 +76,11 @@ static void insert_fixup(tree_t *tree, node_t *z) {
}
-static node_t *insert_recur(node_t *node, unsigned int index, char *val) {
+static node_t *insert_recur(node_t *node, unsigned int index, char *val)
+{
int dir = node->index < index ? CHILD_RIGHT : CHILD_LEFT;
- if( node->children[dir] ) {
+ if ( node->children[dir] ) {
return insert_recur(node->children[dir], index, val);
}
@@ -88,8 +92,9 @@ static node_t *insert_recur(node_t *node, unsigned int index, char *val) {
return new;
}
-node_t *tree_insert_pleb(tree_t *tree, unsigned int index, char *val) {
- if( !tree->root ) {
+node_t *tree_insert_pleb(tree_t *tree, unsigned int index, char *val)
+{
+ if ( !tree->root ) {
tree->root = create_node(index, val);
return tree->root;
}
@@ -97,8 +102,9 @@ node_t *tree_insert_pleb(tree_t *tree, unsigned int index, char *val) {
return insert_recur(tree->root, index, val);
}
-node_t *tree_insert(tree_t *tree, unsigned int index, char *val) {
- if( !tree->root ) {
+node_t *tree_insert(tree_t *tree, unsigned int index, char *val)
+{
+ if ( !tree->root ) {
tree->root = create_node(index, val);
tree->root->black = true;
return tree->root;
@@ -110,11 +116,12 @@ node_t *tree_insert(tree_t *tree, unsigned int index, char *val) {
return new;
}
-char *tree_search(tree_t *tree, unsigned int index) {
+char *tree_search(tree_t *tree, unsigned int index)
+{
node_t *z = tree->root;
- while( z->index != index ) {
+ while ( z->index != index ) {
z = z->children[z->index < index ? CHILD_RIGHT : CHILD_LEFT];
- if( !z ) {
+ if ( !z ) {
return NULL;
}
}
@@ -122,14 +129,16 @@ char *tree_search(tree_t *tree, unsigned int index) {
return z->value;
}
-static inline void print_indent(int num) {
- for( int i = 0; i < num; i++ ) {
+static inline void print_indent(int num)
+{
+ for ( int i = 0; i < num; i++ ) {
printf(" ");
}
}
-static inline void print_text(node_t *node, bool bold) {
- if( bold ) {
+static inline void print_text(node_t *node, bool bold)
+{
+ if ( bold ) {
printf("\033[1m%d\033[22m\n", node->index);
} else {
printf("%d\n", node->index);
@@ -137,8 +146,9 @@ static inline void print_text(node_t *node, bool bold) {
}
-static void print_recur(node_t *node, int ident) {
- if( !node ) {
+static void print_recur(node_t *node, int ident)
+{
+ if ( !node ) {
return;
}
print_recur(node->children[CHILD_RIGHT], ident+1);
@@ -149,7 +159,8 @@ static void print_recur(node_t *node, int ident) {
print_recur(node->children[CHILD_LEFT], ident+1);
}
-void tree_print(tree_t *tree) {
+void tree_print(tree_t *tree)
+{
print_recur(tree->root, 0);
}
diff --git a/sem3/algo/workshop2/dfs/dfs.c b/sem3/algo/workshop2/dfs/dfs.c
index 1244895..aa80519 100644
--- a/sem3/algo/workshop2/dfs/dfs.c
+++ b/sem3/algo/workshop2/dfs/dfs.c
@@ -10,8 +10,9 @@ graph_t g;
graph_t newg;
int step;
-void dfs_visit(graph_t *g, vertex_t *u, bool doprint) {
- if( doprint ) {
+void dfs_visit(graph_t *g, vertex_t *u, bool doprint)
+{
+ if ( doprint ) {
printf("dfs_visit( %s )\n", u->ref);
}
step++;
@@ -20,9 +21,9 @@ void dfs_visit(graph_t *g, vertex_t *u, bool doprint) {
// For every adj
edge_t *e = u->adj;
- while( e ) {
+ while ( e ) {
vertex_t *v = e->to;
- if( v->color == COLOR_WHITE ) {
+ if ( v->color == COLOR_WHITE ) {
graph_edge(&newg, v->ref, u->ref, 1);
dfs_visit(g, v, doprint);
}
@@ -35,13 +36,14 @@ void dfs_visit(graph_t *g, vertex_t *u, bool doprint) {
}
-void dfs(graph_t *g, bool doprint) {
+void dfs(graph_t *g, bool doprint)
+{
step = 0;
// For every edge
vertex_t *u = vertex_next(g, NULL);
- while( u ) {
- if( u->color == COLOR_WHITE ) {
+ while ( u ) {
+ if ( u->color == COLOR_WHITE ) {
dfs_visit(g, u, doprint);
}
u = vertex_next(g, u);
@@ -50,12 +52,13 @@ void dfs(graph_t *g, bool doprint) {
#define BENCH 9999
-int main() {
+int main()
+{
// benchmark
// Start by generating
- for(int i = 0; i < BENCH; i++) {
+ for (int i = 0; i < BENCH; i++) {
char from[5];
char to[5];
sprintf(from, "%d", i);
diff --git a/sem3/algo/workshop2/dfs/graph.c b/sem3/algo/workshop2/dfs/graph.c
index 0f5048c..0ad4467 100644
--- a/sem3/algo/workshop2/dfs/graph.c
+++ b/sem3/algo/workshop2/dfs/graph.c
@@ -6,7 +6,8 @@
#include "graph.h"
// Hashtable
-static unsigned int hash(char *s) {
+static unsigned int hash(char *s)
+{
uint32_t hv = 0;
for( int i = 0; s[i] != '\0'; i++ ) {
// take MSB 6 bits of hv and xors with LSB of s[i]
@@ -20,7 +21,8 @@ static unsigned int hash(char *s) {
}
-static void table_insert(graph_t *g, vertex_t *v, char *var) {
+static void table_insert(graph_t *g, vertex_t *v, char *var)
+{
unsigned int index = hash(var);
// Save old value
@@ -33,19 +35,21 @@ static void table_insert(graph_t *g, vertex_t *v, char *var) {
g->hashtable[index]->next = oldSym;
}
-static vertex_t *table_lookup(graph_t *g, char *var) {
+static vertex_t *table_lookup(graph_t *g, char *var)
+{
unsigned int index = hash(var);
vertex_t *n = g->hashtable[index];
// Look trough list
- while(n != NULL && strcmp(n->ref, var) != 0) {
+ while (n != NULL && strcmp(n->ref, var) != 0) {
n = n->next;
}
return n;
}
-static vertex_t *create_vertex(char *ref) {
+static vertex_t *create_vertex(char *ref)
+{
// Get some space TODO check for null
vertex_t *v = malloc(sizeof(vertex_t));
@@ -57,7 +61,8 @@ static vertex_t *create_vertex(char *ref) {
return v;
}
-static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
+static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight)
+{
edge_t *old = from->adj;
// Create new list node
@@ -68,12 +73,14 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
// Do new link
e->next = old;
- if( old ) {
+ if ( old ) {
e->prev = old->prev;
old->prev = e;
- } else { e->prev = NULL; }
+ } else {
+ e->prev = NULL;
+ }
- if( e->prev ) {
+ if ( e->prev ) {
e->prev->next = e;
}
@@ -83,16 +90,17 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
}
// For iterating edges
-edge_t *edge_next(graph_t *g, edge_t *e) {
- if(e == NULL || e->next == NULL ) {
+edge_t *edge_next(graph_t *g, edge_t *e)
+{
+ if (e == NULL || e->next == NULL ) {
// Find next index
vertex_t *v = e ? e->from : NULL;
// Find next vertex
v = vertex_next(g, v);
- while( v ) {
+ while ( v ) {
// Check if found
- if( v->adj ) {
+ if ( v->adj ) {
return v->adj;
}
@@ -107,12 +115,13 @@ edge_t *edge_next(graph_t *g, edge_t *e) {
return e->next;
}
-vertex_t *vertex_next(graph_t *g, vertex_t *v) {
- if( v == NULL || v->next == NULL) {
+vertex_t *vertex_next(graph_t *g, vertex_t *v)
+{
+ if ( v == NULL || v->next == NULL) {
// Go to next index in hashtable
int i = v ? hash(v->ref)+1 : 0;
- for( ; i < HASHSIZE; i++) {
- if( g->hashtable[i] ) {
+ for ( ; i < HASHSIZE; i++) {
+ if ( g->hashtable[i] ) {
return g->hashtable[i];
}
}
@@ -124,15 +133,16 @@ vertex_t *vertex_next(graph_t *g, vertex_t *v) {
return v->next;
}
-void graph_edge(graph_t *g, char *from, char *to, int weight) {
+void graph_edge(graph_t *g, char *from, char *to, int weight)
+{
vertex_t *fromv, *tov;
// Does a exists
- if( (fromv = table_lookup(g, from)) == NULL ) {
+ if ( (fromv = table_lookup(g, from)) == NULL ) {
fromv = create_vertex(from);
table_insert(g, fromv, from);
}
// What about b
- if( (tov = table_lookup(g, to)) == NULL ) {
+ if ( (tov = table_lookup(g, to)) == NULL ) {
tov = create_vertex(to);
table_insert(g, tov, to);
}
@@ -141,15 +151,16 @@ void graph_edge(graph_t *g, char *from, char *to, int weight) {
create_edge(fromv, tov, weight);
}
-int graph_print_adj(graph_t *g, char *ref) {
+int graph_print_adj(graph_t *g, char *ref)
+{
vertex_t *v = table_lookup(g, ref);
- if( v == NULL ) {
+ if ( v == NULL ) {
return 1;
}
edge_t *e = v->adj;
printf("[ ");
- while(e && e->from->ref == ref) {
+ while (e && e->from->ref == ref) {
printf("%s[%d] ", e->to->ref, e->weight);
e = e->next;
}
@@ -158,19 +169,20 @@ int graph_print_adj(graph_t *g, char *ref) {
return 0;
}
-int graph_to_dot(FILE *f, graph_t *g) {
+int graph_to_dot(FILE *f, graph_t *g)
+{
// print pre stuff
fprintf(f, "digraph coolgraph {\n");
// Label all nodes
vertex_t *v = vertex_next(g, NULL);
- while( v ) {
+ while ( v ) {
fprintf(f, "%s [label=\"%s\"];\n", v->ref, v->ref);
v = vertex_next(g, v);
}
// Print all the edges
edge_t *e = edge_next(g, NULL);
- while( e ) {
+ while ( e ) {
fprintf(f, "%s -> %s [label = %d];\n", e->from->ref, e->to->ref, e->weight);
e = edge_next(g, e);
}
diff --git a/sem3/algo/workshop2/dijkstra/dijkstra.c b/sem3/algo/workshop2/dijkstra/dijkstra.c
index 9609343..c112c6d 100644
--- a/sem3/algo/workshop2/dijkstra/dijkstra.c
+++ b/sem3/algo/workshop2/dijkstra/dijkstra.c
@@ -16,7 +16,8 @@ typedef struct {
struct list_item *end;
} list_t;
-void list_push(list_t *s, vertex_t *v) {
+void list_push(list_t *s, vertex_t *v)
+{
// Create
list_item_t *i = malloc(sizeof(list_item_t));
i->next = NULL;
@@ -24,7 +25,7 @@ void list_push(list_t *s, vertex_t *v) {
i->v = v;
// Link
- if( s->len == 0 ) {
+ if ( s->len == 0 ) {
s->begin = i;
} else {
s->end->next = i;
@@ -35,26 +36,27 @@ void list_push(list_t *s, vertex_t *v) {
s->len++;
}
-vertex_t *list_pop_smallest(list_t *s) {
+vertex_t *list_pop_smallest(list_t *s)
+{
//printf("beginning %s(%d)\n", s->begin->v->ref, s->begin->v->dist);
list_item_t *smallest = s->begin;
// Search
list_item_t *i = s->begin;
- while( i ) {
- if( smallest->v->dist == -1 || (i->v->dist != -1 && i->v->dist < smallest->v->dist) ) {
+ while ( i ) {
+ if ( smallest->v->dist == -1 || (i->v->dist != -1 && i->v->dist < smallest->v->dist) ) {
smallest = i;
}
i = i->next;
}
- if( smallest == s->begin ) {
+ if ( smallest == s->begin ) {
s->begin = smallest->next;
} else {
smallest->prev->next = smallest->next;
}
- if( smallest == s->end ) {
+ if ( smallest == s->end ) {
s->end = smallest->prev;
} else {
smallest->next->prev = smallest->prev;
@@ -71,20 +73,22 @@ vertex_t *list_pop_smallest(list_t *s) {
graph_t g;
// Assumes u has an edge to v
-void relax(vertex_t *u, vertex_t *v) {
+void relax(vertex_t *u, vertex_t *v)
+{
// Get edge between these two guys
edge_t *e = u->adj;
- while(e && e->next && strcmp(e->to->ref, v->ref)) {
+ while (e && e->next && strcmp(e->to->ref, v->ref)) {
e = e->next;
}
- if( v->dist == -1 || v->dist > (u->dist + e->weight) ) {
+ if ( v->dist == -1 || v->dist > (u->dist + e->weight) ) {
v->dist = u->dist + e->weight;
v->p = u;
}
}
-void dijkstra(graph_t *g, vertex_t *s) {
+void dijkstra(graph_t *g, vertex_t *s)
+{
list_t list;
list.len = 0;
list.end = list.begin = 0;
@@ -93,24 +97,24 @@ void dijkstra(graph_t *g, vertex_t *s) {
{
vertex_t *v = vertex_next(g, NULL);
- while( v ) {
+ while ( v ) {
list_push(&list, v);
v = vertex_next(g, v);
}
}
- while( list.len ) {
+ while ( list.len ) {
vertex_t *u = list_pop_smallest(&list);
edge_t *e = u->adj;
- while( e ) {
+ while ( e ) {
relax(u, e->to );
e = e->next;
}
}
}
-int main() {
-
+int main()
+{
int count = graph_from_dot(stdin, &g);
clock_t start, end;
diff --git a/sem3/algo/workshop2/dijkstra/graph.c b/sem3/algo/workshop2/dijkstra/graph.c
index 3f24ccf..51206c4 100644
--- a/sem3/algo/workshop2/dijkstra/graph.c
+++ b/sem3/algo/workshop2/dijkstra/graph.c
@@ -6,9 +6,10 @@
#include "graph.h"
// Hashtable
-static unsigned int hash(char *s) {
+static unsigned int hash(char *s)
+{
uint32_t hv = 0;
- for( int i = 0; s[i] != '\0'; i++ ) {
+ for ( int i = 0; s[i] != '\0'; i++ ) {
// take MSB 6 bits of hv and xors with LSB of s[i]
uint32_t v = ( hv >> 26 ) ^ (s[i] & 0x3f);
@@ -20,7 +21,8 @@ static unsigned int hash(char *s) {
}
-static void table_insert(graph_t *g, vertex_t *v, char *var) {
+static void table_insert(graph_t *g, vertex_t *v, char *var)
+{
unsigned int index = hash(var);
// Save old value
@@ -33,19 +35,21 @@ static void table_insert(graph_t *g, vertex_t *v, char *var) {
g->hashtable[index]->next = oldSym;
}
-static vertex_t *table_lookup(graph_t *g, char *var) {
+static vertex_t *table_lookup(graph_t *g, char *var)
+{
unsigned int index = hash(var);
vertex_t *n = g->hashtable[index];
// Look trough list
- while(n != NULL && strcmp(n->ref, var) != 0) {
+ while (n != NULL && strcmp(n->ref, var) != 0) {
n = n->next;
}
return n;
}
-static vertex_t *create_vertex(char *ref) {
+static vertex_t *create_vertex(char *ref)
+{
// Get some space TODO check for null
vertex_t *v = malloc(sizeof(vertex_t));
@@ -58,7 +62,8 @@ static vertex_t *create_vertex(char *ref) {
return v;
}
-static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
+static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight)
+{
edge_t *old = from->adj;
// Create new list node
@@ -69,12 +74,12 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
// Do new link
e->next = old;
- if( old ) {
+ if ( old ) {
e->prev = old->prev;
old->prev = e;
} else { e->prev = NULL; }
- if( e->prev ) {
+ if ( e->prev ) {
e->prev->next = e;
}
@@ -84,16 +89,17 @@ static edge_t *create_edge(vertex_t *from, vertex_t *to, int weight) {
}
// For iterating edges
-edge_t *edge_next(graph_t *g, edge_t *e) {
- if(e == NULL || e->next == NULL ) {
+edge_t *edge_next(graph_t *g, edge_t *e)
+{
+ if (e == NULL || e->next == NULL ) {
// Find next index
vertex_t *v = e ? e->from : NULL;
// Find next vertex
v = vertex_next(g, v);
- while( v ) {
+ while ( v ) {
// Check if found
- if( v->adj ) {
+ if ( v->adj ) {
return v->adj;
}
@@ -108,12 +114,13 @@ edge_t *edge_next(graph_t *g, edge_t *e) {
return e->next;
}
-vertex_t *vertex_next(graph_t *g, vertex_t *v) {
- if( v == NULL || v->next == NULL) {
+vertex_t *vertex_next(graph_t *g, vertex_t *v)
+{
+ if ( v == NULL || v->next == NULL) {
// Go to next index in hashtable
int i = v ? hash(v->ref)+1 : 0;
- for( ; i < HASHSIZE; i++) {
- if( g->hashtable[i] ) {
+ for ( ; i < HASHSIZE; i++) {
+ if ( g->hashtable[i] ) {
return g->hashtable[i];
}
}
@@ -125,15 +132,16 @@ vertex_t *vertex_next(graph_t *g, vertex_t *v) {
return v->next;
}
-void graph_edge(graph_t *g, char *from, char *to, int weight) {
+void graph_edge(graph_t *g, char *from, char *to, int weight)
+{
vertex_t *fromv, *tov;
// Does a exists
- if( (fromv = table_lookup(g, from)) == NULL ) {
+ if ( (fromv = table_lookup(g, from)) == NULL ) {
fromv = create_vertex(from);
table_insert(g, fromv, from);
}
// What about b
- if( (tov = table_lookup(g, to)) == NULL ) {
+ if ( (tov = table_lookup(g, to)) == NULL ) {
tov = create_vertex(to);
table_insert(g, tov, to);
}
@@ -142,15 +150,16 @@ void graph_edge(graph_t *g, char *from, char *to, int weight) {
create_edge(fromv, tov, weight);
}
-int graph_print_adj(graph_t *g, char *ref) {
+int graph_print_adj(graph_t *g, char *ref)
+{
vertex_t *v = table_lookup(g, ref);
- if( v == NULL ) {
+ if ( v == NULL ) {
return 1;
}
edge_t *e = v->adj;
printf("[ ");
- while(e && e->from->ref == ref) {
+ while (e && e->from->ref == ref) {
printf("%s[%d] ", e->to->ref, e->weight);
e = e->next;
}
@@ -159,19 +168,20 @@ int graph_print_adj(graph_t *g, char *ref) {
return 0;
}
-int graph_to_dot(FILE *f, graph_t *g) {
+int graph_to_dot(FILE *f, graph_t *g)
+{
// print pre stuff
fprintf(f, "digraph coolgraph {\n");
// Label all nodes
vertex_t *v = vertex_next(g, NULL);
- while( v ) {
+ while ( v ) {
fprintf(f, "%s [label=\"%s(%d)\"];\n", v->ref, v->ref, v->dist);
v = vertex_next(g, v);
}
// Print all the edges
edge_t *e = edge_next(g, NULL);
- while( e ) {
+ while ( e ) {
fprintf(f, "%s -> %s [label = %d%s];\n", e->from->ref, e->to->ref, e->weight, e->to->p == e->from ? " color=blue" : "");
e = edge_next(g, e);
}
@@ -181,26 +191,27 @@ int graph_to_dot(FILE *f, graph_t *g) {
}
// This was created in a hurry sorry
-int graph_from_dot(FILE *f, graph_t *g) {
+int graph_from_dot(FILE *f, graph_t *g)
+{
char from[100], to[100];
int weight;
int count = 0;
// just fscanf it
- for(;;) {
+ for (;;) {
// Set first to zero
*from = 0;
*to = 0;
weight = 0;
int c = fscanf(f, "%s -> %s [label=%d];", from, to, &weight);
- if( c <= 0 ) {
+ if ( c <= 0 ) {
break;
}
- if( *from == 0 || *to == 0 ) {
+ if ( *from == 0 || *to == 0 ) {
continue;
}
// Sorry i just want it to work
int tolen = strlen(to);
- if( to[tolen-1] == ';' ) {
+ if ( to[tolen-1] == ';' ) {
to[tolen-1] = 0;
}
@@ -214,6 +225,7 @@ int graph_from_dot(FILE *f, graph_t *g) {
return count;
}
-vertex_t *graph_vertex(graph_t *g, char *ref) {
+vertex_t *graph_vertex(graph_t *g, char *ref)
+{
return table_lookup(g, ref);
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-27 07:42:13 +0000