tpl_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 TPL_SORT_UTILS_H
# define TPL_SORT_UTILS_H

# include <ahPair.H>
# include <tpl_arrayStack.H>
# include <tpl_dynArray.H>
# include <tpl_dynDlist.H>

namespace Aleph 
{
extern const int Insertion_Threshold;

extern const int Not_Found;

    template <typename T, class Compare>
void selection_sort(T a[], const size_t & n)
{
  int i,j, min;

  for (i = 0; i < n - 1; ++i)
    {
      for (min = i, j = i + 1; j < n; ++j)
        if (Compare () (a[j], a[min]))
          min = j;
      if (Compare () (a[min], a[i]))
        Aleph::swap(a[min], a[i]);
    }
}

    template <typename T>
void selection_sort(T a[], const size_t & n)
{
  selection_sort <T, Aleph::less<T> > (a, n);
}

    template <class Compare>
Dlink * search_min(Dlink & list)
{
  typename Dlink::Iterator it(list);

  Dlink * min = it.get_current();
  
  for (it.next(); it.has_current(); it.next())
    {
      Dlink * curr = it.get_current();

      if (Compare () (curr, min))
        min = curr;
    } 

  return min;
}
    template <class Compare>
void selection_sort(Dlink & list)
{
  Dlink aux;

  while (not list.is_empty())
    {
      Dlink * min = search_min<Compare>(list); // menor de list

      min->del(); // saque menor de list
      aux.append(min); // insértelo ordenado en aux;
    }

  list.swap(&aux);
}
    template <typename T, class Compare>
class Compare_Dnode
{

public:

  bool operator () (Dlink * l1, Dlink * l2) const
  {
    Dnode<T> * n1 = static_cast<Dnode<T>*>(l1);
    Dnode<T> * n2 = static_cast<Dnode<T>*>(l2);


    I(n1 == l1 and n2 == l2);

    return Compare () (n1->get_data(), n2->get_data());
  }
};
    template <typename T, class Compare>
void selection_sort(Dnode<T> & list)
{
  selection_sort < Compare_Dnode<T, Compare> > (list);
}
    template <typename T>
void selection_sort(Dnode<T> & list)
{
  selection_sort < T, Aleph::less<T> > (list);
}
    template <typename T, class Equal> inline
int sequential_search(T a[], const T & x, const int & l, const int & r)
{
  for (int i = l; i <= r; i++)
    if (Equal () (a[i], x))
      return i;

  return Not_Found;
}
    template <typename T, class Equal> inline
int sequential_search(DynArray<T> & a, 
                      const T & x, const int & l, const int & r)
{
  for (int i = l; i <= r; i++)
    if (a.exist(i))
      if (Equal () (static_cast<const T&>(a.access(i)), x))
        return i;

  return -1;
}
    template <typename T> inline 
int sequential_search(T a[], const T & x, const int & l, const int & r)
{
  return sequential_search<T, equal_to<T> > (a, x, l, r);
}

    template <typename T> inline
int sequential_search(DynArray<T> & a, 
                      const T & x, const int & l, const int & r)
{
  return sequential_search<T, equal_to<T> > (a, x, l, r);
}
    template <typename T, class Equal> inline
Dnode<T> * sequential_search(Dnode<T> & list, const T & x)
{
  for (typename Dnode<T>::Iterator it(list); it.has_current(); it.next())
    {
      Dnode<T> * curr = it.get_current();

      if (Equal () (curr->get_data(), x))
        return curr;
    }

  return NULL;
}
    template <typename T> inline
Dnode<T> * sequential_search(Dnode<T> & list, const T & x)
{
  return sequential_search<T, Aleph::equal_to<T> > (list, x);
}
    template <typename T, class Equal> inline
T * sequential_search(DynDlist<T> & list, const T & x)
{
  Dnode<T> * ret = 
    sequential_search<T, Equal > (static_cast<Dnode<T>&>(list), x);

  return ret != NULL ? &ret->get_data() : NULL;
}
    template <typename T> inline
T * sequential_search(DynDlist<T> & list, const T & x)
{
  return sequential_search<T, Aleph::equal_to<T> > (list, x);
}
    template <typename T, class Compare> inline
int search_extreme(T a[], const int & l, const int & r)
{
  T extreme_index = l;

  for (int i = l + 1; i <= r; i++)
    if (Compare () (a[i], a[extreme_index])) // ¿se ve un nuevo menor?
      extreme_index = i; // sí
  
  return extreme_index;
}
    template <typename T> inline
int search_extreme(T a[], const int & l, const int & r)
{
  return search_extreme<T, Aleph::less<T> > (a, l, r);
}
    template <typename T> inline
int search_min(T a[], const int & l, const int & r)
{
  return search_extreme<T, Aleph::less<T> > (a, l, r);
}

