tpl_arrayHeap.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# ifndef TPL_ARRAYHEAP_H
# define TPL_ARRAYHEAP_H

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

namespace Aleph {

static size_t u_index(const size_t & i)
{
  return i >> 1; // divide i entre 2
}
static size_t l_index(const size_t & i)
{
  return i << 1; // multiplica i por 2
}
    template <typename T, class Compare> inline
void sift_up(T * ptr, const size_t & l, const size_t & r)
{
   size_t i, p;

    for (i = r; i > l; i = p) 
      {
        p = u_index(i); // índice del padre (c = i/2)

        if (Compare () (ptr[p], ptr[i])) // ¿satisface propiedad orden?
          return; // si, todo el arreglo es un heap

        Aleph::swap(ptr[p], ptr[i]); // intercambie y restaure en nivel p
      }
}
    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 el menor
            c++;

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

        Aleph::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, 1, i);
}
    template <typename T, class Compare>
void heapsort(T * array, const size_t & n)
{
  --array; //desplazar una posición hacia atrás ==> array[1] == primer elemento

  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)
    {
      Aleph::swap(array[1], array[i]); // colocar en la raíz i-ésimo item 
      sift_down <T, Aleph::Inversed_Compare<T, Compare> > (array, 1, i - 1);
    }
}
    template <typename T>
void heapsort(T * array, const size_t & n)
{
  heapsort <T, Aleph::less<T> > (array, n); 
}
    template <typename T, class Compare>
void faster_heapsort(T * array, const size_t & n)
{
  --array; // desplazar una posición hacia atrás ==> array[1] == primer elemento

  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)
    {
      Aleph::swap(array[1], array[i]); // colocar en la raíz i-ésimo item 
      sift_down <T, Aleph::Inversed_Compare<T, Compare> > (array, 1, i - 1);
    }
}
    template <typename T>
void faster_heapsort(T * array, const size_t & n)
{
  faster_heapsort <T, Aleph::less<T> > (array, n); 
}
      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
    sift_up <T, Compare> (array, 1, num_items); // restaurar propiedad de orden

    return array[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--]; // sobreescribir la raíz con último elemento
    sift_down <T, Compare> (array, 1, num_items); // Restaurar propiedad de orden

    return ret_val;
  }
  const size_t & size() const
  {
    return num_items;
  }
  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);
  }
  T & operator [] (const size_t & i)
  {
    return array[i];
  }
};

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

---