\hypertarget{a08232}{}\section{A\+CG\+:\+:HeapT$<$ Heap\+Entry, Heap\+Interface $>$ Class Template Reference}
\label{a08232}\index{A\+C\+G\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$@{A\+C\+G\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$}}


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

Inheritance diagram for A\+CG\+:\+:HeapT$<$ Heap\+Entry, Heap\+Interface $>$\+:\begin{figure}[H]
\begin{center}
\leavevmode
\includegraphics[height=2.000000cm]{a08232}
\end{center}
\end{figure}
\subsection*{Public Types}
\begin{DoxyCompactItemize}
\item 
\mbox{\Hypertarget{a08232_a277c1530acc11fd7d7920a4b5d9c27d3}\label{a08232_a277c1530acc11fd7d7920a4b5d9c27d3}} 
typedef std\+::vector$<$ Heap\+Entry $>$ {\bfseries Base}
\end{DoxyCompactItemize}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item 
\mbox{\Hypertarget{a08232_a61294d7b3ac96f2f12504211123c1bfa}\label{a08232_a61294d7b3ac96f2f12504211123c1bfa}} 
\hyperlink{a08232_a61294d7b3ac96f2f12504211123c1bfa}{HeapT} ()
\begin{DoxyCompactList}\small\item\em Constructor. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a0da742f2ad1b15573ba81828ecf64b15}\label{a08232_a0da742f2ad1b15573ba81828ecf64b15}} 
\hyperlink{a08232_a0da742f2ad1b15573ba81828ecf64b15}{HeapT} (const Heap\+Interface \&\+\_\+interface)
\begin{DoxyCompactList}\small\item\em Construct with a given {\ttfamily Heap\+Iterface}. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_adcfe4c6df9c9da2986414cdef839645b}\label{a08232_adcfe4c6df9c9da2986414cdef839645b}} 
\hyperlink{a08232_adcfe4c6df9c9da2986414cdef839645b}{$\sim$\+HeapT} ()
\begin{DoxyCompactList}\small\item\em Destructor. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a98d3dea1f49362d1bd5cff8fd1664cbc}\label{a08232_a98d3dea1f49362d1bd5cff8fd1664cbc}} 
void \hyperlink{a08232_a98d3dea1f49362d1bd5cff8fd1664cbc}{clear} ()
\begin{DoxyCompactList}\small\item\em clear the heap \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_ad709062d6808618dd40cb42d209a5987}\label{a08232_ad709062d6808618dd40cb42d209a5987}} 
bool \hyperlink{a08232_ad709062d6808618dd40cb42d209a5987}{empty} ()
\begin{DoxyCompactList}\small\item\em is heap empty? \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a8e293187d069ef6d10bb7778cedbb93d}\label{a08232_a8e293187d069ef6d10bb7778cedbb93d}} 
unsigned int \hyperlink{a08232_a8e293187d069ef6d10bb7778cedbb93d}{size} ()
\begin{DoxyCompactList}\small\item\em returns the size of heap \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_ae4a14733513b75c349af8283a4ac3fbd}\label{a08232_ae4a14733513b75c349af8283a4ac3fbd}} 
void \hyperlink{a08232_ae4a14733513b75c349af8283a4ac3fbd}{reserve} (unsigned int \+\_\+n)
\begin{DoxyCompactList}\small\item\em reserve space for \+\_\+n entries \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a76cca23465f406eeca9ce36566cd6c67}\label{a08232_a76cca23465f406eeca9ce36566cd6c67}} 
void \hyperlink{a08232_a76cca23465f406eeca9ce36566cd6c67}{reset\+\_\+heap\+\_\+position} (Heap\+Entry \+\_\+h)
\begin{DoxyCompactList}\small\item\em reset heap position to -\/1 (not in heap) \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a3c6b5bf6193c0a6a30e585356b306ed2}\label{a08232_a3c6b5bf6193c0a6a30e585356b306ed2}} 
bool \hyperlink{a08232_a3c6b5bf6193c0a6a30e585356b306ed2}{is\+\_\+stored} (Heap\+Entry \+\_\+h)
\begin{DoxyCompactList}\small\item\em is an entry in the heap? \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_ab37fa6947306fd8431f8c92a7f7ca884}\label{a08232_ab37fa6947306fd8431f8c92a7f7ca884}} 
void \hyperlink{a08232_ab37fa6947306fd8431f8c92a7f7ca884}{insert} (Heap\+Entry \+\_\+h)
\begin{DoxyCompactList}\small\item\em insert the entry \+\_\+h \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_ae06d55fb2812a55c6c2f5076ca3dd789}\label{a08232_ae06d55fb2812a55c6c2f5076ca3dd789}} 
Heap\+Entry \hyperlink{a08232_ae06d55fb2812a55c6c2f5076ca3dd789}{front} ()
\begin{DoxyCompactList}\small\item\em get the first entry \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a5e30153db88e02f89b0e47949479792a}\label{a08232_a5e30153db88e02f89b0e47949479792a}} 
void \hyperlink{a08232_a5e30153db88e02f89b0e47949479792a}{pop\+\_\+front} ()
\begin{DoxyCompactList}\small\item\em delete the first entry \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_ac6cbbfe2bbe8ad25ae29318a2f76b2b6}\label{a08232_ac6cbbfe2bbe8ad25ae29318a2f76b2b6}} 
void \hyperlink{a08232_ac6cbbfe2bbe8ad25ae29318a2f76b2b6}{remove} (Heap\+Entry \+\_\+h)
\begin{DoxyCompactList}\small\item\em remove an entry \end{DoxyCompactList}\item 
void \hyperlink{a08232_a7d1277508ebf0bf26eab77f8b1aff2c4}{update} (Heap\+Entry \+\_\+h)
\item 
\mbox{\Hypertarget{a08232_ab109caa6f8b6da5acf87d8ffa6588790}\label{a08232_ab109caa6f8b6da5acf87d8ffa6588790}} 
bool \hyperlink{a08232_ab109caa6f8b6da5acf87d8ffa6588790}{check} ()
\begin{DoxyCompactList}\small\item\em check heap condition \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Private Types}
\begin{DoxyCompactItemize}
\item 
\mbox{\Hypertarget{a08232_a361037a521f50fd3ff72980e2dfd8efe}\label{a08232_a361037a521f50fd3ff72980e2dfd8efe}} 
typedef std\+::vector$<$ Heap\+Entry $>$ {\bfseries Heap\+Vector}
\end{DoxyCompactItemize}
\subsection*{Private Member Functions}
\begin{DoxyCompactItemize}
\item 
\mbox{\Hypertarget{a08232_a94f468a9fe4deceaf2086fa478710df4}\label{a08232_a94f468a9fe4deceaf2086fa478710df4}} 
void \hyperlink{a08232_a94f468a9fe4deceaf2086fa478710df4}{upheap} (unsigned int \+\_\+idx)
\begin{DoxyCompactList}\small\item\em Upheap. Establish heap property. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_abe9af5d9fc16146e74f7ca4e0199c4f3}\label{a08232_abe9af5d9fc16146e74f7ca4e0199c4f3}} 
void \hyperlink{a08232_abe9af5d9fc16146e74f7ca4e0199c4f3}{downheap} (unsigned int \+\_\+idx)
\begin{DoxyCompactList}\small\item\em Downheap. Establish heap property. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a33306ce9f5746d5439430e6a5f222477}\label{a08232_a33306ce9f5746d5439430e6a5f222477}} 
Heap\+Entry \hyperlink{a08232_a33306ce9f5746d5439430e6a5f222477}{entry} (unsigned int \+\_\+idx)
\begin{DoxyCompactList}\small\item\em Get the entry at index \+\_\+idx. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_acb01f8df0178d41a2b668c3774bb547a}\label{a08232_acb01f8df0178d41a2b668c3774bb547a}} 
void \hyperlink{a08232_acb01f8df0178d41a2b668c3774bb547a}{entry} (unsigned int \+\_\+idx, Heap\+Entry \+\_\+h)
\begin{DoxyCompactList}\small\item\em Set entry \+\_\+h to index \+\_\+idx and update \+\_\+h\textquotesingle{}s heap position. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a1d29f453970327a5e2fdd4dfc25e48f5}\label{a08232_a1d29f453970327a5e2fdd4dfc25e48f5}} 
unsigned int \hyperlink{a08232_a1d29f453970327a5e2fdd4dfc25e48f5}{parent} (unsigned int \+\_\+i)
\begin{DoxyCompactList}\small\item\em Get parent\textquotesingle{}s index. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a8d5d053eef5fd2825aad7402b0fd5348}\label{a08232_a8d5d053eef5fd2825aad7402b0fd5348}} 
unsigned int \hyperlink{a08232_a8d5d053eef5fd2825aad7402b0fd5348}{left} (unsigned int \+\_\+i)
\begin{DoxyCompactList}\small\item\em Get left child\textquotesingle{}s index. \end{DoxyCompactList}\item 
\mbox{\Hypertarget{a08232_a863b11b618cdb9fdb53b086d6aa7dc39}\label{a08232_a863b11b618cdb9fdb53b086d6aa7dc39}} 
unsigned int \hyperlink{a08232_a863b11b618cdb9fdb53b086d6aa7dc39}{right} (unsigned int \+\_\+i)
\begin{DoxyCompactList}\small\item\em Get right child\textquotesingle{}s index. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Private Attributes}
\begin{DoxyCompactItemize}
\item 
\mbox{\Hypertarget{a08232_af3740bc63532eb37d6940c5e00f217ad}\label{a08232_af3740bc63532eb37d6940c5e00f217ad}} 
Heap\+Interface \hyperlink{a08232_af3740bc63532eb37d6940c5e00f217ad}{interface\+\_\+}
\begin{DoxyCompactList}\small\item\em Instance of Heap\+Interface. \end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
\subsubsection*{template$<$class Heap\+Entry, class Heap\+Interface = Heap\+Entry$>$\newline
class A\+C\+G\+::\+Heap\+T$<$ Heap\+Entry, Heap\+Interface $>$}