    template <typename T> inline
int search_max(T a[], const int & l, const int & r)
{
  return search_extreme<T, Aleph::greater<T> > (a, l, r);
}
    template <class Compare> inline
Dlink * search_extreme(Dlink * list)
{
  typename Dlink::Iterator it(*list);

  Dlink * curr_min  = it.get_current();

  for (it.next(); it.has_current(); it.next())
    {
      Dlink curr = it.get_current();

      if (Compare () (curr, curr_min))
        curr_min = curr;
    }
  return curr_min;
}
    template <typename T, class Compare> inline 
Dnode<T> * search_extreme(Dnode<T> & list)
{
  Dlink * ret= search_extreme<Compare_Dnode<T, Compare> > (list);

  return static_cast<Dnode<T>*>(ret);
}


    template <typename T> inline 
Dnode<T> * search_extreme(Dnode<T> & list)
{
  return search_extreme<T, Aleph::less<T> > (list);
}

    template <typename T, class Compare> inline
T * search_extreme(DynDlist<T> & list)
{
  Dnode<T> * ret = 
    search_extreme <T, Compare> (static_cast<Dnode<T>&>(list)); 

  return ret != NULL ? &(ret->get_data()) : NULL;
}

    template <typename T> inline
T * search_extreme(DynDlist<T> & list)
{
  return search_extreme<T, Aleph::less<T> > (list);
}

    template <typename T> inline
T * search_min(DynDlist<T> & list)
{
  return search_extreme<T, Aleph::less<T> > (list);
}

    template <typename T> inline
T * search_max(DynDlist<T> & list)
{
  return search_extreme<T, Aleph::greater<T> > (list);
}
    template <typename T, class Compare>
void insertion_sort(T a[], const size_t & l, const size_t & r)
{
  int i,j;
  T tmp;

  for (i = l; i <= r; ++i)
    {
      tmp = a[i]; // memorice a[i], pues será sobre escrito
      for (j = i; j > l and Compare() (tmp, a[j - 1]); --j)
        a[j] = a[j - 1]; // desplazar hacia la derecha
      a[j] = tmp; // inserte tmp en la brecha
    }
}
    template <typename T>
void insertion_sort(T a[], const size_t & l, const size_t & r)
{
  insertion_sort <T, Aleph::less<T> > (a, l, r);
}
    template <class Compare>
void insert_sorted(Dlink & list, Dlink * p)
{
  typename Dlink::Iterator it(list); 

  while (it.has_current() and Compare () (it.get_current(), p)) 
    it.next();

  if (it.has_current())
    it.get_current()->append(p); // insertar a la derecha de current
  else
    list.append(p); 
}
    template <class Compare>
void insertion_sort(Dlink & list)
{
  Dlink aux;

  while (not list.is_empty())
    {
      Dlink * p = list.remove_next();

      insert_sorted<Compare>(aux, p);
    }

  list.swap(&aux);
}
    template <typename T, class Compare>
void insertion_sort(Dnode<T> & list)
{
  insertion_sort < Compare_Dnode<T, Compare> > (list);
}
    template <typename T>
void insertion_sort(Dnode<T> & list)
{
  insertion_sort < T, Aleph::less<T> > (list);
}
    template <typename T>
int binary_search_rec(T a[], const T & x, const int & l, const int & r)
{
  return binary_search_rec <T, Aleph::less<T> > (a, x, l, r);
}
    template <typename T, class Compare>
void merge(T a[], const int & l, const int & m, const int & r)
{
  int i, j, k;
  T b[r - l + 1];

  for (i = l; i <= m; i++)
    b[i] = a[i];
  for (j = r, i = m + 1; i <= r; i++, j--)
    b[i] = a[j];
  for (k = l, i = l, j = r; k <= r; k++)
    if (Compare() (b[i] < b[j]))
      a[k] = b[i++];
    else
      a[k] = b[j--]; 
}

