Commit cf2dec1
Changed files (12)
src/03/avl_tree.c
@@ -13,19 +13,14 @@ static void print_tree(AVLTree *tree, int level) {
return;
print_tree(tree->left, level + 1);
print_tree(tree->right, level + 1);
- }
- else {
+ } else {
printf("( )\n");
}
}
-static bool is_even(int value) {
- return value % 2 == 0;
-}
+static bool is_even(int value) { return value % 2 == 0; }
-static bool is_odd(int value) {
- return !is_even(value);
-}
+static bool is_odd(int value) { return !is_even(value); }
static RBTree *to_rb_tree(AVLTree *tree, AVLTree *parent) {
if (!tree)
@@ -43,25 +38,21 @@ static RBTree *to_rb_tree(AVLTree *tree, AVLTree *parent) {
return rb_tree;
}
-static void change_colour(RBTree* tree, enum Colour colour) {
+static void change_colour(RBTree *tree, enum Colour colour) {
if (!tree)
return;
- int left_height = rb_tree_height(tree->left);
- int right_height = rb_tree_height(tree->right);
+ int l = rb_tree_height(tree->left);
+ int r = rb_tree_height(tree->right);
tree->colour = colour;
- change_colour(tree->left, left_height < right_height || is_odd(left_height) ? black : red);
- change_colour(tree->right, right_height < left_height || is_odd(right_height) ? black : red);
+ change_colour(tree->left, l < r || is_odd(l) ? black : red);
+ change_colour(tree->right, r < l || is_odd(r) ? black : red);
}
-static int max(int a, int b) {
- return (a > b) ? a : b;
-}
+static int max(int a, int b) { return (a > b) ? a : b; }
-static int height_of(AVLTree *tree) {
- return tree == NULL ? 0 : tree->height;
-}
+static int height_of(AVLTree *tree) { return tree == NULL ? 0 : tree->height; }
static AVLTree *smallest(AVLTree *tree) {
AVLTree *current = tree;
@@ -102,10 +93,7 @@ static int balance_of(AVLTree *tree) {
return (tree == NULL) ? 0 : height_of(tree->left) - height_of(tree->right);
}
-static int compare(int a, int b)
-{
- return (a < b) ? -1 : ((a > b) ? 1 : 0);
-}
+static int compare(int a, int b) { return (a < b) ? -1 : ((a > b) ? 1 : 0); }
AVLTree *avl_tree_initialize(int value) {
AVLTree *tree = malloc(sizeof(AVLTree));
@@ -131,15 +119,15 @@ AVLTree *avl_tree_insert(AVLTree *tree, int value) {
if (tree == NULL)
return avl_tree_initialize(value);
- switch(compare(value, tree->value)) {
- case -1:
- tree->left = avl_tree_insert(tree->left, value);
- break;
- case 1:
- tree->right = avl_tree_insert(tree->right, value);
- break;
- default:
- return tree;
+ switch (compare(value, tree->value)) {
+ case -1:
+ tree->left = avl_tree_insert(tree->left, value);
+ break;
+ case 1:
+ tree->right = avl_tree_insert(tree->right, value);
+ break;
+ default:
+ return tree;
}
tree->height = 1 + max(height_of(tree->left), height_of(tree->right));
@@ -168,30 +156,30 @@ AVLTree *avl_tree_delete(AVLTree *tree, int value) {
if (tree == NULL)
return tree;
- switch(compare(value, tree->value)) {
- case -1:
- tree->left = avl_tree_delete(tree->left, value);
- break;
- case 1:
- tree->right = avl_tree_delete(tree->right, value);
- break;
- default:
- if (tree->left && tree->right) {
- AVLTree *min = smallest(tree->right);
- tree->value = min->value;
- tree->right = avl_tree_delete(tree->right, min->value);
+ switch (compare(value, tree->value)) {
+ case -1:
+ tree->left = avl_tree_delete(tree->left, value);
+ break;
+ case 1:
+ tree->right = avl_tree_delete(tree->right, value);
+ break;
+ default:
+ if (tree->left && tree->right) {
+ AVLTree *min = smallest(tree->right);
+ tree->value = min->value;
+ tree->right = avl_tree_delete(tree->right, min->value);
+ } else {
+ AVLTree *tmp = tree->left ? tree->left : tree->right;
+
+ if (tmp) {
+ *tree = *tmp;
+ free(tmp);
} else {
- AVLTree *tmp = tree->left ? tree->left : tree->right;
-
- if (tmp) {
- *tree = *tmp;
- free(tmp);
- } else {
- free(tree);
- return NULL;
- }
+ free(tree);
+ return NULL;
}
- break;
+ }
+ break;
}
tree->height = 1 + max(height_of(tree->left), height_of(tree->right));
@@ -225,6 +213,4 @@ RBTree *avl_tree_to_rb_tree(AVLTree *tree) {
return rb_tree;
}
-void avl_tree_inspect(AVLTree *tree) {
- print_tree(tree, 0);
-}
+void avl_tree_inspect(AVLTree *tree) { print_tree(tree, 0); }
src/03/avl_tree_test.c
@@ -38,13 +38,13 @@ Ensure(insert_creates_a_new_root) {
}
Ensure(insert_performs_a_left_rotation) {
-/*
- (10) (20)
- \ / \
- (20) -> (10) (30)
- \
- (30)
-*/
+ /*
+ (10) (20)
+ \ / \
+ (20) -> (10) (30)
+ \
+ (30)
+ */
AVLTree *tree = avl_tree_initialize(10);
tree = avl_tree_insert(tree, 20);
tree = avl_tree_insert(tree, 30);
@@ -55,13 +55,13 @@ Ensure(insert_performs_a_left_rotation) {
};
Ensure(insert_performs_a_right_rotation) {
-/*
- (30) (20)
- / / \
- (20) --> (10) (30)
- /
-(10)
-*/
+ /*
+ (30) (20)
+ / / \
+ (20) --> (10) (30)
+ /
+ (10)
+ */
AVLTree *tree = avl_tree_initialize(30);
tree = avl_tree_insert(tree, 20);
tree = avl_tree_insert(tree, 10);
@@ -72,13 +72,13 @@ Ensure(insert_performs_a_right_rotation) {
}
Ensure(insert_performs_a_left_right_rotation) {
-/*
- (30) (20)
- / / \
-(10) -> (10) (30)
- \
- (20)
-*/
+ /*
+ (30) (20)
+ / / \
+ (10) -> (10) (30)
+ \
+ (20)
+ */
AVLTree *tree = avl_tree_initialize(30);
tree = avl_tree_insert(tree, 10);
tree = avl_tree_insert(tree, 20);
@@ -89,13 +89,13 @@ Ensure(insert_performs_a_left_right_rotation) {
}
Ensure(insert_performs_a_right_left_rotation) {
-/*
-(10) (20)
- \ / \
- (30) --> (10) (30)
- /
-(20)
-*/
+ /*
+ (10) (20)
+ \ / \
+ (30) --> (10) (30)
+ /
+ (20)
+ */
AVLTree *tree = avl_tree_initialize(10);
tree = avl_tree_insert(tree, 30);
tree = avl_tree_insert(tree, 20);
@@ -106,25 +106,25 @@ Ensure(insert_performs_a_right_left_rotation) {
}
Ensure(delete_handles_left_left_case) {
-/*
- (z) (y)
- / \ / \
- (y) (T4) (X) (z)
- / \ --> / \ / \
- (x) (T3) (T1) (T2) (T3) (T4)
- / \
-(T1) (T2)
-
-Delete (37):
-
- (30) (20)
- / \ / \
- (20) (35) (10) (30)
- / \ \ --> / \ / \
- (10) (25) *(37) (5) (15) (25) (35)
- / \
-(5) (15)
-*/
+ /*
+ (z) (y)
+ / \ / \
+ (y) (T4) (X) (z)
+ / \ --> / \ / \
+ (x) (T3) (T1) (T2) (T3) (T4)
+ / \
+ (T1) (T2)
+
+ Delete (37):
+
+ (30) (20)
+ / \ / \
+ (20) (35) (10) (30)
+ / \ \ --> / \ / \
+ (10) (25) *(37) (5) (15) (25) (35)
+ / \
+ (5) (15)
+ */
AVLTree *tree = avl_tree_initialize(30);
tree = avl_tree_insert(tree, 35);
@@ -149,25 +149,25 @@ Delete (37):
}
Ensure(delete_handles_left_right_case) {
-/*
- (z) (x)
- / \ / \
- (y) (T4) (y) (z)
- / \ --> / \ / \
- (T1) (x) (T1) (T2) (T3) (T4)
- / \
- (T2) (T3)
-
-Delete (37):
-
- (30) (25)
- / \ / \
- (20) (35) (20) (30)
- / \ \ --> / \ / \
- (10) (25) *(37) (10) (22) (27) (35)
- / \
- (22) (27)
-*/
+ /*
+ (z) (x)
+ / \ / \
+ (y) (T4) (y) (z)
+ / \ --> / \ / \
+ (T1) (x) (T1) (T2) (T3) (T4)
+ / \
+ (T2) (T3)
+
+ Delete (37):
+
+ (30) (25)
+ / \ / \
+ (20) (35) (20) (30)
+ / \ \ --> / \ / \
+ (10) (25) *(37) (10) (22) (27) (35)
+ / \
+ (22) (27)
+ */
AVLTree *tree = avl_tree_initialize(30);
tree = avl_tree_insert(tree, 20);
tree = avl_tree_insert(tree, 35);
@@ -191,24 +191,24 @@ Delete (37):
}
Ensure(delete_handles_right_right_case) {
-/*
- (z) (y)
- / \ / \
- (T4) (y) (z) (x)
- / \ --> / \ / \
- (T3) (x) (T4) (T3) (T2) (T1)
- / \
- (T2) (T1)
+ /*
+ (z) (y)
+ / \ / \
+ (T4) (y) (z) (x)
+ / \ --> / \ / \
+ (T3) (x) (T4) (T3) (T2) (T1)
+ / \
+ (T2) (T1)
- (20) (30)
- / \ / \
- (15) (30) (20) (35)
- / / \ --> / \ / \
-*(10) (25) (35) (15) (25) (33) (37)
- / \
- (33) (37)
-*/
+ (20) (30)
+ / \ / \
+ (15) (30) (20) (35)
+ / / \ --> / \ / \
+ *(10) (25) (35) (15) (25) (33) (37)
+ / \
+ (33) (37)
+ */
AVLTree *tree = avl_tree_initialize(20);
tree = avl_tree_insert(tree, 30);
@@ -235,24 +235,24 @@ Ensure(delete_handles_right_right_case) {
}
Ensure(delete_handles_right_left) {
-/*
- (z) (x)
- / \ / \
- (T4) (y) (z) (y)
- / \ / \ / \
- (x) (T1) --> (T4) (T3) (T2) (T1)
- / \
- (T3) (T2)
-
-
- (20) (22)
- / \ / \
- (15) (25) (20) (25)
- / / \ / \ / \
-*(10) (22) (30) --> (15) (21) (23) (30)
- / \
- (21) (23)
-*/
+ /*
+ (z) (x)
+ / \ / \
+ (T4) (y) (z) (y)
+ / \ / \ / \
+ (x) (T1) --> (T4) (T3) (T2) (T1)
+ / \
+ (T3) (T2)
+
+
+ (20) (22)
+ / \ / \
+ (15) (25) (20) (25)
+ / / \ / \ / \
+ *(10) (22) (30) --> (15) (21) (23) (30)
+ / \
+ (21) (23)
+ */
AVLTree *tree = avl_tree_initialize(20);
tree = avl_tree_insert(tree, 15);
@@ -277,8 +277,9 @@ Ensure(delete_handles_right_left) {
}
Ensure(delete_handles_a_complicated_and_large_tree) {
- int items[] = { 44, 17, 62, 10, 32, 50, 78, 21, 48, 54, 72, 88, 45, 49, 52, 56, 81, 92 };
- unsigned int length = sizeof(items)/sizeof(items[0]);
+ int items[] = {44, 17, 62, 10, 32, 50, 78, 21, 48,
+ 54, 72, 88, 45, 49, 52, 56, 81, 92};
+ unsigned int length = sizeof(items) / sizeof(items[0]);
AVLTree *tree = NULL;
for (int i = 0; i < length; i++)
@@ -290,8 +291,8 @@ Ensure(delete_handles_a_complicated_and_large_tree) {
}
Ensure(delete_handles_a_complicated_and_small_tree) {
- int items[] = { 9, 1, 10, 0, 5, 11, -1, 2, 6 };
- unsigned int length = sizeof(items)/sizeof(items[0]);
+ int items[] = {9, 1, 10, 0, 5, 11, -1, 2, 6};
+ unsigned int length = sizeof(items) / sizeof(items[0]);
AVLTree *tree = NULL;
for (int i = 0; i < length; i++)
@@ -309,16 +310,16 @@ Ensure(delete_returns_a_null_root) {
}
Ensure(to_rb_tree_returns_a_new_red_black_tree) {
-/*
- (20:3) (20:b)
- / \ --> / \
- (15:2) (30:2) (15:b) (30:b)
- / \ \ / \ \
-(10:1) (17:1) (35:1) (10:r) (17:r) (35:r)
- */
+ /*
+ (20:3) (20:b)
+ / \ --> / \
+ (15:2) (30:2) (15:b) (30:b)
+ / \ \ / \ \
+ (10:1) (17:1) (35:1) (10:r) (17:r) (35:r)
+ */
AVLTree *tree = NULL;
RBTree *expected = NULL;
- int items[] = { 20, 15, 30, 10, 17, 35};
+ int items[] = {20, 15, 30, 10, 17, 35};
int length = sizeof(items) / sizeof(items[0]);
for (int i = 0; i < length; i++) {
src/03/btree_test.c
@@ -1,8 +1,8 @@
#include "btree.h"
#include "rb_tree.h"
#include <cgreen/cgreen.h>
-#include <string.h>
#include <math.h>
+#include <string.h>
Ensure(initialize_returns_new_btree) {
BTree *tree = btree_initialize(10);
src/03/graph.c
@@ -1,6 +1,6 @@
#include "graph.h"
-#include <stdlib.h>
#include <stdio.h>
+#include <stdlib.h>
Vertex *vertex_initialize(char label) {
Vertex *item = malloc(sizeof(Vertex));
src/03/graph_test.c
@@ -32,11 +32,8 @@ Ensure(add_vertex_adds_max_number_of_verticies_to_graph) {
Ensure(add_edge_connects_two_vertices) {
Graph *graph = graph_initialize();
- graph_add_edge(
- graph,
- graph_add_vertex(graph, 'a'),
- graph_add_vertex(graph, 'b')
- );
+ graph_add_edge(graph, graph_add_vertex(graph, 'a'),
+ graph_add_vertex(graph, 'b'));
assert_that(graph->edges['a']['b'], is_equal_to(true));
assert_that(graph->edges['b']['a'], is_equal_to(false));
src/03/matrix.c
@@ -1,15 +1,9 @@
#include <stdio.h>
#include <stdlib.h>
-char labels[26] = {
- 'a', 'b', 'c', 'd',
- 'e', 'f', 'g', 'h',
- 'i', 'j', 'k', 'l',
- 'm', 'n', 'o', 'p',
- 'q', 'r', 's', 't',
- 'u', 'v', 'w', 'x',
- 'y', 'z'
-};
+char labels[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
+ 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
+ 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
void matrix_traverse(int n, int graph[n][n], int visited[n], int vertex) {
printf("->(%c)", labels[vertex]);
src/03/matrix_test.c
@@ -6,22 +6,22 @@ Ensure(every_edge_is_traversed_in_both_directions_at_least_once) {
int n = 16;
int visited[16] = {0};
int graph[16][16] = {
- {0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0},
- {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
- {0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0},
- {0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0},
- {1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
- {1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0},
- {0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,0},
- {0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0},
- {0,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0},
- {0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0},
- {0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0},
- {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
- {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
- {0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0},
- {0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1},
- {0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0},
+ {0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+ {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
+ {1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0},
+ {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0},
+ {0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
+ {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1},
+ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
};
matrix_traverse(n, graph, visited, 0);
src/03/meldable_heap.c
@@ -1,12 +1,9 @@
#include "meldable_heap.h"
#include <stddef.h>
-#include <stdlib.h>
#include <stdio.h>
+#include <stdlib.h>
-static int compare(int a, int b)
-{
- return (a < b) ? -1 : ((a > b) ? 1 : 0);
-}
+static int compare(int a, int b) { return (a < b) ? -1 : ((a > b) ? 1 : 0); }
static void print_tree(MeldableHeap *heap, int level) {
for (int i = 0; i < level; i++)
@@ -19,13 +16,11 @@ static void print_tree(MeldableHeap *heap, int level) {
return;
print_tree(heap->left, level + 1);
print_tree(heap->right, level + 1);
- }
- else {
+ } else {
printf("( )\n");
}
}
-
MeldableHeap *meldable_heap_initialize(int value) {
MeldableHeap *heap = malloc(sizeof(MeldableHeap));
heap->left = NULL;
@@ -36,14 +31,17 @@ MeldableHeap *meldable_heap_initialize(int value) {
};
MeldableHeap *meldable_heap_add(MeldableHeap *heap, int value) {
- MeldableHeap *root = meldable_heap_merge(meldable_heap_initialize(value), heap);
+ MeldableHeap *root =
+ meldable_heap_merge(meldable_heap_initialize(value), heap);
root->parent = NULL;
return root;
}
-MeldableHeap *meldable_heap_merge(MeldableHeap *h1, MeldableHeap* h2) {
- if (h1 == NULL) return h2;
- if (h2 == NULL) return h1;
+MeldableHeap *meldable_heap_merge(MeldableHeap *h1, MeldableHeap *h2) {
+ if (h1 == NULL)
+ return h2;
+ if (h2 == NULL)
+ return h1;
if (compare(h2->value, h1->value) < 0)
return meldable_heap_merge(h2, h1);
@@ -51,21 +49,16 @@ MeldableHeap *meldable_heap_merge(MeldableHeap *h1, MeldableHeap* h2) {
if (rand() % 2 == 0) {
h1->left = meldable_heap_merge(h1->left, h2);
h1->left->parent = h1;
- }
- else {
+ } else {
h1->right = meldable_heap_merge(h1->right, h2);
h1->right->parent = h1;
}
return h1;
}
-void meldable_heap_inspect(MeldableHeap *heap)
-{
- print_tree(heap, 0);
-}
+void meldable_heap_inspect(MeldableHeap *heap) { print_tree(heap, 0); }
-void meldable_heap_remove(MeldableHeap *heap)
-{
+void meldable_heap_remove(MeldableHeap *heap) {
MeldableHeap *replacement = meldable_heap_merge(heap->left, heap->right);
if (replacement)
src/03/rb_tree.c
@@ -1,15 +1,13 @@
#include "rb_tree.h"
-#include <stdlib.h>
#include <stdio.h>
+#include <stdlib.h>
/*
* Implementation derived from:
* * https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion
*/
-static int max(int a, int b) {
- return a == b ? a : (a > b ? a : b);
-}
+static int max(int a, int b) { return a == b ? a : (a > b ? a : b); }
/**
* Number of black nodes to leaf.
@@ -28,13 +26,9 @@ static int depth(RBTree *tree) {
return total;
}
-static bool is_root(RBTree *node) {
- return node->parent == NULL;
-}
+static bool is_root(RBTree *node) { return node->parent == NULL; }
-static RBTree *parent_of(RBTree *node) {
- return node ? node->parent : NULL;
-}
+static RBTree *parent_of(RBTree *node) { return node ? node->parent : NULL; }
static RBTree *root_of(RBTree *node) {
RBTree *current = node;
@@ -60,9 +54,7 @@ static RBTree *sibling_of(RBTree *node) {
return node == parent->left ? parent->right : parent->left;
}
-static RBTree *pibling_of(RBTree *node) {
- return sibling_of(parent_of(node));
-}
+static RBTree *pibling_of(RBTree *node) { return sibling_of(parent_of(node)); }
static void rb_rotate_left(RBTree *tree) {
RBTree *tmp = tree->right;
@@ -136,8 +128,7 @@ static void repair_from(RBTree *tree) {
if (tree == parent->left) {
rb_rotate_right(grand_parent);
- }
- else {
+ } else {
rb_rotate_left(grand_parent);
}
parent->colour = black;
@@ -146,9 +137,7 @@ static void repair_from(RBTree *tree) {
}
}
-static int compare(int a, int b) {
- return a == b ? 0 : a < b ? -1 : 1;
-}
+static int compare(int a, int b) { return a == b ? 0 : a < b ? -1 : 1; }
static void insert(RBTree *root, RBTree *node) {
if (!root)
@@ -176,14 +165,14 @@ static void print_tree(RBTree *tree, int level) {
printf(" ");
if (tree) {
- printf("(%d%c H:%d)\n", tree->value, tree->colour == red ? 'R' : 'B', rb_tree_height(tree));
+ printf("(%d%c H:%d)\n", tree->value, tree->colour == red ? 'R' : 'B',
+ rb_tree_height(tree));
if (!tree->left && !tree->right)
return;
print_tree(tree->left, level + 1);
print_tree(tree->right, level + 1);
- }
- else {
+ } else {
printf("( )\n");
}
}
@@ -212,9 +201,7 @@ RBTree *rb_tree_insert(RBTree *tree, int value) {
return root_of(node);
}
-void rb_tree_inspect(RBTree *tree) {
- print_tree(tree, 0);
-}
+void rb_tree_inspect(RBTree *tree) { print_tree(tree, 0); }
int rb_tree_size(RBTree *tree) {
int total = 0;
@@ -240,10 +227,10 @@ bool rb_equals(RBTree *tree, RBTree *other_tree) {
if (tree->parent && tree->parent->value != other_tree->parent->value)
return false;
- return tree->value == other_tree->value
- && tree->colour == other_tree->colour
- && rb_equals(tree->left, other_tree->left)
- && rb_equals(tree->right, other_tree->right);
+ return tree->value == other_tree->value &&
+ tree->colour == other_tree->colour &&
+ rb_equals(tree->left, other_tree->left) &&
+ rb_equals(tree->right, other_tree->right);
}
bool rb_tree_is_valid(RBTree *tree) {
src/03/rb_tree_test.c
@@ -4,14 +4,17 @@
/*
* Every node has a colour. red or black
* Root of the tree is always black.
- * There are no two adjacent red nodes. (red node cannot have red parent or child)
+ * There are no two adjacent red nodes. (red node cannot have red parent or
+child)
* Every path from root to child NULL node has same # of black nodes.
*
*
* 1. every node is coloured red or black.
* 2. All leaves (nils) are black.
- * 3. Every red node has black children. black nodes can have any color children.
- * 4. From any node, the # of black nodes on any path to the leaves is the same. (same # of black nodes from top to bottom)
+ * 3. Every red node has black children. black nodes can have any color
+children.
+ * 4. From any node, the # of black nodes on any path to the leaves is the same.
+(same # of black nodes from top to bottom)
height: logn if perfectly balanced.
@@ -65,14 +68,14 @@ Ensure(insert_adds_a_new_item_to_left_subtree) {
}
Ensure(rb_tree_insert_performs_a_right_rotation) {
-/*
- (30) (20:b)
- / / \
- (20) -> (10:r) (30:r)
- /
-(10)
-
-*/
+ /*
+ (30) (20:b)
+ / / \
+ (20) -> (10:r) (30:r)
+ /
+ (10)
+
+ */
RBTree *tree = rb_tree_initialize(30);
tree = rb_tree_insert(tree, 20);
@@ -92,13 +95,13 @@ Ensure(rb_tree_insert_performs_a_right_rotation) {
}
Ensure(rb_tree_insert_performs_a_left_rotation) {
-/*
-(10) (20:b)
- \ / \
- (20) -> (10:r) (30:r)
- \
- (30)
-*/
+ /*
+ (10) (20:b)
+ \ / \
+ (20) -> (10:r) (30:r)
+ \
+ (30)
+ */
RBTree *tree = rb_tree_initialize(10);
tree = rb_tree_insert(tree, 20);
@@ -116,13 +119,13 @@ Ensure(rb_tree_insert_performs_a_left_rotation) {
}
Ensure(rb_tree_insert_repaints_the_new_node) {
-/*
- (20:b) (20:b)
- / \ / \
- (10:r) (30:r) --> (10:b) (30:b)
- / /
-(5:r) (5:r)
-*/
+ /*
+ (20:b) (20:b)
+ / \ / \
+ (10:r) (30:r) --> (10:b) (30:b)
+ / /
+ (5:r) (5:r)
+ */
RBTree *tree = rb_tree_initialize(20);
tree = rb_tree_insert(tree, 10);
@@ -258,7 +261,8 @@ Ensure(is_valid_returns_false_when_red_node_has_red_child) {
assert_that(rb_tree_is_valid(tree), is_equal_to(false));
}
-Ensure(is_valid_returns_false_when_each_path_to_leaves_does_not_contain_the_same_number_of_black_nodes) {
+Ensure(
+ is_valid_returns_false_when_each_path_to_leaves_does_not_contain_the_same_number_of_black_nodes) {
RBTree *tree = NULL;
for (int i = 10; i > 0; i--)
@@ -312,7 +316,8 @@ TestSuite *rb_tree_tests() {
add_test(x, equals_returns_false_when_other_tree_is_NULL);
add_test(x, equals_returns_true_when_both_trees_are_NULL);
add_test(x, equals_returns_false_when_tree_has_one_node);
- add_test(x, equals_returns_false_when_tree_has_one_node_with_different_colours);
+ add_test(x,
+ equals_returns_false_when_tree_has_one_node_with_different_colours);
add_test(x, equals_returns_true_when_tree_has_one_node);
add_test(x, equals_returns_true_when_root_and_left_subtree_are_equal);
add_test(x, equals_returns_false_when_root_and_left_subtree_are_not_equal);
@@ -321,7 +326,9 @@ TestSuite *rb_tree_tests() {
add_test(x, is_valid_returns_false_when_root_is_red);
add_test(x, is_valid_returns_false_when_red_node_has_red_child);
- add_test(x, is_valid_returns_false_when_each_path_to_leaves_does_not_contain_the_same_number_of_black_nodes);
+ add_test(
+ x,
+ is_valid_returns_false_when_each_path_to_leaves_does_not_contain_the_same_number_of_black_nodes);
add_test(x, is_valid_return_true);
add_test(x, height_returns_one);
src/03/sort.c
@@ -1,8 +1,7 @@
#include <stdio.h>
#include <stdlib.h>
-static void dump(int *items, int n)
-{
+static void dump(int *items, int n) {
printf("[");
for (int i = 0; i < n; ++i)
printf("%d,", items[i]);
@@ -10,7 +9,7 @@ static void dump(int *items, int n)
}
static void _merge(int *items, int min, int mid, int max) {
- int length = (max-min) + 1;
+ int length = (max - min) + 1;
int tmp[length];
int j = min, k = mid;
@@ -20,15 +19,14 @@ static void _merge(int *items, int min, int mid, int max) {
tmp[i] = items[j++];
else
tmp[i] = items[k++];
+ else if (j >= mid)
+ tmp[i] = items[k++];
else
- if (j >= mid)
- tmp[i] = items[k++];
- else
- tmp[i] = items[j++];
+ tmp[i] = items[j++];
}
for (int i = 0; i < length; i++)
- items[min+i] = tmp[i];
+ items[min + i] = tmp[i];
}
static void _merge_sort(int *items, int min, int max) {
@@ -54,8 +52,8 @@ static int partition(int *items, int min, int max) {
items[j] = tmp;
}
}
- tmp = items[index+1];
- items[index+1] = items[max];
+ tmp = items[index + 1];
+ items[index + 1] = items[max];
items[max] = tmp;
return index + 1;
src/03/sort_test.c
@@ -2,13 +2,9 @@
#include <cgreen/cgreen.h>
#include <string.h>
-Ensure(one_equals_one) {
- assert_that(1, is_equal_to(1));
-}
+Ensure(one_equals_one) { assert_that(1, is_equal_to(1)); }
-Ensure(merge_sort_sorts_a_null_list) {
- merge_sort(NULL, 0);
-}
+Ensure(merge_sort_sorts_a_null_list) { merge_sort(NULL, 0); }
Ensure(merge_sort_sorts_an_empty_list) {
int items[] = {};
@@ -37,7 +33,7 @@ Ensure(merge_sort_sorts_a_list_with_two_items) {
}
Ensure(merge_sort_sorts_three_unique_items) {
- int items[] = { 3, 1, 4 };
+ int items[] = {3, 1, 4};
merge_sort(items, sizeof(items) / sizeof(int));
@@ -47,7 +43,7 @@ Ensure(merge_sort_sorts_three_unique_items) {
}
Ensure(merge_sort_sorts_many_items) {
- int items[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
+ int items[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
merge_sort(items, sizeof(items) / sizeof(int));
@@ -64,9 +60,7 @@ Ensure(merge_sort_sorts_many_items) {
assert_that(items[10], is_equal_to(9));
}
-Ensure(quick_sort_sorts_a_null_list) {
- quick_sort(NULL, 0);
-}
+Ensure(quick_sort_sorts_a_null_list) { quick_sort(NULL, 0); }
Ensure(quick_sort_sorts_an_empty_list) {
int items[] = {};
@@ -94,7 +88,7 @@ Ensure(quick_sort_sorts_a_list_with_two_items) {
}
Ensure(quick_sort_sorts_three_unique_items) {
- int items[] = { 3, 1, 4 };
+ int items[] = {3, 1, 4};
quick_sort(items, sizeof(items) / sizeof(int));
@@ -104,7 +98,7 @@ Ensure(quick_sort_sorts_three_unique_items) {
}
Ensure(quick_sort_sorts_many_items) {
- int items[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
+ int items[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
quick_sort(items, sizeof(items) / sizeof(int));
@@ -121,7 +115,6 @@ Ensure(quick_sort_sorts_many_items) {
assert_that(items[10], is_equal_to(9));
}
-
TestSuite *sort_tests() {
TestSuite *x = create_test_suite();
add_test(x, one_equals_one);