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() { }
66  ~Element() { }
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()
81  {
82  eventAfterInsert_ = NULL;
83  eventBeforeRemove_ = NULL;
84  }
85 
86  ~BinaryHeap()
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()
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() const
116  {
117  return vector_.empty() ? NULL : vector_.at(0);
118  }
119 
121  void pop()
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()
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() const
191  {
192  return vector_.empty();
193  }
194 
196  unsigned int size() 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 
231  {
232  return lt_;
233  }
234 
235  private:
236 
237  LessThan lt_;
238 
239  std::vector<Element*> vector_;
240 
241  EventAfterInsert eventAfterInsert_;
242  void *eventAfterInsertData_;
243  EventBeforeRemove eventBeforeRemove_;
244  void *eventBeforeRemoveData_;
245 
246  void removePos(unsigned int pos)
247  {
248  const int n = vector_.size() - 1;
249  delete vector_[pos];
250  if ((int)pos < n)
251  {
252  vector_[pos] = vector_.back();
253  vector_[pos]->position = pos;
254  vector_.pop_back();
255  percolateDown(pos);
256  }
257  else
258  vector_.pop_back();
259  }
260 
261  Element* newElement(_T& data, unsigned int pos) const
262  {
263  Element *element = new Element();
264  element->data = data;
265  element->position = pos;
266  return element;
267  }
268 
269  void build()
270  {
271  for(int i = vector_.size() / 2 - 1; i >= 0; --i)
272  percolateDown(i);
273  }
274 
275  void percolateDown(const unsigned int pos)
276  {
277  const unsigned int n = vector_.size();
278  Element *tmp = vector_[pos];
279  unsigned int parent = pos;
280  unsigned int child = (pos + 1) << 1;
281 
282  while (child < n)
283  {
284  if (lt_(vector_[child - 1]->data, vector_[child]->data)) --child;
285  if (lt_(vector_[child]->data, tmp->data))
286  {
287  vector_[parent] = vector_[child];
288  vector_[parent]->position = parent;
289  }
290  else
291  break;
292  parent = child;
293  child = (child + 1) << 1;
294  }
295  if (child == n)
296  {
297  --child;
298  if (lt_(vector_[child]->data, tmp->data))
299  {
300  vector_[parent] = vector_[child];
301  vector_[parent]->position = parent;
302  parent = child;
303  }
304  }
305  if (parent != pos)
306  {
307  vector_[parent] = tmp;
308  vector_[parent]->position = parent;
309  }
310  }
311 
312  void percolateUp(const unsigned int pos)
313  {
314  Element *tmp = vector_[pos];
315  unsigned int child = pos;
316  unsigned int parent = (pos - 1) >> 1;
317 
318  while (child > 0 && lt_(tmp->data, vector_[parent]->data))
319  {
320  vector_[child] = vector_[parent];
321  vector_[child]->position = child;
322  child = parent;
323  parent = (parent - 1) >> 1;
324  }
325  if (child != pos)
326  {
327  vector_[child] = tmp;
328  vector_[child]->position = child;
329  }
330  }
331  };
332 
333 }
334 
335 #endif
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
void clear()
Clear the heap.
Definition: BinaryHeap.h:106
void rebuild()
Rebuild the heap.
Definition: BinaryHeap.h:175
When an element is added to the heap, an instance of Element* is created. This instance contains the ...
Definition: BinaryHeap.h:61
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(* EventBeforeRemove)(Element *, void *)
Event that gets called just before a removal.
Definition: BinaryHeap.h:78
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
Main namespace. Contains everything in this library.
Definition: Cost.h:42
Element * top() const
Return the top element. NULL for an empty heap.
Definition: BinaryHeap.h:115
bool empty() const
Check if the heap is empty.
Definition: BinaryHeap.h:190
void pop()
Remove the top element.
Definition: BinaryHeap.h:121
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
unsigned int size() const
Get the number of elements in the heap.
Definition: BinaryHeap.h:196
LessThan & getComparisonOperator()
Return a reference to the comparison operator.
Definition: BinaryHeap.h:230
Element * insert(const _T &data)
Add a new element.
Definition: BinaryHeap.h:135
void(* EventAfterInsert)(Element *, void *)
Event that gets called after an insertion.
Definition: BinaryHeap.h:75
void sort(std::vector< _T > &list)
Sort an array of elements. This does not affect the content of the heap.
Definition: BinaryHeap.h:210