[3365] | 1 | /**************************************************************************
|
---|
| 2 | *
|
---|
| 3 | * mgheap.c -- Heap routines
|
---|
| 4 | * Copyright (C) 1994 Neil Sharman
|
---|
| 5 | *
|
---|
| 6 | * This program is free software; you can redistribute it and/or modify
|
---|
| 7 | * it under the terms of the GNU General Public License as published by
|
---|
| 8 | * the Free Software Foundation; either version 2 of the License, or
|
---|
| 9 | * (at your option) any later version.
|
---|
| 10 | *
|
---|
| 11 | * This program is distributed in the hope that it will be useful,
|
---|
| 12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 14 | * GNU General Public License for more details.
|
---|
| 15 | *
|
---|
| 16 | * You should have received a copy of the GNU General Public License
|
---|
| 17 | * along with this program; if not, write to the Free Software
|
---|
| 18 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
---|
| 19 | *
|
---|
| 20 | **************************************************************************/
|
---|
| 21 |
|
---|
| 22 | #include "mgheap.h"
|
---|
| 23 |
|
---|
| 24 | #define SWAP(s, a, b) \
|
---|
| 25 | do { \
|
---|
| 26 | register int __i; \
|
---|
| 27 | register char *__a = (a), *__b = (b); \
|
---|
[9612] | 28 | for (__i = (s); __i; --__i) \
|
---|
[3365] | 29 | { \
|
---|
| 30 | register char __t = *__a; \
|
---|
| 31 | *__a++ = *__b; *__b++ = __t; \
|
---|
| 32 | } \
|
---|
| 33 | } while(0)
|
---|
| 34 |
|
---|
| 35 |
|
---|
| 36 |
|
---|
| 37 | #define COPY(s, dst, src) \
|
---|
| 38 | do { \
|
---|
| 39 | register int __i; \
|
---|
| 40 | register char *__dst = (dst), *__src = (src); \
|
---|
[9612] | 41 | for (__i = (s); __i; --__i) \
|
---|
[3365] | 42 | *__dst++ = *__src++; \
|
---|
| 43 | } while(0)
|
---|
| 44 |
|
---|
| 45 |
|
---|
| 46 |
|
---|
| 47 | static void
|
---|
| 48 | heap_heapify (void *heap, int size, int num, int curr, heap_comp hc)
|
---|
| 49 | {
|
---|
| 50 | register int child = curr * 2;
|
---|
| 51 | while (child <= num)
|
---|
| 52 | {
|
---|
| 53 | if (child < num && hc ((char *) heap + child * size,
|
---|
| 54 | (char *) heap + child * size - size) < 0)
|
---|
[9612] | 55 | ++child;
|
---|
[3365] | 56 | if (hc ((char *) heap + (curr - 1) * size, (char *) heap + (child - 1) * size) > 0)
|
---|
| 57 | {
|
---|
| 58 | SWAP (size, (char *) heap + (curr - 1) * size,
|
---|
| 59 | (char *) heap + (child - 1) * size);
|
---|
| 60 | curr = child;
|
---|
| 61 | child = child * 2;
|
---|
| 62 | }
|
---|
| 63 | else
|
---|
| 64 | break;
|
---|
| 65 | }
|
---|
| 66 | }
|
---|
| 67 |
|
---|
| 68 | static void
|
---|
| 69 | heap_pullup (void *heap, int size, int num, heap_comp hc)
|
---|
| 70 | {
|
---|
| 71 | register int curr = num;
|
---|
| 72 | register int parent = curr >> 1;
|
---|
| 73 | while (parent &&
|
---|
| 74 | hc ((char *) heap + (curr - 1) * size, (char *) heap + (parent - 1) * size) < 0)
|
---|
| 75 | {
|
---|
| 76 | SWAP (size, (char *) heap + (curr - 1) * size,
|
---|
| 77 | (char *) heap + (parent - 1) * size);
|
---|
| 78 | curr = parent;
|
---|
| 79 | parent = curr >> 1;
|
---|
| 80 | }
|
---|
| 81 | }
|
---|
| 82 |
|
---|
| 83 | /************************************************************************
|
---|
| 84 | *
|
---|
| 85 | * NOTE: If you choose to change the comparison function the first thing
|
---|
| 86 | * you do after changing the function is call heap_build.
|
---|
| 87 | *
|
---|
| 88 | */
|
---|
| 89 | void
|
---|
| 90 | heap_build (void *heap, int size, int num, heap_comp hc)
|
---|
| 91 | {
|
---|
| 92 | register int i;
|
---|
[9612] | 93 | for (i = num / 2; i > 0; --i)
|
---|
[3365] | 94 | heap_heapify (heap, size, num, i, hc);
|
---|
| 95 | }
|
---|
| 96 |
|
---|
| 97 |
|
---|
| 98 |
|
---|
| 99 | /****************************************************
|
---|
| 100 | *
|
---|
| 101 | * NOTE : The heap must be built before heap_sort is called.
|
---|
| 102 | * This has the effect of reversing the order of the array.
|
---|
| 103 | * e.g. if your comparison function is designed to pull the
|
---|
| 104 | * biggest thing off the heap first then the result of
|
---|
| 105 | * sorting with this function will be to put the bigest
|
---|
| 106 | * thing at the end of the array.
|
---|
| 107 | *
|
---|
| 108 | */
|
---|
| 109 | void
|
---|
| 110 | heap_sort (void *heap, int size, int num, heap_comp hc)
|
---|
| 111 | {
|
---|
| 112 | register int i;
|
---|
[9612] | 113 | for (i = num; i > 1; --i)
|
---|
[3365] | 114 | {
|
---|
| 115 | SWAP (size, (char *) heap, (char *) heap + (i - 1) * size);
|
---|
| 116 | heap_heapify (heap, size, i - 1, 1, hc);
|
---|
| 117 | }
|
---|
| 118 | }
|
---|
| 119 |
|
---|
| 120 |
|
---|
| 121 | void
|
---|
| 122 | heap_deletehead (void *heap, int size, int *num, heap_comp hc)
|
---|
| 123 | {
|
---|
[9612] | 124 | --(*num);
|
---|
[3365] | 125 | SWAP (size, (char *) heap, (char *) heap + *num * size);
|
---|
| 126 | heap_heapify (heap, size, *num, 1, hc);
|
---|
| 127 | }
|
---|
| 128 |
|
---|
| 129 |
|
---|
| 130 | void
|
---|
| 131 | heap_changedhead (void *heap, int size, int num, heap_comp hc)
|
---|
| 132 | {
|
---|
| 133 | heap_heapify (heap, size, num, 1, hc);
|
---|
| 134 | }
|
---|
| 135 |
|
---|
| 136 |
|
---|
| 137 | /***********************************************************************
|
---|
| 138 | *
|
---|
| 139 | * This assumes that the item has been added to the end of the
|
---|
| 140 | * array that is the heap. But that num has not been changed.
|
---|
| 141 | *
|
---|
| 142 | */
|
---|
| 143 | void
|
---|
| 144 | heap_additem (void *heap, int size, int *num, heap_comp hc)
|
---|
| 145 | {
|
---|
[9612] | 146 | ++(*num);
|
---|
[3365] | 147 | heap_pullup (heap, size, *num, hc);
|
---|
| 148 | }
|
---|