Branch data     Line data    Source code

       1                 :            : #include <iostream>
       2                 :            : #include "std.h"
       3                 :            : #include "Heap.hpp"
       4                 :            : #include <string.h> /* for memcpy */
       5                 :            : 
       6                 :            : 
       7                 :     269664 : void Heap::swap(int i,int j)
       8                 :            : {
       9 [ +  - ][ +  - ]:     269664 :     heap_node tmp = ref(i);
      10                 :            : 
      11 [ +  - ][ +  - ]:     269664 :     ref(i) = ref(j);
      12         [ +  - ]:     269664 :     ref(j) = tmp;
      13                 :            : 
      14 [ +  - ][ +  - ]:     269664 :     ref(i).obj->setHeapPos(i);
      15 [ +  - ][ +  - ]:     269664 :     ref(j).obj->setHeapPos(j);
      16                 :     269664 : }
      17                 :            : 
      18                 :     490200 : void Heap::upheap(int i)
      19                 :            : {
      20         [ +  + ]:     490200 :     if( i==0 ) return;
      21                 :            : 
      22         [ +  + ]:     488652 :     if( ref(i).import > ref(parent(i)).import ) {
      23                 :     173820 :         swap(i,parent(i));
      24                 :     173820 :         upheap(parent(i));
      25                 :            :     }
      26                 :            : }
      27                 :            : 
      28                 :     143160 : void Heap::downheap(int i)
      29                 :            : {
      30         [ -  + ]:     143160 :     if (i>=size) return;        // perhaps just extracted the last
      31                 :            : 
      32                 :     143160 :     int largest = i,
      33                 :     143160 :         l = left(i),
      34                 :     143160 :         r = right(i);
      35                 :            : 
      36 [ +  + ][ +  + ]:     143160 :     if( l<size && ref(l).import > ref(largest).import ) largest = l;
                 [ +  + ]
      37 [ +  + ][ +  + ]:     143160 :     if( r<size && ref(r).import > ref(largest).import ) largest = r;
                 [ +  + ]
      38                 :            : 
      39         [ +  + ]:     143160 :     if( largest != i ) {
      40                 :      86568 :         swap(i,largest);
      41                 :      86568 :         downheap(largest);
      42                 :            :     }
      43                 :            : }
      44                 :            : 
      45                 :            : 
      46                 :            : 
      47                 :      91200 : void Heap::insert(Heapable *t,double v)
      48                 :            : {
      49         [ -  + ]:      91200 :     if( size == maxLength() )
      50                 :            :     {
      51                 :          0 :         std::cerr << "NOTE: Growing heap from " << size << " to " << 2*size << std::endl;
      52                 :          0 :         resize(2*size);
      53                 :            :     }
      54                 :            : 
      55                 :      91200 :     int i = size++;
      56                 :            : 
      57                 :      91200 :     ref(i).obj = t;
      58                 :      91200 :     ref(i).import = v;
      59                 :            : 
      60                 :      91200 :     ref(i).obj->setHeapPos(i);
      61                 :            : 
      62                 :      91200 :     upheap(i);
      63                 :      91200 : }
      64                 :            : 
      65                 :     272496 : void Heap::update(Heapable *t,double v)
      66                 :            : {
      67                 :     272496 :     int i = t->getHeapPos();
      68                 :            : 
      69         [ -  + ]:     272496 :     if( i >= size )
      70                 :            :     {
      71                 :          0 :         std::cerr << "WARNING: Attempting to update past end of heap!" << std::endl;
      72                 :          0 :         return;
      73                 :            :     }
      74         [ -  + ]:     272496 :     else if( i == NOT_IN_HEAP )
      75                 :            :     {
      76                 :          0 :         std::cerr << "WARNING: Attempting to update object not in heap!" << std::endl;
      77                 :          0 :         return;
      78                 :            :     }
      79                 :            : 
      80                 :     272496 :     float old=ref(i).import;
      81                 :     272496 :     ref(i).import = v;
      82                 :            : 
      83         [ +  + ]:     272496 :     if( v<old )
      84                 :      48696 :         downheap(i);
      85                 :            :     else
      86                 :     223800 :         upheap(i);
      87                 :            : }
      88                 :            : 
      89                 :            : 
      90                 :            : 
      91                 :       3264 : heap_node *Heap::extract()
      92                 :            : {
      93         [ -  + ]:       3264 :     if( size<1 ) return 0;
      94                 :            : 
      95                 :       3264 :     swap(0,size-1);
      96                 :       3264 :     size--;
      97                 :            : 
      98                 :       3264 :     downheap(0);
      99                 :            : 
     100                 :       3264 :     ref(size).obj->notInHeap();
     101                 :            : 
     102                 :       3264 :     return &ref(size);
     103                 :            : }
     104                 :            : 
     105                 :       6012 : heap_node *Heap::kill(int i)
     106                 :            : {
     107         [ -  + ]:       6012 :     if( i>=size )
     108                 :          0 :         std::cerr << "WARNING: Attempt to delete invalid heap node." << std::endl;
     109                 :            : 
     110                 :       6012 :     swap(i, size-1);
     111                 :       6012 :     size--;
     112                 :       6012 :     ref(size).obj->notInHeap();
     113                 :            : 
     114         [ +  + ]:       6012 :     if( ref(i).import < ref(size).import )
     115                 :       4632 :         downheap(i);
     116                 :            :     else
     117                 :       1380 :         upheap(i);
     118                 :            : 
     119                 :            : 
     120                 :       6012 :     return &ref(size);
     121 [ +  - ][ +  - ]:       1872 : }