tpl_arrayHeap.H

# ifndef TPL_ARRAYHEAP_H
# define TPL_ARRAYHEAP_H

# include <ahFunction.H>
# include <ahUtils.H>
# include <ahDefs.H>
# include <ahAssert.H>
# include <ahDry.H>

namespace Aleph {


    template <typename T, class Compare> inline
T & sift_up(T * ptr, const size_t l, const size_t r)
{
  size_t i = r;
  for (size_t p; i > l; i = p) 
    {
      p = u_index(i); // índice del padre (c = i/2)
      if (Compare () (ptr[p], ptr[i])) // ¿cumple propiedad orden?
        return ptr[i]; // si, todo el arreglo es un heap

      std::swap(ptr[p], ptr[i]); // intercambie y restaure nivel p
    }

  return ptr[i];
}

    template <typename T, class Compare> inline
void sift_down(T * ptr, const size_t l, const size_t r)
{
  size_t i = l, c;
  while (true)
    {
      c = l_index(i); // índice del hijo izquierdo (c = i/2)
      if (c > r) // ¿hay hijo izquierdo?
        return; // no ==> termine

      if (c + 1 <= r) // ¿hay hijo derecho?
        if (Compare () (ptr[c + 1], ptr[c])) // sí ==> escoja menor
          c++;

      if (Compare () (ptr[i], ptr[c])) // ¿cumple propiedad orden?
        return;  // sí ==> termine

      std::swap(ptr[c], ptr[i]); 
      i = c;
    }
}

    template <typename T, class Compare> inline
void sift_down_up(T * ptr, const size_t l, const size_t i, const size_t r)
{
  sift_down <T, Compare> (ptr, i, r);
  sift_up <T, Compare> (ptr, l, i);
}

    template <typename T, class Compare = Aleph::less<T> > 
void heapsort(T * array, const size_t n)
{
  --array; //desplazar posición hacia atrás ==> array[1] == primero
  for (int i = 2; i <= n; ++i)
    sift_up <T, Aleph::Inversed_Compare<T, Compare> > (array, 1, i);  
  for (int i = n; i > 1; --i)
    {
      std::swap(array[1], array[i]); // poner en raíz i-ésimo item 
      sift_down<T,Aleph::Inversed_Compare<T,Compare> >(array, 1, i - 1);
    }
}

    template <typename T, class Compare = Aleph::less<T> >
void faster_heapsort(T * array, const size_t n)
{
  --array; // desplazar posición hacia atrás ==> array[1] == primero
  for (int i = n/2; i >= 1; --i)
    sift_down <T, Aleph::Inversed_Compare<T, Compare> > (array, i, n);
  for (int i = n; i > 1; --i)
    {
      std::swap(array[1], array[i]); // poner en raíz i-ésimo item 
      sift_down<T,Aleph::Inversed_Compare<T,Compare> >(array, 1, i - 1);
    }
}

      template <typename T, class Compare>
bool valid_heap(T * array, const size_t l, const size_t r) 
{
  size_t i;
  for (i = l_index(l) /* i = 2*l */; i <= r; i++)
    if (Compare () (array[i], array[u_index (i)]))
      break;
  return i > r;
}

    template <typename T, class Compare = Aleph::less<T>> 
class ArrayHeap 
{
  T * array;
  const size_t dim;
  size_t       num_items;

  static size_t r_index(const size_t & i)
  {
    return (i << 1) + 1; // multiplica i por 2 y suma 1
  }

  mutable bool array_allocated;

public:

  ArrayHeap(const size_t & d = 1024) 
    : array(NULL), dim(d), num_items(0), array_allocated(false) 
  { 
    array = new T [d + 1];
    array_allocated = true;
  }

  ArrayHeap(T * ptr, const size_t & d) 
    : array(ptr), dim(d), num_items(0), array_allocated(false) 
  { 
    // empty
  }

  virtual ~ArrayHeap() 
  {
    if (array_allocated and array != NULL)
      delete [] array;
  }

  T & top() throw(std::exception, std::underflow_error)
  {
    if (num_items == 0)
      throw std::underflow_error("Heap is empty");

    return array[1];
  }

  T & insert(const T & key) throw(std::exception, std::overflow_error)
  {
    if (num_items >= dim)
      throw std::overflow_error("Heap out of capacity"); 

    array[++num_items] = key;  // colocar nuevo elemento
    return sift_up<T,Compare>(array, 1, num_items); 
  }

  T getMin() throw(std::exception, std::underflow_error)
  {
    if (num_items == 0)
      throw std::underflow_error("Heap is empty");

    T ret_val = array[1];
    array[1] = array[num_items--]; 
    sift_down<T, Compare>(array, 1, num_items); 
    return ret_val;
  }

  T get() throw(std::exception, std::underflow_error)
  {
    return getMin();
  }

  T getMax() throw(std::exception, std::underflow_error)
  {
    return getMin();
  }

  const size_t & size() const { return num_items; }
  
  bool is_empty() const { return num_items == 0; }

  void update(T & data) 
  {
    I(&data >= &array[0] and &data <= &array[dim]);

    const size_t i = &data - array;
    sift_down_up <T, Compare> (array, 1, i, num_items);
    sift_up <T, Compare> (array, i, num_items);
  }

  void remove(T & item)
  {
    item = array[num_items--];
    update(item);
  }

  T & operator [] (const size_t i)
  {
    return array[i];
  }

private:

    // super fast array traversal
  template <class Operation>
  bool __traverse(Operation & operation)
  {
    for (size_t i = 1; i <= num_items; ++i)
      if (not operation(array[i]))
        return false;

    return true;
  }

public:

  template <class Operation>
  bool traverse(Operation & operation) const
  {
    return const_cast<ArrayHeap&>(*this).__traverse(operation);
  }

  template <class Operation>
  bool traverse(Operation & operation) 
  {
    return __traverse(operation); 
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation()) const
  {
    return const_cast<ArrayHeap&>(*this).__traverse(operation);
  }

  template <class Operation>
  bool traverse(Operation && operation = Operation()) 
  {
    return traverse(operation);
  }

  Functional_Methods(T);
};

} // end namespace Aleph
# endif /* TPL_ARRAYHEAP_H */