dyn_sort_utils.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 DYN_SORT_UTILS_H 
# define DYN_SORT_UTILS_H

# include <aleph.H>
# include <ahFunction.H>
# include <tpl_arrayStack.H>
# include <tpl_dynArray.H>


namespace Aleph
{


    template <class T, class Compare > inline
void selection_sort(DynArray<T> & a)
{
  const int n = a.size();

  for (int i = 0; i < n - 1; i++)
    {
      int min = i;

      for (int j = i + 1; j < n; j++)
     if (Compare()(static_cast<const T&>(a.access(j)), 
                static_cast<const T&>(a.access(min))))
       min = j;

      if (Compare()(static_cast<const T&>(a.access(min)), 
              static_cast<const T&>(a.access(i))))
     Aleph::swap(static_cast<T&>(a.access(min)), 
              static_cast<T&>(a.access(i)));
    }
}


    template <class T> inline
void selection_sort(DynArray<T> & a)
{
  selection_sort<T, Aleph::less<T> >(a);
}

    template <class T, class Compare> inline
void bubble_sort(DynArray<T> & a)
{
  const int n = a.size();

  for (int i = 0; i < n - 1; i++)
    for (int j = n - 1; j > i; j--)
      {
     if (Compare()(static_cast<const T&>(a.access(j)), 
                static_cast<const T&>(a.access(j - 1))))
       {
         Aleph::swap(static_cast<T&>(a.access(j - 1)), 
               static_cast<T&>(a.access(j)));
       }
      }
}


    template <class T> inline
void bubble_sort(DynArray<T> & a)
{
  bubble_sort<T, Aleph::less<T> >(a);
}

    template <class T, class Compare> inline
void insertion_sort(DynArray<T> & a)
{
  const int n = a.size();

  for (int i = 1; i < n; i++)
    {
      T tmp = a.access(i);
      int j = i;
      while (j > 0 and 
          Compare()(static_cast<const T&>(a.access(j - 1)), tmp))
     {
       a.access(j) = a.access(j - 1);
       j--;
     }

      a.access(j) = tmp;
    }
}

    template <class T> inline
void insertion_sort(DynArray<T> & a)
{
  insertion_sort<T, Aleph::greater<T> >(a);
}

    template <class T, class Compare> inline
void shellsort(DynArray<T> & a)
{
  const int n = a.size();
  int incs[16] = { 1391376, 463792, 198768, 86961, 
             33936, 13776, 4592, 1968, 861, 
             336, 112, 48, 21, 7, 3, 1 }; 

  for (int k = 0; k < 16; k++) 
    { 
      const int h = incs[k]; 
      for (int i = h; i < n; i++) 
      { 
     T tmp = a.access(i); 
     int j = i;

     while (j >= h and 
            Compare()(tmp, static_cast<const T&>(a.access(j - h))))
       {
         a.access(j) = a.access(j - h);
         j -= h;
       } 

     a.access(j) = tmp;
      } 
    } 
}

    template <class T> inline
void shellsort(DynArray<T> & a)
{
  shellsort<T, Aleph::less<T> >(a);
}


inline static int back_index(const int & i) { return i - 1; }


    template <class T, class Compare> inline
static void siftUp(DynArray<T> & table, const size_t & n) 
{ 
  int p;
  for (int i = n; i > 1; i = p) 
    {
      p = i >> 1;     // c = i/2 

      if (Compare()(static_cast<const T&>(table.access(back_index(p))), 
              static_cast<const T&>(table.access(back_index(i)))))
     return;
      Aleph::swap(static_cast<T&>(table.access(back_index(p))), 
            static_cast<T&>(table.access(back_index(i))));
    }
}



    template <class T, class Compare> inline
static void siftDown(DynArray<T> & table, const size_t & n) 
{
  unsigned i = 1;

  while (true)
    {
      int c = i << 1; // c = 2*i

      if (c > n) 
     return;

      if (c + 1 <= n)
     if (Compare()(static_cast<const T&>(table.access(back_index(c + 1))), 
                static_cast<const T&>(table.access(back_index(c)))))
       c++;

      if (Compare()(static_cast<const T&>(table.access(back_index(i))),
              static_cast<const T&>(table.access(back_index(c)))))
     return; 

      Aleph::swap(static_cast<T&>(table.access(back_index(c))), 
            static_cast<T&>(table.access(back_index(i))));
      i = c;
    }
}


