HOG2
Classes | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
Treap< key > Class Template Reference

#include <Treap.h>

Classes

struct  TreapNode
 

Public Member Functions

 Treap ()
 
void Reset ()
 
void Add (key k)
 
key RemoveSmallest ()
 
bool Remove (key &k)
 
void Iterate (double, double, const std::function< void(const key &)> &)
 
const key & Peek ()
 
void Print ()
 
size_t Size ()
 
size_t GetHeight ()
 
key GetNode (size_t)
 
void Verify ()
 

Private Types

typedef size_t TreapNodePtr
 

Private Member Functions

TreapNodePtr GetNode ()
 
void Recycle (TreapNodePtr n)
 
void Insert (TreapNodePtr n, TreapNodePtr head)
 
void HeapifyUp (TreapNodePtr n)
 
void RotateLeftChildUp (TreapNodePtr n)
 
void RotateRightChildUp (TreapNodePtr n)
 
void PrintHelper (TreapNodePtr n, int depth)
 
void VerifyHelper (TreapNodePtr n)
 
void Remove (TreapNodePtr n)
 
size_t GetHeightHelper (TreapNodePtr n)
 
void IterateHelper (TreapNodePtr n, double, double, const std::function< void(const key &)> &)
 

Private Attributes

const size_t nullTreapNode = -1
 
const size_t rootOfTree = -2
 
TreapNodePtr head
 
std::vector< TreapNode > nodes
 

Detailed Description

template<class key>
class Treap< key >

Definition at line 14 of file Treap.h.

Member Typedef Documentation

◆ TreapNodePtr

template<class key >
typedef size_t Treap< key >::TreapNodePtr
private

Definition at line 22 of file Treap.h.

Constructor & Destructor Documentation

◆ Treap()

template<class key >
Treap< key >::Treap ( )
inline

Definition at line 41 of file Treap.h.

Member Function Documentation

◆ Add()

template<class key >
void Treap< key >::Add ( key  k)

Definition at line 64 of file Treap.h.

◆ GetHeight()

template<class key >
size_t Treap< key >::GetHeight

Definition at line 461 of file Treap.h.

◆ GetHeightHelper()

template<class key >
size_t Treap< key >::GetHeightHelper ( TreapNodePtr  n)
private

Definition at line 467 of file Treap.h.

◆ GetNode() [1/2]

template<class key >
Treap< key >::TreapNodePtr Treap< key >::GetNode
private

Definition at line 198 of file Treap.h.

◆ GetNode() [2/2]

template<class key >
key Treap< key >::GetNode ( size_t  which)

Definition at line 455 of file Treap.h.

◆ HeapifyUp()

template<class key >
void Treap< key >::HeapifyUp ( TreapNodePtr  n)
private

Definition at line 82 of file Treap.h.

◆ Insert()

template<class key >
void Treap< key >::Insert ( TreapNodePtr  n,
TreapNodePtr  head 
)
private

Definition at line 168 of file Treap.h.

◆ Iterate()

template<class key >
void Treap< key >::Iterate ( double  low,
double  high,
const std::function< void(const key &)> &  f 
)

Definition at line 290 of file Treap.h.

◆ IterateHelper()

template<class key >
void Treap< key >::IterateHelper ( TreapNodePtr  n,
double  low,
double  high,
const std::function< void(const key &)> &  f 
)
private

Definition at line 296 of file Treap.h.

◆ Peek()

template<class key >
const key & Treap< key >::Peek

Definition at line 313 of file Treap.h.

◆ Print()

template<class key >
void Treap< key >::Print

Definition at line 403 of file Treap.h.

◆ PrintHelper()

template<class key >
void Treap< key >::PrintHelper ( TreapNodePtr  n,
int  depth 
)
private

Definition at line 410 of file Treap.h.

◆ Recycle()

template<class key >
void Treap< key >::Recycle ( TreapNodePtr  n)
private

Definition at line 215 of file Treap.h.

◆ Remove() [1/2]

template<class key >
bool Treap< key >::Remove ( key &  k)

Definition at line 253 of file Treap.h.

◆ Remove() [2/2]

template<class key >
void Treap< key >::Remove ( TreapNodePtr  n)
private

Definition at line 324 of file Treap.h.

◆ RemoveSmallest()

template<class key >
key Treap< key >::RemoveSmallest

Definition at line 277 of file Treap.h.

◆ Reset()

template<class key >
void Treap< key >::Reset

Definition at line 57 of file Treap.h.

◆ RotateLeftChildUp()

template<class key >
void Treap< key >::RotateLeftChildUp ( TreapNodePtr  n)
private

Definition at line 102 of file Treap.h.

◆ RotateRightChildUp()

template<class key >
void Treap< key >::RotateRightChildUp ( TreapNodePtr  n)
private

Definition at line 135 of file Treap.h.

◆ Size()

template<class key >
size_t Treap< key >::Size

Definition at line 449 of file Treap.h.

◆ Verify()

template<class key >
void Treap< key >::Verify

Definition at line 424 of file Treap.h.

◆ VerifyHelper()

template<class key >
void Treap< key >::VerifyHelper ( TreapNodePtr  n)
private

Definition at line 432 of file Treap.h.

Member Data Documentation

◆ head

template<class key >
TreapNodePtr Treap< key >::head
private

Definition at line 25 of file Treap.h.

◆ nodes

template<class key >
std::vector<TreapNode> Treap< key >::nodes
private

Definition at line 27 of file Treap.h.

◆ nullTreapNode

template<class key >
const size_t Treap< key >::nullTreapNode = -1
private

Definition at line 23 of file Treap.h.

◆ rootOfTree

template<class key >
const size_t Treap< key >::rootOfTree = -2
private

Definition at line 24 of file Treap.h.

The documentation for this class was generated from the following file:
Generated by   doxygen 1.8.17