Graphviz  2.41.20170921.2350
BinaryHeap.h
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 #ifndef BinaryHeap_H
15 #define BinaryHeap_H
16 
17 #include "general.h"
18 #include "IntStack.h"
19 
20 /* binary heap code.
21  Caution: items inserted should be kept untouched, e.g., the value of the item should be kepted unchanged while the heap is still in use!
22  To change the valud of am item, use BinaryHeap_reset
23 */
24 
26  int max_len;/* storage allocated for the heap */
27  int len;/*number of elements in the heap so far. <= maxlen */
28  void **heap;
29  int *id_to_pos;/* this array store the position of an item with ID. For ID that was not in use,
30  i.e., no in pos_to_id[1:len],
31  id_to_pos[id] = -1
32  */
33  int *pos_to_id;/* this array stores the ID of item at position pos.
34  pos_to_id[id_to_pos[i]] = i, for i not in the id_stack & i < length(id_stack)+len
35  id_to_pos[pos_to_id[i]] = i, 0 <= i < len
36  */
37  IntStack id_stack;/* a stack that store IDs that is no longer used, to
38  be assigned to newly inserted elements.
39  For sanity check, the union of items in
40  the id_stack, and that is pos_to_id[1:len],
41  should form a set of contiguous numbers
42  {1, 2, ..., len, ...}
43  */
44  int (*cmp)(void*item1, void*item2);/* comparison function. Return 1,0,-1
45  if item1 >, =, < item2 */
46 };
47 
49 
50 typedef struct BinaryHeap_struct* BinaryHeap;
51 
52 BinaryHeap BinaryHeap_new(int (*cmp)(void*item1, void*item2));
53 
54 
55 void BinaryHeap_delete(BinaryHeap h, void (*del)(void* item));/* delete not just the heap data structure, but also the data items
56  through a user supplied del function. */
57 
58 int BinaryHeap_insert(BinaryHeap h, void *item);/* insert an item, and return its ID.
59  This ID can be used later to extract the item. ID
60  are always nonnegative. If the return value is
61  negative, it is an error message */
62 
63 void* BinaryHeap_get_min(BinaryHeap h);/* return the min item */
64 
65 void* BinaryHeap_extract_min(BinaryHeap h);/* return and remove the min item */
66 
67 void* BinaryHeap_extract_item(BinaryHeap h, int id);/* extract an item with ID out and delete it */
68 
69 void* BinaryHeap_get_item(BinaryHeap h, int id);/* get an item with ID out, without deleting */
70 
71 int BinaryHeap_reset(BinaryHeap h, int id, void *item);/* reset value of an item with specified id. Return new pos. If ID is invalue, return -1 */
72 
73 void BinaryHeap_print(BinaryHeap h, void (*pnt)(void*));
74 
75 void BinaryHeap_sanity_check(BinaryHeap h);
76 
77 #endif
void * BinaryHeap_extract_item(BinaryHeap h, int id)
Definition: BinaryHeap.c:175
IntStack id_stack
Definition: BinaryHeap.h:37
int BinaryHeap_reset(BinaryHeap h, int id, void *item)
Definition: BinaryHeap.c:208
struct BinaryHeap_struct * BinaryHeap
Definition: BinaryHeap.h:50
int(* cmp)(void *item1, void *item2)
Definition: BinaryHeap.h:44
Definition: utils.c:981
BinaryHeap BinaryHeap_new(int(*cmp)(void *item1, void *item2))
Definition: BinaryHeap.c:16
int BinaryHeap_insert(BinaryHeap h, void *item)
Definition: BinaryHeap.c:137
int
Definition: grammar.c:1264
void BinaryHeap_sanity_check(BinaryHeap h)
Definition: BinaryHeap.c:237
void * BinaryHeap_extract_min(BinaryHeap h)
Definition: BinaryHeap.c:169
void * BinaryHeap_get_item(BinaryHeap h, int id)
Definition: BinaryHeap.c:225
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