aboutsummaryrefslogtreecommitdiff
path: root/c13
diff options
context:
space:
mode:
Diffstat (limited to 'c13')
-rw-r--r--c13/ex00/ft_btree.h10
-rw-r--r--c13/ex01/btree_apply_prefix.c9
-rw-r--r--c13/ex01/ft_btree.h8
-rw-r--r--c13/ex02/btree_apply_infix.c9
-rw-r--r--c13/ex02/ft_btree.h8
-rw-r--r--c13/ex03/btree_apply_suffix.c9
-rw-r--r--c13/ex03/ft_btree.h8
-rw-r--r--c13/ex04/btree_insert_data.c16
-rw-r--r--c13/ex04/ft_btree.h10
-rw-r--r--c13/ex05/btree_search_item.c20
-rw-r--r--c13/ex05/ft_btree.h8
-rw-r--r--c13/ex06/btree_level_count.c33
-rw-r--r--c13/ex06/ft_btree.h8
-rw-r--r--c13/ex07/btree_apply_by_level.c0
-rw-r--r--c13/ex07/ft_btree.h8
-rw-r--r--c13/ft_btree.h23
-rw-r--r--c13/main.c90
17 files changed, 200 insertions, 77 deletions
diff --git a/c13/ex00/ft_btree.h b/c13/ex00/ft_btree.h
index 3af177e..7d55f1a 100644
--- a/c13/ex00/ft_btree.h
+++ b/c13/ex00/ft_btree.h
@@ -6,7 +6,7 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 12:09:35 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -15,9 +15,11 @@
typedef struct s_btree
{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
+ struct s_btree *left;
+ struct s_btree *right;
+ void *item;
} t_btree;
+t_btree *btree_create_node(void *item);
+
#endif
diff --git a/c13/ex01/btree_apply_prefix.c b/c13/ex01/btree_apply_prefix.c
index 530d698..a1edd28 100644
--- a/c13/ex01/btree_apply_prefix.c
+++ b/c13/ex01/btree_apply_prefix.c
@@ -6,17 +6,18 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/21 18:28:07 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:37:15 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 13:49:17 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
+#include <stdlib.h>
#include "ft_btree.h"
-void btree_apply_prefix(t_btree *root, void (*applyf)(void *))
+void btree_apply_prefix(t_btree *root, void (*applyf)(void *))
{
if (root == NULL)
return ;
(*applyf)(root->item);
- btree_apply_prefix(root->left);
- btree_apply_prefix(root->right);
+ btree_apply_prefix(root->left, applyf);
+ btree_apply_prefix(root->right, applyf);
}
diff --git a/c13/ex01/ft_btree.h b/c13/ex01/ft_btree.h
index 3af177e..a1b6269 100644
--- a/c13/ex01/ft_btree.h
+++ b/c13/ex01/ft_btree.h
@@ -6,7 +6,7 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 12:10:09 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -15,9 +15,9 @@
typedef struct s_btree
{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
+ struct s_btree *left;
+ struct s_btree *right;
+ void *item;
} t_btree;
#endif
diff --git a/c13/ex02/btree_apply_infix.c b/c13/ex02/btree_apply_infix.c
index 3ff3278..c05cbd6 100644
--- a/c13/ex02/btree_apply_infix.c
+++ b/c13/ex02/btree_apply_infix.c
@@ -6,17 +6,18 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/21 18:28:07 by cacharle #+# #+# */
-/* Updated: 2019/07/23 21:09:53 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 13:49:17 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
+#include <stdlib.h>
#include "ft_btree.h"
-void btree_apply_infix(t_btree *root, void (*applyf)(void *))
+void btree_apply_infix(t_btree *root, void (*applyf)(void *))
{
if (root == NULL)
return ;
- btree_apply_infix(root->left);
+ btree_apply_infix(root->left, applyf);
(*applyf)(root->item);
- btree_apply_infix(root->right);
+ btree_apply_infix(root->right, applyf);
}
diff --git a/c13/ex02/ft_btree.h b/c13/ex02/ft_btree.h
index 3af177e..2a1506a 100644
--- a/c13/ex02/ft_btree.h
+++ b/c13/ex02/ft_btree.h
@@ -6,7 +6,7 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 12:10:39 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -15,9 +15,9 @@
typedef struct s_btree
{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
+ struct s_btree *left;
+ struct s_btree *right;
+ void *item;
} t_btree;
#endif
diff --git a/c13/ex03/btree_apply_suffix.c b/c13/ex03/btree_apply_suffix.c
index 6d5c3b2..5c00f37 100644
--- a/c13/ex03/btree_apply_suffix.c
+++ b/c13/ex03/btree_apply_suffix.c
@@ -6,17 +6,18 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/21 18:37:33 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:38:10 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 13:49:17 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
+#include <stdlib.h>
#include "ft_btree.h"
-void btree_apply_suffix(t_btree *root, void (*applyf)(void *))
+void btree_apply_suffix(t_btree *root, void (*applyf)(void *))
{
if (root == NULL)
return ;
- btree_apply_suffix(root->left);
- btree_apply_suffix(root->right);
+ btree_apply_suffix(root->left, applyf);
+ btree_apply_suffix(root->right, applyf);
(*applyf)(root->item);
}
diff --git a/c13/ex03/ft_btree.h b/c13/ex03/ft_btree.h
index 3af177e..f847890 100644
--- a/c13/ex03/ft_btree.h
+++ b/c13/ex03/ft_btree.h
@@ -6,7 +6,7 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 12:10:57 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -15,9 +15,9 @@
typedef struct s_btree
{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
+ struct s_btree *left;
+ struct s_btree *right;
+ void *item;
} t_btree;
#endif
diff --git a/c13/ex04/btree_insert_data.c b/c13/ex04/btree_insert_data.c
index 0999cab..e04514f 100644
--- a/c13/ex04/btree_insert_data.c
+++ b/c13/ex04/btree_insert_data.c
@@ -6,20 +6,20 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/21 18:43:18 by cacharle #+# #+# */
-/* Updated: 2019/07/23 20:49:48 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 14:18:29 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
#include <stdlib.h>
#include "ft_btree.h"
-// this is half shit
-void btree_insert_data(t_btree **root, void *item, int (*cmpf)(void *, void *))
+void btree_insert_data(t_btree **root, void *item,
+ int (*cmpf)(void *, void *))
{
if (*root == NULL)
- *root = btree_create_elem(item);
- if ((*cmpf)((*root)->item, item) < 0)
- btree_insert_root(&(*root)->left, item, cmpf);
- else if ((*cmpf)((*root)->item, item) > 0)
- btree_insert_root(&(*root)->right, item, cmpf);
+ *root = btree_create_node(item);
+ else if ((*cmpf)(item, (*root)->item) < 0)
+ btree_insert_data(&(*root)->left, item, cmpf);
+ else
+ btree_insert_data(&(*root)->right, item, cmpf);
}
diff --git a/c13/ex04/ft_btree.h b/c13/ex04/ft_btree.h
index 3af177e..0572243 100644
--- a/c13/ex04/ft_btree.h
+++ b/c13/ex04/ft_btree.h
@@ -6,7 +6,7 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 12:11:28 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -15,9 +15,11 @@
typedef struct s_btree
{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
+ struct s_btree *left;
+ struct s_btree *right;
+ void *item;
} t_btree;
+t_btree *btree_create_node(void *item);
+
#endif
diff --git a/c13/ex05/btree_search_item.c b/c13/ex05/btree_search_item.c
index b5d7114..a714e0c 100644
--- a/c13/ex05/btree_search_item.c
+++ b/c13/ex05/btree_search_item.c
@@ -6,11 +6,27 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/23 20:49:54 by cacharle #+# #+# */
-/* Updated: 2019/07/23 21:09:10 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 14:15:46 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
-void *btree_search_item(t_btree *root, void *data_ref, int (*cmpf)(void *, void *))
+#include <stdlib.h>
+#include "ft_btree.h"
+
+void *btree_search_item(t_btree *root, void *data_ref,
+ int (*cmpf)(void *, void *))
{
+ void *tmp;
+ if (root == NULL)
+ return (NULL);
+ tmp = btree_search_item(root->left, data_ref, cmpf);
+ if (tmp != NULL)
+ return (tmp);
+ if ((*cmpf)(root->item, data_ref) == 0)
+ return (root->item);
+ tmp = btree_search_item(root->right, data_ref, cmpf);
+ if (tmp != NULL)
+ return (tmp);
+ return (NULL);
}
diff --git a/c13/ex05/ft_btree.h b/c13/ex05/ft_btree.h
index 3af177e..61ef7b6 100644
--- a/c13/ex05/ft_btree.h
+++ b/c13/ex05/ft_btree.h
@@ -6,7 +6,7 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 12:15:59 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -15,9 +15,9 @@
typedef struct s_btree
{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
+ struct s_btree *left;
+ struct s_btree *right;
+ void *item;
} t_btree;
#endif
diff --git a/c13/ex06/btree_level_count.c b/c13/ex06/btree_level_count.c
index e69de29..5f83662 100644
--- a/c13/ex06/btree_level_count.c
+++ b/c13/ex06/btree_level_count.c
@@ -0,0 +1,33 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* btree_level_count.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2019/07/24 11:51:34 by cacharle #+# #+# */
+/* Updated: 2019/07/24 12:28:45 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include <stdlib.h>
+#include "ft_btree.h"
+
+int btree_level_count(t_btree *root)
+{
+ int left_level;
+ int right_level;
+
+ if (root == NULL)
+ return (0);
+ left_level = 0;
+ right_level = 0;
+ if (root->left != NULL)
+ left_level = btree_level_count(root->left);
+ if (root->right != NULL)
+ right_level = btree_level_count(root->right);
+ if (left_level >= right_level)
+ return (1 + left_level);
+ else
+ return (1 + right_level);
+}
diff --git a/c13/ex06/ft_btree.h b/c13/ex06/ft_btree.h
index 3af177e..398e060 100644
--- a/c13/ex06/ft_btree.h
+++ b/c13/ex06/ft_btree.h
@@ -6,7 +6,7 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 12:16:54 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -15,9 +15,9 @@
typedef struct s_btree
{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
+ struct s_btree *left;
+ struct s_btree *right;
+ void *item;
} t_btree;
#endif
diff --git a/c13/ex07/btree_apply_by_level.c b/c13/ex07/btree_apply_by_level.c
deleted file mode 100644
index e69de29..0000000
--- a/c13/ex07/btree_apply_by_level.c
+++ /dev/null
diff --git a/c13/ex07/ft_btree.h b/c13/ex07/ft_btree.h
index 3af177e..88a3bbd 100644
--- a/c13/ex07/ft_btree.h
+++ b/c13/ex07/ft_btree.h
@@ -6,7 +6,7 @@
/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
+/* Updated: 2019/07/24 12:19:36 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -15,9 +15,9 @@
typedef struct s_btree
{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
+ struct s_btree *left;
+ struct s_btree *right;
+ void *item;
} t_btree;
#endif
diff --git a/c13/ft_btree.h b/c13/ft_btree.h
deleted file mode 100644
index 3af177e..0000000
--- a/c13/ft_btree.h
+++ /dev/null
@@ -1,23 +0,0 @@
-/* ************************************************************************** */
-/* */
-/* ::: :::::::: */
-/* ft_btree.h :+: :+: :+: */
-/* +:+ +:+ +:+ */
-/* By: cacharle <charles.cabergs@gmail.com> +#+ +:+ +#+ */
-/* +#+#+#+#+#+ +#+ */
-/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */
-/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */
-/* */
-/* ************************************************************************** */
-
-#ifndef FT_BTREE_H
-# define FT_BTREE_H
-
-typedef struct s_btree
-{
- struct s_btree *left;
- struct s_btree *right;
- void *item;
-} t_btree;
-
-#endif
diff --git a/c13/main.c b/c13/main.c
new file mode 100644
index 0000000..16e7ebb
--- /dev/null
+++ b/c13/main.c
@@ -0,0 +1,90 @@
+#include <stdio.h>
+#include "ex00/ft_btree.h"
+#include "ex00/btree_create_node.c"
+#include "ex01/btree_apply_prefix.c"
+#include "ex02/btree_apply_infix.c"
+#include "ex03/btree_apply_suffix.c"
+#include "ex04/btree_insert_data.c"
+#include "ex05/btree_search_item.c"
+#include "ex06/btree_level_count.c"
+
+void f_print(void *d);
+int cmp(void *x, void *y);
+int equal(void *x, void *y);
+
+int main()
+{
+ int a = 1;
+ int b = 2;
+ int c = 3;
+ int d = 4;
+ int e = 5;
+ int big = 1000;
+ int bigger = 10000;
+ t_btree *t = btree_create_node(&a);
+ t_btree *l = btree_create_node(&b);
+ t_btree *r = btree_create_node(&c);
+ t->left = l;
+ t->right = r;
+
+ printf("%d %p %p\n", *(int*)t->item, t->left, t->right);
+ printf("%d %p %p", *(int*)l->item, l->left, l->right);
+
+ printf("\n-----------------\n");
+ btree_apply_prefix(t, &f_print);
+
+ printf("\n-----------------\n");
+ btree_apply_infix(t, &f_print);
+
+ printf("\n-----------------\n");
+ btree_apply_suffix(t, &f_print);
+
+ printf("\n-----------------\n");
+ t_btree *sorted = NULL;
+ btree_insert_data(&sorted, &c, &cmp);
+ btree_insert_data(&sorted, &a, &cmp);
+ btree_insert_data(&sorted, &b, &cmp);
+ btree_insert_data(&sorted, &e, &cmp);
+ btree_insert_data(&sorted, &d, &cmp);
+ btree_insert_data(&sorted, &big, &cmp);
+ btree_insert_data(&sorted, &big, &cmp);
+ /*btree_insert_data(&sorted, &bigger, &cmp);*/
+ btree_apply_prefix(sorted, &f_print);
+
+ printf("\n-----------------\n");
+ t_btree *empty = NULL;
+ t_btree *one = btree_create_node(&a);
+ printf("%p\n", btree_search_item(empty, &a, &equal));
+ printf("%p\n", (int*)btree_search_item(empty, &a, &equal));
+ printf("%d\n", *(int*)btree_search_item(sorted, &a, &equal));
+ printf("%d\n", *(int*)btree_search_item(sorted, &big, &equal));
+ /*printf("%d\n", *(int*)btree_search_item(sorted, &bigger, &equal));*/
+
+ printf("\n-----------------\n");
+ printf("%d\n", btree_level_count(sorted));
+ printf("%d\n", btree_level_count(t));
+ printf("%d\n", btree_level_count(empty));
+ printf("%d\n", btree_level_count(one));
+}
+
+void f_print(void *d)
+{
+ printf("%d ", *(int*)d);
+ fflush(stdout);
+}
+
+int cmp(void *x, void *y)
+{
+ if (*(int*)x < *(int*)y)
+ return -1;
+ if (*(int*)x > *(int*)y)
+ return 1;
+ return 0;
+}
+
+int equal(void *x, void *y)
+{
+ if (*(int*)x == *(int*)y)
+ return 0;
+ return 1;
+}
generated by cgit (git 2.34.1) at 2026-05-16 03:48:31 +0000