LCOV - code coverage report
Current view: top level - src - PriorityQueue.h (source / functions) Hit Total Coverage
Test: app.info Lines: 23 28 82.1 %
Date: 2010-12-13 Functions: 11 16 68.8 %
Branches: 1 6 16.7 %

           Branch data     Line data    Source code
       1                 :            : // $Id: PriorityQueue.h 6219 2008-10-01 05:39:07Z vern $
       2                 :            : //
       3                 :            : // See the file "COPYING" in the main distribution directory for copyright.
       4                 :            : 
       5                 :            : #ifndef __PriorityQueue__
       6                 :            : #define __PriorityQueue__
       7                 :            : 
       8                 :            : #include <math.h>
       9                 :            : 
      10                 :            : class PriorityQueue;
      11                 :            : 
      12                 :            : class PQ_Element {
      13                 :            : public:
      14                 :      29889 :         PQ_Element(double t)    { time = t; offset = -1; }
      15 [ #  # ][ #  # ]:          0 :         virtual ~PQ_Element()   { }
      16                 :            : 
      17                 :     861186 :         double Time() const     { return time; }
      18                 :            : 
      19                 :       9240 :         int Offset() const      { return offset; }
      20                 :     550415 :         void SetOffset(int off) { offset = off; }
      21                 :            : 
      22                 :       2310 :         void MinimizeTime()     { time = -HUGE_VAL; }
      23                 :            : 
      24                 :            : protected:
      25                 :          0 :         PQ_Element()            { }
      26                 :            :         double time;
      27                 :            :         int offset;
      28                 :            : };
      29                 :            : 
      30                 :            : class PriorityQueue {
      31                 :            : public:
      32                 :            :         PriorityQueue(int initial_size = 16);
      33                 :            :         ~PriorityQueue();
      34                 :            : 
      35                 :            :         // Returns the top of queue, or nil if the queue is empty.
      36                 :      48810 :         PQ_Element* Top() const
      37                 :            :                 {
      38         [ -  + ]:      48810 :                 if ( heap_size == 0 )
      39                 :          0 :                         return 0;
      40                 :            :                 else
      41                 :      48810 :                         return heap[0];
      42                 :            :                 }
      43                 :            : 
      44                 :            :         // Removes (and returns) top of queue.  Returns nil if the queue
      45                 :            :         // is empty.
      46                 :            :         PQ_Element* Remove();
      47                 :            : 
      48                 :            :         // Removes element e.  Returns e, or nil if e wasn't in the queue.
      49                 :            :         // Note that e will be modified via MinimizeTime().
      50                 :            :         PQ_Element* Remove(PQ_Element* e);
      51                 :            : 
      52                 :            :         // Add a new element to the queue.  Returns 0 on failure (not enough
      53                 :            :         // memory to add the element), 1 on success.
      54                 :            :         int Add(PQ_Element* e);
      55                 :            : 
      56                 :          0 :         int Size() const        { return heap_size; }
      57                 :          0 :         int PeakSize() const    { return peak_heap_size; }
      58                 :            : 
      59                 :            : protected:
      60                 :            :         int Resize(int new_size);
      61                 :            : 
      62                 :            :         void BubbleUp(int bin);
      63                 :            :         void BubbleDown(int bin);
      64                 :            : 
      65                 :      55237 :         int Parent(int bin) const
      66                 :            :                 {
      67                 :      55237 :                 return bin >> 1;
      68                 :            :                 }
      69                 :            : 
      70                 :     468902 :         int LeftChild(int bin) const
      71                 :            :                 {
      72                 :     468902 :                 return bin << 1;
      73                 :            :                 }
      74                 :            : 
      75                 :     234451 :         int RightChild(int bin) const
      76                 :            :                 {
      77                 :     234451 :                 return LeftChild(bin) + 1;
      78                 :            :                 }
      79                 :            : 
      80                 :     520598 :         void SetElement(int bin, PQ_Element* e)
      81                 :            :                 {
      82                 :     520598 :                 heap[bin] = e;
      83                 :     520598 :                 e->SetOffset(bin);
      84                 :     520598 :                 }
      85                 :            : 
      86                 :     230446 :         void Swap(int bin1, int bin2)
      87                 :            :                 {
      88                 :     230446 :                 PQ_Element* t = heap[bin1];
      89                 :     230446 :                 SetElement(bin1, heap[bin2]);
      90                 :     230446 :                 SetElement(bin2, t);
      91                 :     230446 :                 }
      92                 :            : 
      93                 :            :         PQ_Element** heap;
      94                 :            :         int heap_size;
      95                 :            :         int peak_heap_size;
      96                 :            :         int max_heap_size;
      97                 :            : };
      98                 :            : 
      99                 :            : #endif

Generated by: LCOV version 1.8