source: vis_dev/glu-2.3/src/heap/heap.h @ 104

Last change on this file since 104 was 13, checked in by cecile, 14 years ago

library glu 2.3
File size: 4.4 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [heap.h]
4
5  PackageName [heap]
6
7  Synopsis    [Heap-based priority queue.]
8
9  Description [This is the external header file for the heap-based
10  priority queue.  The priority of each item is determined by an
11  integer key.  The first element of the heap is the one with the
12  smallest key.  Multiple items with the same key can be inserted.
13  Refer to Chapter 7 of Cormen, Leiserson, and Rivest for the theory.
14  (The only significant difference is that the array indices start
15  from 0 in this implementation.)]
16
17  SeeAlso     []
18
19  Author      [Fabio Somenzi]
20
21  Copyright   [This file was created at the University of Colorado at
22  Boulder.  The University of Colorado at Boulder makes no warranty
23  about the suitability of this software for any purpose.  It is
24  presented on an AS IS basis.]
25
26  Revision    [$Id: heap.h,v 1.13 2005/05/18 19:25:43 jinh Exp $]
27
28******************************************************************************/
29
30#ifndef _HEAP
31#define _HEAP
32
33/*---------------------------------------------------------------------------*/
34/* Nested includes                                                           */
35/*---------------------------------------------------------------------------*/
36#include "util.h"
37#undef MAX
38#undef MIN
39
40/*---------------------------------------------------------------------------*/
41/* Constant declarations                                                     */
42/*---------------------------------------------------------------------------*/
43
44
45/*---------------------------------------------------------------------------*/
46/* Stucture declarations                                                     */
47/*---------------------------------------------------------------------------*/
48
49
50/*---------------------------------------------------------------------------*/
51/* Type declarations                                                         */
52/*---------------------------------------------------------------------------*/
53
54typedef struct HeapSlot HeapSlot_t;
55
56typedef struct Heap Heap_t;
57
58/*---------------------------------------------------------------------------*/
59/* Variable declarations                                                     */
60/*---------------------------------------------------------------------------*/
61
62
63/*---------------------------------------------------------------------------*/
64/* Macro declarations                                                        */
65/*---------------------------------------------------------------------------*/
66
67/**Macro***********************************************************************
68
69  Synopsis    [Iterates over the elements of a heap.]
70
71  SideEffects [none]
72
73******************************************************************************/
74#define Heap_HeapForEachItem(                                              \
75  /* Heap_t * */ heap /* heap whose element should be enumerated */,       \
76  /* int */      i    /* local variable for iterator */,                   \
77  /* void * */   data /* heap item */                                      \
78)                                                                          \
79  for((i) = 0; (((i) < (heap)->nitems) && (data = (heap)->slots[i].item)); \
80      (i)++)
81
82
83
84/**AutomaticStart*************************************************************/
85
86/*---------------------------------------------------------------------------*/
87/* Function prototypes                                                       */
88/*---------------------------------------------------------------------------*/
89
90EXTERN Heap_t * Heap_HeapInit ARGS((int length));
91EXTERN Heap_t * Heap_HeapInitCompare ARGS((int length, int (*compare)(const void *, const void *)));
92EXTERN void Heap_HeapFree ARGS((Heap_t *heap));
93EXTERN int Heap_HeapInsert ARGS((Heap_t *heap, void *item, long key));
94EXTERN int Heap_HeapInsertCompare ARGS((Heap_t *heap, void *item, long key));
95EXTERN int Heap_HeapExtractMin ARGS((Heap_t *heap, void *item, long *key));
96EXTERN int Heap_HeapCount ARGS((Heap_t *heap));
97EXTERN Heap_t * Heap_HeapClone ARGS((Heap_t *source));
98EXTERN int Heap_HeapTest ARGS((Heap_t *heap));
99EXTERN int Heap_HeapTestCompare ARGS((Heap_t *heap));
100EXTERN void Heap_HeapApplyForEachElement(Heap_t *heap, int (*compare)(const void *));
101
102
103
104/**AutomaticEnd***************************************************************/
105
106#endif /* _HEAP */
Note: See TracBrowser for help on using the repository browser.