From bc4e33ab3f7ca960100a0141b1beca83de08059a Mon Sep 17 00:00:00 2001 From: Lukas Jiriste Date: Sat, 23 Dec 2023 12:47:27 +0100 Subject: [PATCH] Implement matrix t_mat as a wrapper around t_vec Implement new struct for matrix and some basic utilities. Everything passes strict compilation and norminette, but may contain bugs in logic. Testing recommended (though it will probably happen when this is needed). Extract ft_vec_forget from ft_vec_erase which functions as ft_vec_erase with free_el = NULL. --- Makefile | 13 +++- ft_arr/ft_mat_append.c | 23 +++++++ ft_arr/ft_mat_free.c | 21 +++++++ ft_arr/ft_mat_init.c | 20 +++++++ ft_arr/ft_mat_insert_col.c | 120 +++++++++++++++++++++++++++++++++++++ ft_arr/ft_mat_insert_row.c | 27 +++++++++ ft_arr/ft_vec_enlarge.c | 36 +++++++++++ ft_arr/ft_vec_erase.c | 20 +++---- ft_arr/ft_vec_forget.c | 30 ++++++++++ ft_arr/ft_vec_insert.c | 28 +-------- inc/ft_arr.h | 44 ++++++++++++-- 11 files changed, 338 insertions(+), 44 deletions(-) create mode 100644 ft_arr/ft_mat_append.c create mode 100644 ft_arr/ft_mat_free.c create mode 100644 ft_arr/ft_mat_init.c create mode 100644 ft_arr/ft_mat_insert_col.c create mode 100644 ft_arr/ft_mat_insert_row.c create mode 100644 ft_arr/ft_vec_enlarge.c create mode 100644 ft_arr/ft_vec_forget.c diff --git a/Makefile b/Makefile index 6f68e1d..a4a3806 100644 --- a/Makefile +++ b/Makefile @@ -1,5 +1,5 @@ CC := cc -CFLAGS := -Wall -Wextra -Werror -Wpedantic -std=c99 +CFLAGS := -std=c99 -Wall -Wextra -Werror -Wpedantic AR := ar RM := rm -f @@ -87,11 +87,19 @@ SRClst := ft_lst_reverse.c \ SRCarr := ft_vec_init.c \ ft_vec_reserve.c \ + ft_vec_enlarge.c \ ft_vec_insert.c \ ft_vec_append.c \ + ft_vec_forget.c \ ft_vec_erase.c \ ft_vec_access.c \ ft_vec_free.c \ + \ + ft_mat_init.c \ + ft_mat_append.c \ + ft_mat_insert_col.c \ + ft_mat_insert_row.c \ + ft_mat_free.c \ SOURCES := $(foreach dir, $(SRCDIR), $(addprefix $(dir)/, $($(dir:ft_%=SRC%)))) OBJECTS := $(SOURCES:.c=.o) @@ -100,6 +108,9 @@ NAME = libft.a all : $(NAME) +debug : CFLAGS += -g +debug : $(NAME) + $(NAME) : $(OBJECTS) $(AR) rcs $@ $^ diff --git a/ft_arr/ft_mat_append.c b/ft_arr/ft_mat_append.c new file mode 100644 index 0000000..50031f8 --- /dev/null +++ b/ft_arr/ft_mat_append.c @@ -0,0 +1,23 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_mat_append.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2023/12/12 10:25:34 by ljiriste #+# #+# */ +/* Updated: 2023/12/12 10:28:46 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "ft_arr.h" + +t_arr_stat ft_mat_append_row(t_mat *mat, const t_vec *vec) +{ + return (ft_mat_insert_row(mat, vec, mat->rows)); +} + +t_arr_stat ft_mat_append_col(t_mat *mat, const t_vec *vec) +{ + return (ft_mat_insert_col(mat, vec, mat->cols)); +} diff --git a/ft_arr/ft_mat_free.c b/ft_arr/ft_mat_free.c new file mode 100644 index 0000000..b166885 --- /dev/null +++ b/ft_arr/ft_mat_free.c @@ -0,0 +1,21 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_mat_free.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2023/12/11 19:06:07 by ljiriste #+# #+# */ +/* Updated: 2023/12/11 19:08:21 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "ft_arr.h" + +void ft_mat_free(t_mat *mat, void (*free_el)(void *)) +{ + ft_vec_free(&(mat->vec), free_el); + mat->cols = 0; + mat->rows = 0; + return ; +} diff --git a/ft_arr/ft_mat_init.c b/ft_arr/ft_mat_init.c new file mode 100644 index 0000000..bf70cb8 --- /dev/null +++ b/ft_arr/ft_mat_init.c @@ -0,0 +1,20 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_mat_init.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2023/12/11 19:03:27 by ljiriste #+# #+# */ +/* Updated: 2023/12/11 19:05:45 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "ft_arr.h" + +t_arr_stat ft_mat_init(t_mat *mat, size_t el_size) +{ + mat->rows = 0; + mat->cols = 0; + return (ft_vec_init(&(mat->vec), el_size)); +} diff --git a/ft_arr/ft_mat_insert_col.c b/ft_arr/ft_mat_insert_col.c new file mode 100644 index 0000000..6c043fb --- /dev/null +++ b/ft_arr/ft_mat_insert_col.c @@ -0,0 +1,120 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_mat_insert_col.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2023/12/12 08:57:22 by ljiriste #+# #+# */ +/* Updated: 2024/01/12 17:24:31 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "ft_arr.h" +#include "ft_mem.h" + +/* Failure is too complicated to deal with in this approach +void revert_partial_col_insert(t_mat *mat, size_t col, size_t failed_row) +{ + while (failed_row > 0) + { + ft_vec_forget(&(mat->vec), (failed_row - 1) * mat->cols + col); + --failed_row; + } + return ; +} + +// Number of bytes moved is O(n^2) but it is doable in O(n) (not that hard) +ft_mat_insert_col(t_mat *mat, const t_vec *vec, size_t index) +{ + size_t i; + t_arr_stat res; + + if (!mat || !input_row || mat->rows != vec->size) + return (invalid_input); + ++mat->cols; + i = 0; + while (i < mat->rows) + { + res = ft_vec_insert(&(mat->vec), (char *)vec->vec + i * vec->el_size, + i * mat->cols + index) + if (res) + { + revert_partial_col_insert(mat, index, i); + --mat->cols; + return (res); + } + ++i; + } + return (success); +} +*/ + +// Creates space for the inserted column inside the mat->vec +void reorganize(t_mat *mat, size_t move_index, size_t change) +{ + size_t i; + + i = mat->rows - 1; + if (move_index < mat->cols) + { + ft_memmove((char *)mat->vec.vec + + ((mat->rows - 1) * mat->cols + move_index) * mat->vec.el_size, + (char *)mat->vec.vec + ((mat->rows - 1) + * (mat->cols + change) + move_index) * mat->vec.el_size, + (mat->cols - move_index) * mat->vec.el_size); + } + --i; + while (i + 1 > 0) + { + ft_memmove((char *)mat->vec.vec + + (i * mat->cols + move_index) * mat->vec.el_size, + (char *)mat->vec.vec + + (i * (mat->cols + change) + move_index) * mat->vec.el_size, + mat->cols * mat->vec.el_size); + --i; + } + mat->cols += change; + return ; +} + +static void copy(t_mat *mat, const t_vec *vec, size_t index) +{ + size_t i; + + i = 0; + while (i < mat->rows) + { + ft_memmove((char *)vec->vec + i * vec->el_size, + (char *)mat->vec.vec + (i * mat->cols + index) + * mat->vec.el_size, vec->el_size); + ++i; + } + return ; +} + +t_arr_stat ft_mat_insert_col(t_mat *mat, const t_vec *vec, size_t index) +{ + size_t cols_change; + size_t move_index; + t_arr_stat res; + + cols_change = 1; + move_index = index; + if (index > mat->cols) + { + cols_change = index - mat->cols + 1; + move_index = mat->cols; + } + while ((mat->cols + cols_change) * mat->rows < mat->vec.capacity) + { + res = ft_vec_enlarge(&(mat->vec)); + if (res != success) + return (res); + } + reorganize(mat, move_index, cols_change); + if (res != success) + return (res); + copy(mat, vec, index); + return (res); +} diff --git a/ft_arr/ft_mat_insert_row.c b/ft_arr/ft_mat_insert_row.c new file mode 100644 index 0000000..31fcfe0 --- /dev/null +++ b/ft_arr/ft_mat_insert_row.c @@ -0,0 +1,27 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_mat_insert_row.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2023/12/11 19:20:00 by ljiriste #+# #+# */ +/* Updated: 2024/01/12 17:08:04 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "ft_arr.h" + +t_arr_stat ft_mat_insert_row(t_mat *mat, const t_vec *vec, size_t index) +{ + size_t res; + + if (!mat || !vec || mat->cols != vec->size) + return (invalid_input); + res = ft_vec_insert_range(&(mat->vec), vec->vec, + mat->cols, index * mat->cols); + if (res != success) + return (res); + ++mat->rows; + return (success); +} diff --git a/ft_arr/ft_vec_enlarge.c b/ft_arr/ft_vec_enlarge.c new file mode 100644 index 0000000..7778eaf --- /dev/null +++ b/ft_arr/ft_vec_enlarge.c @@ -0,0 +1,36 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_vec_enlarge.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/01/12 17:03:50 by ljiriste #+# #+# */ +/* Updated: 2024/01/12 17:06:04 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "ft_arr.h" +#include + +t_arr_stat ft_vec_enlarge(t_vec *vec) +{ + if (vec->capacity == SIZE_MAX) + return (alloc_fail); + if (vec->capacity > SIZE_MAX / 2) + { + if (ft_vec_reserve(vec, SIZE_MAX)) + return (alloc_fail); + } + else if (vec->capacity == 0) + { + if (ft_vec_reserve(vec, V_DEFAULT_CAPACITY)) + return (alloc_fail); + } + else + { + if (ft_vec_reserve(vec, vec->capacity * 2)) + return (alloc_fail); + } + return (success); +} diff --git a/ft_arr/ft_vec_erase.c b/ft_arr/ft_vec_erase.c index 5912fe9..c81b95b 100644 --- a/ft_arr/ft_vec_erase.c +++ b/ft_arr/ft_vec_erase.c @@ -6,12 +6,11 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2023/12/09 17:10:39 by ljiriste #+# #+# */ -/* Updated: 2023/12/11 19:59:50 by ljiriste ### ########.fr */ +/* Updated: 2024/01/11 10:53:17 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ #include "ft_arr.h" -#include "libft.h" t_arr_stat ft_vec_erase(t_vec *vec, size_t index, void (*free_el)(void *)) { @@ -21,23 +20,18 @@ t_arr_stat ft_vec_erase(t_vec *vec, size_t index, void (*free_el)(void *)) t_arr_stat ft_vec_erase_range(t_vec *vec, size_t count, size_t index, void (*free_el)(void *)) { - void *p; + char *p; - if (!vec || index + count > vec->size || index > SIZE_MAX - count) - return (invalid_input); - vec->size -= count; - ft_memmove((char *)vec->vec + index, - (char *)vec->vec + vec->el_size * (index + count), - vec->el_size * (vec->size - index)); if (free_el) { - p = (char *)vec->vec + vec->size * vec->el_size; - while ((char *)p < (char *)vec->vec - + (vec->size + count) * vec->el_size) + p = (char *)vec->vec + index * vec->el_size; + while (p < (char *)vec->vec + + (index + count) * vec->el_size) { free_el(p); - p = (char *)p + vec->el_size; + p += vec->el_size; } } + ft_vec_forget_range(vec, count, index); return (success); } diff --git a/ft_arr/ft_vec_forget.c b/ft_arr/ft_vec_forget.c new file mode 100644 index 0000000..284d6b5 --- /dev/null +++ b/ft_arr/ft_vec_forget.c @@ -0,0 +1,30 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* ft_vec_forget.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2023/12/12 10:11:45 by ljiriste #+# #+# */ +/* Updated: 2023/12/23 12:46:49 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "ft_arr.h" +#include "libft.h" + +t_arr_stat ft_vec_forget(t_vec *vec, size_t index) +{ + return (ft_vec_forget_range(vec, 1, index)); +} + +t_arr_stat ft_vec_forget_range(t_vec *vec, size_t count, size_t index) +{ + if (!vec || index + count > vec->size || index > SIZE_MAX - count) + return (invalid_input); + vec->size -= count; + ft_memmove((char *)vec->vec + index, + (char *)vec->vec + vec->el_size * (index + count), + vec->el_size * (vec->size - index)); + return (success); +} diff --git a/ft_arr/ft_vec_insert.c b/ft_arr/ft_vec_insert.c index a550111..9458136 100644 --- a/ft_arr/ft_vec_insert.c +++ b/ft_arr/ft_vec_insert.c @@ -6,35 +6,13 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2023/12/09 16:50:57 by ljiriste #+# #+# */ -/* Updated: 2023/12/11 19:53:35 by ljiriste ### ########.fr */ +/* Updated: 2024/01/12 17:03:45 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ #include "ft_arr.h" #include "libft.h" -static t_arr_stat ft_vec_enlarge(t_vec *vec) -{ - if (vec->capacity == SIZE_MAX) - return (alloc_fail); - if (vec->capacity > SIZE_MAX / 2) - { - if (ft_vec_reserve(vec, SIZE_MAX)) - return (alloc_fail); - } - else if (vec->capacity == 0) - { - if (ft_vec_reserve(vec, V_DEFAULT_CAPACITY)) - return (alloc_fail); - } - else - { - if (ft_vec_reserve(vec, vec->capacity * 2)) - return (alloc_fail); - } - return (success); -} - t_arr_stat ft_vec_insert(t_vec *vec, void const *element, size_t index) { return (ft_vec_insert_range(vec, element, 1, index)); @@ -56,10 +34,10 @@ t_arr_stat ft_vec_insert_range(t_vec *vec, void const *element, ft_memmove((char *)vec->vec + vec->el_size * (index + count), (char *)vec->vec + vec->el_size * index, vec->el_size * (vec->size - index)); - ft_memcpy((char *)vec->vec + vec->el_size * index, element, + ft_memmove((char *)vec->vec + vec->el_size * index, element, vec->el_size * count); if (index > vec->size) vec->size = index; - ++vec->size; + vec->size += count; return (success); } diff --git a/inc/ft_arr.h b/inc/ft_arr.h index f2bc093..623ceba 100644 --- a/inc/ft_arr.h +++ b/inc/ft_arr.h @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2023/12/09 13:58:15 by ljiriste #+# #+# */ -/* Updated: 2023/12/11 20:04:34 by ljiriste ### ########.fr */ +/* Updated: 2024/01/12 19:13:06 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -25,9 +25,10 @@ typedef enum e_arr_stat alloc_fail, invalid_size, invalid_input, + non_specific_failure, } t_arr_stat; -// It should be possible to remove el_size with the use of macros +// It should be possible to remove el_size with the use of macros? typedef struct s_vec { size_t capacity; @@ -36,17 +37,50 @@ typedef struct s_vec void *vec; } t_vec; -t_arr_stat ft_vec_init(t_vec *vec, size_t el_size); -void ft_vec_free(t_vec *vec, void (*free_el)(void *)); +typedef struct s_mat +{ + size_t rows; + size_t cols; + t_vec vec; +} t_mat; + t_arr_stat ft_vec_reserve(t_vec *vec, size_t capacity); +t_arr_stat ft_vec_enlarge(t_vec *vec); t_arr_stat ft_vec_insert(t_vec *vec, const void *element, size_t index); t_arr_stat ft_vec_append(t_vec *vec, const void *element); +t_arr_stat ft_vec_forget(t_vec *vec, size_t index); +t_arr_stat ft_vec_erase(t_vec *vec, size_t index, void (*free_el)(void *)); + t_arr_stat ft_vec_insert_range(t_vec *vec, const void *element, size_t count, size_t index); t_arr_stat ft_vec_append_range(t_vec *vec, const void *element, size_t count); -t_arr_stat ft_vec_erase(t_vec *vec, size_t index, void (*free_el)(void *)); +t_arr_stat ft_vec_forget_range(t_vec *vec, size_t index, size_t count); t_arr_stat ft_vec_erase_range(t_vec *vec, size_t count, size_t index, void (*free_el)(void *)); + +t_arr_stat ft_vec_init(t_vec *vec, size_t el_size); +void ft_vec_free(t_vec *vec, void (*free_el)(void *)); void *ft_vec_access(t_vec *vec, size_t index); +/* It is probably better to use (type *)vec->vec + index for pointer + * or ((type *)vec->vec)[index] for value + * insted of (type *)ft_vec_access(vec, index) + * because it is smaller, more readable. But it does not range-check! + * Also implement access function that casts to desired type + * eg. int *int_access(t_vec *vec, size_t ind){return ((int *)vec->vec + ind);} + */ + +t_arr_stat ft_mat_init(t_mat *mat, size_t el_size); +void ft_mat_free(t_mat *mat, void (*free_el)(void *)); +t_arr_stat ft_mat_resize(t_mat *mat, size_t rows, size_t cols); +t_arr_stat ft_mat_insert_row(t_mat *mat, const t_vec *vec, size_t index); +t_arr_stat ft_mat_insert_col(t_mat *mat, const t_vec *vec, size_t index); +t_arr_stat ft_mat_append_row(t_mat *mat, const t_vec *vec); +t_arr_stat ft_mat_append_col(t_mat *mat, const t_vec *vec); +t_arr_stat ft_mat_erase_rows(t_mat *mat, size_t count, + size_t index, void (*free_el)(void *)); +t_arr_stat ft_mat_erase_cols(t_mat *mat, size_t count, + size_t index, void (*free_el)(void *)); +void *ft_mat_access(t_mat *mat, size_t row, size_t col); + #endif -- 2.30.2