MeVisLab/Standard/Sources/ML/MLCSO/CSOTools/CSOObjectHeap.h

Go to the documentation of this file.

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

//----------------------------------------------------------------------------------


#ifndef __CSOObjectHeap_H
#define __CSOObjectHeap_H

#include "CSOObjectVector.h"


ML_START_NAMESPACE


template <class T>
class CSOObjectHeap : public CSOObjectVector<T> 
{

public:

  CSOObjectHeap();
  ~CSOObjectHeap();
  T* root() const;
  void swap(unsigned int i,unsigned int j);
  void insert(T *we);
  void insert(T *we,float v);
  void update(T *we,float nv);
  int remove(T *we);
  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>
CSOObjectHeap<T>::CSOObjectHeap() : CSOObjectVector<T>()
{ 
}


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


template <class T>
T* CSOObjectHeap<T>::root() const
{
  return static_cast<T*>(CSOObjectVector<T>::firstBoundsCheck());
}


template <class T>
void CSOObjectHeap<T>::swap(unsigned int i,unsigned int j)
{
  CSOObjectVector<T>::swap(i,j);
  CSOObjectVector<T>::at(i)->heapPosition = i;
  CSOObjectVector<T>::at(j)->heapPosition = j;
}


template <class T>
void CSOObjectHeap<T>::insert(T *we)
{
  if (we==NULL)               { return; }
  if (we->heapPosition != -1) { return; }

  CSOObjectVector<T>::appendUnsafe(we);
  const int n = (int)CSOObjectVector<T>::num()-1;
  CSOObjectVector<T>::last()->heapPosition = n;
  upHeap(n);
}


template <class T>
void CSOObjectHeap<T>::insert(T *we,float v)
{
  if (we==NULL) { return; }

  if (we->heapPosition == -1) 
  {
    we->value = v;
    CSOObjectVector<T>::appendUnsafe(we);
    CSOObjectVector<T>::last()->heapPosition = CSOObjectVector<T>::num()-1;
    upHeap(CSOObjectVector<T>::num()-1);
  } 
  else 
  {
    update(we,v);
  }
}


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

  const int i = we->heapPosition;
  if (i == -1) { return -1; }

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

  if (i != n - 1) 
  {
    swap(i,n - 1);
    CSOObjectVector<T>::at(n - 1)->heapPosition = -1;
    CSOObjectVector<T>::deleteLast();
    if (CSOObjectVector<T>::at(i)->value < we->value) 
    {
      return upHeap(i);
    } 
    else 
    {
      return downHeap(i);
    }
  } 
  else 
  {
    CSOObjectVector<T>::at(n - 1)->heapPosition = -1;
    CSOObjectVector<T>::deleteLast();
  }
  return -1;
}


template <class T>
void CSOObjectHeap<T>::update(T *we,float nv)
{
  const int i = we->heapPosition;
  if (i == -1) { return; }

  const int n = CSOObjectVector<T>::num();
  if (i >= n) { return; }

  const float ov = static_cast<float>(we->value);

  we->value = nv;

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


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


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

  if (i >= n) { return -1; }
  if ((l < n) && (CSOObjectVector<T>::at(l)->value < CSOObjectVector<T>::at(largest)->value)) { largest=l; }
  if ((r < n) && (CSOObjectVector<T>::at(r)->value < CSOObjectVector<T>::at(largest)->value)) { largest=r; }

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


template <class T>
void CSOObjectHeap<T>::sort()
{
  CSOObjectVector<T> *newheap = NULL;
  ML_CHECK_NEW(newheap, CSOObjectVector<T>());

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



ML_END_NAMESPACE

#endif // __CSOObjectHeap_H