All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
BinaryHeap.h
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2008, Willow Garage, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the Willow Garage nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *********************************************************************/
34 
35 /* Author: Ioan Sucan */
36 
37 #ifndef OMPL_DATASTRUCTURES_BINARY_HEAP_
38 #define OMPL_DATASTRUCTURES_BINARY_HEAP_
39 
40 #include <functional>
41 #include <vector>
42 #include <cassert>
43 
44 namespace ompl
45 {
46 
51  template <typename _T,
52  class LessThan = std::less<_T> >
53  class BinaryHeap
54  {
55  public:
56 
61  class Element
62  {
63  friend class BinaryHeap;
64  private:
65  Element(void) { }
66  ~Element(void) { }
68  unsigned int position;
69  public:
71  _T data;
72  };
73 
75  typedef void (*EventAfterInsert) (Element*, void*);
76 
78  typedef void (*EventBeforeRemove)(Element*, void*);
79 
80  BinaryHeap(void)
81  {
82  eventAfterInsert_ = NULL;
83  eventBeforeRemove_ = NULL;
84  }
85 
86  ~BinaryHeap(void)
87  {
88  clear();
89  }
90 
92  void onAfterInsert(EventAfterInsert event, void *arg)
93  {
94  eventAfterInsert_ = event;
95  eventAfterInsertData_ = arg;
96  }
97 
99  void onBeforeRemove(EventBeforeRemove event, void *arg)
100  {
101  eventBeforeRemove_ = event;
102  eventBeforeRemoveData_ = arg;
103  }
104 
106  void clear(void)
107  {
108  for (typename std::vector<Element*>::iterator i = vector_.begin() ;
109  i != vector_.end() ; ++i)
110  delete *i;
111  vector_.clear();
112  }
113 
115  Element* top(void) const
116  {
117  return vector_.empty() ? NULL : vector_.at(0);
118  }
119 
121  void pop(void)
122  {
123  removePos(0);
124  }
125 
127  void remove(Element* element)
128  {
129  if (eventBeforeRemove_)
130  eventBeforeRemove_(element, eventBeforeRemoveData_);
131  removePos(element->position);
132  }
133 
135  Element* insert(const _T& data)
136  {
137  Element* element = new Element();
138  element->data = data;
139  const unsigned int pos = vector_.size();
140  element->position = pos;
141  vector_.push_back(element);
142  percolateUp(pos);
143  if (eventAfterInsert_)
144  eventAfterInsert_(element, eventAfterInsertData_);
145  return element;
146  }
147 
149  void insert(const std::vector<_T>& list)
150  {
151  const unsigned int n = vector_.size();
152  const unsigned int m = list.size();
153  for (unsigned int i = 0 ; i < m ; ++i)
154  {
155  const unsigned int pos = i + n;
156  Element* element = newElement(list[i], pos);
157  vector_.push_back(element);
158  percolateUp(pos);
159  if (eventAfterInsert_)
160  eventAfterInsert_(element, eventAfterInsertData_);
161  }
162  }
163 
165  void buildFrom(const std::vector<_T>& list)
166  {
167  clear();
168  const unsigned int m = list.size();
169  for (unsigned int i = 0 ; i < m ; ++i)
170  vector_.push_back(newElement(list[i], i));
171  build();
172  }
173 
175  void rebuild(void)
176  {
177  build();
178  }
179 
181  void update(Element* element)
182  {
183  const unsigned int pos = element->position;
184  assert(vector_[pos] == element);
185  percolateUp(pos);
186  percolateDown(pos);
187  }
188 
190  bool empty(void) const
191  {
192  return vector_.empty();
193  }
194 
196  unsigned int size(void) const
197  {
198  return vector_.size();
199  }
200 
202  void getContent(std::vector<_T> &content) const
203  {
204  for (typename std::vector<Element*>::const_iterator i = vector_.begin();
205  i != vector_.end() ; ++i)
206  content.push_back((*i)->data);
207  }
208 
210  void sort(std::vector<_T>& list)
211  {
212  const unsigned int n = list.size();
213  std::vector<Element*> backup = vector_;
214  vector_.clear();
215  for (unsigned int i = 0 ; i < n ; ++i)
216  vector_.push_back(newElement(list[i], i));
217  build();
218  list.clear();
219  list.reserve(n);
220 
221  for (unsigned int i = 0 ; i < n ; ++i)
222  {
223  list.push_back(vector_[0]->data);
224  removePos(0);
225  }
226  vector_ = backup;
227  }
228 
229  private:
230 
231  LessThan lt_;
232 
233  std::vector<Element*> vector_;
234 
235  EventAfterInsert eventAfterInsert_;
236  void *eventAfterInsertData_;
237  EventBeforeRemove eventBeforeRemove_;
238  void *eventBeforeRemoveData_;
239 
240  void removePos(unsigned int pos)
241  {
242  const int n = vector_.size() - 1;
243  delete vector_[pos];
244  if ((int)pos < n)
245  {
246  vector_[pos] = vector_.back();
247  vector_[pos]->position = pos;
248  vector_.pop_back();
249  percolateDown(pos);
250  }
251  else
252  vector_.pop_back();
253  }
254 
255  Element* newElement(_T& data, unsigned int pos) const
256  {
257  Element* element = new Element();
258  element->data = data;
259  element->position = pos;
260  return element;
261  }
262 
263  void build(void)
264  {
265  for(int i = vector_.size() / 2 - 1; i >= 0; --i)
266  percolateDown(i);
267  }
268 
269  void percolateDown(const unsigned int pos)
270  {
271  const unsigned int n = vector_.size();
272  Element* tmp = vector_[pos];
273  unsigned int parent = pos;
274  unsigned int child = (pos + 1) << 1;
275 
276  while (child < n)
277  {
278  if (lt_(vector_[child - 1]->data, vector_[child]->data)) --child;
279  if (lt_(vector_[child]->data, tmp->data))
280  {
281  vector_[parent] = vector_[child];
282  vector_[parent]->position = parent;
283  }
284  else
285  break;
286  parent = child;
287  child = (child + 1) << 1;
288  }
289  if (child == n)
290  {
291  --child;
292  if (lt_(vector_[child]->data, tmp->data))
293  {
294  vector_[parent] = vector_[child];
295  vector_[parent]->position = parent;
296  parent = child;
297  }
298  }
299  if (parent != pos)
300  {
301  vector_[parent] = tmp;
302  vector_[parent]->position = parent;
303  }
304  }
305 
306  void percolateUp(const unsigned int pos)
307  {
308  Element* tmp = vector_[pos];
309  unsigned int child = pos;
310  unsigned int parent = (pos - 1) >> 1;
311 
312  while (child > 0 && lt_(tmp->data, vector_[parent]->data))
313  {
314  vector_[child] = vector_[parent];
315  vector_[child]->position = child;
316  child = parent;
317  parent = (parent - 1) >> 1;
318  }
319  if (child != pos)
320  {
321  vector_[child] = tmp;
322  vector_[child]->position = child;
323  }
324  }
325  };
326 
327 }
328 
329 #endif
void pop(void)
Remove the top element.
Definition: BinaryHeap.h:121
void onBeforeRemove(EventBeforeRemove event, void *arg)
Set the event that gets called before a removal.
Definition: BinaryHeap.h:99
_T data
The data of this element.
Definition: BinaryHeap.h:71
When an element is added to the heap, an instance of Element* is created. This instance contains the ...
Definition: BinaryHeap.h:61
unsigned int size(void) const
Get the number of elements in the heap.
Definition: BinaryHeap.h:196
void getContent(std::vector< _T > &content) const
Get the data stored in this heap.
Definition: BinaryHeap.h:202
void update(Element *element)
Update an element in the heap.
Definition: BinaryHeap.h:181
void clear(void)
Clear the heap.
Definition: BinaryHeap.h:106
This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome...
Definition: BinaryHeap.h:53
void buildFrom(const std::vector< _T > &list)
Clear the heap, add the set of elements list to it and rebuild it.
Definition: BinaryHeap.h:165
void(* EventAfterInsert)(Element *, void *)
Event that gets called after an insertion.
Definition: BinaryHeap.h:75
bool empty(void) const
Check if the heap is empty.
Definition: BinaryHeap.h:190
void(* EventBeforeRemove)(Element *, void *)
Event that gets called just before a removal.
Definition: BinaryHeap.h:78
void onAfterInsert(EventAfterInsert event, void *arg)
Set the event that gets called after insertion.
Definition: BinaryHeap.h:92
void insert(const std::vector< _T > &list)
Add a set of elements to the heap.
Definition: BinaryHeap.h:149
Element * top(void) const
Return the top element. NULL for an empty heap.
Definition: BinaryHeap.h:115
void rebuild(void)
Rebuild the heap.
Definition: BinaryHeap.h:175
Element * insert(const _T &data)
Add a new element.
Definition: BinaryHeap.h:135
void sort(std::vector< _T > &list)
Sort an array of elements. This does not affect the content of the heap.
Definition: BinaryHeap.h:210