    template <typename T, class Compare>
void mergesort(T a[], const int & l, const int & r)
{
  if (l >= r) return;

  const int m = (l + r)/2;

  mergesort<T, Compare>(a, l, m);
  mergesort<T, Compare>(a, m + 1, r);

  merge<T, Compare>(a, l, m, r);
}
    template <typename T>
void mergesort(T a[], const int & l, const int & r)
{
  mergesort <T, Aleph::less<T> > (a, l, r);
}
    template <class Compare>
void merge_lists(Dlink & l1, Dlink & l2, Dlink & result)
{

  I(result.is_empty());

  while (not l1.is_empty() and not l2.is_empty())
    if (Compare () (l1.get_next(), l2.get_next()))
      result.append(l1.remove_next());
    else
      result.append(l2.remove_next());

  if (l1.is_empty())
    result.concat_list(&l2);
  else
    result.concat_list(&l1);

  I(l1.is_empty() and l2.is_empty());

}
    template <class T, class Compare>
void merge_lists(Dnode<T> & l1, Dnode<T> & l2, Dnode<T> & result)
{
  merge_lists<Compare_Dnode<T, Compare> >(l1, l2, result);
}
    template <class Compare>
void mergesort(Dlink & list)
{
  if (list.is_unitarian_or_empty())
    return;

  Dlink l, r;

  list.split_list(l, r); // dividir en dos listas
  
  mergesort <Compare> (l); // ordenar la primera
  mergesort <Compare> (r);  // ordenar la segunda
  
  merge_lists <Compare> (l, r, list); // mezclarlas 
}
    template <typename T, class Compare>
void mergesort(Dnode<T> & list)
{
  mergesort < Compare_Dnode<T, Compare> > (list);
}

    template <typename T>
void mergesort(Dnode<T> & list)
{
  mergesort < T, Aleph::less<T> > (list);
}

    template <typename T, class Compare>
void mergesort(DynDlist<T> & list)
{
  mergesort < Compare_Dnode<T, Compare> > (list);
}


   template <typename T, class Compare>
int select_pivot(T a[], const int & l, const int & r); 

    template <typename T, class Compare>
int partition(T a[], const int & l, const int & r)
{
  const int p = select_pivot <T, Compare> (a, l, r);
  Aleph::swap(a[p], a[r]);
  T pivot = a[r]; // elemento pivot
  int i = l - 1,  // índice del primer elemento a la izquierda mayor que pivot
      j = r;      // índice del primer elemento a la derecha mayor que pivot

  while (true)
    {
          // avance mientras a[i] < a[pivot]
      while (Compare() (a[++i], pivot)) { /* no hay cuerpo */ }
      while (Compare() (pivot, a[--j])) // avance mientras a[pivot]< a[j] 
        if (j == l) // ¿se alcanzó el borde izquierdo?
          break; // sí ==> hay que terminar la iteración

      if (i >= j) 
        break;

          // En este punto hay una inversión a[i] > a[pivot] > a[j] 
      Aleph::swap(a[i], a[j]); // Eliminar la inversión
    }
  Aleph::swap(a[i], a[r]);

  return i;
}

