Branch data     Line data    Source code

       1                 :            : #ifndef GFXTOOLS_HEAP_INCLUDED // -*- C++ -*-
       2                 :            : #define GFXTOOLS_HEAP_INCLUDED
       3                 :            : 
       4                 :            : #include "Array.h"
       5                 :            : 
       6                 :            : #define NOT_IN_HEAP -47
       7                 :            : 
       8                 :            : //
       9                 :            : //
      10                 :            : // This file extracted from Terra
      11                 :            : //
      12                 :            : //
      13                 :            : 
      14                 :            : class Heapable
      15                 :            : {
      16                 :            : private:
      17                 :            :     int token;
      18                 :            : 
      19                 :            : public:
      20                 :      30400 :     Heapable() { notInHeap(); }
      21                 :            : 
      22                 :     124324 :     inline int isInHeap() { return token!=NOT_IN_HEAP; }
      23                 :      16746 :     inline void notInHeap() { token = NOT_IN_HEAP; }
      24                 :      92836 :     inline int getHeapPos() { return token; }
      25                 :     630528 :     inline void setHeapPos(int t) { token=t; }
      26                 :            : };
      27                 :            : 
      28                 :            : 
      29                 :            : class heap_node {
      30                 :            : public:
      31                 :            :     double import;
      32                 :            :     Heapable *obj;
      33                 :            : 
      34                 :      15200 :     heap_node() { obj=NULL; import=0.0; }
      35                 :            :     heap_node(Heapable *t, double i=0.0) { obj=t; import=i; }
      36                 :     269664 :     heap_node(const heap_node& h) { import=h.import; obj=h.obj; }
      37                 :            : };
      38                 :            : 
      39                 :            : 
      40                 :            : 
      41                 :            : class Heap : public array<heap_node> {
      42                 :            : 
      43                 :            :     //
      44                 :            :     // The actual size of the heap.  array::length()
      45                 :            :     // simply returns the amount of allocated space
      46                 :            :     int size;
      47                 :            : 
      48                 :            :     void swap(int i, int j);
      49                 :            : 
      50                 :    1672584 :     int parent(int i) { return (i-1)/2; }
      51                 :     286320 :     int left(int i) { return 2*i+1; }
      52                 :     286320 :     int right(int i) { return 2*i+2; }
      53                 :            : 
      54                 :            :     void upheap(int i);
      55                 :            :     void downheap(int i);
      56                 :            : 
      57                 :            : public:
      58                 :            : 
      59                 :            :     Heap() { size=0; }
      60                 :          4 :     Heap(int s) : array<heap_node>(s) { size=0; }
      61                 :            : 
      62                 :            : 
      63                 :            :     void insert(Heapable *, double);
      64                 :            :     void update(Heapable *, double);
      65                 :            : 
      66                 :            :     heap_node *extract();
      67         [ +  - ]:       1088 :     heap_node *top() { return size<1 ? (heap_node *)NULL : &ref(0); }
      68                 :            :     heap_node *kill(int i);
      69                 :            : };
      70                 :            : 
      71                 :            : 
      72                 :            : 
      73                 :            : // GFXTOOLS_HEAP_INCLUDED
      74                 :            : #endif