/*
 *  Tercera Tarea: Ejercicios - Ordenamiento y busqueda
 *  Pregunta 7 - Ordenamiento por intercalacion
 *
 *  Archivo: mergesort_iterativo.cpp
 *  Federico Jhoel Salas Gonzalez 201244557
 *  IC2001 - Estructura de Datos - Grupo 1
 *  Profesor Armando Arce
 *  Ingenieria en Computacion
 *  Escuela de Computacion
 *  Instituto Tecnologico de Costa Rica
 *
 *  Descripcion de la funcion
 *
 *    La funcion recibe como parametros el puntero a un arreglo de
 *    strings y la cantidad de elementos en el arreglo. Se ordenan
 *    los elementos utilizando la tecnica de intercalacion o mergesort,
 *    sin embargo esta se hace de forma iterativa. Para lograr assumir
 *    largos que sean potencias de dos se llenan los espacios restantes
 *    en el arreglo temporal con strings provisionales, en este caso con
 *    strings que contienen el caracter nulo. La funcion no devuelve una
 *    copia sino que altera el arreglo original
 */

#include <iostream>
#include <cmath>
#include "mergesort_iterativo.h"

void ordMergeIterativo(std::string * arreglo, int size){

  // Longitud necesaria (potencia de 2)

  int tmpSize = pow(2, ceil(log2(size)));

  // Crear arreglo temporal

  std::string * tmp = new std::string[tmpSize];

  // Llenar espacios sobrantes con strings
  // que contienen unicamente el caracter nulo

  for(int pos = size; pos < tmpSize; pos++){
    tmp[pos] = "\0";
  }

  // Ordenar el arreglo hasta obtener un grupo de tmpSize

  for(int groups = 2; groups <= tmpSize; groups *= 2){

    // Mover elementos del arreglo original al arreglo temporal

    for(int i = 0; i < size; i++){
      tmp[i] = arreglo[i];
    }

    // Regresar elementos al arreglo original ordenando por grupos

    // Inicio con grupos de dos

    int current = 0;
    int leftIndex = 0;
    int rightIndex = groups / 2;
    int endLeftGroup = rightIndex;
    int endRightGroup = groups;

    while(current < size){

      if(rightIndex == endRightGroup ||
         std::strcmp(tmp[rightIndex].c_str(), "\0") == 0){

        if(leftIndex == endLeftGroup){

          // Continuar con el siguiente par de grupos

          leftIndex = rightIndex;
          rightIndex += groups / 2;
          endLeftGroup = rightIndex;
          endRightGroup += groups;
          continue;
        }

        // Asignar siguiente del grupo izquierdo

        arreglo[current++] = tmp[leftIndex++];
        continue;

      }

      if(leftIndex == endLeftGroup){

        // Asignar siguiente del grupo derecho

        arreglo[current++] = tmp[rightIndex++];
        continue;
      }

      // Asignar el elemento menor

      if(std::strcmp(tmp[leftIndex].c_str(), tmp[rightIndex].c_str()) < 0){
        arreglo[current++] = tmp[leftIndex++];
      } else {
        arreglo[current++] = tmp[rightIndex++];
      }
    }
  }

  delete[] tmp;  // Liberar memoria del arreglo temporal
}