SNAP Library 4.1, User Reference  2018-07-26 16:30:42
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
TMaxPriorityQueue< TVal > Class Template Reference

#include <priorityqueue.h>

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.

57  {
58  IAssertR(Size() > 0, "Attempt to query max priority of empty priority queue.");
59  return Priorities[0];
60  }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
template<class TVal>
void TMaxPriorityQueue< TVal >::GetPriorities ( THash< TVal, TFlt > &  Result)
inline

Definition at line 83 of file priorityqueue.h.

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

Definition at line 49 of file priorityqueue.h.

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  }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91
bool IsKey(const TKey &Key) const
Definition: hash.h:258
template<class TVal>
void TMaxPriorityQueue< TVal >::Insert ( const TVal &  X,
float  Priority 
)
inline

Definition at line 23 of file priorityqueue.h.

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

Definition at line 74 of file priorityqueue.h.

74  {
75  return Size() == 0;
76  }
template<class TVal>
int TMaxPriorityQueue< TVal >::Left ( int  i)
inlineprivate

Definition at line 95 of file priorityqueue.h.

95 { return i * 2 + 1; }
template<class TVal>
void TMaxPriorityQueue< TVal >::MaxHeapify ( int  i)
inlineprivate

Definition at line 106 of file priorityqueue.h.

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  }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void Swap(int i, int j)
Definition: priorityqueue.h:98
int Right(int i)
Definition: priorityqueue.h:96
void MaxHeapify(int i)
template<class TVal>
int TMaxPriorityQueue< TVal >::Parent ( int  i)
inlineprivate

Definition at line 94 of file priorityqueue.h.

94 { return (i + 1) / 2 - 1; }
template<class TVal>
TVal TMaxPriorityQueue< TVal >::PopMax ( )
inline

Definition at line 62 of file priorityqueue.h.

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);
68  ValToIndex.DelKey(maxVal);
69 
70  MaxHeapify(0);
71  return maxVal;
72  }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void DelKey(const TKey &Key)
Definition: hash.h:404
void Swap(int i, int j)
Definition: priorityqueue.h:98
TVec< TVal > IndexToVal
Definition: priorityqueue.h:92
void MaxHeapify(int i)
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91
void DelLast()
Removes the last element of the vector.
Definition: ds.h:665
template<class TVal>
int TMaxPriorityQueue< TVal >::Right ( int  i)
inlineprivate

Definition at line 96 of file priorityqueue.h.

96 { return i * 2 + 2; }
template<class TVal>
void TMaxPriorityQueue< TVal >::SetPriority ( const TVal &  X,
float  NewPriority 
)
inline

Definition at line 31 of file priorityqueue.h.

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  }
float GetPriority(const TVal &X)
Definition: priorityqueue.h:49
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
void Swap(int i, int j)
Definition: priorityqueue.h:98
int Parent(int i)
Definition: priorityqueue.h:94
void MaxHeapify(int i)
void Insert(const TVal &X, float Priority)
Definition: priorityqueue.h:23
THash< TVal, int > ValToIndex
Definition: priorityqueue.h:91
bool IsKey(const TKey &Key) const
Definition: hash.h:258
template<class TVal>
int TMaxPriorityQueue< TVal >::Size ( )
inline

Definition at line 78 of file priorityqueue.h.

78  {
79  return Priorities.Len();
80  }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
template<class TVal>
void TMaxPriorityQueue< TVal >::Swap ( int  i,
int  j 
)
inlineprivate

Definition at line 98 of file priorityqueue.h.

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

Member Data Documentation

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

Definition at line 92 of file priorityqueue.h.

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

Definition at line 90 of file priorityqueue.h.

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

Definition at line 91 of file priorityqueue.h.


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