WEMHeap.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 "WEMVector.h"
#include "WEMBase/WEMPrimitive.h"
 
 
ML_START_NAMESPACE


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

  WEMHeap();
  WEMHeap(WEMHeap &&) noexcept = default;
  WEMHeap& operator=(WEMHeap &&) noexcept = default;
  ~WEMHeap() override;
  T* root();
  const T* root() const;
  void swap(unsigned int i,unsigned int j) override;
  void insert(WEMPrimitive *wp);
  void insert(WEMPrimitive *wp, double v);
  void update(WEMPrimitive *wp, double nv);
  int remove(WEMPrimitive *wp) override;
  void sort();
  void clear() override;
 
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 nullptr;
  }
}

 
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 == nullptr)                  { 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 == nullptr) { 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 == nullptr) { 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);
    wp->setHeapPosition(-1);
    deleteLast();
    if (WEMMinHeapCompare::less(*at(i), *wp))
    {
      return upHeap(i);
    }
    else
    {
      return downHeap(i);
    }
  }
  else
  {
    wp->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 (WEMMinHeapCompare::less(*at(i), *at(pi)))
  {
    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) && WEMMinHeapCompare::less(*at(l), *at(largest)))
  {
    largest = l;
  }
  if ((r < n) && WEMMinHeapCompare::less(*at(r), *at(largest)))
    {
      largest = r;
    }
 
  if (largest !=i )
  {
    swap(i,largest);
    return downHeap(largest);
  }
  return i;
}

 
template <class T>
void WEMHeap<T>::sort()
{
  WEMVector<WEMPrimitive> *newheap = nullptr;
  newheap = new 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)); }
  delete newheap;
  newheap = nullptr;
}

 
template <class T>
void WEMHeap<T>::clear()
{
  const unsigned int n = num();
  for (unsigned int i = 0; i < n; i++) {
    at(i)->setHeapPosition(-1);
  }
  WEMVector<WEMPrimitive>::clear();
}
 
ML_END_NAMESPACE