source: vis_dev/glu-2.1/src/heap/heapInt.h @ 13

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

src glu
File size: 4.8 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [heapInt.h]
4
5  PackageName [heap]
6
7  Synopsis    [Heap-based priority queue.]
8
9  Description [This is the internal header file for the heap-based priority
10  queue.]
11
12  SeeAlso     []
13
14  Author      [Fabio Somenzi]
15
16  Copyright   [This file was created at the University of Colorado at
17  Boulder.  The University of Colorado at Boulder makes no warranty
18  about the suitability of this software for any purpose.  It is
19  presented on an AS IS basis.]
20
21  Revision    [$Id: heapInt.h,v 1.7 2005/05/18 19:25:43 jinh Exp $]
22
23******************************************************************************/
24
25#ifndef _HEAPINT
26#define _HEAPINT
27
28/*---------------------------------------------------------------------------*/
29/* Nested includes                                                           */
30/*---------------------------------------------------------------------------*/
31#include "heap.h"
32
33
34/*---------------------------------------------------------------------------*/
35/* Constant declarations                                                     */
36/*---------------------------------------------------------------------------*/
37
38
39/*---------------------------------------------------------------------------*/
40/* Stucture declarations                                                     */
41/*---------------------------------------------------------------------------*/
42
43/**Struct**********************************************************************
44
45  Synopsis    [Slot of a heap.]
46
47  Description [Slot of a heap.  Each slots holds a generic object and an
48  integer key.]
49
50******************************************************************************/
51struct HeapSlot {
52  long key;
53  void *item;
54};
55
56
57/**Struct**********************************************************************
58
59  Synopsis    [Heap.]
60
61  Description []
62
63******************************************************************************/
64struct Heap {
65  int length;
66  int nitems;
67  struct HeapSlot *slots;
68  int (*compare)(const void *, const void *);
69};
70
71
72/*---------------------------------------------------------------------------*/
73/* Type declarations                                                         */
74/*---------------------------------------------------------------------------*/
75
76
77/*---------------------------------------------------------------------------*/
78/* Variable declarations                                                     */
79/*---------------------------------------------------------------------------*/
80
81
82/*---------------------------------------------------------------------------*/
83/* Macro declarations                                                        */
84/*---------------------------------------------------------------------------*/
85
86/**Macro***********************************************************************
87
88  Synopsis    [Returns the parent of the i-th element in a heap.]
89
90  Description [Returns the parent of the i-th element in a heap.
91  Argument <code>i</code> should be strictly positive, otherwise the
92  result is implementation dependent.]
93
94  SideEffects [none]
95
96******************************************************************************/
97#define PARENT(i)       (((i)-1)>>1)
98
99/**Macro***********************************************************************
100
101  Synopsis    [Returns the left child of the i-th element in a heap.]
102
103  SideEffects [none]
104
105******************************************************************************/
106#define LEFT(i)         (((i)<<1)+1)
107
108/**Macro***********************************************************************
109
110  Synopsis    [Returns the right child of the i-th element in a heap.]
111
112  SideEffects [none]
113
114******************************************************************************/
115#define RIGHT(i)        (((i)+1)<<1)
116
117/**Macro***********************************************************************
118
119  Synopsis    [Returns the item stored in the i-th element in a heap.]
120
121  SideEffects [none]
122
123******************************************************************************/
124#define ITEM(p,i)       ((p)[i].item)
125
126/**Macro***********************************************************************
127
128  Synopsis    [Returns the key of the i-th element in a heap.]
129
130  SideEffects [none]
131
132******************************************************************************/
133#define KEY(p,i)        ((p)[i].key)
134
135
136/**AutomaticStart*************************************************************/
137
138/*---------------------------------------------------------------------------*/
139/* Function prototypes                                                       */
140/*---------------------------------------------------------------------------*/
141
142/**AutomaticEnd***************************************************************/
143
144#endif /* _HEAPINT */
Note: See TracBrowser for help on using the repository browser.