From 348e1fe22b84225da0dc3ddb9cf9351a6c687800 Mon Sep 17 00:00:00 2001 From: Alexandre P Francisco Date: Thu, 8 Jan 2015 10:59:48 +0000 Subject: [PATCH] Add some extra examples. --- extra/binheap.c | 86 +++++++++++++++++++++++++++++++++ extra/binheap.h | 111 +++++++++++++++++++++++++++++++++++++++++++ extra/binheap_test.c | 58 ++++++++++++++++++++++ extra/unfnd.c | 109 ++++++++++++++++++++++++++++++++++++++++++ extra/unfnd.h | 33 +++++++++++++ 5 files changed, 397 insertions(+) create mode 100644 extra/binheap.c create mode 100644 extra/binheap.h create mode 100644 extra/binheap_test.c create mode 100644 extra/unfnd.c create mode 100644 extra/unfnd.h diff --git a/extra/binheap.c b/extra/binheap.c new file mode 100644 index 0000000..e465243 --- /dev/null +++ b/extra/binheap.c @@ -0,0 +1,86 @@ +/*- + * Copyright (c) 2011, A P Francisco + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include +#include +#include + +#include + +#define LEFT(x) ((((x) + 1) << 1) - 1) +#define RIGHT(x) (((x) + 1) << 1) +#define PARENT(x) ((((x) + 1) >> 1) - 1) + +void +binheap_exchange(size_t *heap, size_t *map, size_t i, size_t j) +{ + size_t v; + + assert(map[heap[i]] == i && map[heap[j]] == j); + + map[heap[i]] = j; + map[heap[j]] = i; + v = heap[i]; + heap[i] = heap[j]; + heap[j] = v; + + assert(map[heap[i]] == i && map[heap[j]] == j); +} + +void +binheap_siftdown(void *key, size_t *heap, size_t *map, size_t n, size_t size, + size_t i, int(*cmp)(const void *, const void *)) +{ + size_t l = LEFT(i), r = RIGHT(i), m = i; + + if (l < n && cmp(((char *) key) + heap[l]*size, + ((char *) key) + heap[m]*size) < 0) + m = l; + if (r < n && cmp(((char *) key) + heap[r]*size, + ((char *) key) + heap[m]*size) < 0) + m = r; + if (m == i) return; + binheap_exchange(heap, map, i, m); + binheap_siftdown(key, heap, map, n, size, m, cmp); +} + +void +binheap_siftup(void *key, size_t *heap, size_t *map, size_t n, size_t size, + size_t i, int(*cmp)(const void *, const void *)) +{ + size_t p = PARENT(i); + + if (p >= ULONG_MAX || cmp(((char *) key) + heap[p]*size, + ((char *) key) + heap[i]*size) <= 0) { + return; + } + binheap_exchange(heap, map, i, p); + binheap_siftup(key, heap, map, n, size, p, cmp); +} + +void +binheap_make(void *key, size_t *heap, size_t *map, size_t n, + size_t size, int(*cmp)(const void *, const void *)) +{ + int i; + + for (i = 0; i < n; i++) + heap[i] = map[i] = i; + + for (i = PARENT(n - 1); i >= 0; i--) + binheap_siftdown(key, heap, map, n, size, i, cmp); +} + diff --git a/extra/binheap.h b/extra/binheap.h new file mode 100644 index 0000000..c3072ce --- /dev/null +++ b/extra/binheap.h @@ -0,0 +1,111 @@ +/*- + * Copyright (c) 2011, A P Francisco + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef _BINHEAP_H_ +#define _BINHEAP_H_ + +#include +#include +#include + +struct binheap { + size_t size; + size_t max_size; + size_t *heap; + size_t *map; + void *key; + size_t ksz; + int (*cmp)(const void *,const void *); +}; + +#define LEFT(x) ((((x) + 1) << 1) - 1) +#define RIGHT(x) (((x) + 1) << 1) +#define PARENT(x) ((((x) + 1) >> 1) - 1) + +#define BINHEAP_INIT(q, type, k, n, c) do { \ + (q) = malloc(sizeof(struct binheap)); \ + (q)->max_size = (n); \ + (q)->size = 0; \ + (q)->heap = malloc(sizeof(size_t)*(n)); \ + memset((q)->heap, 0xFF, sizeof(size_t)*(n)); \ + (q)->map = malloc(sizeof(size_t)*(n)); \ + memset((q)->map, 0xFF, sizeof(size_t)*(n)); \ + (q)->key = (k); \ + (q)->ksz = sizeof(type); \ + (q)->cmp = (c); \ +} while (/*CONSTCOND*/0) + +#define BINHEAP_FREE(q) do { \ + free((q)->heap); \ + free((q)->map); \ + free(q); \ +} while (/*CONSTCOND*/0) + +#define BINHEAP_EMPTY(q) ((q)->size == 0) +#define BINHEAP_HAS(q, id) ((q)->map[id] < (q)->size) +#define BINHEAP_TOP(q) ((q)->heap[0]) + +#define BINHEAP_RESET(q) do { \ + (q)->size = 0; \ + memset((q)->heap, 0xFF, sizeof(size_t)*(q)->max_size); \ + memset((q)->map, 0xFF, sizeof(size_t)*(q)->max_size); \ +} while (/*CONSTCOND*/0) + +#define BINHEAP_PUSH(q, id) do { \ + if ((q)->map[id] >= ULONG_MAX) { \ + if ((q)->size >= (q)->max_size) \ + abort(); \ + \ + (q)->map[id] = (q)->size; \ + (q)->heap[(q)->size] = (id); \ + (q)->size ++; \ + } \ + binheap_siftup((q)->key, (q)->heap, (q)->map, (q)->size, \ + (q)->ksz, (q)->map[id], (q)->cmp); \ + binheap_siftdown((q)->key, (q)->heap, (q)->map, (q)->size, \ + (q)->ksz, (q)->map[id], (q)->cmp); \ +} while (/*CONSTCOND*/0) + +#define BINHEAP_UPDATE(q, id) BINHEAP_PUSH(q, id) + +#define BINHEAP_POP(q) do { \ + register size_t aux = q->heap[0]; \ + q->size--; \ + binheap_exchange((q)->heap, (q)->map, (q)->size, 0); \ + binheap_siftdown((q)->key, (q)->heap, (q)->map, (q)->size, \ + (q)->ksz, 0, (q)->cmp); \ + q->heap[q->size] = ULONG_MAX; \ + q->map[aux] = ULONG_MAX; \ +} while (/*CONSTCOND*/0) + +#define BINHEAP_MAKE(q, n) do { \ + (q)->size = (n); \ + binheap_make((q)->key, (q)->heap, (q)->map, \ + (q)->size, (q)->ksz, (q)->cmp); \ +} while (/*CONSTCOND*/0) + +void binheap_exchange(size_t *heap, size_t *map, size_t i, size_t j); + +void binheap_make(void *key, size_t *heap, size_t *map, size_t n, + size_t size, int(*cmp)(const void *, const void *)); + +void binheap_siftdown(void *key, size_t *heap, size_t *map, size_t n, + size_t size, size_t i, int(*cmp)(const void *, const void *)); + +void binheap_siftup(void *key, size_t *heap, size_t *map, size_t n, + size_t size, size_t i, int(*cmp)(const void *, const void *)); + +#endif /* _BINHEAP_H_ */ diff --git a/extra/binheap_test.c b/extra/binheap_test.c new file mode 100644 index 0000000..7936b04 --- /dev/null +++ b/extra/binheap_test.c @@ -0,0 +1,58 @@ +#include +#include + +#include "binheap.h" + +int +doublecmp(const void *ap, const void *bp) +{ + double a = * (double *) ap; + double b = * (double *) bp; + + if (a < b) + return -1; + if (a > b) + return 1; + + return 0; +} + +int +main(int argc, char *argv[]) +{ + struct binheap *q; + int i = 0; + + double a[7] = {2,1,3,4,6,5,7}; + + BINHEAP_INIT(q, double, a, 7, doublecmp); + BINHEAP_MAKE(q, 7); + + if (BINHEAP_EMPTY(q)) + printf("Empty!\n"); + + a[4] = -0.5; + BINHEAP_UPDATE(q, 4); + + a[1] = 100; + BINHEAP_UPDATE(q, 1); + + printf("%d %f\n", BINHEAP_TOP(q), a[BINHEAP_TOP(q)]); + BINHEAP_POP(q); + + printf("%d %f\n", BINHEAP_TOP(q), a[BINHEAP_TOP(q)]); + BINHEAP_POP(q); + + a[4] = 10; + BINHEAP_PUSH(q, 4); + + printf("--\n"); + while (! BINHEAP_EMPTY(q)) { + printf("%d %f\n", BINHEAP_TOP(q), a[BINHEAP_TOP(q)]); + BINHEAP_POP(q); + } + + BINHEAP_FREE(q); + + return EXIT_SUCCESS; +} diff --git a/extra/unfnd.c b/extra/unfnd.c new file mode 100644 index 0000000..110128f --- /dev/null +++ b/extra/unfnd.c @@ -0,0 +1,109 @@ +/*- + * Copyright (c) 2008, A P Francisco + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* + * This is an implementation of the well known disjoint-set data structure + * and associated union-find operations. + */ + +#include +#include +#include + +#include "unfnd.h" + +struct _disjoint_set { + int sz; + struct { int pi, rank; } my[1]; +}; + +/* + * Initialize the data structure with capacity to 'sz' elements. + */ +disjoint_set +make_set(int sz) +{ + disjoint_set set; + int i; + + if (sz == 0) + return NULL; + set = malloc(sizeof(int) + 2 * sizeof(int) * sz); + if (set == NULL) + return NULL; + set->sz = sz; + for (i = 0; i < sz; i++) { + set->my[i].pi = i; + set->my[i].rank = 0; + } + return set; +} + +/* + * Finds the root of the set to which 'i' belongs applying path compression + * by halving. + */ +int +find_set(disjoint_set set, int i) +{ + if (set == NULL || i < 0 || i >= set->sz) + return UINT_MAX; + for (; i != set->my[i].pi; i = set->my[i].pi) + set->my[i].pi = set->my[set->my[i].pi].pi; + return i; +} + +/* + * Link the sets to which 'i' and 'j' belong with union by rank. + */ +int +same_set(disjoint_set set, int i, int j) +{ + int i_root, j_root; + + if (set == NULL || i < 0 || j < 0 || i >= set->sz || j >= set->sz) + return 0; + i_root = find_set(set, i); + j_root = find_set(set, j); + if (i_root == j_root) + return 1; + return 0; +} + +/* + * Link the sets to which 'i' and 'j' belong with union by rank. + */ +void +union_set(disjoint_set set, int i, int j) +{ + int i_root, j_root; + + if (set == NULL || i < 0 || j < 0 || i >= set->sz || j >= set->sz) + return; + i_root = find_set(set, i); + j_root = find_set(set, j); + if (i_root == j_root) + return; + if (set->my[i_root].rank > set->my[j_root].rank) + set->my[j_root].pi = i_root; + else if (set->my[i_root].rank < set->my[j_root].rank) + set->my[i_root].pi = j_root; + else { /* set->my[i_root].rank == set->my[j_root].rank */ + set->my[i_root].pi = j_root; + set->my[j_root].rank ++; + } +} + diff --git a/extra/unfnd.h b/extra/unfnd.h new file mode 100644 index 0000000..de1c9f1 --- /dev/null +++ b/extra/unfnd.h @@ -0,0 +1,33 @@ +/*- + * Copyright (c) 2008, A P Francisco + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* + * This is an implementation of the well known disjoint-set data structure + * and associated union-find operations. + */ + +#ifndef UNFND_H +#define UNFND_H + +typedef struct _disjoint_set *disjoint_set; + +disjoint_set make_set(int); +void union_set(disjoint_set, int, int); +int same_set(disjoint_set, int, int); +int find_set(disjoint_set, int); + +#endif /* UNFND_H */ + -- 2.30.2