Menge
Modular Pedestrian Simulation Framework for Research and Development
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
MinHeap.h
Go to the documentation of this file.
1 /*
2 
3 License
4 
5 Menge
6 Copyright and trademark 2012-14 University of North Carolina at Chapel Hill.
7 All rights reserved.
8 
9 Permission to use, copy, modify, and distribute this software and its documentation
10 for educational, research, and non-profit purposes, without fee, and without a
11 written agreement is hereby granted, provided that the above copyright notice,
12 this paragraph, and the following four paragraphs appear in all copies.
13 
14 This software program and documentation are copyrighted by the University of North
15 Carolina at Chapel Hill. The software program and documentation are supplied "as is,"
16 without any accompanying services from the University of North Carolina at Chapel
17 Hill or the authors. The University of North Carolina at Chapel Hill and the
18 authors do not warrant that the operation of the program will be uninterrupted
19 or error-free. The end-user understands that the program was developed for research
20 purposes and is advised not to rely exclusively on the program for any reason.
21 
22 IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL OR THE AUTHORS
23 BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
24 DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
25 DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL OR THE
26 AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL AND THE AUTHORS SPECIFICALLY
29 DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
30 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE AND ANY STATUTORY WARRANTY
31 OF NON-INFRINGEMENT. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND
32 THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL AND THE AUTHORS HAVE NO OBLIGATIONS
33 TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
34 
35 Any questions or comments should be sent to the authors {menge,geom}@cs.unc.edu
36 
37 */
38 
45 #ifndef __MIN_HEAP_H__
46 #define __MIN_HEAP_H__
47 
48 #ifndef _WIN32
49 #include "sys/types.h"
50 #endif
51 
52 namespace Menge {
53 
62  class AStarMinHeap {
63  public:
77  AStarMinHeap( unsigned int * heap, float * data, bool * state, unsigned int * path, size_t N );
78 
84  bool empty() const { return _nextFree == 0; }
85 
91  unsigned int pop();
92 
98  void push( unsigned int x );
99 
106  inline void g( unsigned int node, float value ) { _g[ node ] = value; }
107 
114  inline float g( unsigned int node ) const { return _g[ node ]; }
115 
122  inline void h( unsigned int node, float value ) { _h[ node ] = value; }
123 
130  inline float h( unsigned int node ) const { return _h[ node ]; }
131 
138  inline void f( unsigned int node, float value ) { if ( _inHeap[ node ] ) changeF( node, value ); else _f[ node ] = value; }
139 
146  inline float f( unsigned int node ) const { return _f[ node ]; }
147 
154  void changeF( unsigned int node, float value);
155 
162  inline bool isVisited( unsigned int node ) const { return _visited[ node ]; }
163 
170  inline bool isInHeap( unsigned int node ) const { return _inHeap[ node ]; }
171 
178  inline void setReachedFrom( unsigned int dst, unsigned int src ) { _cameFrom[ dst ] = src; }
179 
186  inline unsigned int getReachedFrom( unsigned int dst ) const { return _cameFrom[ dst ]; }
187 
188  protected:
194  void initialize( size_t N);
195 
199  float _minKey;
200 
204  unsigned int _minIdx;
205 
209  unsigned int _nextFree;
210 
216  float * _f;
217 
223  float * _g;
224 
230  float * _h;
231 
236  bool * _inHeap;
237 
242  bool * _visited;
243 
248  unsigned int * _heap;
249 
254  unsigned int * _cameFrom;
255  };
256 } // namespace Menge
257 
258 #endif // __MIN_HEAP_H__
bool * _inHeap
An array of booleans reporting if the given node is in the heap. The memory is supplied upon construc...
Definition: MinHeap.h:236
The core namespace. All elements of Menge are contained in this namespace.
Definition: AgentGenerator.cpp:43
void f(unsigned int node, float value)
Set the f-value for the given node.
Definition: MinHeap.h:138
bool * _visited
An array of booleans reporting if the given node has been visited. The memory is supplied upon constr...
Definition: MinHeap.h:242
float _minKey
The VALUE of the minimum keyed heap member.
Definition: MinHeap.h:199
float g(unsigned int node) const
Retrieve the g-value for the given node.
Definition: MinHeap.h:114
unsigned int getReachedFrom(unsigned int dst) const
Report the node from which this node was reached.
Definition: MinHeap.h:186
unsigned int * _cameFrom
An array of node indices which indicate how a node was reached. The memory is supplied upon construct...
Definition: MinHeap.h:254
An implementation of a min heap for A* algorithm. The heap needs to be able to restructure itself bec...
Definition: MinHeap.h:62
float f(unsigned int node) const
Retrieve the f-value for the given node.
Definition: MinHeap.h:146
void h(unsigned int node, float value)
Set the h-value for the given node.
Definition: MinHeap.h:122
AStarMinHeap(unsigned int *heap, float *data, bool *state, unsigned int *path, size_t N)
Constructor.
Definition: MinHeap.cpp:51
float * _h
An array of h-values for each node in the navigation mesh. This is a value used in the A* algorithm...
Definition: MinHeap.h:230
bool isInHeap(unsigned int node) const
Reports if the node is currently in the heap.
Definition: MinHeap.h:170
bool isVisited(unsigned int node) const
Reports if the node has been visited.
Definition: MinHeap.h:162
void initialize(size_t N)
Resets the heap and all data.
Definition: MinHeap.cpp:64
void g(unsigned int node, float value)
Set the g-value for the given node.
Definition: MinHeap.h:106
float h(unsigned int node) const
Retrieve the h-value for the given node.
Definition: MinHeap.h:130
float * _g
An array of g-values for each node in the navigation mesh. This is a value used in the A* algorithm...
Definition: MinHeap.h:223
unsigned int _minIdx
The location of the minimum keyed heap member.
Definition: MinHeap.h:204
float * _f
An array of f-values for each node in the navigation mesh. This is a value used in the A* algorithm...
Definition: MinHeap.h:216
unsigned int _nextFree
The location of the next free slot on the heap.
Definition: MinHeap.h:209
unsigned int pop()
Extract the minimum keyed value.
Definition: MinHeap.cpp:78
bool empty() const
Reports if the heap is empty.
Definition: MinHeap.h:84
void setReachedFrom(unsigned int dst, unsigned int src)
Sets the node from which this node was reached.
Definition: MinHeap.h:178
void changeF(unsigned int node, float value)
Change the f-value for the given node in the heap.
Definition: MinHeap.cpp:114
unsigned int * _heap
An array of node indices of the nodes in the heap. The memory is supplied upon construction.
Definition: MinHeap.h:248
void push(unsigned int x)
Insert a new value into the heap.
Definition: MinHeap.cpp:102