\hypertarget{a00692}{\section{Open\+Mesh\+:\+:Utils\+:\+:Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$ Class Template Reference}
\label{a00692}\index{Open\+Mesh\+::\+Utils\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$@{Open\+Mesh\+::\+Utils\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$}}
}


{\ttfamily \#include $<$O\+S\+G/\+Utils/\+Heap\+T.\+hh$>$}

Inheritance diagram for Open\+Mesh\+:\+:Utils\+:\+:Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$\+:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[height=2.000000cm]{a00692}
\end{center}
\end{figure}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00692_a24a2c62d488a9a9e73572ad7820a8e68}{\hyperlink{a00692_a24a2c62d488a9a9e73572ad7820a8e68}{Heap\+T} ()}\label{a00692_a24a2c62d488a9a9e73572ad7820a8e68}

\begin{DoxyCompactList}\small\item\em Constructor. \end{DoxyCompactList}\item 
\hypertarget{a00692_a03ec9a9ca32d9d6409e980b90d53f54b}{\hyperlink{a00692_a03ec9a9ca32d9d6409e980b90d53f54b}{Heap\+T} (const Heap\+Interface \&\+\_\+interface)}\label{a00692_a03ec9a9ca32d9d6409e980b90d53f54b}

\begin{DoxyCompactList}\small\item\em Construct with a given {\ttfamily Heap\+Iterface}. \end{DoxyCompactList}\item 
\hypertarget{a00692_a7e0a462d94cdd0c68aeeaaeadfa78d2d}{\hyperlink{a00692_a7e0a462d94cdd0c68aeeaaeadfa78d2d}{$\sim$\+Heap\+T} ()}\label{a00692_a7e0a462d94cdd0c68aeeaaeadfa78d2d}

\begin{DoxyCompactList}\small\item\em Destructor. \end{DoxyCompactList}\item 
\hypertarget{a00692_aba777f483777c18a4ce9d7a6a87993c8}{Heap\+Interface \& {\bfseries get\+Interface} ()}\label{a00692_aba777f483777c18a4ce9d7a6a87993c8}

\item 
\hypertarget{a00692_a7885c6d13895b638af278d0779aa691c}{const Heap\+Interface \& {\bfseries get\+Interface} () const }\label{a00692_a7885c6d13895b638af278d0779aa691c}

\item 
\hypertarget{a00692_afef1992d5a553b9e8d152af61b9e4fc2}{void \hyperlink{a00692_afef1992d5a553b9e8d152af61b9e4fc2}{clear} ()}\label{a00692_afef1992d5a553b9e8d152af61b9e4fc2}

\begin{DoxyCompactList}\small\item\em clear the heap \end{DoxyCompactList}\item 
\hypertarget{a00692_ade912131211221530243c1c465d553f2}{bool \hyperlink{a00692_ade912131211221530243c1c465d553f2}{empty} () const }\label{a00692_ade912131211221530243c1c465d553f2}

\begin{DoxyCompactList}\small\item\em is heap empty? \end{DoxyCompactList}\item 
\hypertarget{a00692_a8023f6b4c686a6300ca767b71f5d6380}{size\+\_\+t \hyperlink{a00692_a8023f6b4c686a6300ca767b71f5d6380}{size} () const }\label{a00692_a8023f6b4c686a6300ca767b71f5d6380}

\begin{DoxyCompactList}\small\item\em returns the size of heap \end{DoxyCompactList}\item 
\hypertarget{a00692_ab25df952eaf2a9195243759dab1c252e}{void \hyperlink{a00692_ab25df952eaf2a9195243759dab1c252e}{reserve} (size\+\_\+t \+\_\+n)}\label{a00692_ab25df952eaf2a9195243759dab1c252e}

\begin{DoxyCompactList}\small\item\em reserve space for \+\_\+n entries \end{DoxyCompactList}\item 
\hypertarget{a00692_a35feb375cbcf48457e8e2d6307fe7fba}{void \hyperlink{a00692_a35feb375cbcf48457e8e2d6307fe7fba}{reset\+\_\+heap\+\_\+position} (Heap\+Entry \+\_\+h)}\label{a00692_a35feb375cbcf48457e8e2d6307fe7fba}

\begin{DoxyCompactList}\small\item\em reset heap position to -\/1 (not in heap) \end{DoxyCompactList}\item 
\hypertarget{a00692_af286643ed54c1f7252989b2a525c0c07}{bool \hyperlink{a00692_af286643ed54c1f7252989b2a525c0c07}{is\+\_\+stored} (Heap\+Entry \+\_\+h)}\label{a00692_af286643ed54c1f7252989b2a525c0c07}