    template <typename T, class Compare>
void quicksort_rec(T a[], const int & l, const int & r)
{
  if (l >= r) return;

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

  quicksort_rec <T, Compare> (a, l, pivot - 1);
  quicksort_rec <T, Compare> (a, pivot + 1, r);
}
    template <typename T>
void quicksort_rec(T a[], const int & l, const int & r)
{
  quicksort_rec<T, Aleph::less<T> > (a, l, r);
}
    template <typename T, class Compare>
void quicksort_rec_min(T a[], const int & l, const int & r)
{
  if (r <= l) 
    return;
  
  const int pivot = partition<T, Compare>(a, l, r);

  if (pivot - l < r - pivot) // ¿cual es la partición más pequeña?
    {     // partición izquierda más pequeña
      quicksort_rec_min<T, Compare>(a, l, pivot - 1);
      quicksort_rec_min<T, Compare>(a, pivot + 1, r);
    }
  else
    {     // partición derecha más pequeña
      quicksort_rec_min<T, Compare>(a, pivot + 1, r);
      quicksort_rec_min<T, Compare>(a, l, pivot - 1);
    }
}
    template <typename T>
void quicksort_rec_min(T a[], const int & l, const int & r)
{
  quicksort_rec_min <T, Aleph::less<T> > (a, l, r);
}
    template <typename T, class Compare>
int select_pivot(T a[], const int & l, const int & r)
{

  I(l <= r);

  if (l - r <= 2)
    return r;

  const int m = (r + l) / 2; // índice del centro

  int p = Compare () (a[l], a[m]) ? m : l; // p = max(a[l], a[m])

  return Compare () (a[r], a[m]) ? r : p;  // retornar min(a[r], a[m])
}
    template <typename T, class Compare>
void quicksort(T a[], const int & l, const int & r)
{

  if (r <= l) 
    return;

  typedef typename Aleph::pair<int, int> Partition;

  FixedStack<Partition, 32> stack;

  stack.push(Partition(l, r));

  while (stack.size() > 0)
    {
      const Partition p = stack.pop();

      const int pivot = partition<T, Compare>(a, p.first, p.second);

      if (pivot - p.first < p.second - pivot) // ¿cuál partición más pequeña?
        {     // partición izquierda más pequeña
          stack.push(Partition(pivot + 1, p.second));
          stack.push(Partition(p.first, pivot - 1));
        }
      else
        {     // partición derecha más pequeña
          stack.push(Partition(p.first, pivot - 1));
          stack.push(Partition(pivot + 1, p.second));
        }
    }
}
    template <typename T>
void quicksort(T a[], const int & l, const int & r)
{
  quicksort<T, Aleph::less<T> > (a, l, r);
}
    template <class Compare>
void quicksort(Dlink & list) 
{
  if (list.is_unitarian_or_empty()) 
    return;

  Dlink * pivot = list.remove_next();

  Dlink smaller; // lista de los menores que pivot
  Dlink bigger;  // lista de los mayores que pivot

  while (not list.is_empty()) 
  {
    Dlink * p = list.remove_next();

    if (Compare () (p, pivot))
      smaller.append(p);
    else
      bigger.append(p);
  }
 
  quicksort <Compare> (bigger);  
  quicksort <Compare> (smaller);

  list.concat_list(&smaller);
  list.append(pivot);
  list.concat_list(&bigger);
} 
    template <typename T, class Compare>
void quicksort(Dnode<T> & list)
{
  quicksort < Compare_Dnode<T, Compare> > (list);
}

