Heap< HeapEntry, HeapInterface > Class Template Reference

A class implementing a heap. More...

#include <easy3d/core/heap.h>

Inheritance diagram for Heap< HeapEntry, HeapInterface >:

Public Types
typedef Heap< HeapEntry, HeapInterface >	This
	This class.

Public Member Functions
	Heap ()
	Default constructor.
	Heap (const HeapInterface &i)
	Constructs a heap with a given HeapInterface.
	~Heap ()=default
	Destructor.
void	clear ()
	Clears the heap.
bool	empty ()
	Checks if the heap is empty.
unsigned int	size ()
	Returns the size of the heap.
void	reserve (unsigned int n)
	Reserves space for n entries.
void	reset_heap_position (HeapEntry h)
	Resets the heap position of an entry to -1 (not in heap).
bool	is_stored (HeapEntry h)
	Checks if an entry is stored in the heap.
void	insert (HeapEntry h)
	Inserts an entry into the heap.
HeapEntry	front ()
	Retrieves the first entry in the heap.
void	pop_front ()
	Deletes the first entry in the heap.
void	remove (HeapEntry h)
	Removes an entry from the heap.
void	update (HeapEntry h)
	Updates an entry in the heap.
bool	check ()
	Checks the heap condition.

Detailed Description

template<class HeapEntry, class HeapInterface>
class easy3d::Heap< HeapEntry, HeapInterface >

A class implementing a heap.

This class provides methods to manage a heap data structure, including insertion, removal, and updating of elements.

Template Parameters

HeapEntry	The type of the elements stored in the heap.
HeapInterface	The interface class that provides methods for comparing and managing heap positions.

An example of heap interface

class HeapInterface {
public:
    HeapInterface(SurfaceMesh::VertexProperty<float> prio, SurfaceMesh::VertexProperty<int> pos)
            : prio_(prio), pos_(pos) {
    }
 
    bool less(SurfaceMesh::Vertex v0, SurfaceMesh::Vertex v1) { return prio_[v0] < prio_[v1]; }
    bool greater(SurfaceMesh::Vertex v0, SurfaceMesh::Vertex v1) { return prio_[v0] > prio_[v1]; }
    int get_heap_position(SurfaceMesh::Vertex v) { return pos_[v]; }
    void set_heap_position(SurfaceMesh::Vertex v, int pos) { pos_[v] = pos; }
 
private:
    SurfaceMesh::VertexProperty<float> prio_;
    SurfaceMesh::VertexProperty<int> pos_;
};

Constructor & Destructor Documentation

Heap()

template<class HeapEntry, class HeapInterface>

Heap ( const HeapInterface & i )

inlineexplicit

Constructs a heap with a given HeapInterface.

Parameters

i	The heap interface.

Member Function Documentation

check()

template<class HeapEntry, class HeapInterface>

bool check ( )

inline

Checks the heap condition.

Returns

True if the heap condition is satisfied, false otherwise.

empty()

template<class HeapEntry, class HeapInterface>

bool empty ( )

inline

Checks if the heap is empty.

Returns

True if the heap is empty, false otherwise.

front()

template<class HeapEntry, class HeapInterface>

HeapEntry front ( )

inline

Retrieves the first entry in the heap.

Returns

The first entry in the heap.

insert()

template<class HeapEntry, class HeapInterface>

void insert ( HeapEntry h )

inline

Inserts an entry into the heap.

Parameters

h	The entry to insert.

is_stored()

template<class HeapEntry, class HeapInterface>

bool is_stored ( HeapEntry h )

inline

Checks if an entry is stored in the heap.

Parameters

h	The entry to check.

Returns

True if the entry is in the heap, false otherwise.

remove()

template<class HeapEntry, class HeapInterface>

void remove ( HeapEntry h )

inline

Removes an entry from the heap.

Parameters

h	The entry to remove.

reserve()

template<class HeapEntry, class HeapInterface>

void reserve ( unsigned int n )

inline

Reserves space for n entries.

Parameters

n	The number of entries to reserve space for.

reset_heap_position()

template<class HeapEntry, class HeapInterface>

void reset_heap_position ( HeapEntry h )

inline

Resets the heap position of an entry to -1 (not in heap).

Parameters

h	The entry to reset.

size()

template<class HeapEntry, class HeapInterface>

unsigned int size ( )

inline

Returns the size of the heap.

Returns

The number of elements in the heap.

update()

template<class HeapEntry, class HeapInterface>

void update ( HeapEntry h )

inline

Updates an entry in the heap.

Changes the key of the entry and updates its position to reestablish the heap property.

Parameters

h	The entry to update.

---

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

• G:/3_code/Easy3D/easy3d/core/heap.h