Added ft_btsorted_insert, ft_btsorted_search, Red-black tree struct (not tested)

10 files changed, 413 insertions, 16 deletions

diff --git a/include/libft_bt.h b/include/libft_bt.h
index 6e2cc91..7bd7eb4 100644
--- a/include/libft_bt.h
+++ b/include/libft_bt.h
@@ -6,23 +6,44 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/02/07 21:26:34 by cacharle          #+#    #+#             */
-/*   Updated: 2020/02/07 21:34:52 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/04/26 19:45:56 by charles          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #ifndef LIBFT_BT_H
 # define LIBFT_BT_H
 
+/*
+** \file   libft_bt.h
+** \brief  Binary tree
+*/
+
 # include <stdlib.h>
 
-typedef struct			s_ftbtree
+/*
+** \brief        Binary tree struct
+** \param left   Left node
+** \param right  Right node
+** \param data   Node data
+*/
+
+typedef struct		s_ftbt
 {
-	void				*data;
-	struct s_ftbtree	*left;
-	struct s_ftbtree	*right;
-}						t_ftbtree;
+	struct s_ftbt	*left;
+	struct s_ftbt	*right;
+	void			*data;
+}					t_ftbt;
+
+t_ftbt				*ft_btnew(void *data);
+void				ft_btdestroy(t_ftbt *tree, void (*del)(void *data));
 
-t_ftbtree				*ft_btnew(void *data);
-void					ft_btdestroy(t_ftbtree *tree, void (*del)(void *data));
+t_ftbt				*ft_btsorted_insert(
+						t_ftbt *tree,
+						void *data,
+						int (*cmp)(void*, void*));
 
+void				*ft_btsorted_search(
+						t_ftbt *tree,
+						void *ref,
+						int (*cmp)(void*, void*));
 #endif
diff --git a/include/libft_rbt.h b/include/libft_rbt.h
new file mode 100644
index 0000000..57653cc
--- /dev/null
+++ b/include/libft_rbt.h
@@ -0,0 +1,96 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   libft_rbt.h                                        :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: charles <charles.cabergs@gmail.com>        +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/04/26 16:09:51 by charles           #+#    #+#             */
+/*   Updated: 2020/04/26 20:25:36 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#ifndef LIBFT_RBT_H
+# define LIBFT_RBT_H
+
+/*
+** \file   libft_rbt.h
+** \brief  Red-black tree
+**
+** Rules: (from wikipedia)
+** 1. Each node is either red or black.
+** 2. The root is black. This rule is sometimes omitted. Since the root can
+**    always be changed from red to black, but not necessarily vice versa,
+**    this rule has little effect on analysis.
+** 3. All leaves (NULL) are black.
+** 4. If a node is red, then both its children are black.
+** 5. Every path from a given node to any of its descendant NULL nodes goes
+**    through the same number of black nodes.
+**
+**
+** Unbalance case:
+**
+** 1. Node and parent are both red
+**
+**   B1
+**    \     left rot         color swap
+**   > R2     -->       R2      -->       B2
+**      \              /  \              /  \
+**     > R3           B1  R3            R1  R3
+**
+** 2. Node and parent are both red and uncle node is red
+**
+**          B2                    R2
+**         / \     color swap    / \
+** uncle> R1  R3      -->       B1  B3
+**             \                     \
+**             R4                    R4
+*/
+
+# include <stdlib.h>
+
+/*
+** \brief                    Red-black tree color enum
+** \param FTRBT_COLOR_RED    color red
+** \param FTRBT_COLOR_BLACK  color black
+*/
+
+enum					e_ftrbt_color
+{
+	FTRBT_COLOR_RED = 0,
+	FTRBT_COLOR_BLACK,
+};
+
+/*
+** \brief         Red-black tree struct
+** \param left    Left node
+** \param right   Right node
+** \param data    Pointer to data
+** \param parent  Parent node
+** \param color   Color of the node
+** \note          The first 3 attricutes are the same
+**                as t_ftbt (binary tree) struct
+**                which means that we can use all functions
+**                of binary tree on red-black tree.
+*/
+
+typedef struct			s_ftrbt
+{
+	struct s_ftrbt		*left;
+	struct s_ftrbt		*right;
+	void				*data;
+	struct s_ftrbt		*parent;
+	enum e_ftrbt_color	color;
+}						t_ftrbt;
+
+t_ftrbt					*ft_rbtnew(void *data, enum e_ftrbt_color color);
+void					ft_rbtrotate_right(t_ftrbt **tree);
+void					ft_rbtrotate_left(t_ftrbt **tree);
+
+t_ftrbt					*ft_rbtinsert(
+							t_ftrbt *tree,
+							void *data,
+							int (*cmp)(void*, void*));
+
+
+#endif
diff --git a/src/bt/ft_btdestroy.c b/src/bt/ft_btdestroy.c
index c802db0..d8746ef 100644
--- a/src/bt/ft_btdestroy.c
+++ b/src/bt/ft_btdestroy.c
@@ -6,18 +6,25 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/02/07 21:30:53 by cacharle          #+#    #+#             */
-/*   Updated: 2020/02/07 21:35:19 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/04/26 19:47:45 by charles          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #include "libft_bt.h"
 
-void	ft_btdestroy(t_ftbtree *tree, void (*del)(void *data))
+/*
+** \brief       Destroy a binary tree
+** \param tree  Binary tree to destroy
+** \param del   Delete function applied to each node data
+*/
+
+void	ft_btdestroy(t_ftbt *tree, void (*del)(void *data))
 {
 	if (tree == NULL)
 		return ;
 	ft_btdestroy(tree->left, del);
 	ft_btdestroy(tree->right, del);
-	(*del)(tree->data);
+	if (del != NULL)
+		del(tree->data);
 	free(tree);
 }
