data_structures
union_find_new.c
Go to the documentation of this file.
1 /* ************************************************************************** */
3 /* */
4 /* ::: :::::::: */
5 /* union_find_new.c :+: :+: :+: */
6 /* +:+ +:+ +:+ */
7 /* By: unite <marvin@42.fr> +#+ +:+ +#+ */
8 /* +#+#+#+#+#+ +#+ */
9 /* Created: 2020/07/21 21:54:21 by unite #+# #+# */
10 /* Updated: 2020/09/07 22:13:12 by unite ### ########.fr */
11 /* */
12 /* ************************************************************************** */
13 
14 #include "union_find.h"
15 
16 t_union_find *union_find_new(size_t size)
17 {
18  t_union_find *uf;
19  size_t i;
20 
21  uf = ds_xmalloc(sizeof(t_union_find));
22  uf->parent = ds_xcalloc(sizeof(size_t), size);
23  uf->nchild = ds_xcalloc(sizeof(size_t), size);
24  uf->size = size;
25  uf->count = size;
26  i = 0;
27  while (i < size)
28  {
29  uf->parent[i] = i;
30  uf->nchild[i] = 1;
31  i++;
32  }
33  return (uf);
34 }
s_union_find::count
size_t count
The number of disconnected sets.
Definition: union_find.h:41
s_union_find::parent
size_t * parent
An array with each element's parent.
Definition: union_find.h:38
union_find.h
union_find_new
t_union_find * union_find_new(size_t size)
Initializes a new union-find data structure of the specified size.
Definition: union_find_new.c:16
s_union_find
Weighted quick-union by rank with path compression by halving.
Definition: union_find.h:36
ds_xcalloc
void * ds_xcalloc(size_t count, size_t size)
Replicates behaviour of calloc from libc, but fails on memory allocation errors.
Definition: ds_xcalloc.c:22
ds_xmalloc
void * ds_xmalloc(size_t size)
Replicates behaviour of malloc from libc, but fails on memory allocation errors.
Definition: ds_xmalloc.c:22
s_union_find::nchild
size_t * nchild
An array with the number of each element's children.
Definition: union_find.h:39
s_union_find::size
size_t size
The number of elements.
Definition: union_find.h:40
Generated by   doxygen 1.8.16