OpenMesh.Tools.Utils.HeapT
- struct
HeapInterfaceT
(HeapEntry);
- This class demonstrates the HeapInterface's interface. If you
want to build your customized heap you will have to specity a heap
interface class and use this class as a template parameter for the
class HeapT. This class defines the interface that this heap
interface has to implement.
See Also:
HeapT
- bool
less
(ref HeapEntry _e1, ref HeapEntry _e2);
- Comparison of two HeapEntry's: strict
less
- bool
greater
(ref HeapEntry _e1, ref HeapEntry _e2);
- Comparison of two HeapEntry's: strict
greater
- int
get_heap_position
(ref HeapEntry _e);
- Get the heap position of HeapEntry e
- void
set_heap_position
(ref HeapEntry _e, int _i);
- Set the heap position of HeapEntry e
- struct
HeapT
(HeapEntry,HeapInterface = HeapEntry);
- An efficient, highly customizable heap.
The main difference (and performace boost) of this heap compared
to e.g. the heap of the STL is that here to positions of the
heap's elements are accessible from the elements themself.
Therefore if one changes the priority of an element one does not
have to remove and re-insert this element, but can just call the
update(HeapEntry) method.
This heap class is parameterized by two template arguments:
- the class \c HeapEntry, that will be stored in the heap
- the HeapInterface telling the heap how to compare heap entries and
how to store the heap positions in the heap entries.
As an example how to use the class see declaration of class
Decimater.DecimaterT.
See Also:
HeapInterfaceT
- HeapT
opCall
();
- Constructor
- HeapT
opCall
(ref HeapInterface _interface);
- Construct with a given \c HeapIterface.
- void
clear
();
-
clear
the heap
- bool
empty
();
- is heap
empty
?
- uint
size
();
- returns the
size
of heap
- void
reserve
(uint _n);
-
reserve
space for n entries
- void
reset_heap_position
(HeapEntry _h);
- reset heap position to -1 (not in heap)
- bool
is_stored
(HeapEntry _h);
- is an entry in the heap?
- void
insert
(HeapEntry _h);
-
insert
the entry h
- HeapEntry
front
();
- get the first entry
- void
pop_front
();
- delete the first entry
- void
remove
(HeapEntry _h);
-
remove
an entry
- void
update
(HeapEntry _h);
-
update
an entry: change the key and
update
the position to
reestablish the heap property.
- bool
check
();
-
check
heap condition
- HeapInterface
interface_
;
- Instance of HeapInterface
- void
upheap
(uint _idx);
- Upheap. Establish heap property.
- void
downheap
(uint _idx);
- Downheap. Establish heap property.
- HeapEntry
entry
(uint _idx);
- Get the
entry
at index idx
- void
entry
(uint _idx, HeapEntry _h);
- Set
entry
h to index idx and update h's heap position.
- uint
parent
(uint _i);
- Get
parent
's index
- uint
left
(uint _i);
- Get
left
child's index
- uint
right
(uint _i);
- Get
right
child's index
|