\begin{DoxyCompactList}\small\item\em is an entry in the heap? \end{DoxyCompactList}\item 
\hypertarget{a00692_a986a09f8eef49ee033663b59fa068c22}{void \hyperlink{a00692_a986a09f8eef49ee033663b59fa068c22}{insert} (Heap\+Entry \+\_\+h)}\label{a00692_a986a09f8eef49ee033663b59fa068c22}

\begin{DoxyCompactList}\small\item\em insert the entry \+\_\+h \end{DoxyCompactList}\item 
\hypertarget{a00692_a73bb3ecb13f6553a1e279e97f224d5cf}{Heap\+Entry \hyperlink{a00692_a73bb3ecb13f6553a1e279e97f224d5cf}{front} () const }\label{a00692_a73bb3ecb13f6553a1e279e97f224d5cf}

\begin{DoxyCompactList}\small\item\em get the first entry \end{DoxyCompactList}\item 
\hypertarget{a00692_aa0f851857c3aee86ea1eb763a5980660}{void \hyperlink{a00692_aa0f851857c3aee86ea1eb763a5980660}{pop\+\_\+front} ()}\label{a00692_aa0f851857c3aee86ea1eb763a5980660}

\begin{DoxyCompactList}\small\item\em delete the first entry \end{DoxyCompactList}\item 
\hypertarget{a00692_ac141346bca01e86f1f7d9e4f0f2a9d8c}{void \hyperlink{a00692_ac141346bca01e86f1f7d9e4f0f2a9d8c}{remove} (Heap\+Entry \+\_\+h)}\label{a00692_ac141346bca01e86f1f7d9e4f0f2a9d8c}

\begin{DoxyCompactList}\small\item\em remove an entry \end{DoxyCompactList}\item 
void \hyperlink{a00692_a5a4198bf734a87481ee5fedc46f2eebd}{update} (Heap\+Entry \+\_\+h)
\item 
\hypertarget{a00692_a3acd94c1497f8b6afd9548ffd64e2318}{bool \hyperlink{a00692_a3acd94c1497f8b6afd9548ffd64e2318}{check} ()}\label{a00692_a3acd94c1497f8b6afd9548ffd64e2318}

\begin{DoxyCompactList}\small\item\em check heap condition \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Protected Attributes}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00692_afb629f999cdff18c71780372ffa4a655}{Heap\+Interface \hyperlink{a00692_afb629f999cdff18c71780372ffa4a655}{interface\+\_\+}}\label{a00692_afb629f999cdff18c71780372ffa4a655}

\begin{DoxyCompactList}\small\item\em Instance of Heap\+Interface. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Private Types}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00692_a6a6ce0a9be43bc890a88dc17dec40429}{typedef std\+::vector$<$ Heap\+Entry $>$ {\bfseries Base}}\label{a00692_a6a6ce0a9be43bc890a88dc17dec40429}

\item 
\hypertarget{a00692_a74bb768a5dde2fb600a95b1f87134882}{typedef std\+::vector$<$ Heap\+Entry $>$ {\bfseries Heap\+Vector}}\label{a00692_a74bb768a5dde2fb600a95b1f87134882}

\end{DoxyCompactItemize}
\subsection*{Private Member Functions}
\begin{DoxyCompactItemize}
\item 
\hypertarget{a00692_aa3b5a57251a46777558c9bea35013c03}{void \hyperlink{a00692_aa3b5a57251a46777558c9bea35013c03}{upheap} (size\+\_\+t \+\_\+idx)}\label{a00692_aa3b5a57251a46777558c9bea35013c03}

\begin{DoxyCompactList}\small\item\em Upheap. Establish heap property. \end{DoxyCompactList}\item 
\hypertarget{a00692_a38a9bd2d0ba146e4eac3f4e9cf96bdd5}{void \hyperlink{a00692_a38a9bd2d0ba146e4eac3f4e9cf96bdd5}{downheap} (size\+\_\+t \+\_\+idx)}\label{a00692_a38a9bd2d0ba146e4eac3f4e9cf96bdd5}

\begin{DoxyCompactList}\small\item\em Downheap. Establish heap property. \end{DoxyCompactList}\item 
\hypertarget{a00692_a1ba493e2400ef7f8cc158f92a16a3cf0}{Heap\+Entry \hyperlink{a00692_a1ba493e2400ef7f8cc158f92a16a3cf0}{entry} (size\+\_\+t \+\_\+idx) const }\label{a00692_a1ba493e2400ef7f8cc158f92a16a3cf0}