    template <typename T>
void quicksort(Dnode<T> & list)
{
  quicksort < T, Aleph::less<T> > (list);
}
    template <typename T, class Compare>
void quicksort_insertion(T a[], const int & l, const int & r)
{
  if (r <= l) return;

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

  const int l_size = pivot - l; // tamaño partición izquierda
  const int r_size = r - pivot; // tamaño partición derecha

  bool left_done  = false; // true si partición izquierda está ordenada
  bool right_done = false; // true si partición derecha está ordenada

  if (l_size <= Aleph::Insertion_Threshold) // ¿partición izquierda pequeña?
    {     // sí ==> ordénela por inserción
      insertion_sort<T, Compare>(a, l, pivot - 1);  
      left_done = true;
    }

  if (r_size <= Aleph::Insertion_Threshold) // ¿partición derecha pequeña?
    {     // sí ==> ordénela por inserción
      insertion_sort<T, Compare>(a, pivot + 1, r);
      right_done = true;
    }

  if (left_done and right_done) 
    return; // ambas particiones ya están ordenadas por inserción

  if (left_done) // ¿partición izquierda ordenada por inserción?
    {     // sí; sólo resta ordenar recursivamente la partición derecha
      quicksort_insertion<T, Compare>(a, pivot + 1, r);

      return;
    }

  if (right_done) // ¿partición derecha ordenada por inserción?
    {     // sí; sólo resta ordenar recursivamente la partición izquierda
      quicksort_insertion<T, Compare>(a, l, pivot - 1);

      return;
    }

      // En este punto, ambas particiones no fueron ordenadas por inserción

      // Ordenar recursivamente de primero partición más pequeña 
  if (l_size < r_size)
    {     // partición izquierda más pequeña
      quicksort_insertion <T, Compare> (a, l, pivot - 1);
      quicksort_insertion <T, Compare> (a, pivot + 1, r);
    }
  else
    {     // partición derecha más pequeña
      quicksort_insertion <T, Compare> (a, pivot + 1, r);
      quicksort_insertion <T, Compare> (a, l, pivot - 1);
    }
}    
    template <typename T>
void quicksort_insertion(T a[], const int & l, const int & r)
{
  quicksort_insertion <T, Aleph::less<T> > (a, l, r);
}
    template <typename T, class Compare>
int random_search(T a[], const T & x, const int & l, const int & r)
{
  if (l > r)
    return Not_Found;

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

  if (Compare() (x, a[pivot]))
    return random_search(a, l, pivot - 1);
  else if (Compare() (a[pivot], x))
    return random_search(a, pivot + 1, r);

  return pivot; // elemento encontrado en el índice x
}
    template <typename T>
int random_search(T a[], const T & x, const int & l, const int & r)
{
  return random_search <T, Aleph::less<T> > (a, x, l, r);
}
    template <typename T, class Compare>
Dnode<T> * dlink_random_search(Dlink & list, const T & x)
{
  if (list.is_empty()) 
    return NULL;

  Dnode<T> * pivot = static_cast<Dnode<T>*>(list.remove_next());
  Dnode<T> item(x);
  Dnode<T> * item_ptr = &item; // puntero a una celda que contiene a x

  Dlink smaller; // lista de los menores que pivot
  Dlink bigger;  // lista de los mayores que pivot

  while (not list.is_empty()) 
  {
    Dlink * p = list.remove_next();

    if (Compare () (p, pivot))
      smaller.append(p);
    else
      bigger.append(p);
  }

  Dnode<T> * ret_val = NULL;

  if (Compare () (item_ptr, pivot))
    ret_val = dlink_random_search <T, Compare> (smaller, x);
  else if (Compare () (pivot, item_ptr))
    ret_val = dlink_random_search <T, Compare> (bigger, x);
  else
    ret_val = pivot;


  I(list.is_empty());

  list.swap(&smaller); 
  list.append(pivot);  
  list.concat_list(&bigger);

  return ret_val;
}
    template <typename T, class Compare_T>
Dnode<T> * random_search(Dlink & list, const T & x)
{
  return dlink_random_search <T, Compare_Dnode<T, Compare_T> > (list, x);
}

