// Este arquivo: MYTOOLS.h
// Data: 2019-10-28
// Autor: Paulo Feofiloff
//
// Esta é a interface de minha biblioteca particular de ferramentas genéricas
// básicas.
////////////////////////////////////////////////////////////////////////////////


#ifndef _MYTOOLS_h
#define _MYTOOLS_h

#include <stdlib.h> // malloc(), free(), rand()
#include <stdio.h> // printf()
#include <limits.h> // INT_MAX
#include <stdbool.h>
#include <assert.h>



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

// Minha versão de malloc() interrompe execução se malloc() devolver NULL.
void *
mallocc( size_t n);

// Muitas funções usam strings.
typedef char *string;

// Recebe uma vetor vv[0..n-1] de vértices de um grafo e inverte o vetor
// (trocando vv[0] com vv[n-1], vv[1] com vv[n-2], etc.).
void
invertArray( int *vv, int n);

// Esta função decide se as partições do conjunto 0..V-1 determinadas pelos
// vetores sc1[] e sc2[] são iguais. Para cada v em 0..V-1, sc1[v] é o "nome" do
// bloco que contém v na primeira partição. Analogamente, sc2[v] é o "nome" do
// bloco que contém v na segunda partição. Os dois vetores são indexados por
// 0..V-1 e têm valores em 0..V-1. As duas partições são iguais se v e w estão
// no mesmo bloco da primeira partição sempre que estão no mesmo bloco da
// segunda partição, e vice-versa.
bool 
comparePartitions( int *sc1, int *sc2, int V);



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

// Esta função devolve um inteiro aleatório entre a e b inclusive, ou seja, no
// intervalo fechado [a,b]. Vamos supor que a <= b e que b-a <= RAND_MAX. (O
// código foi copiado da biblioteca random de Eric S. Roberts, "The Art and
// Science of C: a Library-Based Introduction to Computer Science", Addison-
// Wesley, 1995.)
int 
randInteger( int a, int b);

// Devolve um número real aleatório no intervalo semi-aberto [a,b). (O código
// foi copiado da biblioteca random de Eric Roberts.)
double 
randReal( double a, double b);

// Esta função faz uma permutação aleatória (random shuffle) dos elementos do
// vetor v[0..V-1].
void 
randPermutation( int v[], int V);



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

// A função lg() recebe um inteiro N > 0 e devolve o piso de log N, ou seja, o
// único inteiro i tal que 2^i <= N < 2^(i+1).
int 
lg( int N);



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

// Dizemos que um número x é bom se -M <= x <= +M, sendo M = INT_MAX. A função
// noOverflow() recebe números bons t e c e decide se t+c é bom. 
bool
noOverflow( int t, int c);



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

// Rearranja o vetor v[0..n-1] em ordem crescente. Esta é uma implementação
// iterativa do algoritmo Mergesort. O algoritmo é estável, ou seja, preserva a
// posição relativa de elementos do vetor que têm o mesmo valor. (Veja 
// www.ime.usp.br/~pf/algoritmos/aulas/mrgsrt.html.)
void
mergesort_i( int n, int v[]);

// Rearranja o vetor v[0..n-1] em ordem crescente. Esta é uma implementação do
// algoritmo Quicksort. O algoritmo não é estável, ou seja, não preserva a
// posição relativa de elementos do vetor que têm o mesmo valor. (Veja
// www.ime.usp.br/~pf/algoritmos/aulas/quick.html.)
void 
quickSort( int v[], int p, int r);

// Em lugar de minha função quicksort(), é melhor usar a poderosa função qsort()
// da biblioteca padrão stdlib. Essa função é muito genérica e por isso exige
// que o cliente defina uma função de comparação compare().
//    Exemplo: A função compare() compara inteiros apontados por elem1 e elem2.
// Devolve -1 se *elem1 é menor que *elem2, devolve +1 se *elem1 é maior que
// *elem2, devolve 0 se *elem1 é igual a *elem2.
int 
compare( const void *elem1, const void *elem2);
// Para ordenar um vetor arr[0..N-1] de inteiros, diga qsort( arr, N,
// sizeof (int), compare).

#endif