SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Public Member Functions | Private Member Functions | Private Attributes | List of all members
TMaxPriorityQueue< TVal > Class Template Reference

#include <priorityqueue.h>

Collaboration diagram for TMaxPriorityQueue< TVal >:
Collaboration graph
[legend]

Public Member Functions

 TMaxPriorityQueue ()
 
void Insert (const TVal &X, float Priority)
 
void SetPriority (const TVal &X, float NewPriority)
 
float GetPriority (const TVal &X)
 
float GetMaxPriority ()
 
TVal PopMax ()
 
bool IsEmpty ()
 
int Size ()
 
void GetPriorities (THash< TVal, TFlt > &Result)
 

Private Member Functions

int Parent (int i)
 
int Left (int i)
 
int Right (int i)
 
void Swap (int i, int j)
 
void MaxHeapify (int i)
 

Private Attributes

TFltV Priorities
 
THash< TVal, int > ValToIndex
 
TVec< TVal > IndexToVal
 

Detailed Description

template<class TVal>
class TMaxPriorityQueue< TVal >

Definition at line 19 of file priorityqueue.h.

Constructor & Destructor Documentation

template<class TVal>
TMaxPriorityQueue< TVal >::TMaxPriorityQueue ( )
inline

Definition at line 21 of file priorityqueue.h.

21 {}

Member Function Documentation

template<class TVal>
float TMaxPriorityQueue< TVal >::GetMaxPriority ( )
inline

Definition at line 57 of file priorityqueue.h.

References IAssertR, TMaxPriorityQueue< TVal >::Priorities, and TMaxPriorityQueue< TVal >::Size().

Referenced by anonymous_namespace{randwalk.h}::ApproxContributionsBalanced().

57  {
58  IAssertR(Size() > 0, "Attempt to query max priority of empty priority queue.");
59  return Priorities[0];
60  }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
void TMaxPriorityQueue< TVal >::GetPriorities ( THash< TVal, TFlt > &  Result)
inline

Definition at line 83 of file priorityqueue.h.

References THash< TKey, TDat, THashFunc >::AddDat(), TMaxPriorityQueue< TVal >::IndexToVal, TVec< TVal, TSizeTy >::Len(), and TMaxPriorityQueue< TVal >::Priorities.

Referenced by anonymous_namespace{randwalk.h}::ApproxContributionsBalanced().

83  {
84  for (int i = 0; i < Priorities.Len(); i++) {
85  Result.AddDat(IndexToVal[i], Priorities[i]);
86  }
87  }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TMaxPriorityQueue::IndexToVal
TVec< TVal > IndexToVal
Definition: priorityqueue.h:92
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
float TMaxPriorityQueue< TVal >::GetPriority ( const TVal &  X)
inline

Definition at line 49 of file priorityqueue.h.

References THash< TKey, TDat, THashFunc >::GetDat(), THash< TKey, TDat, THashFunc >::IsKey(), TMaxPriorityQueue< TVal >::Priorities, and TMaxPriorityQueue< TVal >::ValToIndex.

Referenced by anonymous_namespace{randwalk.h}::ApproxContributionsBalanced(), and TMaxPriorityQueue< TVal >::SetPriority().

49  {
50  if (ValToIndex.IsKey(X)) {
51  return Priorities[ValToIndex.GetDat(X)];
52  } else {
53  return 0.0f; // Default value is 0.0
54  }
55  }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TMaxPriorityQueue::ValToIndex
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
void TMaxPriorityQueue< TVal >::Insert ( const TVal &  X,
float  Priority 
)
inline

Definition at line 23 of file priorityqueue.h.

References TVec< TVal, TSizeTy >::Add(), THash< TKey, TDat, THashFunc >::AddDat(), TMaxPriorityQueue< TVal >::IndexToVal, TVec< TVal, TSizeTy >::Len(), TMaxPriorityQueue< TVal >::Priorities, TMaxPriorityQueue< TVal >::SetPriority(), and TMaxPriorityQueue< TVal >::ValToIndex.

Referenced by anonymous_namespace{randwalk.h}::ApproxContributionsBalanced(), and TMaxPriorityQueue< TVal >::SetPriority().

23  {
24  ValToIndex.AddDat(X, IndexToVal.Len());
25  IndexToVal.Add(X);
26  // Priorities.Add(-INFINITY);
27  Priorities.Add(INT_MIN);
28  SetPriority(X, Priority);
29  }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TMaxPriorityQueue::IndexToVal
TVec< TVal > IndexToVal
Definition: priorityqueue.h:92
TMaxPriorityQueue::SetPriority
void SetPriority(const TVal &X, float NewPriority)
Definition: priorityqueue.h:31
TMaxPriorityQueue::ValToIndex
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
bool TMaxPriorityQueue< TVal >::IsEmpty ( )
inline