    template <typename T>
Dnode<T> * random_search(Dlink & list, const T & x)
{
  return random_search <T, Aleph::less<T> > (list, x);
}

    template <typename T, class Compare>
T * random_search(DynDlist<T> & list, const T & x)
{
  Dnode<T> * p = dlink_random_search <T, Compare_Dnode<T, Compare> > (list, x);

  return p == NULL ? NULL : &(p->get_data());
}

    template <typename T>
T * random_search(DynDlist<T> & list, const T & x)
{
  return random_search <T, Aleph::less<T> > (list, x);
}
    template <typename T, class Compare> static inline
const T & __random_select(T a[], const int & i, const int & l, const int & r)
{
  const int pivot = partition<T, Compare>(a, l, r);

  if (i == pivot)
    return a[i];
  
  if (i < pivot)
    return __random_select<T, Compare>(a, i, l, pivot - 1);
  else
    return __random_select<T, Compare>(a, i, pivot + 1, r);
}
    template <typename T, class Compare> 
const T & random_select(T a[], const int & i, const int & n)
{
  if (i >= n)
    throw std::out_of_range("index out of range");

  return __random_select(a, i, 0, n - 1);
}
    template <typename T> 
const T & random_select(T a[], const int & i, const int & n)
{
  return random_select <T, Aleph::less<T> > (a, i, 0, n - 1);
}
    template <class Compare>
Dlink * dlink_random_select(Dlink & list, const size_t & i)
{
  if (list.is_empty()) 
    return NULL;

  Dlink * pivot = list.remove_next();

  Dlink smaller; // lista de los menores que pivot
  Dlink bigger;  // lista de los mayores que pivot

  size_t smaller_count = 0, // cantidad de elementos de smaller
         bigger_count  = 0; // cantidad de elementos de bigger

  while (not list.is_empty()) 
  {
    Dlink * p = list.remove_next();

    if (Compare () (p, pivot))
      {
        smaller.append(p); ++smaller_count;
      }
    else
      {
        bigger.append(p); ++bigger_count;
      }
  }

  if (i >= bigger_count)
    throw std::out_of_range("index of selection greater than list's size");


  Dlink * ret_val = NULL;

  if (i == smaller_count)
    ret_val = pivot;
  else if (i < smaller_count)
    ret_val = dlink_random_select <Compare> (smaller, i);
  else
    ret_val = dlink_random_select <Compare> (bigger, i - (smaller_count + 1));

  list.concat_list(&smaller);
  list.append(pivot);
  list.concat_list(&bigger);

  return ret_val;
}
    template <typename T, class Compare>
Dnode<T> * random_select(Dlink & list, const size_t & i)
{
  return static_cast <Dnode<T>*> 
    (dlink_random_select < Compare_Dnode<T, Compare> > (list, i));
}
    template <typename T>
Dnode<T> * random_select(Dlink & list, const size_t & i)
{
  return random_select < T, Aleph::less<T> > (list, i);
}

    template <typename T, class Compare>
T * random_select(DynDlist<T> list, const size_t & i)
{
  Dlink * link = dlink_random_select <Compare_Dnode<T, Compare> > (list, i);

  Dnode<T> * p = static_cast<Dnode<T>*>(link);

  return p != NULL ? &(p->get_data()) : NULL;
}

    template <typename T>
T * random_select(DynDlist<T> list, const size_t & i)
{
  return random_select <T, Aleph::less<T> > (list, i);
}
    template <typename T, class Compare>
int binary_search_rec(T a[], const T & x, const int & l, const int & r)
{
  const int m = (l + r) / 2;

  if (l > r)
    return m;

  if (Compare() (x, a[m]))
    return binary_search_rec<T, Compare>(a, l, m - 1);
  else if (Compare() (a[m], x))
    return binary_search_rec<T, Compare>(a, m + 1, r);

  return m; // encontrado
}

}

# endif // TPL_SORT_UTILS_H

---