FMDaryHeap< cell_t > Class Template Reference

Wrap for the Boost D-ary Heap class to be used as a binary heap in the FM algorithms. Ready to be used with FMCell and derived types. More...

#include <fmdaryheap.hpp>

Public Member Functions
	FMDaryHeap (const size_t &n)
	Creates a heap with n maximum elements.
void	setMaxSize (const size_t &n)
	Sets the maximum number of cells the heap will contain.
void	push (const cell_t *c)
	Pushes a new element into the heap.
unsigned int	popMinIdx ()
	Pops index of the element with lowest value and removes it from the heap.
size_t	size () const
	Returns current size of the heap.
void	update (const cell_t *c)
	Updates the position of the cell in the heap. Its priority can increase or decrease.
void	increase (const cell_t *c)
	Updates the position of the cell in the heap. Its priority can only increase. It is more efficient than the update() function if it is ensured that the priority will increase.
void	clear ()
	Deallocates heap memory.
bool	empty () const
	Returns true if the heap is empty.

Protected Attributes
d_ary_heap_t	heap_
	The actual heap for cell_t. More...
std::vector< handle_t >	handles_
	Stores the handles of each cell by keeping the indices: handles_(0) is the handle for the cell with index 0 in the grid. Makes possible to update the heap.

Private Types
typedef boost::heap::d_ary_heap< const cell_t *, boost::heap::mutable_< true > , boost::heap::arity < 2 >, boost::heap::compare < FMCompare< cell_t > > >	d_ary_heap_t
	Shorthand for heap type.
typedef d_ary_heap_t::handle_type	handle_t
	Shorthand for heap element handle type.

Detailed Description

template<class cell_t = FMCell>
class FMDaryHeap< cell_t >

Wrap for the Boost Fibonacci Heap class to be used in the FM algorithms. Ready to be used with FMCell and derived types.

Note

for memory efficiency, use map instead of vector for handles_.

Copyright (C) 2014 Javier V. Gomez and Jose Pardeiro www.javiervgomez.com

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Definition at line 28 of file fmdaryheap.hpp.

Member Data Documentation

template<class cell_t = FMCell>

d_ary_heap_t FMDaryHeap< cell_t >::heap_

protected

The actual heap for cell_t.

Definition at line 99 of file fmdaryheap.hpp.

---

The documentation for this class was generated from the following file:

• /home/jvgomez/Desktop/fastmarching/include/fast_methods/datastructures/fmdaryheap.hpp