diff --git a/src/bt/ft_btnew.c b/src/bt/ft_btnew.c
index 973e1a4..09cfa12 100644
--- a/src/bt/ft_btnew.c
+++ b/src/bt/ft_btnew.c
@@ -6,20 +6,26 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2020/02/07 21:33:16 by cacharle          #+#    #+#             */
-/*   Updated: 2020/02/07 21:34:35 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/04/26 19:46:57 by charles          ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
 #include "libft_bt.h"
 
-t_ftbtree	*ft_btnew(void *data)
+/*
+** \brief       Create a new binary tree
+** \param data  Node's data
+** \return      Allocated node with left and right set to NULL, NULL on error
+*/
+
+t_ftbt	*ft_btnew(void *data)
 {
-	t_ftbtree	*tree;
+	t_ftbt	*tree;
 
-	if ((tree = (t_ftbtree*)malloc(sizeof(t_ftbtree))) == NULL)
+	if ((tree = (t_ftbt*)malloc(sizeof(t_ftbt))) == NULL)
 		return (NULL);
-	tree->data = data;
 	tree->left = NULL;
 	tree->right = NULL;
+	tree->data = data;
 	return (tree);
 }
diff --git a/src/bt/ft_btsorted_insert.c b/src/bt/ft_btsorted_insert.c
new file mode 100644
index 0000000..12c0cde
--- /dev/null
+++ b/src/bt/ft_btsorted_insert.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_btsorted_insert.c                               :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: charles <charles.cabergs@gmail.com>        +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/04/26 19:10:36 by charles           #+#    #+#             */
+/*   Updated: 2020/04/26 19:19:24 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_bt.h"
+
+/*
+** \brief       Insert a data in a binary search tree so that it stays sorted
+** \param tree  Tree where data is inserted
+** \param data  Data to insert
+** \param cmp   Comparison function
+** \return      The new root or NULL if a new node couldn't be allocated
+*/
+
+t_ftbt	*ft_btsorted_insert(t_ftbt *tree, void *data, int (*cmp)(void*, void*))
+{
+	if (tree == NULL)
+		return (ft_btnew(data));
+	if (cmp(data, tree->data) < 0)
+	{
+		if (ft_btsorted_insert(tree->left, data, cmp) == NULL)
+			return (NULL);
+	}
+	else
+	{
+		if (ft_btsorted_insert(tree->right, data, cmp) == NULL)
+			return (NULL);
+	}
+	return (tree);
+}
diff --git a/src/bt/ft_btsorted_search.c b/src/bt/ft_btsorted_search.c
new file mode 100644
index 0000000..00629d0
--- /dev/null
+++ b/src/bt/ft_btsorted_search.c
@@ -0,0 +1,35 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_btsorted_search.c                               :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: charles <charles.cabergs@gmail.com>        +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/04/26 19:31:42 by charles           #+#    #+#             */
+/*   Updated: 2020/04/26 19:35:53 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_bt.h"
+
+/*
+** \brief      Search a element in a sorted binary tree
+** \param tree  Searched tree
+** \param ref   First argument of comparison function
+** \param cmp   Comparison function
+** \return      Node data if found, NULL otherwise
+*/
+
+void	*ft_btsorted_search(t_ftbt *tree, void *ref, int (*cmp)(void*, void*))
+{
+	int	res;
+
+	if (tree == NULL)
+		return (NULL);
+	if ((res = cmp(ref, tree->data)) == 0)
+		return (tree->data);
+	if (res < 0)
+		return (ft_btsorted_search(tree->left, ref, cmp));
+	else
+		return (ft_btsorted_search(tree->right, ref, cmp));
+}
diff --git a/src/rbt/ft_rbtinsert.c b/src/rbt/ft_rbtinsert.c
new file mode 100644
index 0000000..ce86777
--- /dev/null
+++ b/src/rbt/ft_rbtinsert.c
@@ -0,0 +1,83 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_rbtinsert.c                                     :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: charles <charles.cabergs@gmail.com>        +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/04/26 19:10:36 by charles           #+#    #+#             */
+/*   Updated: 2020/04/26 21:02:52 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+static void	st_insert_node(
+				t_ftrbt **root,
+				t_ftrbt *node,
+				int (*cmp)(void*, void*))
+{
+	if (*root == NULL)
+	{
+		*root = node;
+		return ;
+	}
+	if (cmp(node->data, (*root)->data) < 0)
+		st_insert_node(&(*root)->left, node->data, cmp);
+	else
+		st_insert_node(&(*root)->left, node->data, cmp);
+}
+
+static void st_repare_tree(t_ftrbt *node)
+{
+	(void)node;
+	/* t_ftrbt	*parent; */
+    /*  */
+	/* parent = node->parent; */
+	/* if (parent == NULL) */
+	/* 	node->color = FTRBT_COLOR_BLACK; */
+	/* else if (parent->color == FTRBT_COLOR_BLACK) */
+	/* 	return ; */
+	/* else if (parent->color == FTRBT_COLOR_RED && uncle(node)->color == FTRBT_COLOR_RED) */
+	/* { */
+	/* 	parent->color == FTRBT_COLOR_BLACK; */
+	/* 	uncle->color = FTRBT_COLOR_BLACK; */
+	/* 	parent->parent->color = FTRBT_COLOR_RED; */
+	/* 	st_repare_tree(parent->parent); */
+	/* } */
+	/* else if (parent->color == FTRBT_COLOR_RED && uncle(node)->color == FTRBT_COLOR_BLACK) */
+	/* { */
+	/* 	if (node == parent->right && parent == parent->parent->left) */
+	/* 	{ */
+	/* 		ft_rbtrotate_left(parent); */
+	/* 		node = node->left; */
+	/* 	} */
+	/* 	else if (node == parent->left && parent == parent->parent->right) */
+	/* 	{ */
+	/* 		ft_rbtrotate_right(parent); */
+	/* 		node = node->right; */
+	/* 	} */
+	/* 	if (node == parent->left) */
+	/* 		ft_rbtrotate_right(parent); */
+	/* 	else */
+	/* 		ft_rbtrotate_left(parent); */
+	/* 	parent->color = FTRBT_COLOR_BLACK; */
+	/* 	parent->parent->color = FTRBT_COLOR_RED; */
+	/* } */
+}
+
+t_ftrbt		*ft_rbtinsert(
+				t_ftrbt *tree,
+				void *data,
+				int (*cmp)(void*, void*))
+{
+	t_ftrbt	*node;
+
+	if ((node = ft_rbtnew(data, FTRBT_COLOR_RED)) == NULL)
+		return (NULL);
+	st_insert_node(&tree, node, cmp);
+	st_repare_tree(node);
+	while (node->parent != NULL)
+		node = node->parent;
+	return node;
+}
diff --git a/src/rbt/ft_rbtnew.c b/src/rbt/ft_rbtnew.c
new file mode 100644
index 0000000..bda7d55
--- /dev/null
+++ b/src/rbt/ft_rbtnew.c
@@ -0,0 +1,35 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_rbtnew.c                                        :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: charles <charles.cabergs@gmail.com>        +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/04/26 20:22:07 by charles           #+#    #+#             */
+/*   Updated: 2020/04/26 20:24:44 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief        Create a new red-black tree
+** \param data   Node's data
+** \param color  Node's color
+** \return       The created node with left, right and parent pointer to NULL
+**               or NULL on error
+*/
+
+t_ftrbt	*ft_rbtnew(void *data, enum e_ftrbt_color color)
+{
+	t_ftrbt	*tree;
+
+	if ((tree = (t_ftrbt*)malloc(sizeof(t_ftrbt))) == NULL)
+		return (NULL);
+	tree->left = NULL;
+	tree->right = NULL;
+	tree->data = data;
+	tree->parent = NULL;
+	tree->color = color;
+	return (tree);
+}
diff --git a/src/rbt/ft_rbtrotate_left.c b/src/rbt/ft_rbtrotate_left.c
new file mode 100644
index 0000000..7cff65d
--- /dev/null
+++ b/src/rbt/ft_rbtrotate_left.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_rbtrotate_left.c                                :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: charles <charles.cabergs@gmail.com>        +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/04/26 18:03:35 by charles           #+#    #+#             */
+/*   Updated: 2020/04/26 20:27:44 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief       Rotate a red-black tree to the left
+** \param tree  Pointer to Pointer to a red-black tree
+**
+**   5                 10
+**  / \               /  \
+** 4   10     -->    5    11
+**    /  \          / \
+**   6    11       4   6
+*/
+
+void	ft_rbtrotate_left(t_ftrbt **tree)
+{
+	t_ftrbt	*new_root;
+	t_ftrbt	*tmp;
+
+	if (tree == NULL || *tree == NULL || (*tree)->right == NULL)
+		return ;
+	new_root = (*tree)->right;
+	tmp = new_root->left;
+	new_root->left = *tree;
+	(*tree)->right = tmp;
+	*tree = new_root;
+}
diff --git a/src/rbt/ft_rbtrotate_right.c b/src/rbt/ft_rbtrotate_right.c
new file mode 100644
index 0000000..46d72e2
--- /dev/null
+++ b/src/rbt/ft_rbtrotate_right.c
@@ -0,0 +1,38 @@
+/* ************************************************************************** */
+/*                                                                            */
+/*                                                        :::      ::::::::   */
+/*   ft_rbtrotate_right.c                               :+:      :+:    :+:   */
+/*                                                    +:+ +:+         +:+     */
+/*   By: charles <charles.cabergs@gmail.com>        +#+  +:+       +#+        */
+/*                                                +#+#+#+#+#+   +#+           */
+/*   Created: 2020/04/26 18:10:57 by charles           #+#    #+#             */
+/*   Updated: 2020/04/26 20:27:53 by charles          ###   ########.fr       */
+/*                                                                            */
+/* ************************************************************************** */
+
+#include "libft_rbt.h"
+
+/*
+** \brief       Rotate a red-black tree to the right
+** \param tree  Pointer to Pointer to a red-black tree
+**
+**     10            5
+**    /  \          / \
+**   5    11  -->  4   10
+**  / \               /  \
+** 4   6             6    11
+*/
+
+void	ft_rbtrotate_right(t_ftrbt **tree)
+{
+	t_ftrbt	*new_root;
+	t_ftrbt	*tmp;
+
+	if (tree == NULL || *tree == NULL || (*tree)->left == NULL)
+		return ;
+	new_root = (*tree)->left;
+	tmp = new_root->right;
+	new_root->right = *tree;
+	(*tree)->left = tmp;
+	*tree = new_root;
+}