TMaxPriorityQueue< TVal > Class Template Reference

#include <priorityqueue.h>

Collaboration diagram for TMaxPriorityQueue< TVal >:

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.

{}

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().

                         {
    IAssertR(Size() > 0, "Attempt to query max priority of empty priority queue.");
    return Priorities[0];
  }

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().

                                                 {
    for (int i = 0; i < Priorities.Len(); i++) {
      Result.AddDat(IndexToVal[i], Priorities[i]);
    }
  }

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().

                                   {
    if (ValToIndex.IsKey(X)) {
      return Priorities[ValToIndex.GetDat(X)];
    } else {
      return 0.0f; // Default value is 0.0
    }
  }

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().

                                             {
    ValToIndex.AddDat(X, IndexToVal.Len());
    IndexToVal.Add(X);
    // Priorities.Add(-INFINITY);
    Priorities.Add(INT_MIN);
    SetPriority(X, Priority);
  }

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().

                 {
    return Size() == 0;
  }

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().

{ 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 >::Right(), and TMaxPriorityQueue< TVal >::Swap().

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

                         {
    int largest = i;
    if (Left(i) < Priorities.Len() && Priorities[Left(i)] > Priorities[largest]) {
      largest = Left(i);
    }
    if (Right(i) < Priorities.Len() && Priorities[Right(i)] > Priorities[largest]) {
      largest = Right(i);
    }
    if (largest != i) {
      Swap(i, largest);
      MaxHeapify(largest);
    }
  }

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().

{ 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().

                {
    IAssertR(Size() > 0, "Attempt to query max priority of empty priority queue.");
    TVal maxVal = IndexToVal[0];
    Swap(0, Priorities.Len() - 1);
    Priorities.DelLast();
    IndexToVal.DelLast();
    ValToIndex.DelKey(maxVal);
    
    MaxHeapify(0);
    return maxVal;
  }

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().

{ 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().

                                                     {
    if (!ValToIndex.IsKey(X)) {
      Insert(X, NewPriority);
    } else {
      int i = ValToIndex.GetDat(X);
      if (NewPriority >= GetPriority(X)) {
        Priorities[i] = NewPriority;
        while (i > 0 && Priorities[i] > Priorities[Parent(i)]) {
          Swap(i, Parent(i));
          i = Parent(i);
        }
      } else {
        Priorities[i] = NewPriority;
        MaxHeapify(i);
      }
    }
  }

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().

             {
    return Priorities.Len();
  }

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(), and TVec< TVal, TSizeTy >::Swap().

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

                          {
    Priorities.Swap(i, j);
    IndexToVal.Swap(i, j);
    ValToIndex.GetDat(IndexToVal[i]) = i;
    ValToIndex.GetDat(IndexToVal[j]) = j;
  }

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(), and TMaxPriorityQueue< TVal >::PopMax().

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 >::PopMax(), TMaxPriorityQueue< TVal >::SetPriority(), and TMaxPriorityQueue< TVal >::Size().

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(), and TMaxPriorityQueue< TVal >::SetPriority().

---

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

• glib-core/priorityqueue.h