oakbinheap.h

/***************************************************************************
 * The contents of this file are subject to the Mozilla Public             *
 * License Version 1.1 (the "License"); you may not use this file          *
 * except in compliance with the License. You may obtain a copy of         *
 * the License at http://www.mozilla.org/MPL/                              *
 *                                                                         *
 * Software distributed under the License is distributed on an "AS         *
 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or              *
 * implied. See the License for the specific language governing            *
 * rights and limitations under the License.                               *
 *                                                                         *
 * The Original Code is Game Network Framework (GaNeF).                    *
 *                                                                         *
 * The Initial Developers of the Original Code are                         *
 * Lars Langer and Emanuel Greisen                                         *
 * Copyright (C) 2005. Lars Langer & Emanuel Greisen                       *
 * All Rights Reserved.                                                    *
 *                                                                         *
 * Contributor(s):                                                         *
 *   none yet....                                                          *
 *                                                                         *
 ***************************************************************************/

#ifndef OAKBINARYMINHEAP_H
#define OAKBINARYMINHEAP_H

#define HEAP_INITIAL_SIZE 4

#include <map>
#include <iostream>
#include <pasync.h>

USING_PTYPES

/**
 * @brief Just an ordenary binary min-heap.
 * Well not completely, because this one also has both semaphore and mutex capabilities. Hence a thread will block when trying to get an element from the heap if its empty(semaphore), and only one thread is manipulating the heap at any time (mutex).
 *
 * @author Emanuel Greisen
*/
template<class E, class Comparer>
class OakBinaryMinHeap : semaphore, mutex
{
private:
   E ** elements;
   std::map<E*, int> positions;

   Comparer comp;
   int heap_size;
   int last;
   inline int parent(int i) { return i/2; }
   inline int left(int i) { return i*2; }
   inline int right(int i) { return i*2+1; }

   inline void moveup(int i)
   {
      //std::cout << "moveup("<<i<<")\n";
      swap(i,parent(i));
      heapify(parent(i));
   }

   inline void swap(int i, int j)
   {
      //std::cout << "swap("<<i<<","<<j<<")\n";
      E * tmp = elements[i];
      elements[i] = elements[j];
      elements[j] = tmp;
      positions[elements[i]] = i;
      positions[elements[j]] = j;
   }

   void heapify(int i)
   {
      // std::cout << "heapify("<<i<<")\n";
      if(i > 0) // do not move the root up
      {
         if(comp(*elements[i],*elements[parent(i)]))
         {
            moveup(i);
            return;
         }
      }
      if(i != last) // do not move last element down
      {
         // move down ?
         int l = left(i);
         int r = right(i);
         int smallest = i;
         if(l <= last && comp(*elements[l],*elements[i])) // We are smaller than our left leg
         {
            smallest = l;
         }
         if(r <= last && comp(*elements[r],*elements[smallest])) // Right is the smallest
         {
            smallest = r;
         }
         if(smallest != i)
         {
            swap(i,smallest);
            heapify(smallest);
         }
      }
   }
   /**
    * This method will expand the heap to double size (if required)
    */
   void checkHeapSize()
   {
      if(last+1 == heap_size)
      {
         std::cout << "Expand heap from: " << heap_size << " to " << (heap_size * 2) << std::endl;
         E **tmp = new E*[heap_size * 2];
         memcpy(tmp, elements, heap_size * sizeof(E*));
         delete[] elements;
         elements = tmp;
         heap_size = heap_size * 2;
      }
   }

public:
   OakBinaryMinHeap() : semaphore(0)
   {
      positions.clear();
      heap_size = HEAP_INITIAL_SIZE;
      //elements = (E**)malloc(sizeof(E*) * size);
      elements = 0;
      elements = new E*[heap_size];
      this->last = -1;
   }
   ~OakBinaryMinHeap()
   {
      delete[] elements;
   }
   void clear()
   {
      this->last = -1;
   }

   void insert(E * e)
   {
      enter();
      checkHeapSize();
      elements[++last] = e;
      positions.insert(std::make_pair(e,last));
      heapify(last); // Let the element move up (untill its min of the tree)
      leave();
      post();
   }
   E * getMin()
   {
      wait();
      enter();
      E * tmpE = elements[0];
      elements[0] = elements[last];
      positions.erase(tmpE);
      positions[elements[0]] = 0;
      last--;
      heapify(0);
      leave();
      return tmpE;
   }

   E * peek()
   {
      E * tmpE;
      wait();
      enter();
      tmpE = elements[0];
      leave();
      post();
      return tmpE;
   }

   inline int size() const { return last + 1; };

   void heapify(E * e)
   {
      enter();
      heapify(positions[e]);
      leave();
   }
};

#endif

---