Definition at line 74 of file priorityqueue.h.

References TMaxPriorityQueue< TVal >::Size().

Referenced by anonymous_namespace{randwalk.h}::ApproxContributionsBalanced().

74  {
75  return Size() == 0;
76  }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
int TMaxPriorityQueue< TVal >::Left ( int  i)
inlineprivate

Definition at line 95 of file priorityqueue.h.

Referenced by TMaxPriorityQueue< TVal >::MaxHeapify().

95 { return i * 2 + 1; }

Here is the caller graph for this function:

template<class TVal>
void TMaxPriorityQueue< TVal >::MaxHeapify ( int  i)
inlineprivate

Definition at line 106 of file priorityqueue.h.

References TMaxPriorityQueue< TVal >::Left(), TVec< TVal, TSizeTy >::Len(), TMaxPriorityQueue< TVal >::Priorities, TMaxPriorityQueue< TVal >::Right(), and TMaxPriorityQueue< TVal >::Swap().

Referenced by TMaxPriorityQueue< TVal >::PopMax(), and TMaxPriorityQueue< TVal >::SetPriority().

106  {
107  int largest = i;
108  if (Left(i) < Priorities.Len() && Priorities[Left(i)] > Priorities[largest]) {
109  largest = Left(i);
110  }
111  if (Right(i) < Priorities.Len() && Priorities[Right(i)] > Priorities[largest]) {
112  largest = Right(i);
113  }
114  if (largest != i) {
115  Swap(i, largest);
116  MaxHeapify(largest);
117  }
118  }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TMaxPriorityQueue::Swap
void Swap(int i, int j)
Definition: priorityqueue.h:98
TMaxPriorityQueue::Right
int Right(int i)
Definition: priorityqueue.h:96
TMaxPriorityQueue::MaxHeapify
void MaxHeapify(int i)
Definition: priorityqueue.h:106

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
int TMaxPriorityQueue< TVal >::Parent ( int  i)
inlineprivate

Definition at line 94 of file priorityqueue.h.

Referenced by TMaxPriorityQueue< TVal >::SetPriority().

94 { return (i + 1) / 2 - 1; }

Here is the caller graph for this function:

template<class TVal>
TVal TMaxPriorityQueue< TVal >::PopMax ( )
inline

Definition at line 62 of file priorityqueue.h.

References THash< TKey, TDat, THashFunc >::DelKey(), TVec< TVal, TSizeTy >::DelLast(), IAssertR, TMaxPriorityQueue< TVal >::IndexToVal, TVec< TVal, TSizeTy >::Len(), TMaxPriorityQueue< TVal >::MaxHeapify(), TMaxPriorityQueue< TVal >::Priorities, TMaxPriorityQueue< TVal >::Size(), TMaxPriorityQueue< TVal >::Swap(), and TMaxPriorityQueue< TVal >::ValToIndex.

Referenced by anonymous_namespace{randwalk.h}::ApproxContributionsBalanced().

62  {
63  IAssertR(Size() > 0, "Attempt to query max priority of empty priority queue.");
64  TVal maxVal = IndexToVal[0];
65  Swap(0, Priorities.Len() - 1);
66  Priorities.DelLast();
67  IndexToVal.DelLast();
68  ValToIndex.DelKey(maxVal);
69 
70  MaxHeapify(0);
71  return maxVal;
72  }
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:404
TMaxPriorityQueue::Swap
void Swap(int i, int j)
Definition: priorityqueue.h:98
TMaxPriorityQueue::IndexToVal
TVec< TVal > IndexToVal
Definition: priorityqueue.h:92
TMaxPriorityQueue::MaxHeapify
void MaxHeapify(int i)
Definition: priorityqueue.h:106
TMaxPriorityQueue::ValToIndex
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91
TVec::DelLast
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
int TMaxPriorityQueue< TVal >::Right ( int  i)
inlineprivate

Definition at line 96 of file priorityqueue.h.

Referenced by TMaxPriorityQueue< TVal >::MaxHeapify().

96 { return i * 2 + 2; }

Here is the caller graph for this function:

template<class TVal>
void TMaxPriorityQueue< TVal >::SetPriority ( const TVal &  X,
float  NewPriority 
)
inline

Definition at line 31 of file priorityqueue.h.

References THash< TKey, TDat, THashFunc >::GetDat(), TMaxPriorityQueue< TVal >::GetPriority(), TMaxPriorityQueue< TVal >::Insert(), THash< TKey, TDat, THashFunc >::IsKey(), TMaxPriorityQueue< TVal >::MaxHeapify(), TMaxPriorityQueue< TVal >::Parent(), TMaxPriorityQueue< TVal >::Priorities, TMaxPriorityQueue< TVal >::Swap(), and TMaxPriorityQueue< TVal >::ValToIndex.

