MeVisLab/Standard/Sources/ML/MLWEM/WEMDataStructure/WEMHeap.h

Go to the documentation of this file.

// **InsertLicense** code
//----------------------------------------------------------------------------------

#ifndef __WEMHeap_H
#define __WEMHeap_H

#include "WEMVector.h"
#include "WEMBase/WEMPrimitive.h"


ML_START_NAMESPACE


template <class T>
class WEMHeap : public WEMVector<WEMPrimitive> 
{
public:

  WEMHeap();
  ~WEMHeap();
  T* root();
  const T* root() const;
  void swap(unsigned int i,unsigned int j);
  void insert(WEMPrimitive *wp);
  void insert(WEMPrimitive *wp, double v);
  void update(WEMPrimitive *wp, double nv);
  int remove(WEMPrimitive *wp);
  void sort();

private:

  inline int parent(int i) const {return (i-1)/2;}
  inline int left(int i)   const {return 2*i+1;}
  inline int right(int i)  const {return 2*i+2;}
  int upHeap(int i);
  int downHeap(int i);
};


template <class T>
WEMHeap<T>::WEMHeap() : WEMVector<WEMPrimitive>()
{
}


template <class T>
WEMHeap<T>::~WEMHeap()
{
  clear();
}


template <class T>
T* WEMHeap<T>::root()
{
  WEMPrimitive *wp = WEMVector<WEMPrimitive>::first();
  if (wp) 
  {
    return reinterpret_cast<T*>(wp);
  } 
  else 
  {
    return NULL;
  }
}


template <class T>
const T* WEMHeap<T>::root() const
{
  return root();
}


template <class T>
void WEMHeap<T>::swap(unsigned int i,unsigned int j) 
{
  WEMVector<WEMPrimitive>::swap(i,j);
  at(i)->setHeapPosition(i);
  at(j)->setHeapPosition(j);
}


template <class T>
void WEMHeap<T>::insert(WEMPrimitive *wp)
{
  if (wp == NULL)                  { return; }
  if (wp->getHeapPosition() != -1) { return; }

  WEMVector<WEMPrimitive>::appendUnsafe(wp);
  const unsigned int n = num()-1;
  last()->setHeapPosition(n);
  upHeap(n);
}


template <class T>
void WEMHeap<T>::insert(WEMPrimitive *wp,double v)
{
  if (wp == NULL) { return; }

  if (wp->getHeapPosition() == -1) 
  {
    wp->setHeapValue(v);
    WEMVector<WEMPrimitive>::appendUnsafe(wp);
    const unsigned int n = num()-1;
    last()->setHeapPosition(n);
    upHeap(n);
  } 
  else 
  {
    update(wp,v);
  }
}


template <class T>
int WEMHeap<T>::remove(WEMPrimitive *wp)
{
  if (wp == NULL) { return -1; }

  const int i = wp->getHeapPosition();
  if (i == -1) { return -1; }

  const int n = num();
  if (i >= n) { return -1; }

  if (i != n - 1)
  {
    swap(i,n - 1);
    at(n - 1)->setHeapPosition(-1);
    deleteLast();
    if (at(i)->getHeapValue() < wp->getHeapValue()) 
    {
      return upHeap(i);
    } 
    else 
    {
      return downHeap(i);
    }
  } 
  else 
  {
    at(n - 1)->setHeapPosition(-1);
    deleteLast();
  }
  return -1;
}


template <class T>
void WEMHeap<T>::update(WEMPrimitive *wp,double nv)
{
  const int i = wp->getHeapPosition();
  if (i == -1) { return; }

  const int n = num();
  if (i >= n) { return; }

  const double ov = wp->getHeapValue();

  wp->setHeapValue(nv);

  if (nv < ov) 
  { 
    upHeap(i); 
  } 
  else 
  {
    downHeap(i);
  }
}


template <class T>
int WEMHeap<T>::upHeap(int i)
{
  if (i == 0) { return 0; }
  const int pi = parent(i);
  if (at(i)->getHeapValue() < at(pi)->getHeapValue()) 
  {
    swap(i,pi);
    return upHeap(pi);
  }
  return i;
}


template <class T>
int WEMHeap<T>::downHeap(int i)
{
  int largest=i,l=left(i),r=right(i);
  const int n = num();

  if (i >= n) { return -1; }
  if ((l < n) && (at(l)->getHeapValue() < at(largest)->getHeapValue())) { largest=l; }
  if ((r < n) && (at(r)->getHeapValue() < at(largest)->getHeapValue())) { largest=r; }

  if (largest !=i ) 
  {
    swap(i,largest);
    return downHeap(largest);
  }
  return i;
}


template <class T>
void WEMHeap<T>::sort()
{
  WEMVector<WEMPrimitive> *newheap = NULL;
  ML_CHECK_NEW(newheap, WEMVector<WEMPrimitive>());

  unsigned int i = 0;
  const unsigned int n = num();
  for (i = 0; i < n; i ++) { newheap->append(at(i)); }
  clear();
  const unsigned int nn = newheap->num();
  for (i = 0; i < nn; i ++) { insert(newheap->at(i)); }
  ML_DELETE(newheap);
}


ML_END_NAMESPACE

#endif // __WEMHEAP_H__