CSOObjectHeap.h

Go to the documentation of this file.

/*************************************************************************************
**
** Copyright 2007, MeVis Medical Solutions AG
**
** The user may use this file in accordance with the license agreement provided with
** the Software or, alternatively, in accordance with the terms contained in a
** written agreement between the user and MeVis Medical Solutions AG.
**
** For further information use the contact form at https://www.mevislab.de/contact
**
**************************************************************************************/
 
 
 
#pragma once
 
 
#include "CSOObjectVector.h"
 
 
ML_START_NAMESPACE
 
 
template <class T>
class CSOObjectHeap : public CSOObjectVector<T>
{
 
public:
 
  CSOObjectHeap();
  ~CSOObjectHeap() override;
  T* root() const;
  void swap(unsigned int i,unsigned int j) override;
  void insert(T *we);
  void insert(T *we,float v);
  void update(T *we,float nv);
  int remove(T *we) override;
  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==nullptr)               { return; }
  if (we->heapPosition != -1) { return; }
 
  CSOObjectVector<T>::appendUnsafe(we);
  // No range cast, explicitly allow heapPosition to be < 0 if num() is 0.
  const int n = static_cast<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==nullptr) { 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 == nullptr) { 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 = nullptr;
  newheap = new 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));
  }
  delete newheap;
  newheap = nullptr;
}
 
 
ML_END_NAMESPACE