// Este arquivo: MYTOOLS.c
// Data: 2019-10-28
// Autor: Paulo Feofiloff
//
// Esta é a implementação de minha biblioteca particular de ferramentas 
// genéricas básicas.
////////////////////////////////////////////////////////////////////////////////


#include "MYTOOLS.h"
// contém a interface padrão stdlib.h


// Miscelânea 
////////////////////////////////////////////////////////////////////////////////

void *
mallocc( size_t n) {
   void *pointer = malloc( n);
   if (pointer == NULL) {
      fprintf( stderr, "\nmalloc devolveu NULL!\n"); 
      exit( EXIT_FAILURE);
   }
   return pointer;
}

void
invertArray( int *vv, int n) {
   for (int i = 0; i < n/2; ++i) {
      int temp = vv[i];
      vv[i] = vv[n-1-i];
      vv[n-1-i] = temp;
   }
}



// Números aleatórios 
////////////////////////////////////////////////////////////////////////////////

int 
randInteger( int a, int b) {
    double d = (double) rand() / ((double) RAND_MAX + 1); 
    // 0 <= d < 1
    int k = d * (b - a + 1); // 0 <= k <= b-a
    return a + k;
}

// A função rand() da biblioteca stdlib produz um número inteiro aleatório no
// intervalo fechado 0..RAND_MAX.

double 
randReal( double a, double b) {
    double d = (double) rand() / ((double) RAND_MAX + 1);
    // 0 <= d < 1
    return a + d * (b - a);
}

void 
randPermutation( int v[], int V) {
   for (int n = V-1; n > 0; --n) {
      int r = randInteger( 0, n); // 0 <= r <= n
      int t;
      t = v[n], v[n] = v[r], v[r] = t;
   }
}



// Logaritmos
////////////////////////////////////////////////////////////////////////////////

int 
lg( int N) {  
   int i = 0;
   int n = N;
   while (n > 1) {
      n = n / 2;
      i += 1;
   }
   return i;    
}



// Overflow 
////////////////////////////////////////////////////////////////////////////////



// Algoritmos de ordenação
////////////////////////////////////////////////////////////////////////////////

// Função auxiliar usada por mergesort_i. Recebe vetores crescentes v[p..q-1] e
// v[q..r-1] e rearranja v[p..r-1] em ordem crescente.
static void
intercala( int p, int q, int r, int v[]) {
   int i, j, *w;
   w = malloc( (r-p) * sizeof (int));
   for (i = p; i < q; ++i) w[i-p] = v[i];
   for (j = q; j < r; ++j) w[r-p+q-j-1] = v[j];
   i = 0; j = r-p-1;
   for (int k = p; k < r; ++k)
      if (w[i] <= w[j]) v[k] = w[i++];
      else v[k] = w[j--];
   free( w);
}

void
mergesort_i( int n, int v[]) {
   int b = 1;
   while (b < n) {
      int p = 0;
      while (p + b < n) {
         int r = p + 2*b;
         if (r > n) r = n;
         intercala( p, p+b, r, v);
         p = p + 2*b; 
      }
      b = 2*b;
   }
}

// Função auxiliar usada por de quickSort(). Rearanja os elementos do vetor
// v[p..r] (com p <= r) e devolve j em p..r tal que v[p..j-1] <= v[j] <
// v[j+1..r]. (Veja www.ime.usp.br/~pf/algoritmos/aulas/quick.html.)
static int
separa( int v[], int p, int r) {
   int c = v[r]; // pivô
   int t, j = p;
   for (int k = p; k < r; ++k)
      if (v[k] <= c) {
         t = v[j], v[j] = v[k], v[k] = t;
         ++j; 
      } 
   t = v[j], v[j] = v[r], v[r] = t;
   return j; 
}

void 
quickSort( int v[], int p, int r) {
   while (p < r) {      
      int j = separa (v, p, r);    
      if (j - p < r - j) {     
         quickSort (v, p, j-1);
         p = j + 1;            
      } else {                 
         quickSort (v, j+1, r);
         r = j - 1;
      }
   }
}

int 
compare( const void *a, const void *b) {
    int x = *((int *) a);
    int y = *((int *) b);
    if (x < y) return -1;
    if (x > y) return  1;
    return 0;
}


////////////////////////////////////////////////////////////////////////////////