    template <class T> inline
void heapsort(DynArray<T> & a)
{
  const int n = a.size();

  int i;
  for (i = 2; i <= n; i++)
    siftUp<T, Aleph::greater<T> >(a, i);

  for (i = n; i >= 2; i--)
    {
      Aleph::swap(static_cast<T&>(a.access(0)), 
            static_cast<T&>(a.access(i - 1)));

      siftDown<T, Aleph::greater<T> >(a, i - 1);
    }
}
  

    template <class T, class Compare> inline
int partition(DynArray<T> & a, const int & l, const int & r)
{
  int i = l - 1, 
      j = r;
  const T & pivot = a.access(r);

  while (true)
    {
      while (Compare()(static_cast<const T&>(a.access(++i)), pivot)) { }

      while (Compare()(pivot, static_cast<const T&>(a.access(--j))))
     if (j == l)
       break;

      if (i >= j)
     break;

      Aleph::swap(static_cast<T&>(a.access(i)), static_cast<T&>(a.access(j)));
    }

  Aleph::swap(static_cast<T&>(a.access(i)), static_cast<T&>(a.access(r)));

  return i;
}


    template <class T, class Compare> inline static
void quicksort_rec(DynArray<T> & a, const int & l, const int & r)
{
  if (r <= l) 
    return;

  int i = partition<T, Compare>(a, l, r);

  if (i - l < r - i)
    {
      quicksort_rec<T, Compare>(a, l, i - 1);
      quicksort_rec<T, Compare>(a, i + 1, r);
    }
  else
    {
      quicksort_rec<T, Compare>(a, i + 1, r);
      quicksort_rec<T, Compare>(a, l, i - 1);
    }
}

# define push2(stack, a, b)  stack.push(b); stack.push(a);

    template <class T, class Compare> inline
void quicksort(DynArray<T> & a)
{
  int i, l = 0, r = a.size() -1;

  FixedStack<int, 40> stack;

  push2(stack, l, r);

  while (not stack.is_empty())
    {
      l = stack.pop(); r = stack.pop();

      if (r <= l) 
     continue;

      i = partition<T, Compare>(a, l, r);

      if (i - l > r - i)
     {
       push2(stack, l, i - 1); push2(stack, i + 1, r);
     }
      else 
     {
       push2(stack, i + 1, r); push2(stack, l, i - 1); 
     } 
    }
}

    template <class T> inline
void quicksort(DynArray<T> & a)
{
  quicksort<T, Aleph::less<T> >(a);
}


# undef push2

    template <class T, class Compare> inline
int search_extreme(DynArray<T>& a, const int & l, const int & r)
{
  int extreme_index = l;

  for (int i = l + 1; i <= r; i++)
    if (Compare()(static_cast<const T&>(a.access(i)), 
            static_cast<const T&>(a.access(extreme_index))))
      extreme_index = i;

  return extreme_index;
}

    template <class T> inline
int search_min(DynArray<T>& a, const int & l, const int & r)
{
  return search_extreme<T, Aleph::less<T> >(a, l, r);
}

    template <class T> inline
int search_max(DynArray<T>& a, const int & l, const int & r)
{
  return search_extreme<T, Aleph::greater<T> >(a, l, r);
} 

    template <class T, class Compare> inline
int binary_search(DynArray<T> & a, const T & x, int l, int r)
{
  while (l <= r)
    {
      int m = (l + r)/2;

      if (Compare() (x, static_cast<const T&>(a.access(m))))
     r = m -1;
      else if (Compare() (static_cast<const T&>(a.access(m)), x))
     l = m + 1;
      else
     return m; // clave encontrada
    }

  return -1;
}

    template <class T> inline
int binary_search(DynArray<T> & a, const T & x, const int & l, const int & r)
{
  return binary_search<T, Aleph::less<T> >(a, x, l, r);
}


    template <class T> inline
int binary_search(DynArray<T> & a, const T & x)
{
  return binary_search<T>(a, x, 0, static_cast<int>(a.size()) - 1);
}


} // end namespace Aleph



# endif // DYN_SORT_UTILS_H

---