Graphviz  2.41.20170921.2350
BinaryHeap.c
Go to the documentation of this file.
1 /* $Id$Revision: */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 #include "BinaryHeap.h"
15 
16 BinaryHeap BinaryHeap_new(int (*cmp)(void*item1, void*item2)){
17  BinaryHeap h;
18  int max_len = 1<<8, i;
19 
20  h = MALLOC(sizeof(struct BinaryHeap_struct));
21  h->max_len = max_len;
22  h->len = 0;
23  h->heap = MALLOC(sizeof(void*)*max_len);
24  h->id_to_pos = MALLOC(sizeof(int)*max_len);
25  for (i = 0; i < max_len; i++) (h->id_to_pos)[i] = -1;
26 
27  h->pos_to_id = MALLOC(sizeof(int)*max_len);
28  h->id_stack = IntStack_new();
29  h->cmp = cmp;
30  return h;
31 }
32 
33 
34 void BinaryHeap_delete(BinaryHeap h, void (*del)(void* item)){
35  int i;
36  if (!h) return;
37  FREE(h->id_to_pos);
38  FREE(h->pos_to_id);
40  if (del) for (i = 0; i < h->len; i++) del((h->heap)[i]);
41  FREE(h->heap);
42  FREE(h);
43 }
44 
45 static BinaryHeap BinaryHeap_realloc(BinaryHeap h){
46  int max_len0 = h->max_len, max_len = h->max_len, i;
47  max_len = max_len + MAX(0.2*max_len, 10);
48  h->max_len = max_len;
49 
50  h->heap = REALLOC(h->heap, sizeof(void*)*max_len);
51  if (!(h->heap)) return NULL;
52 
53  h->id_to_pos = REALLOC(h->id_to_pos, sizeof(int)*max_len);
54  if (!(h->id_to_pos)) return NULL;
55 
56  h->pos_to_id = REALLOC(h->pos_to_id, sizeof(int)*max_len);
57  if (!(h->pos_to_id)) return NULL;
58 
59  for (i = max_len0; i < max_len; i++) (h->id_to_pos)[i] = -1;
60  return h;
61 
62 }
63 
64 #define ParentPos(pos) (pos - 1)/2
65 #define ChildrenPos1(pos) (2*(pos)+1)
66 #define ChildrenPos2(pos) (2*(pos)+2)
67 
68 static void swap(BinaryHeap h, int parentPos, int nodePos){
69  int parentID, nodeID;
70  void *tmp;
71  void **heap = h->heap;
72  int *id_to_pos = h->id_to_pos, *pos_to_id = h->pos_to_id;
73 
74  assert(parentPos < h->len);
75  assert(nodePos < h->len);
76 
77  parentID = pos_to_id[parentPos];
78  nodeID = pos_to_id[nodePos];
79 
80  tmp = heap[parentPos];
81  heap[parentPos] = heap[nodePos];
82  heap[nodePos] = tmp;
83 
84  pos_to_id[parentPos] = nodeID;
85  id_to_pos[nodeID] = parentPos;
86 
87  pos_to_id[nodePos] = parentID;
88  id_to_pos[parentID] = nodePos;
89 
90 }
91 
92 static int siftUp(BinaryHeap h, int nodePos){
93  int parentPos;
94 
95  void **heap = h->heap;
96 
97 
98  if (nodePos != 0) {
99  parentPos = ParentPos(nodePos);
100 
101  if ((h->cmp)(heap[parentPos], heap[nodePos]) == 1) {/* if smaller than parent, swap */
102  swap(h, parentPos, nodePos);
103  nodePos = siftUp(h, parentPos);
104  }
105  }
106  return nodePos;
107 }
108 
109 static int siftDown(BinaryHeap h, int nodePos){
110  int childPos, childPos1, childPos2;
111 
112  void **heap = h->heap;
113 
114 
115  childPos1 = ChildrenPos1(nodePos);
116  childPos2 = ChildrenPos2(nodePos);
117  if (childPos1 > h->len - 1) return nodePos;/* no child */
118  if (childPos1 == h->len - 1) {
119  childPos = childPos1;/* one child */
120  } else {/* two child */
121  if ((h->cmp)(heap[childPos1], heap[childPos2]) == 1){ /* pick the smaller of the two child */
122  childPos = childPos2;
123  } else {
124  childPos = childPos1;
125  }
126  }
127 
128  if ((h->cmp)(heap[nodePos], heap[childPos]) == 1) {
129  /* if larger than child, swap */
130  swap(h, nodePos, childPos);
131  nodePos = siftDown(h, childPos);
132  }
133 
134  return nodePos;
135 }
136 
138  int len = h->len, id = len, flag, pos;
139 
140  /* insert an item, and return its ID. This ID can be used later to extract the item */
141  if (len > h->max_len - 1) {
142  if (BinaryHeap_realloc(h) == NULL) return BinaryHeap_error_malloc;
143  }
144 
145  /* check if we have IDs in the stack to reuse. If no, then assign the last pos as the ID */
146  id = IntStack_pop(h->id_stack, &flag);
147  if (flag) id = len;
148 
149  h->heap[len] = item;
150  h->id_to_pos[id] = len;
151  h->pos_to_id[len] = id;
152 
153  (h->len)++;
154 
155  pos = siftUp(h, len);
156  assert(h->id_to_pos[id] == pos);
157  assert(h->pos_to_id[pos] == id);
158 
159 
160  return id;
161 }
162 
163 
165  /* return the min item */
166  return h->heap[0];
167 }
168 
170  /* return and remove the min item */
171  if (h->len == 0) return NULL;
172  return BinaryHeap_extract_item(h, (h->pos_to_id)[0]);
173 }
174 
176  /* extract an item with ID out and delete it */
177  void *item;
178  int *id_to_pos = h->id_to_pos;
179  int pos;
180 
181  if (id >= h->max_len) return NULL;
182 
183  pos = id_to_pos[id];
184 
185  if (pos < 0) return NULL;
186 
187  assert(pos < h->len);
188 
189  item = (h->heap)[pos];
190 
191  IntStack_push(h->id_stack, id);
192 
193  if (pos < h->len - 1){/* move the last item to occupy the position of extracted item */
194  swap(h, pos, h->len - 1);
195  (h->len)--;
196  pos = siftUp(h, pos);
197  pos = siftDown(h, pos);
198  } else {
199  (h->len)--;
200  }
201 
202  (h->id_to_pos)[id] = -1;
203 
204  return item;
205 
206 }
207 
208 int BinaryHeap_reset(BinaryHeap h, int id, void *item){
209  /* reset value of an item with specified id */
210  int pos;
211 
212  if (id >= h->max_len) return -1;
213  pos = h->id_to_pos[id];
214  if (pos < 0) return -1;
215 
216  h->heap[pos] = item;
217 
218  pos = siftUp(h, pos);
219 
220  pos = siftDown(h, pos);
221 
222  return pos;
223 
224 }
226  /* get an item with ID out, without deleting */
227  int pos;
228 
229  if (id >= h->max_len) return NULL;
230 
231  pos = h->id_to_pos[id];
232 
233  if (pos < 0) return NULL;
234  return (h->heap)[pos];
235 }
236 
238  int i, key_spare, parentPos, *id_to_pos = h->id_to_pos, *pos_to_id = h->pos_to_id;
239  void **heap = h->heap;
240  int *mask;
241 
242  /* check that this is a binary heap: children is smaller than parent */
243  for (i = 1; i < h->len; i++){
244  parentPos = ParentPos(i);
245  assert((h->cmp)(heap[i], heap[parentPos]) >= 0);
246  }
247 
248  mask = MALLOC(sizeof(int)*(h->len + IntStack_get_length(h->id_stack)));
249  for (i = 0; i < h->len + IntStack_get_length(h->id_stack); i++) mask[i] = -1;
250 
251  /* check that spare keys has negative id_to_pos mapping */
252  for (i = 0; i <= h->id_stack->last; i++){
253  key_spare = h->id_stack->stack[i];
254  assert(h->id_to_pos[key_spare] < 0);
255  mask[key_spare] = 1;/* mask spare ID */
256  }
257 
258  /* check that
259  pos_to_id[id_to_pos[i]] = i, for i not in the id_stack & i < length(id_stack)+len
260  id_to_pos[pos_to_id[i]] = i, 0 <= i < len
261  */
262  for (i = 1; i < h->len; i++){
263  assert(mask[pos_to_id[i]] == -1);/* that id is in use so can't be spare */
264  mask[pos_to_id[i]] = 1;
265  assert(id_to_pos[pos_to_id[i]] == i);
266  }
267 
268  /* all IDs, spare or in use, are ccounted for and give a contiguous set */
269  for (i = 0; i < h->len + IntStack_get_length(h->id_stack); i++) assert(mask[i] =- 1);
270 
271  FREE(mask);
272 }
273 void BinaryHeap_print(BinaryHeap h, void (*pnt)(void*)){
274  int i, k = 2;
275 
276  for (i = 0; i < h->len; i++){
277  pnt(h->heap[i]);
278  fprintf(stderr, "(%d) ",(h->pos_to_id)[i]);
279  if (i == k-2) {
280  fprintf(stderr, "\n");
281  k *= 2;
282  }
283  }
284  fprintf(stderr, "\nSpare keys =");
285  for (i = 0; i <= h->id_stack->last; i++){
286  fprintf(stderr,"%d(%d) ",h->id_stack->stack[i], h->id_to_pos[h->id_stack->stack[i]]);
287  }
288  fprintf(stderr, "\n");
289 }
290 
291 
void * BinaryHeap_extract_item(BinaryHeap h, int id)
Definition: BinaryHeap.c:175
#define MAX(a, b)
Definition: agerror.c:17
IntStack id_stack
Definition: BinaryHeap.h:37
int BinaryHeap_reset(BinaryHeap h, int id, void *item)
Definition: BinaryHeap.c:208
int(* cmp)(void *item1, void *item2)
Definition: BinaryHeap.h:44
Definition: utils.c:981
#define FREE
Definition: PriorityQueue.c:23
#define assert(x)
Definition: cghdr.h:47
BinaryHeap BinaryHeap_new(int(*cmp)(void *item1, void *item2))
Definition: BinaryHeap.c:16
#define ChildrenPos2(pos)
Definition: BinaryHeap.c:66
IntStack IntStack_new(void)
Definition: IntStack.c:17
#define IntStack_get_length(s)
Definition: IntStack.h:30
int BinaryHeap_insert(BinaryHeap h, void *item)
Definition: BinaryHeap.c:137
#define ChildrenPos1(pos)
Definition: BinaryHeap.c:65
void BinaryHeap_sanity_check(BinaryHeap h)
Definition: BinaryHeap.c:237
#define MALLOC
Definition: PriorityQueue.c:21
int IntStack_pop(IntStack s, int *flag)
Definition: IntStack.c:53
#define ParentPos(pos)
Definition: BinaryHeap.c:64
void * BinaryHeap_extract_min(BinaryHeap h)
Definition: BinaryHeap.c:169
#define REALLOC
Definition: PriorityQueue.c:22
#define NULL
Definition: logic.h:39
void IntStack_delete(IntStack s)
Definition: IntStack.c:28
int IntStack_push(IntStack s, int i)
Definition: IntStack.c:45
void * BinaryHeap_get_item(BinaryHeap h, int id)
Definition: BinaryHeap.c:225
struct item_s item
Definition: dijkstra.c:54
void * BinaryHeap_get_min(BinaryHeap h)
Definition: BinaryHeap.c:164
void BinaryHeap_print(BinaryHeap h, void(*pnt)(void *))
Definition: BinaryHeap.c:273
void BinaryHeap_delete(BinaryHeap h, void(*del)(void *item))
Definition: BinaryHeap.c:34