An efficient, highly customizable heap.

The main difference (and performace boost) of this heap compared to e.\+g. the heap of the S\+TL is that here to positions of the heap\textquotesingle{}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{a08232_a7d1277508ebf0bf26eab77f8b1aff2c4}{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}


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



\subsection{Member Function Documentation}
\mbox{\Hypertarget{a08232_a7d1277508ebf0bf26eab77f8b1aff2c4}\label{a08232_a7d1277508ebf0bf26eab77f8b1aff2c4}} 
\index{A\+C\+G\+::\+HeapT@{A\+C\+G\+::\+HeapT}!update@{update}}
\index{update@{update}!A\+C\+G\+::\+HeapT@{A\+C\+G\+::\+HeapT}}
\subsubsection{\texorpdfstring{update()}{update()}}
{\footnotesize\ttfamily template$<$class Heap\+Entry , class Heap\+Interface  = Heap\+Entry$>$ \\
void \hyperlink{a08232}{A\+C\+G\+::\+HeapT}$<$ Heap\+Entry, Heap\+Interface $>$\+::update (\begin{DoxyParamCaption}\item[{Heap\+Entry}]{\+\_\+h }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [inline]}}

update an entry\+: change the key and update the position to reestablish the heap property. 

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



The documentation for this class was generated from the following file\+:\begin{DoxyCompactItemize}
\item 
Open\+Flipper/libs\+\_\+required/\+A\+C\+G/\+Utils/Heap\+T.\+hh\end{DoxyCompactItemize}