\begin{DoxyCompactList}\small\item\em Get the entry at index \+\_\+idx. \end{DoxyCompactList}\item 
\hypertarget{a00692_a4a9b4cb124b148fbe344540bf7e8c707}{void \hyperlink{a00692_a4a9b4cb124b148fbe344540bf7e8c707}{entry} (size\+\_\+t \+\_\+idx, Heap\+Entry \+\_\+h)}\label{a00692_a4a9b4cb124b148fbe344540bf7e8c707}

\begin{DoxyCompactList}\small\item\em Set entry \+\_\+h to index \+\_\+idx and update \+\_\+h's heap position. \end{DoxyCompactList}\item 
\hypertarget{a00692_aab929c8e37990e56e7feb552c470616f}{size\+\_\+t \hyperlink{a00692_aab929c8e37990e56e7feb552c470616f}{parent} (size\+\_\+t \+\_\+i)}\label{a00692_aab929c8e37990e56e7feb552c470616f}

\begin{DoxyCompactList}\small\item\em Get parent's index. \end{DoxyCompactList}\item 
\hypertarget{a00692_a1884c88581582231e82713ec2dcb83b4}{size\+\_\+t \hyperlink{a00692_a1884c88581582231e82713ec2dcb83b4}{left} (size\+\_\+t \+\_\+i)}\label{a00692_a1884c88581582231e82713ec2dcb83b4}

\begin{DoxyCompactList}\small\item\em Get left child's index. \end{DoxyCompactList}\item 
\hypertarget{a00692_ac516abac46c46b480cec49702d903d7b}{size\+\_\+t \hyperlink{a00692_ac516abac46c46b480cec49702d903d7b}{right} (size\+\_\+t \+\_\+i)}\label{a00692_ac516abac46c46b480cec49702d903d7b}

\begin{DoxyCompactList}\small\item\em Get right child's index. \end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
\subsubsection*{template$<$class Heap\+Entry, class Heap\+Interface = Heap\+Entry$>$class Open\+Mesh\+::\+Utils\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$}

An efficient, highly customizable heap.

The main difference (and performance boost) of this heap compared to e.\+g. the heap of the S\+T\+L is that here the 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 \hyperlink{a00692_a5a4198bf734a87481ee5fedc46f2eebd}{update(\+Heap\+Entry)} method.

This heap class is parameterized by two template arguments\+: \begin{DoxyItemize}
\item the class {\ttfamily Heap\+Entry}, that will be stored in the heap \item the Heap\+Interface telling the heap how to compare heap entries and how to store the heap positions in the heap entries.\end{DoxyItemize}
As an example how to use the class see declaration of class \hyperlink{a00482}{Decimater\+::\+Decimater\+T}.

\begin{DoxySeeAlso}{See also}
\hyperlink{a00690}{Heap\+Interface\+T} 
\end{DoxySeeAlso}


Definition at line 143 of file Heap\+T.\+hh.



\subsection{Member Function Documentation}
\hypertarget{a00692_a5a4198bf734a87481ee5fedc46f2eebd}{\index{Open\+Mesh\+::\+Utils\+::\+Heap\+T@{Open\+Mesh\+::\+Utils\+::\+Heap\+T}!update@{update}}
\index{update@{update}!Open\+Mesh\+::\+Utils\+::\+Heap\+T@{Open\+Mesh\+::\+Utils\+::\+Heap\+T}}
\subsubsection[{update}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Heap\+Entry , class Heap\+Interface  = Heap\+Entry$>$ void {\bf Open\+Mesh\+::\+Utils\+::\+Heap\+T}$<$ Heap\+Entry, Heap\+Interface $>$\+::update (
\begin{DoxyParamCaption}
\item[{Heap\+Entry}]{\+\_\+h}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{a00692_a5a4198bf734a87481ee5fedc46f2eebd}
update an entry\+: change the key and update the position to reestablish the heap property. 

Definition at line 253 of file Heap\+T.\+hh.



The documentation for this class was generated from the following file\+:\begin{DoxyCompactItemize}
\item 
libs\+\_\+required/\+Open\+Mesh/src/\+Open\+Mesh/\+Tools/\+Utils/\hyperlink{a01753}{Heap\+T.\+hh}\end{DoxyCompactItemize}
