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
25struct BinaryHeap_struct {
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
48enum {BinaryHeap_error_malloc = -10};
49
50typedef struct BinaryHeap_struct* BinaryHeap;
51
52BinaryHeap BinaryHeap_new(int (*cmp)(void*item1, void*item2));
53
54
55void 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
58int 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
63void* BinaryHeap_get_min(BinaryHeap h);/* return the min item */
64
65void* BinaryHeap_extract_min(BinaryHeap h);/* return and remove the min item */
66
67void* BinaryHeap_extract_item(BinaryHeap h, int id);/* extract an item with ID out and delete it */
68
69void* BinaryHeap_get_item(BinaryHeap h, int id);/* get an item with ID out, without deleting */
70
71int 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
73void BinaryHeap_print(BinaryHeap h, void (*pnt)(void*));
74
75void BinaryHeap_sanity_check(BinaryHeap h);
76
77#endif
78