Referenced by anonymous_namespace{randwalk.h}::ApproxContributionsBalanced(), and TMaxPriorityQueue< TVal >::Insert().

31  {
32  if (!ValToIndex.IsKey(X)) {
33  Insert(X, NewPriority);
34  } else {
35  int i = ValToIndex.GetDat(X);
36  if (NewPriority >= GetPriority(X)) {
37  Priorities[i] = NewPriority;
38  while (i > 0 && Priorities[i] > Priorities[Parent(i)]) {
39  Swap(i, Parent(i));
40  i = Parent(i);
41  }
42  } else {
43  Priorities[i] = NewPriority;
44  MaxHeapify(i);
45  }
46  }
47  }
TMaxPriorityQueue::GetPriority
float GetPriority(const TVal &X)
Definition: priorityqueue.h:49
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TMaxPriorityQueue::Swap
void Swap(int i, int j)
Definition: priorityqueue.h:98
TMaxPriorityQueue::Parent
int Parent(int i)
Definition: priorityqueue.h:94
TMaxPriorityQueue::MaxHeapify
void MaxHeapify(int i)
Definition: priorityqueue.h:106
TMaxPriorityQueue::Insert
void Insert(const TVal &X, float Priority)
Definition: priorityqueue.h:23
TMaxPriorityQueue::ValToIndex
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
int TMaxPriorityQueue< TVal >::Size ( )
inline

Definition at line 78 of file priorityqueue.h.

References TVec< TVal, TSizeTy >::Len(), and TMaxPriorityQueue< TVal >::Priorities.

Referenced by TMaxPriorityQueue< TVal >::GetMaxPriority(), TMaxPriorityQueue< TVal >::IsEmpty(), and TMaxPriorityQueue< TVal >::PopMax().

78  {
79  return Priorities.Len();
80  }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TVal>
void TMaxPriorityQueue< TVal >::Swap ( int  i,
int  j 
)
inlineprivate

Definition at line 98 of file priorityqueue.h.

References THash< TKey, TDat, THashFunc >::GetDat(), TMaxPriorityQueue< TVal >::IndexToVal, TMaxPriorityQueue< TVal >::Priorities, TVec< TVal, TSizeTy >::Swap(), and TMaxPriorityQueue< TVal >::ValToIndex.

Referenced by TMaxPriorityQueue< TVal >::MaxHeapify(), TMaxPriorityQueue< TVal >::PopMax(), and TMaxPriorityQueue< TVal >::SetPriority().

98  {
99  Priorities.Swap(i, j);
100  IndexToVal.Swap(i, j);
101  ValToIndex.GetDat(IndexToVal[i]) = i;
102  ValToIndex.GetDat(IndexToVal[j]) = j;
103  }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
TMaxPriorityQueue::IndexToVal
TVec< TVal > IndexToVal
Definition: priorityqueue.h:92
TMaxPriorityQueue::ValToIndex
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

template<class TVal>
TVec<TVal> TMaxPriorityQueue< TVal >::IndexToVal
private

Definition at line 92 of file priorityqueue.h.

Referenced by TMaxPriorityQueue< TVal >::GetPriorities(), TMaxPriorityQueue< TVal >::Insert(), TMaxPriorityQueue< TVal >::PopMax(), and TMaxPriorityQueue< TVal >::Swap().

template<class TVal>
TFltV TMaxPriorityQueue< TVal >::Priorities
private

Definition at line 90 of file priorityqueue.h.

Referenced by TMaxPriorityQueue< TVal >::GetMaxPriority(), TMaxPriorityQueue< TVal >::GetPriorities(), TMaxPriorityQueue< TVal >::GetPriority(), TMaxPriorityQueue< TVal >::Insert(), TMaxPriorityQueue< TVal >::MaxHeapify(), TMaxPriorityQueue< TVal >::PopMax(), TMaxPriorityQueue< TVal >::SetPriority(), TMaxPriorityQueue< TVal >::Size(), and TMaxPriorityQueue< TVal >::Swap().

template<class TVal>
THash<TVal, int> TMaxPriorityQueue< TVal >::ValToIndex
private

Definition at line 91 of file priorityqueue.h.

Referenced by TMaxPriorityQueue< TVal >::GetPriority(), TMaxPriorityQueue< TVal >::Insert(), TMaxPriorityQueue< TVal >::PopMax(), TMaxPriorityQueue< TVal >::SetPriority(), and TMaxPriorityQueue< TVal >::Swap().

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