Branch data     Line data    Source code

       1                 :            : // $Id: PriorityQueue.cc 6219 2008-10-01 05:39:07Z vern $
       2                 :            : //
       3                 :            : // See the file "COPYING" in the main distribution directory for copyright.
       4                 :            : 
       5                 :            : #include "config.h"
       6                 :            : 
       7                 :            : #include <stdio.h>
       8                 :            : #include <stdlib.h>
       9                 :            : 
      10                 :            : #include "PriorityQueue.h"
      11                 :            : #include "util.h"
      12                 :            : 
      13                 :          3 : PriorityQueue::PriorityQueue(int initial_size)
      14                 :            :         {
      15                 :          3 :         max_heap_size = initial_size;
      16                 :          3 :         heap = new PQ_Element*[max_heap_size];
      17                 :          3 :         peak_heap_size = heap_size = 0;
      18                 :          3 :         }
      19                 :            : 
      20                 :          1 : PriorityQueue::~PriorityQueue()
      21                 :            :         {
      22 [ -  + ][ #  # ]:          1 :         for ( int i = 0; i < heap_size; ++i )
      23 [ #  # ][ #  # ]:          0 :                 delete heap[i];
      24                 :            : 
      25 [ +  - ][ #  # ]:          1 :         delete [] heap;
      26                 :          1 :         }
      27                 :            : 
      28                 :      29819 : PQ_Element* PriorityQueue::Remove()
      29                 :            :         {
      30         [ +  + ]:      29819 :         if ( heap_size == 0 )
      31                 :          2 :                 return 0;
      32                 :            : 
      33                 :      29817 :         PQ_Element* top = heap[0];
      34                 :            : 
      35                 :      29817 :         --heap_size;
      36                 :      29817 :         SetElement(0, heap[heap_size]);
      37                 :      29817 :         BubbleDown(0);
      38                 :            : 
      39                 :      29817 :         top->SetOffset(-1);  // = not in heap
      40                 :      29819 :         return top;
      41                 :            :         }
      42                 :            : 
      43                 :       2310 : PQ_Element* PriorityQueue::Remove(PQ_Element* e)
      44                 :            :         {
      45 [ +  - ][ +  - ]:       2310 :         if ( e->Offset() < 0 || e->Offset() >= heap_size ||
         [ -  + ][ -  + ]
      46                 :            :              heap[e->Offset()] != e )
      47                 :          0 :                 return 0;       // not in heap
      48                 :            : 
      49                 :       2310 :         e->MinimizeTime();
      50                 :       2310 :         BubbleUp(e->Offset());
      51                 :            : 
      52                 :       2310 :         PQ_Element* e2 = Remove();
      53                 :            : 
      54         [ -  + ]:       2310 :         if ( e != e2 )
      55                 :          0 :                 internal_error("inconsistency in PriorityQueue::Remove");
      56                 :            : 
      57                 :       2310 :         return e2;
      58                 :            :         }
      59                 :            : 
      60                 :      29889 : int PriorityQueue::Add(PQ_Element* e)
      61                 :            :         {
      62                 :      29889 :         SetElement(heap_size, e);
      63                 :            : 
      64                 :      29889 :         BubbleUp(heap_size);
      65                 :            : 
      66         [ +  + ]:      29889 :         if ( ++heap_size > peak_heap_size )
      67                 :        601 :                 peak_heap_size = heap_size;
      68                 :            : 
      69         [ +  + ]:      29889 :         if ( heap_size >= max_heap_size )
      70                 :          9 :                 return Resize(max_heap_size * 2);
      71                 :            :         else
      72                 :      29889 :                 return 1;
      73                 :            :         }
      74                 :            : 
      75                 :          9 : int PriorityQueue::Resize(int new_size)
      76                 :            :         {
      77                 :          9 :         PQ_Element** tmp = new PQ_Element*[new_size];
      78         [ +  + ]:       1129 :         for ( int i = 0; i < max_heap_size; ++i )
      79                 :       1120 :                 tmp[i] = heap[i];
      80                 :            : 
      81         [ +  - ]:          9 :         delete [] heap;
      82                 :          9 :         heap = tmp;
      83                 :            : 
      84                 :          9 :         max_heap_size = new_size;
      85                 :            : 
      86                 :          9 :         return heap != 0;
      87                 :            :         }
      88                 :            : 
      89                 :      57735 : void PriorityQueue::BubbleUp(int bin)
      90                 :            :         {
      91         [ +  + ]:      57735 :         if ( bin == 0 )
      92                 :       2498 :                 return;
      93                 :            : 
      94                 :      55237 :         int p = Parent(bin);
      95         [ +  + ]:      55237 :         if ( heap[p]->Time() > heap[bin]->Time() )
      96                 :            :                 {
      97                 :      25536 :                 Swap(p, bin);
      98                 :      57735 :                 BubbleUp(p);
      99                 :            :                 }
     100                 :            :         }
     101                 :            : 
     102                 :     234451 : void PriorityQueue::BubbleDown(int bin)
     103                 :            :         {
     104                 :     234451 :         double v = heap[bin]->Time();
     105                 :            : 
     106                 :     234451 :         int l = LeftChild(bin);
     107                 :     234451 :         int r = RightChild(bin);
     108                 :            : 
     109         [ +  + ]:     234451 :         if ( l >= heap_size )
     110                 :      14146 :                 return;         // No children.
     111                 :            : 
     112         [ +  + ]:     220305 :         if ( r >= heap_size )
     113                 :            :                 { // Just a left child.
     114         [ +  + ]:        622 :                 if ( heap[l]->Time() < v )
     115                 :        622 :                         Swap(l, bin);
     116                 :            :                 }
     117                 :            : 
     118                 :            :         else
     119                 :            :                 {
     120                 :     219683 :                 double lv = heap[l]->Time();
     121                 :     219683 :                 double rv = heap[r]->Time();
     122                 :            : 
     123         [ +  + ]:     219683 :                 if ( lv < rv )
     124                 :            :                         {
     125         [ +  + ]:     100150 :                         if ( lv < v )
     126                 :            :                                 {
     127                 :      95493 :                                 Swap(l, bin);
     128                 :     100150 :                                 BubbleDown(l);
     129                 :            :                                 }
     130                 :            :                         }
     131                 :            : 
     132         [ +  + ]:     119533 :                 else if ( rv < v )
     133                 :            :                         {
     134                 :     109141 :                         Swap(r, bin);
     135                 :     234451 :                         BubbleDown(r);
     136                 :            :                         }
     137                 :            :                 }
     138                 :            :         }