1. Programación procedimental
1.1. Entrada y salida
1.1.1. Replicador de la entrada estándar
El siguiente programa lee un carácter a la vez de la entrada estándar y lo imprime en la salida estándar:
Listado 1. Replicador de la entrada estándar (replicate.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
// Copyright 2022 Jeisson Hidalgo
#include <stdio.h>
int main(void) {
char character = '\0';
// Read one character at a time
while (scanf("%c", &character) == 1) {
// Print that character
printf("%c", character);
}
return 0;
}
1.1.2. Separador de letras y números
La siguiente variación hace que el programa separe letras seguidas inmediatamante por números y un espacio en blanco. Las letras son impresas en la salida estándar y los números en el error estándar. El espacio en blanco en la entrada puede ser espacios en blanco, tabuladores, cambios de línea…
Listado 2. Separador de caracteres y números (sep_nums.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Copyright 2022 Jeisson Hidalgo
#include <stdio.h>
int main(void) {
char character = '\0';
long number = 0;
// Read one character at a time
while (scanf("%c%ld ", &character, &number) == 2) {
// Print that character
printf("%c", character);
fprintf(stderr, "%ld\n", number);
}
return 0;
}
Por ejemplo para la entrada a28 c290 m0 el programa produce en la salida estándar:
acm
y en el error estándar:
28 290 0
1.1.3. Múltiples puntos de retorno
No hay problema de tener múltiples puntos de retorno (varios return) en una función, pues no tiene efectos colaterales. Por ejemplo, la siguiente función usa recursión de pila para calcular un factorial y requiere al menos de dos puntos de retorno: la condición de parada y la invocación recursiva:
Listado 3. Función con múltiples puntos de retorno
1
2
3
4
5
long factorial(const long number) {
if (number < 0) return -1;
if (number < 2) return 1;
return number * factorial(number - 1);
}
En cambio, en un procedimiento depende de si los retornos provocan una ejecución incorrecta debido a efectos colaterales como limpieza o liberación de recursos. En el siguiente ejemplo, el procedimiento main() abre un archivo nombrado datos.txt y libera el recurso en la línea 11 con fclose(). En la línea 5 obtiene un valor del archivo y en función de este valor puede terminar su ejecución en la línea 8.
Listado 4. Mal uso de múltiples puntos de retorno en un procedimiento
1
2
3
4
5
6
7
8
9
10
11
12
13
int main(void) {
FILE* file = fopen("datos.txt", "r");
...
int value = 0;
fscanf(file, "%d", &value);
if (value == 0) {
fclose(file);
return EXIT_FAILURE;
}
...
fclose(file);
return EXIT_SUCCESS;
}
Tener dos (o más) puntos de retorno en este código es muy propenso a errores. Si la persona desarrolladora olvida hacer la limpieza que se hizo en la línea 7, el programa podría tener efectos indeseados, por ejemplo, si el procedimiento se invocara varias veces durante la ejecución del programa. Si la persona desarrolladora replica la limpieza como ocurre con la línea 7, es redundancia de código no controada, que es una pésima práctica de programación.
Ambos problemas se evitan si el procedimiento sólo tiene un punto de retorno, como ocurre en la siguiente corrección, donde se usa una variable de error y el if usa "lógica positiva", es decir, la condición verdadera ejecuta el código de éxito y el else el manejo del error. Este código facilita el mantenimiento porque el código de limpieza está en un único lugar del procedimiento, normalmente hacia el final del mismo.
Listado 5. Corrección de múltiples puntos de retorno
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(void) {
int error = EXIT_SUCCESS;
FILE* file = fopen("datos.txt", "r");
...
int value = 0;
fscanf(file, "%d", &value);
if (value != 0) {
...
} else {
error = EXIT_FAILURE;
}
fclose(file);
return error;
}
1.2. Expresiones y condicionales
1.2.1. Algoritmos
Se recomienda seguir el proceso de resolución de problemas, compuesto de las fases de análisis (comprender qué debe hacer el sistema), diseño (idear una solución con un artefacto barato como algoritmos en pseudocódigo), e implementación (traducir el pseudocódigo al lenguaje de programación). En todas las fases se hacen pruebas constantes y son éstas las que indican cuando se pasa de una fase a la otra.
En la fase de diseño, el artefacto barato para solucionar un problema que permita probar lo más rápidamente posible, varía de acuerdo al paradigma de programación. Por ejemplo, para el paradigma funcional es matemática, para el procedimental son algoritmos, y para el orientado a objetos es el lenguaje unificado de modelado (UML, Unnified Modeling Language). Los algoritmos se pueden especificar en diagramas de flujo o en pseudocódigo. No hay una convención estándar para el pseudocódigo, pero en el curso se usarán los ocho tipos de instrucciones provistas en el Material del curso. El siguiente es el algoritmo resultado de seguir este procedimiento para el problema del índice de masa corporal.
Listado 6. Solución en pseudocódigo para el índice de masa corporal (bmi.pseudo)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
procedure Main:
While there is data do
Classify person
procedure Classify person:
Read mass in kilograms
Read height in centimeters
Print mass, height
If mass is valid and height is valid then
Create body mass index as mass / height^2
Create nutritional state as the result of classifying the body mass index
Print body mass index, nutritional state
Else
Print invalid data
function Is mass valid:
return mass > 0 and mass <= 1000
function Is height valid:
return height > 0 and height <= 300
function Classify the body mass index (bmi):
If bmi < 18.5 then
return "underweight"
If bmi < 25 then
return "normal"
If bmi < 30 then
return "overweight"
return "obese"
1.2.2. Índice de masa corporal
En la fase de implementación, se traduce el algoritmo a código fuente en algún lenguaje de programación. Esta fase es bastante mecánica y lo que requiere es un buen dominio del lenguaje usado. El siguiente es la traducción del pseudocódigo anterior al lenguaje de programación C. Nótese la calidad del código y su documentación que surge de la fase de diseño. También considere la cantidad de pruebas y errores realizadas para crear esta solución.
Listado 7. Implementación en C del pseudocódigo para el índice de masa corporal (bmi.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
bool classify_person(void);
bool is_mass_valid(double mass);
/**
@brief Returns true if is a valid height for a human being
@details
@code
if ...
@endcode
@param height A real number in centimeters
@return True if height is suitable for a human being
*/
bool is_height_valid(double height);
/**
@param bmi Must be always positive
*/
const char* classify_body_mass_index(double bmi);
// procedure Main:
int main(void) {
// While there is data then
while (classify_person()) {
// Classify person
}
}
#include <stdint.h>
// procedure Classify person:
bool classify_person(void) {
// Read mass in kilograms
double mass = 0.0;
// Read height in centimeters
double height_in_cm = 0.0;
if (scanf("%lg %lg", &mass, &height_in_cm) == 2) {
// Print mass, height
printf("%6.2lf %6.2lf ", mass, height_in_cm);
// If is mass valid and is height in centimeters valid then
if (is_mass_valid(mass) && is_height_valid(height_in_cm)) {
// Create height in meters as height in centimeters / 100
const double height_in_meters = height_in_cm / 100.0;
// Create body mass index as mass / height in meters^2
const double bmi = mass / (height_in_meters * height_in_meters);
// Create nutrition state as the result of classifying the body mass index
const char* const nutrition_state = classify_body_mass_index(bmi);
// Print body mass index, nutrition state
printf("%5.2lf %s\n", bmi, nutrition_state);
} else {
// Print "invalid data"
printf("invalid data\n");
}
// Continue reading the next person
return true;
} else {
// Stop, there is no more people
return false;
}
}
// function is mass valid:
bool is_mass_valid(double mass) {
// Return mass > 0 and mass <= 1000
return mass > 0 && mass <= 1000;
}
// function is height valid:
bool is_height_valid(double height) {
// return height > 0 and height <= 300
return height > 0 && height <= 300;
}
// function classify the body mass (bmi) index:
const char* classify_body_mass_index(double bmi) {
// if bmi < 18.5 then
if (bmi < 18.5) {
return "underweight";
}
// if bmi < 25 then
if (bmi < 25) {
return "normal";
}
// if bmi < 30 then
if (bmi < 30) {
return "overweight";
}
return "obese";
}
1.3. Subrutinas
1.3.1. Combinaciones y permutaciones
Programa que imprime una tabla de combinaciones y permutaciones, tanto con y sin reemplazo. Se construyó un algoritmo, se implementó en un único archivo main.c, y finalmente se modularizó en archivos fuente y encabezado. Esos archivos permiten separar los que forman parte de una biblioteca y aquellos que constituyen un programa ejecutable.
Figure 1. Arquitectura del programa y biblioteca de combinatoria
El main.c es el único que conforma la aplicación:
Listado 8. Programa que imprime una tabla de combinatoria (main.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "combinations.h"
#include "permutations.h"
#define INT_T "llu"
/**
* @brief
*
* @param n
* @param r
*/
void print_combinatorics_table(int_t n, int_t r);
/**
* @brief
* @see print_combinatorics_table for params documentation
*/
void print_permutations_row(int_t n, int_t r);
void print_combinations_row(int_t n, int_t r);
// main:
int main(void) {
// Read n, r
int_t n = 0, r = 0;
if (scanf("%" INT_T " %" INT_T, &n, &r) == 2) {
// Print combinatorics table
print_combinatorics_table(n, r);
}
return EXIT_SUCCESS;
}
// procedure Print combinatorics table:
void print_combinatorics_table(int_t n, int_t r) {
// Print header
puts(" No repetitions With repetitions");
// Print permutations row
print_permutations_row(n, r);
// Print combinations row
print_combinations_row(n, r);
}
// procedure Print permutations row:
void print_permutations_row(int_t n, int_t r) {
// Print "Permutations" header
printf("Permutations");
// Print permutations no repetition
printf(" %20" INT_T, permutations_no_repetition(n, r));
// Print permutations with repetition
printf(" %20" INT_T "\n", permutations_with_repetition(n, r));
}
// procedure Print combinations row:
void print_combinations_row(int_t n, int_t r) {
// Print "combinations" header
printf("Combinations");
// Print combinations no repetition
printf(" %20" INT_T, combinations_no_repetition(n, r));
// Print combinations with repetition
printf(" %20" INT_T "\n", combinations_with_repetition(n, r));
}
Todos los demás archivos conforman la biblioteca de combinatoria con funciones reutilizables. Los archivos de combinatorics.* contienen las subrutinas comunes para las combinaciones y permutaciones:
Listado 9. combinatorics.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef COMBINATORICS_H
#define COMBINATORICS_H
typedef unsigned long long int_t;
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
/**
* @brief
*
* @param n
* @return int_t
*/
int_t factorial(const int_t n);
int_t pow_llu(const int_t n, const int_t exp);
#endif // COMBINATORICS_H
Listado 10. combinatorics.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include "combinatorics.h"
int_t factorial(const int_t n) {
// Taken from http://...
// Adapted from http://...
/// @see http://...
int_t result = 1;
for (int_t counter = 2; counter <= n; ++counter) {
result *= counter;
}
return result;
}
int_t pow_llu(const int_t n, const int_t exp) {
int_t result = 1;
for (int_t counter = 1; counter <= exp; ++counter) {
result *= n;
}
return result;
}
El encabezado permutations.h declara los símbolos que corresponden a la interfaz pública de las permutaciones. El archivo permutations.c las implementa y puede tener otras subrutinas, las cuales son de acceso privado.
Listado 11. permutations.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#ifndef PERMUTATIONS_H
#define PERMUTATIONS_H
#include "combinatorics.h"
/**
* @brief
*
* @param n
* @param r
* @remark If r > n returns 0
* @return int_t
*/
int_t permutations_no_repetition(const int_t n, const int_t r);
/**
* @brief
*
* @param n
* @param r
* @return int_t
*/
int_t permutations_with_repetition(const int_t n, const int_t r);
#endif // PERMUTATIONS_H
Listado 12. permutations.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "permutations.h"
// function Permutations with repetition:
int_t permutations_with_repetition(const int_t n, const int_t r) {
// return n^r
// return pow(n, r);
return pow_llu(n, r);
}
// function Permutations no repetition:
int_t permutations_no_repetition(const int_t n, const int_t r) {
// return n! / (n - r)!
// return factorial(n) / factorial(n - r);
// ...
int_t result = 1;
if (n >= r) {
for (int_t count = n; count > n - r; --count) {
result *= count;
}
} else {
result = 0;
}
return result;
}
Finalmente la interfaz e implementación de las combinaciones:
Listado 13. combinations.h
1
2
3
4
5
6
7
8
9
#ifndef COMBINATIONS_H
#define COMBINATIONS_H
#include "combinatorics.h"
int_t combinations_no_repetition(const int_t n, const int_t r);
int_t combinations_with_repetition(const int_t n, const int_t r);
#endif // COMBINATIONS_H
Listado 14. combinations.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include "combinations.h"
// function Combinations no repetition:
int_t combinations_no_repetition(const int_t n, const int_t r) {
// return n! / (r!(n - r)!)
// return factorial(n) / (factorial(r) * factorial(n - r));
int_t result = 1;
int_t max_denominator = MAX(r, n - r);
for (int_t i = n; i > max_denominator; --i) {
result *= i;
}
return result / factorial(MIN(r, n - r));
}
// function Combinations with repetition:
int_t combinations_with_repetition(const int_t n, const int_t r) {
// return (n + r - 1)! / (r!(n - 1)!)
// return factorial(n + r - 1) / (factorial(r) * factorial(n - 1));
int_t result = 1;
int_t max_denominator = MAX(r, n - 1);
for (int_t i = n + r - 1; i > max_denominator; --i) {
result *= i;
}
return result / factorial(MIN(r, n - 1));
}
Para compilar, se debe construir primero la biblioteca. Se pueden usar los comandos siguientes.
1
2
3
4
5
6
7
mkdir -p build
cc -c -fPIC -g -Wall -Wextra src/combinatorics.c -o build/combinatorics.o
cc -c -fPIC -g -Wall -Wextra src/combinations.c -o build/combinations.o
cc -c -fPIC -g -Wall -Wextra src/permutations.c -o build/permutations.o
mkdir -p bin
cc -shared build/combinatorics.o build/combinations.o build/permutations.o -o bin/combinatorics.so
Luego de que la biblioteca ha sido creada, se compila el ejecutable y se liga a la biblioteca dinámica:
1
2
cc -c -g -Wall -Wextra src/main.c -o build/main.o
cc build/main.o bin/combinatorics.so -o bin/combinations_permutations
Para invocar el ejecutable se llama bin/combinations_permutations. La biblioteca debe existir. Si se renombra o modifica, el ejecutable fallará.
1.4. Indirección
1.4.1. Imprimir rango de números
Listado 15. Solución al problema del rango usando punteros (range.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Copyright 2020 Jeisson Hidalgo
#include <stdio.h>
// Subroutine declaration or Function prototype
void swap(int* value1, int* value2);
// main: Prints all integer values in range {min, min + 1, ..., max}
int main(void) {
// Read min, max
int min = 0, max = 0;
if (scanf("%d %d", &min, &max) == 2) {
// If min > max then
if (min > max) {
// Swap min with max
swap(&min, &max); // Arguments
}
// Repeat index from min to max inclusive do
for (int index = min; index <= max; ++index) {
// Print index
printf("%d%c", index, (index == max ? '\n' : ' '));
}
}
return 0;
}
// Swap <value1> with <value2>:
void swap(int* value1, int* value2) { // Params: DataType varName = initValue
// Create a copy of value1
const int value1_copy = *value1;
// Assign value1 as value2
*value1 = *value2;
// Assign value2 as the copy of value1
*value2 = value1_copy;
}
1.5. Arreglos
El siguiente código crea arreglos en los diferentes segmentos (secciones) de memoria del proceso.
Listado 16. Arreglos en diferentes segmentos de memoria (array.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>
double global_array[10];
void print_global_array(void) {
for (size_t index = 0; index < 10; ++index) {
printf("%zu: %lf\n", index + 1, global_array[index]);
}
}
#if 0
int print_static_array_n(const size_t count) {
static double static_array[count];
for (size_t index = 0; index < count; ++index) {
printf("%zu: %lf\n", index + 1, static_array[index]);
}
}
#endif
void print_automatic_array(void) {
double auto_array[10];
for (size_t index = 0; index < 10; ++index) {
printf("%zu: %lf\n", index + 1, auto_array[index]);
}
}
void print_automatic_array_n(const size_t count) {
double auto_array[count];
for (size_t index = 0; index < count; ++index) {
printf("%zu: %lf\n", index + 1, auto_array[index]);
}
}
void print_heap_array_n(const size_t count) {
double* auto_array = calloc(count, sizeof(double));
for (size_t index = 0; index < count; ++index) {
printf("%zu: %lf\n", index + 1, auto_array[index]);
}
}
int main(int argc, char* argv[]) {
size_t count = 10;
if (argc == 2) {
sscanf(argv[1], "%zu", &count);
}
// print_global_array();
// print_automatic_array();
// print_static_array_n(count);
// print_automatic_array_n(count);
print_heap_array_n(count);
}
1.5.1. Mediana v1: arreglos automáticos (vulnerabilidad)
Programa que lee la cantidad de datos y luego los datos de la entrada estándar, los almacena en un arreglo automático en la pila (vulnerabilidad), los ordena, y reporta el valor del centro (mediana):
Listado 17. Mediana v1 (median1.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>
// #define ERROR_READ_VALUE_COUNT 1
// const int ERROR_READ_VALUE_COUNT = 1;
enum error_t { // unsigned int
ERROR_SUCCESS = EXIT_SUCCESS,
ERROR_READ_VALUE_COUNT,
ERROR_READ_VALUES,
};
enum error_t read_values(const size_t value_count, double values[value_count]);
int compare_double(const void* p1, const void* p2);
double calculate_median(const size_t value_count, const double* const values);
// procedure main:
int main(void) {
enum error_t error = ERROR_SUCCESS;
// Read value count
size_t value_count = 0;
if (scanf("%zu", &value_count) == 1) {
// Read values as an array of value count of real numbers
double values[value_count];
error = read_values(value_count, values);
if (error == ERROR_SUCCESS) {
// Sort values
qsort(values, value_count, sizeof(double), compare_double);
// Create median as the result of calculate the median of values
const double median = calculate_median(value_count, values);
// Print median
printf("%.2lf\n", median);
} else {
fprintf(stderr, "median: error: could not read values\n");
}
} else {
fprintf(stderr, "median: error: could not read value count\n");
error = ERROR_READ_VALUE_COUNT;
}
return error;
}
// enum error_t read_values(const size_t value_count, double* values);
// enum error_t read_values(const size_t value_count, double values[]);
enum error_t read_values(const size_t value_count, double values[value_count]) {
for (size_t index = 0; index < value_count; ++index) {
// if (scanf("%lg", &values[index]) != 1) {
if (scanf("%lg", values + index) != 1) {
return ERROR_READ_VALUES;
}
}
return ERROR_SUCCESS;
}
int compare_double(const void* p1, const void* p2) {
// const double* value1 = (const double*)p1;
// const double* value2 = (const double*)p2;
// return *value1 - *value2;
return *(const double*)p1 - *(const double*)p2;
}
// function Calculate the median of values
double calculate_median(const size_t value_count, const double* const values) {
// If value count is odd then
if (value_count % 2 == 1) {
// Return value at the center of values
return values[value_count / 2];
} else {
// Return the average of the two values at the center of values
return (values[value_count / 2 - 1] + values[value_count / 2]) / 2.0;
}
}
1.5.2. Mediana v2: arreglos en memoria dinámica
Corrige la vulnerabilidad de la versión 1. Crea el arreglo en memoria dinámica y reporta error si no hubo suficiente memoria:
Listado 18. Mediana v2 (median2.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>
// #define ERROR_READ_VALUE_COUNT 1
// const int ERROR_READ_VALUE_COUNT = 1;
enum error_t { // unsigned int
ERROR_SUCCESS = EXIT_SUCCESS,
ERROR_READ_VALUE_COUNT,
ERROR_READ_VALUES,
ERROR_NO_ENOUGH_MEMORY,
};
enum error_t read_values(const size_t value_count, double values[value_count]);
int compare_double(const void* p1, const void* p2);
double calculate_median(const size_t value_count, const double* const values);
// procedure main:
int main(void) {
enum error_t error = ERROR_SUCCESS;
// Read value count
size_t value_count = 0;
if (scanf("%zu", &value_count) == 1) {
// Read values as an array of value count of real numbers
double* values = (double*) malloc(value_count * sizeof(double));
if (values) {
error = read_values(value_count, values);
if (error == ERROR_SUCCESS) {
// Sort values
qsort(values, value_count, sizeof(double), compare_double);
// Create median as the result of calculate the median of values
const double median = calculate_median(value_count, values);
// Print median
printf("%.2lf\n", median);
} else {
fprintf(stderr, "median: error: could not read values\n");
}
free(values);
} else {
fprintf(stderr, "median: error: could not allocate values\n");
error = ERROR_NO_ENOUGH_MEMORY;
}
} else {
fprintf(stderr, "median: error: could not read value count\n");
error = ERROR_READ_VALUE_COUNT;
}
return error;
}
// enum error_t read_values(const size_t value_count, double* values);
// enum error_t read_values(const size_t value_count, double values[]);
enum error_t read_values(const size_t value_count, double values[value_count]) {
for (size_t index = 0; index < value_count; ++index) {
// if (scanf("%lg", &values[index]) != 1) {
if (scanf("%lg", values + index) != 1) {
return ERROR_READ_VALUES;
}
}
return ERROR_SUCCESS;
}
int compare_double(const void* p1, const void* p2) {
// const double* value1 = (const double*)p1;
// const double* value2 = (const double*)p2;
// return *value1 - *value2;
return *(const double*)p1 - *(const double*)p2;
}
// function Calculate the median of values
double calculate_median(const size_t value_count, const double* const values) {
// If value count is odd then
if (value_count % 2 == 1) {
// Return value at the center of values
return values[value_count / 2];
} else {
// Return the average of the two values at the center of values
return (values[value_count / 2 - 1] + values[value_count / 2]) / 2.0;
}
}
1.6. Matrices
Ejemplo que crea matrices y las imprime:
Listado 19. Mediana v2 (create_matrix.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>
void print_matrix1(const size_t rows, const size_t cols, double matrix[rows][cols]);
void print_matrix(const size_t rows, const size_t cols, double** matrix);
void test_static_matrix();
void test_heap_matrix();
double** create_double_matrix(const size_t rows, const size_t cols);
void destroy_double_matrix(double** matrix, size_t rows);
int main(void) {
// test_static_matrix();
test_heap_matrix();
}
void test_heap_matrix() {
size_t rows = 3;
size_t cols = 4;
double** matrix = create_double_matrix(rows, cols);
print_matrix(rows, cols, matrix);
destroy_double_matrix(matrix, rows);
}
double** create_double_matrix(const size_t rows, const size_t cols) {
double** matrix = calloc(rows, sizeof(double*));
if (matrix) {
for (size_t row = 0; row < rows; ++row) {
if ((matrix[row] = calloc(cols, sizeof(double))) == NULL) {
destroy_double_matrix(matrix, rows);
return NULL;
}
}
}
return matrix;
}
void destroy_double_matrix(double** matrix, size_t rows) {
if (matrix) {
for (size_t row = 0; row < rows; ++row) {
free(matrix[row]);
}
free(matrix);
}
}
void test_static_matrix() {
const size_t rows = 3;
const size_t cols = 4;
// double matrix[rows][cols] = {
double matrix[][4] = {
{1.1, 1.2, 1.3, 1.4},
{2.1, 2.2, 2.3, 2.4},
{3.1, 3.2, 3.3, 3.4},
};
// print_matrix(rows, cols, (double**)matrix);
print_matrix1(rows, cols, matrix);
}
void print_matrix1(const size_t rows, const size_t cols, double matrix[rows][cols]) {
for (size_t row = 0; row < rows; ++row) {
for (size_t col = 0; col < cols; ++col) {
printf("%g%c", matrix[row][col], col == cols - 1 ? '\n' : ' ');
}
}
}
void print_matrix(const size_t rows, const size_t cols, double** matrix) {
for (size_t row = 0; row < rows; ++row) {
for (size_t col = 0; col < cols; ++col) {
printf("%g%c", matrix[row][col], col == cols - 1 ? '\n' : ' ');
}
}
}
1.7. Registros de memoria (records)
1.7.1. Mediana v3: arreglo dinámico
Las versiones anteriores exigían al usuario proveer la cantidad de datos. Pero si el usuario no conoce este número ¿qué se puede hacer? La versión 3 de la mediana usa un arreglo dinámico. Es decir, un arreglo que puede crecer (o decrecer) en tiempo de ejecución conforme se agreguen o eliminen datos del arreglo.
Listado 20. Mediana v3 (median3.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
#include "array.h"
// #define ERROR_READ_VALUE_COUNT 1
// const int ERROR_READ_VALUE_COUNT = 1;
enum error_t { // unsigned int
ERROR_SUCCESS = EXIT_SUCCESS,
ERROR_READ_VALUE_COUNT,
ERROR_READ_VALUES,
ERROR_NO_ENOUGH_MEMORY,
};
enum error_t read_values(struct array* const values);
int compare_double(const void* p1, const void* p2);
double calculate_median(const struct array* const values);
// procedure main:
int main(void) {
enum error_t error = ERROR_SUCCESS;
// Read values as an array of value count of real numbers
// array_t values = {0, 0, NULL};
struct array values;
if (array_init(&values) == EXIT_SUCCESS) {
error = read_values(&values);
if (error == ERROR_SUCCESS) {
// Sort values
qsort(values.elements, values.count, sizeof(double), compare_double);
// Create median as the result of calculate the median of values
const double median = calculate_median(&values);
// Print median
printf("%.2lf\n", median);
} else {
fprintf(stderr, "median: error: could not read values\n");
}
array_uninit(&values);
} else {
fprintf(stderr, "median: error: could not allocate memory\n");
error = ERROR_NO_ENOUGH_MEMORY;
}
return error;
}
enum error_t read_values(struct array* const values) {
double value = 0.0;
while (scanf("%lg", &value) == 1) {
if (array_append(values, value) == EXIT_FAILURE) {
return ERROR_READ_VALUES;
}
}
return ERROR_SUCCESS;
}
int compare_double(const void* p1, const void* p2) {
// const double* value1 = (const double*)p1;
// const double* value2 = (const double*)p2;
// return *value1 - *value2;
return *(const double*)p1 - *(const double*)p2;
}
// function Calculate the median of values
double calculate_median(const struct array* const values) {
// If value count is odd then
if ((*values).count % 2 == 1) {
// Return value at the center of values
return values->elements[values->count / 2];
} else {
// Return the average of the two values at the center of values
return (values->elements[values->count / 2 - 1]
+ values->elements[values->count / 2]) / 2.0;
}
}
Listado 21. Arreglo dinámico: Interfaz pública (array.h)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#ifndef ARRAY_H
#define ARRAY_H
/**
* @brief
*
*/
struct array {
/**
* @brief
*
*/
size_t count; // 8 [1000, 1008[
size_t capacity; // 8 [1016, 1024[
double* elements; // 8 [1024, 1032[]
}; // sizeof(struct array) == 32
/*
short dirty; // 2 [1008, 1010[
char padding1[6]; // 6 [1010, 1016[ word alignment
*/
typedef struct array array_t;
int array_init(struct array* array);
int array_uninit(struct array* array);
int array_append(struct array* array, const double element);
#endif // ARRAY_H
/*
Arreglo (vector): region continua de memoria que almacena valores del
mismo tipo
Registro de memoria (record): region continua de memoria que puede almacenar
valores (campos) de diferente tipo. No es Registro de CPU (register)
Subrutina: region continua de memoria que almacena instrucciones que pueden ser
ejecutadas (invocadas, llamadas)
*/
Listado 22. Arreglo dinámico: Implementación (array.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <assert.h>
#include <stdlib.h>
#include "array.h"
#define INITIAL_CAPACITY 10
#define INCREASE_FACTOR 10
/**
* @brief (private)
*
* @param array
* @return int
*/
int increase_capacity(struct array* array);
int array_init(struct array* array) {
assert(array);
int error = EXIT_SUCCESS;
array->count = 0;
array->capacity = INITIAL_CAPACITY;
array->elements = (double*) calloc(array->capacity, sizeof(double));
if (array->elements == NULL) {
array->capacity = 0;
error = EXIT_FAILURE;
}
return error;
}
int array_uninit(struct array* array) {
assert(array);
free(array->elements);
array->count = array->capacity = 0;
return EXIT_SUCCESS;
}
int array_append(struct array* array, const double element) {
assert(array);
int error = EXIT_SUCCESS;
if (array->count == array->capacity) {
error = increase_capacity(array);
}
if (error == EXIT_SUCCESS) {
array->elements[array->count++] = element;
}
return error;
}
int increase_capacity(struct array* array) {
assert(array);
int error = EXIT_SUCCESS;
size_t new_capacity = INCREASE_FACTOR * array->capacity;
double* new_elements = (double*) calloc(new_capacity, sizeof(double));
if (new_elements) {
for (size_t index = 0; index < array->count; ++index) {
new_elements[index] = array->elements[index];
}
free(array->elements);
array->elements = new_elements;
array->capacity = new_capacity;
} else {
error = EXIT_FAILURE;
}
return error;
}
1.8. Cadenas de caracteres terminadas en nulo
1.8.1. Mediana v4: archivos
Las versiones anteriores sólo leen datos de la entrada estándar. La versión 4 permite al usuario indicar los nombres y rutas de archivos en los argumentos de línea de comandos. Esto requiere el procesamiento de cadenas de caracteres.
Listado 23. Mediana v4 (median4.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "array.h"
// #define ERROR_READ_VALUE_COUNT 1
// const int ERROR_READ_VALUE_COUNT = 1;
enum error_t { // unsigned int
ERROR_SUCCESS = EXIT_SUCCESS,
ERROR_READ_VALUE_COUNT,
ERROR_READ_VALUES,
ERROR_NO_ENOUGH_MEMORY,
ERROR_OPEN_FILE,
};
typedef struct {
bool is_input_binary;
} arguments_t;
enum error_t analyze_arguments(int argc, char* argv[], arguments_t* arguments);
int process_file(FILE* input, const char* input_filename);
enum error_t read_values(FILE* input, struct array* const values);
int compare_double(const void* p1, const void* p2);
double calculate_median(const struct array* const values);
// procedure main:
int main(int argc, char* argv[]) {
enum error_t error = ERROR_SUCCESS;
arguments_t arguments = { false };
error = analyze_arguments(argc, argv, &arguments);
// printf("is_input_binary == %d\n", arguments.is_input_binary);
if (error != ERROR_SUCCESS) {
if (argc == 1) {
process_file(stdin, "stdin");
} else {
for (int index = 1; index < argc; ++index) {
FILE* input = fopen(argv[index], "r");
if (input) { // input != NULL
error = process_file(input, argv[index]);
fclose(input);
} else {
fprintf(stderr, "median: error: could not open %s\n", argv[index]);
error = ERROR_OPEN_FILE;
}
}
}
}
return error;
}
enum error_t analyze_arguments(int argc, char* argv[], arguments_t* arguments) {
// assert
for (int index = 1; index < argc; ++index) {
if (strcmp(argv[index], "-b") == 0) {
arguments->is_input_binary = true;
}
}
return EXIT_SUCCESS;
}
int process_file(FILE* input, const char* input_filename) {
enum error_t error = ERROR_SUCCESS;
// Read values as an array of value count of real numbers
// array_t values = {0, 0, NULL};
struct array values;
if (array_init(&values) == EXIT_SUCCESS) {
error = read_values(input, &values);
if (error == ERROR_SUCCESS) {
// Sort values
qsort(values.elements, values.count, sizeof(double), compare_double);
// Create median as the result of calculate the median of values
const double median = calculate_median(&values);
// Print median
printf("%s: %.2lf\n", input_filename, median);
} else {
fprintf(stderr, "median: error: could not read values\n");
}
array_uninit(&values);
} else {
fprintf(stderr, "median: error: could not allocate memory\n");
error = ERROR_NO_ENOUGH_MEMORY;
}
return error;
}
enum error_t read_values(FILE* input, struct array* const values) {
double value = 0.0;
while (fscanf(input, "%lg", &value) == 1) {
if (array_append(values, value) == EXIT_FAILURE) {
return ERROR_READ_VALUES;
}
}
return ERROR_SUCCESS;
}
int compare_double(const void* p1, const void* p2) {
// const double* value1 = (const double*)p1;
// const double* value2 = (const double*)p2;
// return *value1 - *value2;
return *(const double*)p1 - *(const double*)p2;
}
// function Calculate the median of values
double calculate_median(const struct array* const values) {
// If value count is odd then
if ((*values).count % 2 == 1) {
// Return value at the center of values
return values->elements[values->count / 2];
} else {
// Return the average of the two values at the center of values
return (values->elements[values->count / 2 - 1]
+ values->elements[values->count / 2]) / 2.0;
}
}
#if 0
for (int index = 0; index < argc; ++index) {
printf("%d: [%s]\n", index, argv[index]);
}
#endif
Listado 24. Arreglo dinámico: Interfaz pública (array.h)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#ifndef ARRAY_H
#define ARRAY_H
/**
* @brief
*
*/
struct array {
/**
* @brief
*
*/
size_t count; // 8 [1000, 1008[
size_t capacity; // 8 [1016, 1024[
double* elements; // 8 [1024, 1032[]
}; // sizeof(struct array) == 32
/*
short dirty; // 2 [1008, 1010[
char padding1[6]; // 6 [1010, 1016[ word alignment
*/
typedef struct array array_t;
int array_init(struct array* array);
int array_uninit(struct array* array);
int array_append(struct array* array, const double element);
#endif // ARRAY_H
/*
Arreglo (vector): region continua de memoria que almacena valores del
mismo tipo
Registro de memoria (record): region continua de memoria que puede almacenar
valores (campos) de diferente tipo. No es Registro de CPU (register)
Subrutina: region continua de memoria que almacena instrucciones que pueden ser
ejecutadas (invocadas, llamadas)
*/
Listado 25. Arreglo dinámico: Implementación (array.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <assert.h>
#include <stdlib.h>
#include "array.h"
#define INITIAL_CAPACITY 10
#define INCREASE_FACTOR 10
/**
* @brief (private)
*
* @param array
* @return int
*/
int increase_capacity(struct array* array);
int array_init(struct array* array) {
assert(array);
int error = EXIT_SUCCESS;
array->count = 0;
array->capacity = INITIAL_CAPACITY;
array->elements = (double*) calloc(array->capacity, sizeof(double));
if (array->elements == NULL) {
array->capacity = 0;
error = EXIT_FAILURE;
}
return error;
}
int array_uninit(struct array* array) {
assert(array);
free(array->elements);
array->count = array->capacity = 0;
return EXIT_SUCCESS;
}
int array_append(struct array* array, const double element) {
assert(array);
int error = EXIT_SUCCESS;
if (array->count == array->capacity) {
error = increase_capacity(array);
}
if (error == EXIT_SUCCESS) {
array->elements[array->count++] = element;
}
return error;
}
int increase_capacity(struct array* array) {
assert(array);
int error = EXIT_SUCCESS;
size_t new_capacity = INCREASE_FACTOR * array->capacity;
double* new_elements = (double*) calloc(new_capacity, sizeof(double));
if (new_elements) {
for (size_t index = 0; index < array->count; ++index) {
new_elements[index] = array->elements[index];
}
free(array->elements);
array->elements = new_elements;
array->capacity = new_capacity;
} else {
error = EXIT_FAILURE;
}
return error;
}
La versión 4 también puede leer datos de archivos binarios. Para convertir archivos de datos en texto a archivos de datos en binario, se provee una pequeña herramienta txt2bin:
Listado 26. txt2bin: convertidor de datos de texto a binario (txt2bin.c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <stdlib.h>
int process_file(FILE* input, const char* input_filename);
int convert(FILE* input, const char* input_filename, FILE* output
, const char* output_filename);
// procedure main:
int main(int argc, char* argv[]) {
int error = EXIT_SUCCESS;
if (argc == 1) {
process_file(stdin, "stdin");
} else {
for (int index = 1; index < argc; ++index) {
FILE* input = fopen(argv[index], "r");
if (input) { // input != NULL
error = process_file(input, argv[index]);
fclose(input);
} else {
fprintf(stderr, "txt2bin: error: could not open %s\n", argv[index]);
error = EXIT_FAILURE;
}
}
}
return error;
}
size_t length_idx(const char* text) {
size_t index = 0;
while (text[index]) { // != '\0'
++index;
}
return index;
}
size_t length_ptr(const char* text) {
size_t length = 0;
while (*text++) { // *(text + length)
++length;
}
return length;
}
int process_file(FILE* input, const char* input_filename) {
int error = EXIT_SUCCESS;
// const char* output_filename = input_filename + ".bin";
const char* extension = ".bin";
const size_t len_output_filename = length_ptr(input_filename)
+ length_ptr(extension);
const size_t capacity_output_filename = len_output_filename + 1;
char output_filename[capacity_output_filename];
sprintf(output_filename, "%s%s", input_filename, extension);
FILE* output = fopen(output_filename, "wb");
if (output) {
convert(input, input_filename, output, output_filename);
fclose(output);
} else {
fprintf(stderr, "txt2bin: error: could not create %s\n", output_filename);
error = EXIT_FAILURE;
}
return error;
}
int convert(FILE* input, const char* input_filename, FILE* output
, const char* output_filename) {
int error = EXIT_SUCCESS;
(void)input_filename;
double value = 0.0;
while (fscanf(input, "%lg", &value) == 1) {
// fprintf(output, "%lg", value);
// size_t fwrite(const void* ptr, size_t size, size_t count, FILE* stream);
const size_t written_count = fwrite(&value, sizeof(value), 1, output);
if (written_count < 1) {
fprintf(stderr, "txt2bin: error: could not write %s\n", output_filename);
error = EXIT_FAILURE;
break;
}
}
// printf("converting from %s to %s\n", input_filename, output_filename);
return error;
}
#if 0
for (size_t index = 0; index < length(input_filename); ++index) {
// 1µs 10^12/10^6 = 10^6
}
const size_t len = length(input_filename);
for (size_t index = 0; index < len; ++index) {
}
#endif
2. Programación genérica
Conceptos del paradigma:
-
Entrada y salida genérica (
std::cin,std::cout). -
Sobrecarga de subrutinas y name mangling.
-
Sobrecarga de operadores (operator overloading).
-
Plantillas de subrutinas (templates).
-
Plantillas de registros.
-
Espacios de nombres (namespaces).
2.1. Sobrecarga de subrutinas y plantillas
2.1.1. Fracción v1: fracción genérica con registros
Una fracción es un tipo de datos que se compone de un númerador y un denominador, ambos enteros, y el denominador no puede ser cero. Como enteros podrían usarse tipos de datos como int o long long o short, o incluso precisión arbitraria, de acuerdo a los requerimientos del problema. Conviene entonces que los tipos de datos puedan pasarse por parámetro, y C++ permite esto con plantillas. Las Plantillas siempre deben estar en archivos de encabezados por una limitación del diseño de compiladores de este lenguaje.
Listado 27. main.cpp: hace algunas pruebas informales a las fracciones genéricas (main.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdlib>
#include "fraction.hpp"
// main:
int main() {
int error = EXIT_SUCCESS;
Fraction<int> value;
fraction_init(&value);
Fraction<int> sum;
fraction_init(&sum);
while (std::cin >> value) {
std::cout << "> " << value << std::endl;
sum = sum + value;
}
// fraction_print(std::cout, value) << ':';
// fraction_print(std::cout, sum) << std::endl;
// operator<<(std::cout, sum) << std::endl;
std::cout << sum << std::endl;
return error;
}
// fixed-point 2^64, unsigned/signed(two's complement)
// floating-point 238.72 == 23.872*10^1 == 287.2*10^-1 IEEE 754
// quantum arithmetic
// arbitrary-precision arithmetic (SW)
Listado 28. fraction.hpp: registro genérico y subrutinas genéricas para fracciones (fraction.hpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#ifndef ARRAY_H
#define ARRAY_H
#include <iostream>
template <typename Integer>
struct Fraction {
Integer numerator; // fields -> attributes
Integer denominator; // member = attributes | method
};
template <typename Integer>
const Integer& gcd(const Integer& a, const Integer& b) {
// TODO(any): verify behvaior with a or b negatives
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
template <typename Integer>
void fraction_simplify(Fraction<Integer>* fraction) {
assert(fraction);
const Integer& fraction_gcd = gcd(fraction->numerator, fraction->denominator);
fraction->numerator /= fraction_gcd;
fraction->denominator /= fraction_gcd;
if (fraction->denominator < 0) {
fraction->numerator = -fraction->numerator;
fraction->denominator = -fraction->denominator;
}
}
template <typename Integer>
void fraction_init(Fraction<Integer>* fraction, const Integer& numerator = 0,
const Integer& denominator = 1) { // default arguments
assert(fraction);
fraction->numerator = numerator;
fraction->denominator = denominator;
fraction->fraction_simplify();
}
template <typename Integer>
std::ostream& fraction_print(std::ostream& output
, const Fraction<Integer>& fraction) {
return output << fraction.numerator << '/' << fraction.denominator;
}
template <typename Integer>
std::ostream& operator<<(std::ostream& output
, const Fraction<Integer>& fraction) {
return output << fraction.numerator << '/' << fraction.denominator;
}
template <typename Integer>
std::istream& operator>>(std::istream& input, Fraction<Integer>& fraction) {
input >> fraction.numerator >> fraction.denominator;
// fraction_simplify(&fraction);
fraction.fraction_simplify();
return input;
}
template <typename Integer>
Fraction<Integer> add(const Fraction<Integer>& fr1
, const Fraction<Integer>& fr2) {
Fraction<Integer> result;
// a/b + c/d = (ad + bc)/(bd)
result.numerator = fr1.numerator * fr2.denominator
+ fr1.denominator * fr2.numerator;
result.denominator = fr1.denominator * fr2.denominator;
// fraction_simplify(&result);
result.fraction_simplify();
return result;
}
template <typename Integer>
Fraction<Integer> operator+(const Fraction<Integer>& fr1
, const Fraction<Integer>& fr2) {
Fraction<Integer> result;
// a/b + c/d = (ad + bc)/(bd)
fraction_init(&result
, fr1.numerator * fr2.denominator + fr1.denominator * fr2.numerator
, fr1.denominator * fr2.denominator);
return result;
}
#endif // ARRAY_H
2.1.2. Mediana v5: arreglo dinámico genérico
La versión 4 usa un arreglo dinámico pero de números de doble precisión flotante. No se puede usar con otro tipo de datos. La versión 5 usa programación genérica para que el registro y las subrutinas del arreglo dinámico sean genéricas, y por lo tanto, pueda obtenerse la mediana de cualquier tipo de datos que represente números.
Listado 29. Mediana v5 (median.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cmath>
#include <cstdlib>
#include <fstream>
#include <iostream>
// using std::cerr;
// using namespace std;
#include "arguments.hpp"
#include "array.hpp"
// long cerr = 022928282828228l;
enum error_code read_values(array_t<double>* values, std::istream& input
, const arguments_t* const arguments);
int compare_double(const void* p1, const void* p2);
double calculate_median(const array_t<double>* const values);
int process_file(std::istream& input, const char* filename
, const arguments_t* const arguments);
// main:
int main(int argc, char* argv[]) {
int error = ERROR_SUCCESS;
arguments_t arguments;
arguments_init(&arguments);
error = analyze_arguments(&arguments, argc, argv);
if (error == ERROR_SUCCESS) {
if (argc >= 2) {
for (int index = 1; index < argc; ++index) {
if (*argv[index] != '-') {
// printf("%d = [%s]\n", index, argv[index]);
std::ios_base::openmode mode = arguments.is_input_binary
? std::ios_base::in | std::ios_base::binary : std::ios_base::in;
std::ifstream input(argv[index], mode);
if (input) {
process_file(input, argv[index], &arguments);
input.close();
} else {
// int cerr = 0;
// ::cerr = cerr;
std::cerr << "could not open " << argv[index] << '\n';
}
}
}
} else {
process_file(std::cin, "stdin", &arguments);
}
arguments_uninit(&arguments);
}
return error;
}
int process_file(std::istream& input, const char* filename
, const arguments_t* const arguments) {
enum error_code error = ERROR_SUCCESS;
// Read values as an array of real numbers
// array_t values;
array_t<double> values;
if (array_init(&values) == EXIT_SUCCESS) {
error = read_values(&values, input, arguments);
if (error == ERROR_SUCCESS) {
// Sort values
qsort(values.elements, values.count, sizeof(double), compare_double);
// Calculate median of values
const double median = calculate_median(&values);
// Print median
std::cout << filename << ": " << median << std::endl;
} else {
std::cerr << "median: error: could not read values\n";
}
array_uninit(&values);
} else {
std::cerr << "median: error: could not allocate memory\n";
error = ERROR_NO_ENOUGH_MEMORY;
}
return error;
}
// const_cast<>
// static_cast<>
// dynamic_cast<>
// reinterpret_cast<>
enum error_code read_values(array_t<double>* values, std::istream& input
, const arguments_t* const arguments) {
double value = 0.0;
if (arguments->is_input_binary) {
// size_t fread(void* ptr, size_t size, size_t count, FILE * stream);
while (input.read(reinterpret_cast<char*>(&value), sizeof(value))) {
if (array_append(values, value) != EXIT_SUCCESS) {
return ERROR_CANNOT_APPEND_VALUE;
}
}
} else {
// std::cout << value << std::endl;
// std::cin >> value >> value;
while (input >> value) {
if (array_append(values, value) != EXIT_SUCCESS) {
return ERROR_CANNOT_APPEND_VALUE;
}
}
}
return ERROR_SUCCESS;
}
int compare_double(const void* p1, const void* p2) {
// const double* value1 = (double*) p1;
// const double* value2 = (double*) p2;
// return *value1 - *value2;
return *(double*)p1 - *(double*)p2;
}
// median:
double calculate_median(const array_t<double>* const values) {
// If value count is odd then
if ((*values).count % 2 == 1) {
// Return value at index value count / 2
return values->elements[values->count / 2];
} else {
// Return average of two values at the center of the array
return (values->elements[values->count / 2 - 1]
+ values->elements[values->count / 2]) / 2.0;
}
}
// array_t<int> enteros;
// array_init(&enteros);
// array_append(&enteros, 0);
// array_uninit(&enteros);
// array_t<array_t<double>> matrix;
// array_init(&matrix);
Listado 30. Arreglo dinámico: Plantillas de registro y subrutinas (array.hpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#ifndef ARRAY_H
#define ARRAY_H
#include <cstddef>
/*
Arreglo (vector): region continua de memoria que almacena valores del
mismo tipo
Registro de memoria (record): region continua de memoria que puede almacenar
valores (campos) de diferente tipo. No es Registro de CPU (register)
Subrutina: region continua de memoria que almacena instrucciones que pueden ser
ejecutadas (invocadas, llamadas)
*/
/**
* @brief
*
*/
// template<class T>
template<typename DataType>
struct array_t {
/**
* @brief
*
*/
size_t count;
size_t capacity;
DataType* elements;
};
// template<typename DataType>
// using array_t = struct array<DataType>;
// int array_init(array_t* array);
template<typename DataType>
int array_init(array_t<DataType>* array); // Constructor
template<typename DataType>
int array_uninit(array_t<DataType>* array); // Destructor
template<typename DataType>
int array_append(array_t<DataType>* array, const DataType& value);
#include <assert.h>
#include <stdlib.h>
#define INITIAL_CAPACITY 10
#define INCREASE_FACTOR 10
/**
* @brief (private subroutine)
*
* @param array
* @return int
*/
template<typename DataType>
int increase_capacity(array_t<DataType>* array);
template<typename DataType>
int array_init(array_t<DataType>* array) {
assert(array);
int error = EXIT_SUCCESS;
array->count = 0;
array->capacity = INITIAL_CAPACITY;
array->elements = (DataType*) calloc(INITIAL_CAPACITY, sizeof(DataType));
if (array->elements == NULL) {
array->capacity = 0;
error = EXIT_FAILURE;
}
return error;
}
template<typename DataType>
int array_uninit(array_t<DataType>* array) {
assert(array);
free(array->elements);
return EXIT_SUCCESS;
}
template<typename DataType>
int array_append(array_t<DataType>* array, const DataType& value) {
assert(array);
int error = EXIT_SUCCESS;
if (array->count == array->capacity) {
error = increase_capacity(array);
}
if (error == EXIT_SUCCESS) {
array->elements[array->count++] = value;
}
return error;
}
template<typename DataType>
int increase_capacity(array_t<DataType>* array) {
assert(array);
int error = EXIT_SUCCESS;
size_t new_capacity = INCREASE_FACTOR * array->capacity;
DataType* new_elements = (DataType*) calloc(new_capacity, sizeof(DataType));
if (new_elements) {
for (size_t index = 0; index < array->count; ++index) {
new_elements[index] = array->elements[index];
}
free(array->elements);
array->capacity = new_capacity;
array->elements = new_elements;
} else {
error = EXIT_FAILURE;
}
return error;
}
#endif // ARRAY_H
Listado 31. Arreglo dinámico: Implementación (código movido al encabezado) (array.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <assert.h>
#include <stdlib.h>
#include "array.hpp"
#ifdef MOVED_TO_HEADER
#define INITIAL_CAPACITY 10
#define INCREASE_FACTOR 10
/**
* @brief (private subroutine)
*
* @param array
* @return int
*/
template<typename DataType>
int increase_capacity(array_t<DataType>* array);
template<typename DataType>
int array_init(array_t<DataType>* array) {
assert(array);
int error = EXIT_SUCCESS;
array->count = 0;
array->capacity = INITIAL_CAPACITY;
array->elements = (double*) calloc(INITIAL_CAPACITY, sizeof(double));
if (array->elements == NULL) {
array->capacity = 0;
error = EXIT_FAILURE;
}
return error;
}
template<typename DataType>
int array_uninit(array_t<DataType>* array) {
assert(array);
free(array->elements);
return EXIT_SUCCESS;
}
template<typename DataType>
int array_append(array_t<DataType>* array, const double value) {
assert(array);
int error = EXIT_SUCCESS;
if (array->count == array->capacity) {
error = increase_capacity(array);
}
if (error == EXIT_SUCCESS) {
array->elements[array->count++] = value;
}
return error;
}
template<typename DataType>
int increase_capacity(array_t<DataType>* array) {
assert(array);
int error = EXIT_SUCCESS;
size_t new_capacity = INCREASE_FACTOR * array->capacity;
double* new_elements = (double*) calloc(new_capacity, sizeof(double));
if (new_elements) {
for (size_t index = 0; index < array->count; ++index) {
new_elements[index] = array->elements[index];
}
free(array->elements);
array->capacity = new_capacity;
array->elements = new_elements;
} else {
error = EXIT_FAILURE;
}
return error;
}
#endif // MOVED_TO_HEADER
/*
struct array {
double* array; // 8 [1000, 1008[
size_t capacity; // 8 [1016, 1024[
size_t count; // 8 [1024, 1032[
// 32
char dirty; // 1 [1008, 1009[
// char padding1[7];// 7 [1009, 1016[
};
int main() {
struct array local_array = {NULL, 0, 0};
static struct array var1;
printf("%zu\n", sizeof(var1));
}
*/
Ejercicio: Que la versión 5 de txt2bin use E/S de C++ en lugar de FILE*.
Listado 32. txt2bin: convertidor de datos de texto a binario (txt2bin.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// Copyright 2020 Jeisson Hidalgo ECCI-UCR
#include <stdio.h>
#include <stdlib.h>
int process_file(FILE* input, const char* input_filename);
int convert(FILE* input, const char* input_filename, FILE* output
, const char* output_filename);
// main:
int main(int argc, char* argv[]) {
int error = EXIT_SUCCESS;
if (argc >= 2) {
for (int index = 1; index < argc; ++index) {
// printf("%d = [%s]\n", index, argv[index]);
if (*argv[index] != '-') {
FILE* input = fopen(argv[index], "r");
if (input) {
process_file(input, argv[index]);
fclose(input);
} else {
fprintf(stderr, "could not open %s\n", argv[index]);
error = EXIT_FAILURE;
}
}
}
} else {
error = process_file(stdin, "stdin");
}
return error;
}
size_t length_idx(const char* text) {
size_t index = 0;
while (text[index]) { /* != '\0' */
++index;
}
return index;
}
size_t length_ptr(const char* text) {
size_t length = 0;
while (*text++) { /* != '\0' */
++length;
}
return length;
}
int process_file(FILE* input, const char* input_filename) {
int error = EXIT_SUCCESS;
// const char* output_filename = input_filename + ".bin";
const char* const extension = ".bin";
const size_t len_output_filename = length_ptr(input_filename)
+ length_idx(extension);
char output_filename[len_output_filename + 1];
// *output_filename = '\0'; output_filename[0] = '\0';
snprintf(output_filename, len_output_filename + 1, "%s%s", input_filename
, extension);
FILE* output = fopen(output_filename, "wb");
if (output) {
error = convert(input, input_filename, output, output_filename);
fclose(output);
} else {
fprintf(stderr, "could not open %s\n", output_filename);
error = EXIT_FAILURE;
}
return error;
}
int convert(FILE* input, const char* input_filename, FILE* output
, const char* output_filename) {
(void)input_filename;
int error = EXIT_SUCCESS;
// printf("converting from %s to %s\n", input_filename, output_filename);
double value = 0;
while (fscanf(input, "%lg", &value) == 1) {
// fprintf(output, "%lg\n", value); // text output file
// size_t fwrite(const void * ptr, size_t size, size_t count, FILE * stream);
size_t written_count = fwrite(&value, sizeof(value), 1, output);
if (written_count < 1) {
fprintf(stderr, "could not write to %s\n", output_filename);
error = EXIT_FAILURE;
break;
}
}
return error;
}
#if 0
for (size_t index = 0; index < length_idx(input); ++index) {
// O(n^2)
}
const size_t len = length_idx(input);
for (size_t index = 0; index < len; ++index) {
// O(n^2)
}
#endif
3. Programación orientada a objetos
El paradigma de programación orientado a objetos agrega los siguientes conceptos:
-
Clases (registros), objetos (instancias), atributos (campos), métodos (subrutinas). Corresponden a un azúcar sintáctico cuya novedad es asociar subrutinas a los registros mediante un parámetro oculto (
this) que referencia al registro. -
Herencia de registros.
-
Polimorfismo de subrutinas (métodos).
3.1. Fracción v2: Objeto fracción genérico
PENDIENTE
4. Programación genérica orientada objetos
Se crea una pequeña biblioteca reutilizable de uso general que contiene clases comunes: cadenas de caracteres (String), arreglo dinámico (Array), lista doblemente enlazada (List), y árbol (Map). Para cada clase se crea una aplicación de ejemplo, e idealmente un programa de pruebas. El siguiente Makefile se usa para construir la biblioteca, programas de prueba, y programas de ejemplo.
Listado 33. Makefile: construye la biblioteca, aplicaciones, y pruebas (Makefile)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
CXX=g++
CXXFLAGS=-Wall -Wextra -std=c++17 -fno-elide-constructors
DEFS=#-DVERBOSE
.PHONY: all
all: bin/ecci.a bin/concat bin/median bin/words
.PHONY: asan
asan: CXXFLAGS += -fsanitize=address -fno-omit-frame-pointer
asan: all
# Link Concat app
bin/concat: build/concat/main.o bin/ecci.a | bin/.
$(CXX) -g $(CXXFLAGS) $(DEFS) $^ -o $@
# Compile Concat app
build/concat/main.o: src/concat/main.cpp | build/concat/.
$(CXX) -c -g $(CXXFLAGS) $(DEFS) -Isrc/ecci $< -o $@
# Link Median app
bin/median: build/median/median.o bin/ecci.a | bin/.
$(CXX) -g $(CXXFLAGS) $(DEFS) $^ -o $@
# Compile Median app
build/median/median.o: src/median/median.cpp | build/median/.
$(CXX) -c -g $(CXXFLAGS) $(DEFS) -Isrc/ecci $< -o $@
# Link Words app
bin/words: build/words/main.o bin/ecci.a | bin/.
$(CXX) -g $(CXXFLAGS) $(DEFS) $^ -o $@
# Compile Words app
build/words/main.o: src/words/main.cpp | build/words/.
$(CXX) -c -g $(CXXFLAGS) $(DEFS) -Isrc/ecci $< -o $@
# ECCI static library
bin/ecci.a: build/ecci/String.o | bin/.
ar rs $@ $^
build/ecci/%.o: src/ecci/%.cpp src/ecci/%.hpp | build/ecci/.
$(CXX) -c -g $(CXXFLAGS) $(DEFS) $< -o $@
.PRECIOUS: %/.
%/.:
mkdir -p $@
.PHONY: clean
clean:
rm -rf bin/ build/ doc/
.PHONY: lint
lint:
cpplint --filter=-build/header_guard,-build/include_subdir,-build/c++11,-runtime/references src/concat/*.?pp src/ecci/*.?pp
4.1. Clase String
El manejo de cadenas de caracteres (textos) es muy complejo en C. La orientación a objetos y la sobrecarga de operadores facilitan crear interfaces que faciliten el trabajo con textos y reutilizar esta funcionalidad. La siguiente implementación de String es un registro de dos campos: la longitud y el texto que siempre está almacenado en memoria dinámica. Por consistencia con C, C++ trata a los registros como valores, y por defecto, la copia de registros está permitida. Esto ocasiona varios inconvenientes, y por lo tanto, se deben sobrecargar los métodos que el lenguaje provee por defecto para permitir copias (copy semantics):
-
Destructor: para liberar la memoria dinámica
-
Constructor de copia: para evitar que un nuevo objeto comparta memoria con el objeto modelo del cual debe copiarse.
-
Operador de asignación de copia: para evitar que un objeto existente copie la dirección de memoria de otro.
Cuando uno de los tres métodos anteriores se implementa, es necesario implementar los otros dos. A esto se le llama regla de los 3. C++ siempre implementa esos tres métodos para todo registro (struct o class). Las versiones por defecto, realizan copia directa de los campos del registro. Se puede pedir al lenguaje que no provea estas implementaciones.
A partir de C++11 se pueden proveer dos métodos que pueden aprovechar (trasladar o "robar") los recursos de otro objeto que no va a ser utilizado más (move semantics):
-
Constructor de traslado: cuando un objeto en creación debe copiar a otro que se sabe no va a ser utilizado más.
-
Operador de asignación de traslado: cuando un objeto ya creado debe copiar a otro que se sabe no va a ser utilizado más.
Listado 34. concat: programa que usa la clase String para leer palabras (tokens) de la entrada estándar y concatenarlos (main.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CC-BY-4.0
#include "String.hpp"
void print(const ecci::String& str) {
for (size_t index = 0; index < str.getLength(); ++index) {
std::cout << '[' << str[index] << ']';
}
std::cout << std::endl;
}
int main() {
ecci::String sum;
// ecci::String sum = "djjd";
// ecci::String value("dos2");
// ecci::String value(std::move(sum));
ecci::String value;
// ecci::String value("esto era de value");
// value = std::move(sum);
// value = (ecci::String&&)(sum);
// ecci::String value = sum;
while (std::cin >> value) {
// std::cout << value << std::endl;
sum += value;
// sum = sum + ecci::String(7);
// sum = sum + 7;
// sum = sum + ":)";
// sum = sum + " " + value;
// sum = sum + ' ' + value;
// sum = sum + ecci::String(" ") + value;
}
sum[0] = std::toupper(sum[0]);
print(sum);
std::cout << sum << std::endl;
// NO: value.~String();
// double x = 5.0;
// double y = 3.0, z;
// (z = y) = 2 * x;
// std::cout << z << std::endl;
}
void legacy_c(ecci::String input_filename) {
ecci::String output_filename = input_filename + ".bin";
// FILE* output = fopen((const char*)output_filename, "wb");
FILE* output = fopen(output_filename.c_str(), "wb");
// ...
fclose(output);
}
Listado 35. String.hpp: declara la clase
String (String.hpp) 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CC-BY-4.0
#ifndef STRING_HPP
#define STRING_HPP
#include <iostream>
#define TESTING
#define implicit
namespace ecci {
class String {
private:
/// Count of characters stored in text
size_t length;
/// Pointer to the first char
char* text;
public:
/// Default constructor and conversion constructor
implicit String(const char* text = "");
/// Conversion constructor
implicit String(char ch);
/// Capacity constructor
explicit String(const size_t length);
/// Copy constructor. Copy semantics
String(const String& other);
/// Move constructor. Move semantics
String(String&& other);
/// Destructor
~String();
/// Copy assignment operator. Copy semantics
String& operator=(const String& other);
/// Move assignment operator. Move semantics
String& operator=(String&& other);
public: // Accessors
/// Get the count of chars
inline size_t getLength() const { return this->length; }
/// Get access to the internal text
inline const char* getText() const { return this->text; }
/// Get access to the internal text: std uses c_str() or data() methods
inline const char* c_str() const { return this->text; }
#ifdef DANGEROUS
/// Converts ecci::String object when it is used within a const char* context
inline explicit operator const char*() const { return this->text; }
#endif
/// Get read-only access to the i-th char element. Caller must be sure index
/// is not out of bounds
inline const char& operator[](size_t index) const { // const String* this
return this->text[index];
}
/// Get read-write access to the i-th char element. Caller must be sure index
/// is not out of bounds
inline char& operator[](size_t index) { // String* this
return this->text[index];
}
/// Get read-only access to the i-th char element. An exception is launched
/// if index is out of bounds
const char& at(size_t index) const;
/// Get read-write access to the i-th char element. An exception is launched
/// if index is out of bounds
char& at(size_t index);
public: // Input/output
/// E.g: std::cout << string << std::endl
friend std::ostream& operator<<(std::ostream& output, const String& text);
/// Read a token from the given stream. E.g: std::cin >> string
friend std::istream& operator>>(std::istream& input, String& text);
public:
/// Concatenation str1 + str2
friend String operator+(const String& left, const String& right);
/// Extends this object concatenating the given string
/// friend String& operator+=(String& left, const String& right);
String& operator+=(const String& right);
private:
/// This is not a buffered string, capacity is always length + 1
inline size_t capacity() const {
return this->length + 1;
}
#ifdef TESTING
private:
/// Counts the amount of String instances created during process execution
static size_t instanceCount;
public:
/// Returns the count of instances created during process execution
inline static size_t getInstanceCount() { return String::instanceCount; }
#endif // TESTING
};
} // namespace ecci
#endif // STRING_HPP
Listado 36. String.cpp: implementa la clase
String (String.cpp) 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CC-BY-4.0
#include <cassert>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include "String.hpp"
namespace ecci {
size_t String::instanceCount = 0;
String::String(const char* text)
: length(std::strlen(text))
, text{ reinterpret_cast<char*>(
std::malloc(this->capacity() * sizeof(char))) } {
assert(text);
if (this->text == nullptr) {
throw std::runtime_error("no enough memory to create string from char*");
}
std::strncpy(this->text, text, this->capacity());
#ifdef VERBOSE
std::cerr << "::String(" << this->text << ")" << std::endl;
#endif // VERBOSE
#ifdef TESTING
++String::instanceCount;
#endif // TESTING
}
String::String(char ch)
: length(1)
, text(reinterpret_cast<char*>(
std::malloc(this->capacity() * sizeof(char)))) {
if (this->text == nullptr) {
throw std::runtime_error("no enough memory to create string from char");
}
this->text[0] = ch;
this->text[1] = '\0';
#ifdef VERBOSE
std::cerr << "::StringCh(" << this->text << ")" << std::endl;
#endif // VERBOSE
#ifdef TESTING
++String::instanceCount;
#endif // TESTING
}
String::String(const size_t length)
: length(0)
, text(reinterpret_cast<char*>(std::malloc((length + 1) * sizeof(char)))) {
if (this->text == nullptr) {
throw std::runtime_error("no enough memory to create string with capacity");
}
*this->text = '\0';
#ifdef VERBOSE
std::cerr << "::StringSz(" << length << ")" << std::endl;
#endif // VERBOSE
#ifdef TESTING
++String::instanceCount;
#endif // TESTING
}
String::String(const String& other)
: length(other.length)
, text(reinterpret_cast<char*>(
std::malloc(other.capacity() * sizeof(char)))) {
if (this->text == nullptr) {
throw std::runtime_error("no enough memory to create string as a copy");
}
std::strncpy(this->text, other.text, other.capacity());
#ifdef VERBOSE
std::cerr << "::StringCp(" << this->text << ")" << std::endl;
#endif // VERBOSE
#ifdef TESTING
++String::instanceCount;
#endif // TESTING
}
String::String(String&& other)
: length(other.length)
, text(other.text) {
other.length = 0;
other.text = nullptr;
#ifdef VERBOSE
std::cerr << "::StringMv(" << this->text << ")" << std::endl;
#endif // VERBOSE
#ifdef TESTING
++String::instanceCount;
#endif // TESTING
}
String::~String() {
#ifdef VERBOSE
std::cerr << "::~String(" << (this->text ? this->text : "null") << ")"
<< std::endl;
#endif // VERBOSE
free(this->text);
// NOTE: Do not decrease instance count
}
String& String::operator=(const String& other) {
if (this != &other) {
if (this->capacity() != other.capacity()) {
this->length = other.length;
free(this->text);
this->text = reinterpret_cast<char*>(
std::malloc(other.capacity() * sizeof(char)));
if (this->text == nullptr) {
throw std::runtime_error("no enough memory to assign string to other");
}
}
std::strncpy(this->text, other.text, other.capacity());
}
#ifdef VERBOSE
std::cerr << "::operator=(" << this->text << ")" << std::endl;
#endif // VERBOSE
return *this;
}
String& String::operator=(String&& other) {
if (this != &other) {
std::swap(this->length, other.length);
std::swap(this->text, other.text);
}
#ifdef VERBOSE
std::cerr << "::operator=Mv(" << this->text << ")" << std::endl;
#endif // VERBOSE
return *this;
}
char& String::at(size_t index) {
if (index < this->length) {
return this->text[index];
} else {
throw std::runtime_error("index out of bounds");
}
}
const char& String::at(size_t index) const {
if (index < this->length) {
return this->text[index];
} else {
throw std::runtime_error("index out of bounds");
}
}
String operator+(const String& left, const String& right) {
const size_t result_length = left.length + right.length;
String result(result_length);
std::strncpy(result.text, left.text, left.length);
std::strncpy(result.text + left.length, right.text, right.capacity());
result.length = result_length;
return result;
}
String& String::operator+=(const String& right) {
const size_t myNewLength = this->length + right.length;
char* myNewText = reinterpret_cast<char*>(
std::realloc(this->text, (myNewLength + 1) * sizeof(char)));
if (myNewText == nullptr) {
throw std::runtime_error("no enough memory to concatenate with +=");
}
this->text = myNewText;
std::strncpy(this->text + this->length, right.text, right.capacity());
this->length = myNewLength;
return *this;
}
std::ostream& operator<<(std::ostream& output, const String& text) {
#ifdef VERBOSE
return output << '[' << text.length << "]{" << text.text << '}';
#else
return output << text.text;
#endif // VERBOSE
}
std::istream& operator>>(std::istream& input, String& text) {
size_t buffer_capacity = 100;
char* buffer = reinterpret_cast<char*>(
::malloc(buffer_capacity * sizeof(char)));
size_t buffer_length = 0;
// Ignore whitespace before the token
while (input.get(buffer[buffer_length]) && ::isspace(buffer[buffer_length])) {
}
// Avoid increase length if EOF was read
if (input) {
++buffer_length;
}
// Read token characters
while (input.get(buffer[buffer_length])
&& !::isspace(buffer[buffer_length])) {
++buffer_length;
if (buffer_length == buffer_capacity) {
buffer_capacity *= 10;
buffer = reinterpret_cast<char*>(
::realloc(buffer, buffer_capacity * sizeof(char)));
assert(buffer);
}
}
buffer[buffer_length] = '\0';
free(text.text);
// Remove extra bytes from buffer to match capacity to length + 1
text.length = buffer_length;
text.text = reinterpret_cast<char*>(
::realloc(buffer, text.capacity() * sizeof(char)));
return input;
}
} // namespace ecci
4.2. Makefile para la biblioteca ECCI
El siguiente Makefile es compartido por:
-
La biblioteca ECCI:
src/ecci/ -
Las aplicaciones de ejemplo:
src/<app>/que muestran cómo usar los contenedores genéricos para algún propósito concreto. -
El programa de pruebas unitarias (caja blanca) con Catch2:
src/test/
Listado 37. Makefile (Makefile)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
CXX=g++
CXXFLAGS=-Wall -Wextra -std=c++17 -fno-elide-constructors
.PHONY: all
all: bin/ecci.a bin/concat bin/median bin/words bin/word_count # bin/test
.PHONY: asan
asan: CXXFLAGS += -fsanitize=address -fno-omit-frame-pointer
asan: all
# Link Concat app
bin/concat: build/concat/main.o bin/ecci.a | bin/.
$(CXX) -g $(CXXFLAGS) $^ -o $@
# Compile Concat app source
build/concat/main.o: src/concat/main.cpp | build/concat/.
$(CXX) -c -g $(CXXFLAGS) -Isrc/ecci $< -o $@
# Link Median app
bin/median: build/median/median.o bin/ecci.a | bin/.
$(CXX) -g $(CXXFLAGS) $^ -o $@
# Compile Median app source
build/median/median.o: src/median/median.cpp | build/median/.
$(CXX) -c -g $(CXXFLAGS) -Isrc/ecci $< -o $@
# Link Words app
bin/words: build/words/main.o bin/ecci.a | bin/.
$(CXX) -g $(CXXFLAGS) $^ -o $@
# Compile Words app source
build/words/main.o: src/words/main.cpp | build/words/.
$(CXX) -c -g $(CXXFLAGS) -Isrc/ecci $< -o $@
# Link Word count app
bin/word_count: build/word_count/main.o bin/ecci.a | bin/.
$(CXX) -g $(CXXFLAGS) $^ -o $@
# Compile word_count app source
build/word_count/main.o: src/word_count/main.cpp | build/word_count/.
$(CXX) -c -g $(CXXFLAGS) -Isrc/ecci $< -o $@
# Link Word count app
bin/test: build/test/test_array.o build/test/test_map.o build/test/main.o bin/ecci.a | bin/.
$(CXX) -g $(CXXFLAGS) $^ -o $@
# Compile test app source
build/test/%.o: src/test/%.cpp src/test/catch.hpp | build/test/.
$(CXX) -c -g $(CXXFLAGS) -Isrc/ecci $< -o $@
# Download the catch.hpp v2 header file
src/test/catch.hpp:
wget -q https://github.com/catchorg/Catch2/releases/download/v2.13.9/catch.hpp -O $@
# Link ECCI static library
bin/ecci.a: build/ecci/String.o | bin/.
ar rs $@ $^
# Compile ECCI static library source
build/ecci/%.o: src/ecci/%.cpp src/ecci/%.hpp | build/ecci/.
$(CXX) -c -g $(CXXFLAGS) $< -o $@
# Link ECCI dynamic library
bin/ecci.so: build/ecci_dyn/String.o | bin/.
$(CXX) -shared $^ -o $@
# Compile ECCI dynamic library source
build/ecci_dyn/%.o: src/ecci/%.cpp src/ecci/%.hpp | build/ecci_dyn/.
$(CXX) -c -fPIC -g $(CXXFLAGS) $< -o $@
.PRECIOUS: %/.
%/.:
mkdir -p $@
.PHONY: clean
clean:
rm -rf bin/ build/ doc/
.PHONY: lint
lint:
cpplint --filter=-build/header_guard,-build/include_subdir,-build/c++11,-runtime/references src/concat/*.?pp src/ecci/*.?pp
4.3. Clase Arreglo dinámico genérico
Dado que C++ considera a los registros (struct, class, union) como objetos, es necesario implementar las nociones del paradigma de programación orientado a objetos como copia de valores para que funcionen adecuadamente al ser reutilizado en una universidalidad de contextos.
Listado 38. Array.hpp: plantilla de a (Array.hpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#ifndef ARRAY_HPP
#define ARRAY_HPP
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <utility>
const size_t INCREASE_FACTOR = 10;
/*
Arreglo (vector): region continua de memoria que almacena valores del
mismo tipo
Registro de memoria (record): region continua de memoria que puede almacenar
valores (campos) de diferente tipo. No es Registro de CPU (register)
Subrutina: region continua de memoria que almacena instrucciones que pueden ser
ejecutadas (invocadas, llamadas)
*/
namespace ecci {
/**
* @brief
*
*/
template<typename DataType, size_t initial_capacity = 10>
class Array {
private:
/**
* @brief
*
*/
size_t count;
size_t capacity;
DataType* elements;
public:
/// Default constructor and NOT conversion constructor
explicit Array(size_t initialCount = 0)
: count(initialCount)
, capacity(initialCount ? initialCount : initial_capacity)
, elements(new DataType[this->capacity]()) {
if (this->elements == nullptr) {
this->capacity = 0;
throw std::runtime_error("no memory to create dynamic array");
}
// new operator:
// Type* ptr = new Type calls constructor if Type is a record
// Type* ptr = new Type() calls constructor always, eg double()
// new[] operator:
// Type* arr = new Type[capacity] calls constructor if Type is a record
// Type* arr = new Type[capacity]() calls constructor always, eg double()
}
/// Copy constructor
Array(const Array& other)
: count(other.count)
, capacity(other.capacity)
, elements(new DataType[other.capacity]) {
if (this->elements == nullptr) {
this->capacity = 0;
throw std::runtime_error("no memory to create copy of dynamic array");
}
this->copy(other);
}
/// Move constructor
Array(Array&& other)
: count(other.count)
, capacity(other.capacity)
, elements(other.elements) {
other.count = other.capacity = 0;
other.elements = nullptr;
}
/// Destructor
~Array() {
// delete ptr
// delete[] arr
delete[] this->elements;
}
/// Copy assignment operator
Array& operator=(const Array& other) {
if (this != &other) {
if (this->capacity != other.capacity) {
delete[] this->elements;
this->elements = new DataType[other.capacity];
if (this->elements == nullptr) {
throw std::runtime_error("no memory to copy existing dynamic array");
}
this->capacity = other.capacity;
}
this->count = other.count;
this->copy(other);
}
return *this;
}
/// Move assignment operator
Array& operator=(Array&& other) {
if (this != &other) {
std::swap(this->count, other.count);
std::swap(this->capacity, other.capacity);
std::swap(this->elements, other.elements);
}
return *this;
}
public: // Accessors
inline size_t getCount() const {
return this->count;
}
inline const DataType& operator[](size_t index) const {
return this->elements[index];
}
inline DataType& operator[](size_t index) {
return this->elements[index];
}
public:
/// Add an element to the rightmost empty space in the array
void append(const DataType& value) {
if (this->count == this->capacity) {
this->increaseCapacity();
}
this->elements[this->count++] = value;
}
void resize(size_t newCount) {
if (newCount > this->capacity) {
this->increaseCapacity(newCount);
}
this->count = newCount;
}
public:
friend std::ostream& operator<<(std::ostream& out, const Array& array) {
for (size_t index = 0; index < array.count; ++index) {
out << array.elements[index] << (index < array.count - 1 ? "," : "");
}
return out;
}
private:
void increaseCapacity(size_t newCapacity = 0) {
if (newCapacity == 0) {
newCapacity = INCREASE_FACTOR * this->capacity;
}
DataType* newElements = new DataType[newCapacity];
if (newElements) {
for (size_t index = 0; index < this->count; ++index) {
newElements[index] = this->elements[index]; // copy semantics
}
delete[] this->elements;
this->capacity = newCapacity;
this->elements = newElements;
} else {
throw std::runtime_error("no memory to increase dynamic array capacity");
}
}
/// ...
void copy(const Array& other) {
assert(this->capacity >= other.capacity);
for (size_t index = 0; index < other.count; ++index) {
this->elements[index] = other.elements[index];
}
}
};
} // namespace ecci
#if 0
template<typename DataType>
int increase_capacity(array_t<DataType>* array) {
assert(array);
int error = EXIT_SUCCESS;
size_t new_capacity = INCREASE_FACTOR * array->capacity;
DataType* new_elements = (DataType*)
realloc(array->elements, new_capacity * sizeof(DataType));
if (new_elements) {
array->capacity = new_capacity;
array->elements = new_elements;
} else {
error = EXIT_FAILURE;
}
return error;
}
#endif
#endif // ARRAY_HPP
4.3.1. Mediana v6
Usa el arreglo dinámico genérico orientado a objetos
Listado 39. median.cpp: plantilla de arreglo dinámico (median.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <iostream>
// using std::cerr;
// using namespace std;
// #include "arguments.hpp"
#include "Array.hpp"
#include "String.hpp"
template <typename DataType, size_t initial_capacity = 10>
void printArray(const ecci::Array<DataType, initial_capacity>& values, const char* separator = ", ") {
std::cout << '[';
for (size_t index = 0; index < values.getCount(); ++index) {
if (index) {
std::cout << separator;
}
std::cout << values[index];
}
std::cout << ']';
}
int main() {
try {
ecci::Array<double, 10000> values;
ecci::Array<double, 10000> copy;
double value = 0.0;
while (std::cin >> value) {
values.append(value);
}
copy = values;
printArray(copy);
std::cout << std::endl;
// std::cout << values << std::endl;
ecci::Array<ecci::String> texts;
texts.append("que");
texts.append("funcione");
texts.append("please");
texts.append("!!!");
printArray(texts);
std::cout << std::endl;
ecci::Array<ecci::Array<size_t>> matrix(20);
for (size_t row = 0; row < 20; ++row) {
matrix[row].resize(20);
for (size_t col = 0; col < 15; ++col) {
matrix[row][col] = row * 100 + col;
}
}
for (size_t row = 0; row < 20; ++row) {
for (size_t col = 0; col < 15; ++col) {
std::cout << std::setw(4) << std::setfill('0') << matrix[row][col] << " ";
}
std::cout << std::endl;
}
} catch (const std::runtime_error& error) {
std::cerr << "median: error: " << error.what() << std::endl;
}
// std::vector<std::vector<double>> matrix(rows, std::vector<double>(cols));
}
// long cerr = 022928282828228l;
#if 0
enum error_code read_values(struct array* values, std::istream& input
, const arguments_t* const arguments);
int compare_double(const void* p1, const void* p2);
double calculate_median(const struct array* const values);
int process_file(std::istream& input, const char* filename
, const arguments_t* const arguments);
// main:
int main(int argc, char* argv[]) {
int error = ERROR_SUCCESS;
arguments_t arguments;
arguments_init(&arguments);
error = analyze_arguments(&arguments, argc, argv);
if (error == ERROR_SUCCESS) {
if (argc >= 2) {
for (int index = 1; index < argc; ++index) {
if (*argv[index] != '-') {
// printf("%d = [%s]\n", index, argv[index]);
std::ios_base::openmode mode = arguments.is_input_binary
? std::ifstream::in | std::ifstream::binary
: std::ifstream::in;
std::ifstream input(argv[index], mode);
if (input) {
process_file(input, argv[index], &arguments);
input.close();
} else {
// int cerr = 0;
// ::cerr = cerr;
std::cerr << "could not open " << argv[index] << '\n';
}
}
}
} else {
process_file(std::cin, "stdin", &arguments);
}
arguments_uninit(&arguments);
}
return error;
}
int process_file(std::istream& input, const char* filename
, const arguments_t* const arguments) {
enum error_code error = ERROR_SUCCESS;
// Read values as an array of real numbers
// array_t values;
struct array values;
if (array_init(&values) == EXIT_SUCCESS) {
error = read_values(&values, input, arguments);
if (error == ERROR_SUCCESS) {
// Sort values
qsort(values.elements, values.count, sizeof(double), compare_double);
// Calculate median of values
const double median = calculate_median(&values);
// Print median
std::cout << filename << ": " << median << std::endl;
} else {
std::cerr << "median: error: could not read values\n";
}
array_uninit(&values);
} else {
std::cerr << "median: error: could not allocate memory\n";
error = ERROR_NO_ENOUGH_MEMORY;
}
return error;
}
// (data_type*) C-style cast
// const_cast<data_type*>(expr) quitar constancia a un puntero
// static_cast<data_type>(expr)
// dynamic_cast<data_type>(expr) polimorfismo
// reinterpret_cast<data_type>(expr) punteros
enum error_code read_values(struct array* values, std::istream& input
, const arguments_t* const arguments) {
double value = 0.0;
if (arguments->is_input_binary) {
// size_t fread(void* ptr, size_t size, size_t count, FILE * stream);
// while (fread(&value, sizeof(value), 1, input) == 1) {
while (input.read(reinterpret_cast<char*>(&value), sizeof(value))) {
if (array_append(values, value) != EXIT_SUCCESS) {
return ERROR_CANNOT_APPEND_VALUE;
}
}
} else {
// while (fscanf(input, "%lg", &value) == 1) {
// std::cout << value << value << std::endl;
// std::cin >> value >> value;
while (input >> value) {
if (array_append(values, value) != EXIT_SUCCESS) {
return ERROR_CANNOT_APPEND_VALUE;
}
}
}
return ERROR_SUCCESS;
}
int compare_double(const void* p1, const void* p2) {
// const double* value1 = (double*) p1;
// const double* value2 = (double*) p2;
// return *value1 - *value2;
return *(double*)p1 - *(double*)p2;
}
// median:
double calculate_median(const struct array* const values) {
// If value count is odd then
if ((*values).count % 2 == 1) {
// Return value at index value count / 2
return values->elements[values->count / 2];
} else {
// Return average of two values at the center of the array
return (values->elements[values->count / 2 - 1]
+ values->elements[values->count / 2]) / 2.0;
}
}
#endif
4.4. Lista doblemente enlazada genérica
Los arreglos tienen el prodigio de acceder de inmediato a los elementos a costa de exigir memoria continua, lo cual es una limitación seria para alojar grandes cantidades de datos. Además insertar elementos en un arreglo puede implicar correr otros de lugar o tener que reubicar el arreglo completo en otro lugar de la memoria.
El contenedor lista solventa estos problemas al usar memoria discontinua, pero pierde el acceso inmediato a los elementos. Un objeto, llamado iterador, que encapsula un puntero, permite mitigar este tiempo de acceso en recorridos secuenciales.
| container | access | append | remove | continous? |
|---|---|---|---|---|
array |
O(1) |
O(n) |
O(n) |
always |
list |
O(n) |
O(1) |
O(1) |
no |
tree |
O(log n) |
O(log n) |
O(log n) |
no |
graph |
yes/no |
Listado 40. List.hpp: plantilla de lista doblemente enlazada (List.hpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// #pragma once
#ifndef LIST_HPP
#define LIST_HPP
#include <iostream>
#include <stdexcept>
#include <string>
namespace ecci {
class List {
private:
struct Node {
public:
Node* previous;
std::string data;
Node* next;
public:
explicit Node(const std::string& data, Node* previous = nullptr
, Node* next = nullptr)
: previous(previous)
, data(data)
, next(next) {
}
};
private:
size_t count;
Node* first; // head
Node* last; // tail
public: // Construction, copy, and destruction
/// Default constructor
List()
: count(0)
, first(nullptr)
, last(nullptr) {
}
/// Destructor
~List() {
this->clear();
}
public: // Accessors
inline bool isEmpty() const { return this->first == nullptr; }
inline bool operator!() const { return this->isEmpty(); }
// inline operator bool() const { return !this->isEmpty(); }
inline size_t getCount() const { return this->count; }
public: // Insertion, removal
void append(const std::string& data) {
if (this->isEmpty()) {
this->first = this->last = new Node(data);
if (this->isEmpty()) {
throw std::runtime_error("list: no memory to append node");
}
} else {
this->last->next = new Node(data, this->last);
if (this->last->next == nullptr) {
throw std::runtime_error("list: no memory to append node");
}
this->last = this->last->next;
}
++this->count;
}
/// Empties the list from last element to the fisrt one
void clear() {
while (this->last) {
Node* const current = this->last;
this->last = this->last->previous;
delete current;
}
this->first = nullptr;
this->count = 0;
}
public:
// friend std::ostream& operator<<(std::ostream& out, const List& list) {
// for (const Node* node = list.first; node; node = node->next) {
// out << node->data << std::endl;
// }
// return out;
// }
class ConstIterator {
private:
Node* node;
public:
explicit ConstIterator(Node* node)
: node(node) {
}
/// Returns true if two iterators point to the same element
inline bool operator!=(const ConstIterator& other) const {
return this->node != other.node;
}
/// Get access to the pointed data. Iterator must no be end()
inline const std::string& operator*() const {
return this->node->data;
}
/// Moves to the next element. Must not be end()
inline ConstIterator& operator++() {
this->node = this->node->next;
return *this;
}
/// Moves to the next element. Must not be end()
inline ConstIterator operator++(int) {
ConstIterator result(*this);
this->node = this->node->next;
return result;
}
};
/// Get access to the first element
// Iterator begin();
inline ConstIterator begin() const {
return ConstIterator(this->first);
}
/// Returns a no valid position
inline ConstIterator end() const {
return ConstIterator(nullptr);
}
};
} // namespace ecci
#endif // LIST_HPP
4.4.1. Extractor de palabras
Programa que usa la lista para extraer palabras de la entrada estándar y mostrarlas una por línea en la salida estándar.
Listado 41. median.cpp: extractor de palabras (main.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <string>
#include "List.hpp"
int main() {
ecci::List words;
std::string word;
while (std::cin >> word) {
words.append(word);
}
// std::cout << words << std::endl;
//for (ecci::List::ConstIterator itr = words.begin(); itr != words.end(); itr.operator++(0)) {
for (ecci::List::ConstIterator itr = words.begin(); itr != words.end(); itr++) {
std::cout << *itr << std::endl;
}
if (!words) {
std::cout << "no words loaded" << std::endl;
} else {
std::cout << words.getCount() << " words loaded" << std::endl;
}
}
4.5. Arreglo asociativo (mapa o diccionario)
Listado 42. Map.hpp: plantilla de Mapa implementado como un árbol binario de búsqueda sin balanceo (Map.hpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#pragma once
// #include <iostream>
#include <cassert>
#include <stdexcept>
#define DECLARE_RULE5(Class, Action) \
Class(const Class& other) = Action; \
Class(Class&& other) = Action; \
Class& operator=(const Class& other) = Action; \
Class& operator=(Class&& other) = Action
#define DISABLE_COPY(Class) \
DECLARE_RULE5(Class, delete);
namespace ecci {
// Functor
template <typename DataType>
struct Less {
inline bool operator()(const DataType& value1, const DataType& value2) {
return value1 < value2;
}
};
template <typename DataType>
struct Greater {
inline bool operator()(const DataType& value1, const DataType& value2) {
return value1 > value2;
}
};
// int foo() {
// Less<int> less;
// if (less(89, 7)) {
// }
// }
template <typename KeyType, typename ValueType
, typename Comparator = Less<KeyType>>
class Map {
DISABLE_COPY(Map);
private:
struct Node {
public:
DECLARE_RULE5(Node, delete);
public:
Node* parent;
KeyType key;
ValueType value;
Node* left;
Node* right;
// ecci::Array<Node*> children;
// ecci::List<Node*> children;
public:
explicit Node(const KeyType& key, const ValueType& value = ValueType()
, Node* parent = nullptr, Node* left = nullptr, Node* right = nullptr)
: parent(parent)
, key(key)
, value(value)
, left(left)
, right(right) {
}
~Node() {
delete this->left;
delete this->right;
}
// void print(std::ostream& out) const {
// if (this->left) this->left->print(out); // Left
// out << this->key << "=" << this->value << std::endl; // Node
// if (this->right) this->right->print(out); // Right
// }
}; // struct Node
private:
size_t count;
Node* root;
public: // Construction, destruction!!!
/// Default constructor
Map()
: count(0)
, root(nullptr) {
}
/// Destrutor
~Map() {
delete this->root;
}
public: // Accessors
/// Returns true if this map has no elements
inline bool isEmpty() const { return this->root == nullptr; }
inline size_t getCount() const { return this->count; }
// friend std::ostream& operator<<(std::ostream& out, const Map& map) {
// if (map.root) {
// map.root->print(out);
// }
// return out;
// }
public: // Insertion, removal
/// Insert an element to the map
void insert(const KeyType& key, const ValueType& value = ValueType()) {
this->insertImpl(key, value);
// TODO: return an iterator
}
/// Get acces to the associated value to the given key. If key does not exist
/// in the map, it is inserted as a new element
ValueType& operator[](const KeyType& key) {
Node* node = this->insertImpl(key);
return node->value;
}
public:
class Iterator {
public:
DECLARE_RULE5(Iterator, default);
private:
Node* node;
public:
explicit Iterator(Node* node)
: node(node) {
}
inline bool operator!=(const Iterator& other) const {
return this->node != other.node;
}
/// this must not be end()
inline KeyType& getKey() {
assert(this->node);
return this->node->key;
}
/// this must not be end()
inline const KeyType& getKey() const {
assert(this->node);
return this->node->key;
}
/// this must not be end()
inline ValueType& getValue() {
assert(this->node);
return this->node->value;
}
/// this must not be end()
inline const ValueType& getValue() const {
assert(this->node);
return this->node->value;
}
inline Iterator& operator++() {
this->node = Map::findNextNode(this->node);
return *this;
}
};
Iterator begin() {
return Iterator(this->findMinimum(this->root));
}
Iterator end() {
return Iterator(nullptr);
}
private:
Node* insertImpl(const KeyType& key, const ValueType& value = ValueType()) {
if (this->isEmpty()) {
return this->root = this->createNode(key, value);
} else {
Comparator comparator;
Node* current = this->root;
while (true) {
// if (key < current->key) {
if (comparator(key, current->key)) {
if (current->left == nullptr) {
return current->left = this->createNode(key, value, current);
} else {
current = current->left;
}
// } else if (key > current->key) {
} else if (comparator(current->key, key)) {
if (current->right == nullptr) {
return current->right = this->createNode(key, value, current);
} else {
current = current->right;
}
} else {
// Set politics, element must not be twice within the container
return current;
}
} // while
} // if empty
}
Node* createNode(const KeyType& key, const ValueType& value = ValueType()
, Node* parent = nullptr) {
Node* newNode = new Node(key, value, parent);
if (newNode == nullptr) {
throw std::runtime_error("map: no memory to insert node");
}
++this->count;
return newNode;
}
static Node* findMinimum(Node* subtree) {
if (subtree) {
while (subtree->left) {
subtree = subtree->left;
}
}
return subtree;
}
static Node* findNextNode(Node* current) {
Node* original = current;
if (current->right) {
return Map::findMinimum(current->right);
}
while (current->parent && current == current->parent->right) {
current = current->parent;
if (current->parent == nullptr) {
return nullptr;
}
}
if (current->parent && current == current->parent->left) {
current = current->parent;
}
return current == original ? nullptr : current;
}
};
} // namespace ecci
4.5.1. Contador de palabras
Programa que usa el mapa para extraer palabras de la entrada estándar, mostrarlas una por línea en la salida estándar en orden alfabético junto con su cantidad de apariciones.
Listado 43. word_count.cpp: contador de palabras (main.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <string>
#include "List.hpp"
#include "Map.hpp"
typedef ecci::Map<std::string, size_t> OcurrencesType;
typedef ecci::Map<size_t, ecci::List<std::string>, ecci::Greater<size_t>> WordsByFrequency;
int main() {
OcurrencesType occurrences;
std::string word;
while (std::cin >> word) {
// itr = occurrences.insert(word, 1);
++occurrences[word];
}
WordsByFrequency wordsByFrequency;
// std::cout << occurrences << std::endl;
for (typename OcurrencesType::Iterator itr = occurrences.begin();
itr != occurrences.end(); ++itr) {
const std::string& currentWord = itr.getKey();
const size_t frequency = itr.getValue();
std::cout << currentWord << "\t" << frequency << std::endl;
wordsByFrequency[frequency].append(currentWord);
}
std::cout << "-------------------\n";
for (typename WordsByFrequency::Iterator itr = wordsByFrequency.begin();
itr != wordsByFrequency.end(); ++itr) {
const size_t frequency = itr.getKey();
const ecci::List<std::string>& words = itr.getValue();
std::cout << frequency << "\t";
for (const std::string& currentWord : words) {
std::cout << currentWord << " ";
}
std::cout << std::endl;
}
}
4.6. Pruebas unitarias (caja blanca) con Catch2
Se crea al menos un archivo fuente (.cpp) por cada contenedor, de la forma test_container.cpp. Se incluye a catch.hpp y se declaran los casos de prueba:
Listado 44. test_array.cpp: Pruebas unitarias de Array (test_array.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "catch.hpp"
#include "Array.hpp"
TEST_CASE("Array append", "[array][append]") {
/*ecci::*/Array<int> array;
array.append(-1);
array.append(2);
REQUIRE(array[0] == -1);
REQUIRE(array[1] == 2);
}
TEST_CASE("Array append for", "[array][append]") {
/*ecci::*/Array<size_t> array;
const size_t COUNT = 1000000;
for (size_t index = 0; index < COUNT; ++index) {
array.append(index);
}
REQUIRE(array[0] == 0);
REQUIRE(array[COUNT - 1] == COUNT - 1);
}
Listado 45. test_map.cpp: Pruebas unitarias de Map (test_map.cpp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "catch.hpp"
#include "Map.hpp"
TEST_CASE("Map default constructor", "[map][default_ctor]") {
ecci::Map<int, int> map;
REQUIRE(map.isEmpty() == true);
REQUIRE(map.getCount() == 0);
}
TEST_CASE("Map insert", "[map][insert]") {
ecci::Map<int, int> map;
map.insert(0);
REQUIRE(map.isEmpty() == false);
REQUIRE(map.getCount() == 1);
}
Se agrega un main.cpp con la macro CATCH_CONFIG_MAIN para que Catch2 genere un procedimiento main() que se encarga del manejo de argumentos y ejecución de los casos de prueba.
Listado 46. main.cpp: Inicia la ejecución de los casos de prueba (main.cpp)
1
2
#define CATCH_CONFIG_MAIN
#include "catch.hpp"
El Makefile (véase Makefile para la biblioteca ECCI) contiene reglas para descargar el archivo catch.hpp usando wget. Además compila todos los archivos *.cpp que se coloquen en la carpeta src/test/ como parte de un mismo ejecutable bin/test. Al correr este ejecutable, la computadora realiza la cantidad de pruebas definidas a una velocidad superior a la que un humano corroboraría manualmente.
4.7. Problema de imprimir la tabla de notas
Suponga que a una oficina de Registro llegan notas de estudiantes en los cursos como el siguiente fragmento. Por ejemplo la línea 1 indica que el estudiante con carné B54171 obtuvo en el curso con identificación 10 una nota de 97.
1
2
3
4
5
6
B54171 10 97
B48496 6 71.5
B54171 1 79
B83997 8 20
B48496 2 93
...
Los datos vienen en cualquier orden. Se sabe que para este ejemplo, sólo existen 12 cursos distintos, identificados de 1 a 12. La cantidad de filas es arbitraria y puede ser muy grande (i.e: la población estudiantil puede ser muy grande). Se quiere un programa eficiente que produzca una tabla como el siguiente fragmento.
CARNE CURS01 CURS02 CURS03 CURS04 CURS05 CURS06 CURS07 CURS08 CURS09 CURS10 CURS11 CURS12
------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------
B48496 10 93 90 89 71.5 28 70 41 73 75 30
B54124 57 2.55 37 77 55 83 62 33 70 39
B54171 79 43 52 25 74 58 29 84 97 77 27Dado que en los datos los carnés no necesariamente son secuenciales y que no son enteros, resulta natural usar un arreglo asociativo. Para cada estudiante puede haber 12 o menos notas de curso. Por lo tanto, se puede asociar carnés (textos std::string) con un arreglo dinámico (std::vector) de notas (double). Imprimir la tabla sería hacer un recorrido por estas dos estructuras de datos.
Listado 47. Agrupa los datos de estudiantes y los imprime en una tabla (link:3.3-tree/grade/src/main.cpp^])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
#include <vector>
typedef std::vector<double> Grades;
typedef std::map<std::string, Grades> StudentGrades;
void printTable(const StudentGrades& studentGrades);
void printGrades(const Grades& grades);
int main() {
StudentGrades studentGrades;
std::string studentId;
size_t courseId = 0;
double grade = 0.0;
// Load
while (std::cin >> studentId >> courseId >> grade) {
Grades& grades = studentGrades[studentId];
if (grades.size() == 0) {
grades = Grades(12, -1.0);
}
// TODO: verify courseId, grade
grades.at(courseId - 1) = grade;
}
// Print table
printTable(studentGrades);
}
void printTable(const StudentGrades& studentGrades) {
// For each student
// for (typename StudentGrades::const_iterator itr = studentGrades.cbegin(),
// for (auto itr = studentGrades.cbegin(),
// end = studentGrades.cend(); itr != end; ++itr) {
// const std::string& studentId = itr->first;
// const Grades& grades = itr->second;
// std::cout << studentId << " ";
// printGrades(grades);
// std::cout << std::endl;
// }
for (const auto& [studentId, grades] : studentGrades) {
std::cout << studentId << " ";
printGrades(grades);
std::cout << std::endl;
}
}
void printGrades(const Grades& grades) {
// for (typename Grades::const_iterator itr = grades.cbegin()
// , end = grades.cend(); itr != end; ++itr) {
// const double grade = *itr;
for (const double grade : grades) {
if (grade >= 0.0) {
std::cout << std::setw(6) << grade << ' ';
} else {
std::cout << std::setw(6) << "" << ' ';
}
}
}
5. Programación orientada a objetos (parte 2)
5.1. Análisis orientado a objetos: Problema Trivia
UML ofrece meanismos para representar el resultado de la fase de análisis de forma que es comprensible por otros. Dos de estos mecanismos son los casos de uso y especificaciones de requerimientos.
Los casos de uso son como guiones de una obra de teatro, donde los actores son el sistema a desarrollar y sus usuarios (humanos u otros sistemas). El siguiente es un fragmento de un caso de uso ("Jugar") para el problema de Trivia.
El diagrama de casos de uso muestra una vista de alto nivel de todos los casos de uso donde participa el sistema. Cada caso de uso es como un "acto" de la obra de teatro. El caso de uso está divido en cursos de eventos que pueden considerarse "escenas" de la obra de teatro. Lo importante es documentar la interacción que tendrá el sistema con sus usuarios.
5.2. Trivia v1: Herencia
La herencia es un mecanismo de la programación orientada a objetos que permite representar la relación "es un(a)" entre entidades, y reutilizar código. La herencia es un mecanismo que trabaja sobre los registros. Se implementa en la máquina procedimental con redundancia controlada de campos. Los campos son copiados del registro base y duplicados en los registros derivados por el compilador. En C++ es opcional. Se activa cuando la persona desarrolladora expresamente solicita heredar un registro de otro.
Archivo de preguntas. Cada pregunta consta de un texto y una respuesta. Las preguntas se separan por una línea vacía en el archivo de datos:
Listado 48. trivia1.txt
Cuántos metros hay en un kilómetro?
1000
¿A cuántos metros cuadrados equivale una hectárea?
10000
Si a < b, y b < 0, entonces el valor de a es?
negativo
¿Cuántos lados tiene un triángulo rectángulo?
3
¿Cuál país actualmente es el mayor exportador mundial de piña?
Costa Rica
Después del Sol, la estrella más cercana a la Tierra está en la Constelación de:
Alfa Centauro
Según la leyenda, Tío Sam, la personificación nacional de Estados Unidos, fue de profesión un
carnicero
¿Cuál es el país que ha ganado más certámenes de Miss Universo?
Estados Unidos
La primera copa mundial de futbol en 1930 tuvo sede en este país:
Uruguay
Antónimo de: antónimo
sinónimo
Cuál fue la primera compañía en implementar el concepto de ventanas (windows)
XeroxEl punto de entrada del programa, la función main() se encarga de instanciar el controlador e indicarle que inicie la ejecución. Dado que sólo debe existir una única instancia del controlador Trivia, se usa el patrón singleton que crea la única instancia en el segmento de datos (variable estática). Dado que el constructor de Trivia es privado, sólo la clase Trivia puede crear esta instancia. Nótese el nombre en minúscula para indicar que no contiene una clase.
Listado 49. main.cpp
1
2
3
4
5
6
7
// Copyright 2022 Jeisson Hidalgo ECCI-UCR
#include "Trivia.hpp"
int main(int argc, char* argv[]) {
return Trivia::getInstance().run(argc, argv);
}
La clase controladora Trivia contiene la colección de preguntas. Se escogió un arreglo por tener acceso aleatorio, útil para la aleatorización de las preguntas. El controlador carga las preguntas de un archivo de texto usando un objeto ifstream. Su interfaz es la misma que del objeto std::cin. La clase Question implementa los operadores de flujo operator>>() para lectura y operator<<() para impresión. De esta forma se facilita la lectura de las preguntas como cualquier otro tipo de datos. Se utiliza funcionalidad de C++ para generar mejores números pseudoaleatorios, usando una semilla verdaderamente aleatoria.
Listado 50. Trivia.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#pragma once
#include <vector>
#include "common.hpp"
#include "Question.hpp"
class Trivia {
DISABLE_COPY(Trivia);
private:
std::vector<Question> questions;
long score = 0;
public:
static Trivia& getInstance();
int run(int argc, char* argv[]);
void showStatistics() const;
static size_t randomIndex(const size_t count);
private:
Trivia();
void loadQuestions();
bool askQuestion();
void printQuestions() const;
};
Listado 51. Trivia.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cassert>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <random>
#include <stdexcept>
#include "Trivia.hpp"
const char* const QUESTION_FILENAME = "data/trivia1.txt";
// Try to get a seed from hardware, if available
static std::random_device::result_type seed = std::random_device()();
// This object generates randon numbers using the Mersenne-Twister algoritym
static std::mt19937 randomEngine(seed);
Trivia::Trivia() : score(0) {
}
Trivia& Trivia::getInstance() {
static Trivia trivia;
return trivia;
}
int Trivia::run(int argc, char* argv[]) {
(void)argc;
(void)argv;
try {
std::cout << "Trivia 1.0" << std::endl;
this->loadQuestions();
while (this->askQuestion()) {
std::cout << std::endl;
}
this->showStatistics();
} catch (const std::runtime_error& error) {
std::cerr << "trivia: " << error.what() << std::endl;
}
return EXIT_SUCCESS;
}
void Trivia::loadQuestions() {
std::ifstream file(QUESTION_FILENAME);
if (!file) {
throw std::runtime_error(std::string("could not open ")
+ QUESTION_FILENAME);
}
this->questions.clear();
Question question;
while (file >> question) {
this->questions.push_back(question);
}
// this->printQuestions();
}
bool Trivia::askQuestion() {
const size_t index = Trivia::randomIndex(this->questions.size());
assert(index >= 0 && index < this->questions.size());
long questionScore = this->questions[index].ask();
if (questionScore < 0) {
return false;
}
this->score += questionScore;
return true;
}
void Trivia::showStatistics() const {
std::cout << "Final score: " << this->score << std::endl;
}
void Trivia::printQuestions() const {
for (const Question& question : this->questions) {
std::cout << question << std::endl;
}
}
size_t Trivia::randomIndex(const size_t count) {
// Produce random values with uniform discrete distribution
std::uniform_int_distribution<size_t> randomDistribution(0, count - 1);
// Generate and return a random number using the uniform distribution
return randomDistribution(randomEngine);
}
El encabezado common.hpp contiene declaraciones que son comunes para todo el proyecto. Provee una macro para deshabilitar o hacer explícita las copias implícitas que implementa el compilador (regla de los 5). Nótese el nombre en minúscula para indicar que no contiene una clase.
Listado 52. common.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Copyright 2022 Jeisson Hidalgo ECCI-UCR
#ifndef COMMON_HPP
#define COMMON_HPP
#define DECLARE_RULE4(Class, action) \
Class(const Class& other) = action; \
Class(Class&& other) = action; \
Class& operator=(const Class& other) = action; \
Class& operator=(Class&& other) = action
#define DISABLE_COPY(Class) \
DECLARE_RULE4(Class, delete)
#endif // COMMON_HPP
La clase Question es un modelo, y por tanto, se encarga de parte de la lógica del dominio. Los modelos normalmente se cargan o guardan en medios persistentes. Una pregunta (Question) es capaz de cargarse de un archivo de texto, imprimirse, y efectuar la pregunta al usuario.
Listado 53. Question.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#pragma once
#include <iostream>
#include <string>
#include "common.hpp"
class Question {
public:
DECLARE_RULE4(Question, default);
private:
std::string text;
std::string answer;
public:
Question();
friend std::istream& operator>>(std::istream& input, Question& question);
friend std::ostream& operator<<(std::ostream& output
, const Question& question);
long ask();
};
Listado 54. Question.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <limits>
#include "Question.hpp"
Question::Question() {
}
std::istream& operator>>(std::istream& input, Question& question) {
std::getline(input, question.text);
std::getline(input, question.answer);
input.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
return input;
}
std::ostream& operator<<(std::ostream& output, const Question& question) {
return output << question.text << std::endl << question.answer << std::endl;
}
long Question::ask() {
std::cout << this->text << std::endl;
std::string userAnswer;
if (!std::getline(std::cin, userAnswer)) {
// User did not answer, pressed Ctrl+D
return -1;
}
// TODO(you): use probabilistic string comparison instead
if (userAnswer == this->answer) {
std::cout << "Right!" << std::endl;
return 1; // this->score;
}
std::cout << "Wrong!" << std::endl;
return 0;
}
El Makefile para construir la aplicación usa el Makefile genérico provisto en el curso:
Listado 55. Makefile
1
2
3
4
5
6
7
include ../../../../../misc/Makefile
# debug: $(EXEFILE) bin/trivia1.txt
# release: $(EXEFILE) bin/trivia1.txt
# bin/trivia1.txt: data/trivia1.txt
# cp -pf $^ $@
5.3. Trivia v2: Polimorfismo
En la versión 1, las respuestas numéricas se comparan como textos, por lo tanto, espacio en blanco o un cero a la izquierda, o un signo de + hace que la aplicación considere la respuesta como incorrecta. Para las preguntas textuales, las mayúsculas y minúsculas se consideran como distintas. Se quiere mejorar estos dos aspectos para no castigar severamente al jugador. Para eso agrega a cada pregunta su tipo en el archivo de datos versión 2:
Listado 56. trivia2.txt
numeric
Cuántos metros hay en un kilómetro?
1000
numeric
¿A cuántos metros cuadrados equivale una hectárea?
10000
textual
Si a < b, y b < 0, entonces el valor de a es?
negativo
numeric
¿Cuántos lados tiene un triángulo rectángulo?
3
textual
¿Cuál país actualmente es el mayor exportador mundial de piña?
Costa Rica
textual
Después del Sol, la estrella más cercana a la Tierra está en la Constelación de:
Alfa Centauro
textual
Según la leyenda, Tío Sam, la personificación nacional de Estados Unidos, fue de profesión un
carnicero
textual
¿Cuál es el país que ha ganado más certámenes de Miss Universo?
Estados Unidos
textual
La primera copa mundial de futbol en 1930 tuvo sede en este país:
Uruguay
textual
Antónimo de: antónimo
sinónimo
textual
Cuál fue la primera compañía en implementar el concepto de ventanas (windows)
XeroxEl punto de entrada del programa no cambia:
Listado 57. main.cpp
1
2
3
4
5
6
7
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include "Trivia.hpp"
int main(int argc, char* argv[]) {
return Trivia::getInstance().run(argc, argv);
}
Para poder hacer que la aplicación haga un trato diferenciado entre preguntas numéricas y las textuales a la hora de verificar si la respuesta del usuario es correcta, se requiere el polimorfismo. Conceptualmente el polimorfismo permite que un tipo de datos (llamado supertipo) pueda representar diferentes tipos de datos (subtipos) y que una operación en el supertipo se realice acorde a los subtipos de las entidades representadas. La herencia es a registros como el polimorfismo es a subrutinas (métodos). Se implementa en la máquina procedimental con información adicional llamada RunTime Type Information (RTTI), como tablas de indirección (punteros) a subrutinas polimórficas (virtuales).
La clase controladora Trivia contiene la colección de preguntas, pero no se puede almacenar valores de diferentes tipos (preguntas numéricas y textuales) en un arreglo. Se almacenan punteros que son todos enteros sin signo de ocho bytes. Cada puntero puede apuntar a un tipo diferente de pregunta, usando la clase base como valor apuntado.
Listado 58. Trivia.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <string>
#include <vector>
#include "common.hpp"
#include "Question.hpp"
class Trivia {
DISABLE_COPY(Trivia);
private:
std::vector<Question*> questions;
score_t score = 0;
public:
static Trivia& getInstance();
int run(int argc, char* argv[]);
void showStatistics() const;
static size_t randomIndex(const size_t count);
private:
Trivia();
~Trivia();
void clear();
void loadQuestions();
bool askQuestion();
void printQuestions() const;
static Question* createQuestion(const std::string& questionType);
};
En el cargado de las preguntas se lee primero el tipo de la pregunta y se crea un objeto acorde en la memoria dinámica. El método o clase que se encarga de este trabajo es un patrón de software llamado factory pattern (fábrica de objetos). Para esta versión, el método factory implementa lógica de switch y es el único lugar en el proyecto donde se permite esta mala práctica. Nótese las inclusiones a cada tipo de pregunta. Si en el futuro se agrega un nuevo tipo de pregunta, es necesario actualizar cada switch del proyecto. Cada nueva pregunta se agrega al arreglo de punteros a preguntas. Estas deben eliminarse en el destructor ~Trivia(). Es necesario que todos los destructores de las preguntas sean virtuales para que se invoque la versión correcta cuando se invoca el operator delete.
Listado 59. Trivia.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include <cassert>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <random>
#include <stdexcept>
#include "Trivia.hpp"
const char* const QUESTION_FILENAME = "data/trivia2.txt";
// Try to get a seed from hardware, if available
static std::random_device::result_type seed = std::random_device()();
// This object generates randon numbers using the Mersenne-Twister algoritym
static std::mt19937 randomEngine(seed);
Trivia::Trivia() : score(0) {
}
Trivia& Trivia::getInstance() {
static Trivia trivia;
return trivia;
}
Trivia::~Trivia() {
this->clear();
}
void Trivia::clear() {
for (size_t index = 0; index < this->questions.size(); ++index) {
delete this->questions[index];
}
this->questions.clear();
}
int Trivia::run(int argc, char* argv[]) {
(void)argc;
(void)argv;
try {
std::cout << "Trivia 1.0" << std::endl;
this->loadQuestions();
while (this->askQuestion()) {
std::cout << std::endl;
}
this->showStatistics();
} catch (const std::runtime_error& error) {
std::cerr << "trivia: " << error.what() << std::endl;
}
return EXIT_SUCCESS;
}
void Trivia::loadQuestions() {
std::ifstream file(QUESTION_FILENAME);
if (!file) {
throw std::runtime_error(std::string("could not open ")
+ QUESTION_FILENAME);
}
this->clear();
std::string questionType;
while (std::getline(file, questionType)) {
Question* question = Trivia::createQuestion(questionType);
if (question == nullptr) {
throw std::runtime_error("invalid question type: " + questionType);
}
file >> *question;
this->questions.push_back(question);
}
// this->printQuestions();
}
bool Trivia::askQuestion() {
const size_t index = Trivia::randomIndex(this->questions.size());
assert(index >= 0 && index < this->questions.size());
score_t questionScore = this->questions[index]->ask();
if (questionScore < 0) {
return false;
}
this->score += questionScore;
return true;
}
void Trivia::showStatistics() const {
std::cout << "Final score: " << this->score << std::endl;
}
void Trivia::printQuestions() const {
for (const Question* question : this->questions) {
std::cout << *question << std::endl;
}
}
size_t Trivia::randomIndex(const size_t count) {
// Produce random values with uniform discrete distribution
std::uniform_int_distribution<size_t> randomDistribution(0, count - 1);
// Generate and return a random number using the uniform distribution
return randomDistribution(randomEngine);
}
#include "NumericQuestion.hpp"
#include "TextualQuestion.hpp"
Question* Trivia::createQuestion(const std::string& questionType) {
if (questionType == "textual") {
return new TextualQuestion();
} else if (questionType == "numeric") {
return new NumericQuestion();
} else {
return nullptr;
}
}
Al encabezado common.hpp se agregan métodos para eliminar espacio en blanco adicional de las cadenas de caracteres (trim) y para cambiar una cadena a mayúsculas o a minúsculas.
Listado 60. common.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#ifndef COMMON_HPP
#define COMMON_HPP
#include <cinttypes>
#include <string>
#define DECLARE_RULE4(Class, action) \
Class(const Class& other) = action; \
Class(Class&& other) = action; \
Class& operator=(const Class& other) = action; \
Class& operator=(Class&& other) = action
#define DISABLE_COPY(Class) \
DECLARE_RULE4(Class, delete)
typedef int64_t score_t;
// Adapted from http://www.martinbroadhurst.com/how-to-trim-a-stdstring.html
static const char* const whitespace = " \t\n\v\f\r";
std::string& ltrim(std::string& str, const std::string& chars = whitespace);
std::string& rtrim(std::string& str, const std::string& chars = whitespace);
std::string& trim(std::string& str, const std::string& chars = whitespace);
std::string& tolower(std::string& str);
std::string& toupper(std::string& str);
#endif // COMMON_HPP
La clase Question se encarga de cargarse de un archivo, imprimirse, y efectuar la pregunta al usuario. Sus campos son ahora protegidos para que las clases hijas puedan accederlos pero no clases externas. Del método ask() se separa la funcionalidad isRightAnswer() que compara la respuesta del jugador con la respuesta correcta. Este método isRightAnswer() se dice que es polimórfico, porque actúa diferente de acuerdo al tipo de objeto hijo, y se marca con la palabra reservada virtual que le indica al compilador agregar información adicional en el código objeto para producir el comportamiento polimórfico. El destructor debe marcarse también virtual para que se puedan destruir los objetos heredados completos a partir de punteros a la clase base.
Listado 61. Question.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <iostream>
#include <string>
#include "common.hpp"
// template <typename QuestionImpl>
class Question {
public:
DECLARE_RULE4(Question, default);
protected:
// std::string type;
// QuestionImpl impl;
std::string text;
std::string answer;
public:
Question();
virtual ~Question() = default;
friend std::istream& operator>>(std::istream& input, Question& question);
friend std::ostream& operator<<(std::ostream& output
, const Question& question);
score_t ask();
virtual bool isRightAnswer(const std::string& userAnswer) const;
};
Listado 62. Question.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include <limits>
#include "Question.hpp"
Question::Question() {
}
// Question::~Question() {
// }
std::istream& operator>>(std::istream& input, Question& question) {
std::getline(input, question.text);
std::getline(input, question.answer);
input.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
return input;
}
std::ostream& operator<<(std::ostream& output, const Question& question) {
return output << question.text << std::endl << question.answer << std::endl;
}
// #include "NumericQuestion.hpp"
// #include "TextualQuestion.hpp"
score_t Question::ask() {
std::cout << this->text << std::endl;
std::string userAnswer;
if (!std::getline(std::cin, userAnswer)) {
// User did not answer, pressed Ctrl+D
return -1;
}
// bool hit = false;
// if (this->type == "numeric") {
// hit = std::stod(userAnswer) == std::stod(this->answer);
// } else {
// hit = stricmp(userAnswer, this->answer) == 0;
// }
// TODO(you): use probabilistic string comparison instead
// bool hit = this->impl.compare(userAnswer, this->answer);
// if (hit) {
// NumericQuestion* numericQuestion = dynamic_cast<NumericQuestion*>(this);
// TextualQuestion* textualQuestion = dynamic_cast<TextualQuestion*>(this);
// if (numericQuestion != nullptr) {
// numericQuestion->compareAnswer(userAnswer);
// } else if (textualQuestion) {
// textualQuestion->compareAnswer(userAnswer);
// }
if (this->isRightAnswer(userAnswer)) {
std::cout << "Right!" << std::endl;
return 1;
}
std::cout << "Wrong!" << std::endl;
return 0;
}
bool Question::isRightAnswer(const std::string& userAnswer) const {
return userAnswer == this->answer;
}
La clase NumericQuestion se encarga de preguntas cuya respuesta es numérica y debe compararse como tal, es decir, ignorando ceros a la izquierda o espacios en blanco. Se agrega un atributo epsilon que permite al jugador errar por máximo este valor. Es muy importante marcar a los métodos que sobrescriben como override. Esta palabra reservada no tiene efecto en el código objeto, sino que el compilador revisa (en tiempo de compilación) si el método realmente está sobrescribiendo un método de la clase base o está desconectado de ella.
Listado 63. NumericQuestion.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <string>
#include "Question.hpp"
class NumericQuestion : public Question {
public:
DECLARE_RULE4(NumericQuestion, default);
protected:
static const double epsilon;
public:
NumericQuestion();
bool isRightAnswer(const std::string& userAnswer) const override;
};
Listado 64. NumericQuestion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include <cmath>
#include "NumericQuestion.hpp"
const double NumericQuestion::epsilon = 0.5;
NumericQuestion::NumericQuestion() {
}
bool NumericQuestion::isRightAnswer(const std::string& userAnswer) const {
// |x1 - x2| < epsilon
return std::fabs(std::stod(userAnswer) - std::stod(this->answer))
< NumericQuestion::epsilon;
}
La clase TextualQuestion realiza preguntas textuales. La comparación de las respuestas del jugador se realizan ignorando mayúsculas y minúsculas, y espacio adicional antes y después de la respuesta en el método isRightAnswer(). Se emplean los procedimientos reutilizables trim() y tolower() que de common.hpp/cpp.
Listado 65. TextualQuestion.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <string>
#include "Question.hpp"
class TextualQuestion : public Question {
public:
DECLARE_RULE4(TextualQuestion, default);
public:
TextualQuestion();
// @Override override != overload
bool isRightAnswer(const std::string& userAnswer) const override;
};
Listado 66. TextualQuestion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include "TextualQuestion.hpp"
TextualQuestion::TextualQuestion() {
}
bool TextualQuestion::isRightAnswer(const std::string& userAnswer) const {
std::string comparableUserAnswer = userAnswer;
::tolower(::trim(comparableUserAnswer));
std::string comparableRightAnswer = this->answer;
::tolower(::trim(comparableRightAnswer));
return comparableUserAnswer == comparableRightAnswer;
}
El Makefile sigue sin cambios:
Listado 67. Makefile
1
2
3
4
5
6
7
include ../../../../../misc/Makefile
# debug: $(EXEFILE) bin/trivia1.txt
# release: $(EXEFILE) bin/trivia1.txt
# bin/trivia1.txt: data/trivia1.txt
# cp -pf $^ $@
5.4. Trivia v3: Reutilización mediante herencia y polimorfismo
Un buen diseño permitiría agregar un nuevo tipo de pregunta mediante tres pasos:
-
Heredar el nuevo tipo de pregunta de
Question. -
Sobrescribir (override) los métodos virtuales puros y los métodos virtuales que tienen un comportamiento distinto en el nuevo tipo de pregunta.
-
Agregar el nuevo tipo de pregunta a la fábrica de objetos.
-
Listo! El resto del código del proyecto debería mantenerse inalterado o cambiar lo mínimo posible.
La versión 2 no cumple este ideal de los tres pasos anteriores. Para afinar el código se agregará un nuevo tipo de preguntas en la versión 3: preguntas de respuesta de selección única. Una vez que se haya agregado el nuevo tipo de pregunta y hecho estos afinamientos, agregar otro tipo de pregunta será cercano a los tres pasos anteriors, menos propenso a errores y más rápido responderle al cliente, en especial si éste quiere agregar muchos tipos de preguntas en el futuro.
Listado 68. trivia3.txt
numeric
Cuántos metros hay en un kilómetro?
1000
single_choice
Quién tiene 4 estómagos?
2
Una gallina
Una vaca
El Botija
Una máquina tragamonedas
single_choice
Cuántos pies tiene un ciempiés?
4
100
74
104
Ninguna de las anteriores
numeric
¿A cuántos metros cuadrados equivale una hectárea?
10000
textual
Si a < b, y b < 0, entonces el valor de a es?
negativo
single_choice
¿Cómo se llama la supercomputadora que controla el Discovery 1 en "2001: Odisea del Espacio"?
2
TMA-1
HAL 9000
ENIAC
HANGAR 68
single_choice
¿El nombre de la sustancia "Nicotina" proviene de:?
1
Jean Nicot que introdujo la planta del tabaco en Francia
De sus componentes: nitrógeno e hidrógeno, y su efecto insecticida
De su descubridor: Francesco Nicota
numeric
¿Cuántos lados tiene un triángulo rectángulo?
3
single_choice
¿Cuál es considerado el animal más venenoso del mundo?
4
La serpiente marina
El alacrán
El sapo dorado
La avispa marina
single_choice
¿La fuerza de gravitación es inversamente proporcional a:?
3
la masa
el peso
la distancia
la constante de gravitación
single_choice
¿Por qué los teclados no están en orden alfabético?
2
Porque el inventor es de apellido Qwerty
Para evitar que los mazos de la máquina de escribir chocaran
Para competir con Dvorak
El proyecto que creó la máquina de escribir se denominaba Qwerty
single_choice
¿De dónde proviene el aguacate?
4
China
India
Australia
América Central
single_choice
¿Cuál de las siguientes afirmaciones es válida?
1
La avispa es más delgada que la abeja y no pierde el aguijón al picar, la abeja sí
La abeja es más delgada que la avispa y no pierde el aguijón al picar, la avispa sí
La abeja es un insecto, la avispa es un arácnido
Ninguna de las anteriores
single_choice
Antes de ser cantante, Julio Iglesias era portero de:
2
Barcelona
Real Madrid
Celta de Vigo
Saprissa
textual
¿Cuál país actualmente es el mayor exportador mundial de piña?
Costa Rica
single_choice
¿Cuál de los siguientes alimentos NO es un veneno para la babosa?
1
Hojas putrefactas
La cerveza
La sal
Compuestos de metaldehido
single_choice
La población de la India y China juntas representa
3
tres cuartas partes de la población mundial
la mitad de la población mundial
un tercio de la población mundial
un cuarto de la población mundial
single_choice
El tejido que hace a los ojos del gato y otros animales reflejar la luz se llama
2
Tejido fotoreflector
Tapete de luz
Captaluces
Halógenos
textual
Después del Sol, la estrella más cercana a la Tierra está en la Constelación de:
Alfa Centauro
single_choice
A partir de este invento de 1877 se pudo en la humanidad grabar y reproducir sonido con éxito:
1
El Fonógrafo de Thomas Alva Edison
El Gramófono de Emile Berliner
El casete de Fritz Pfleumer
La Victrola de RCA
single_choice
La Esvástica es un símbolo inventado por
3
Los Nazis
Los Vikingos
Los Hindúes
Los Egipcios
textual
Según la leyenda, Tío Sam, la personificación nacional de Estados Unidos, fue de profesión un
carnicero
single_choice
"Watson, ven aquí" es una frase célebre asociada al siguiente hecho
3
Descubrimiento del ADN
Aparición de Sherlock Holmes en la radio
Invención del teléfono
Película "Casa Blanca"
single_choice
¿Cuál de los siguientes campos NO es premiado con un Nobel?
3
Física
Química
Biología
Economía
textual
¿Cuál es el país que ha ganado más certámenes de Miss Universo?
Estados Unidos | USA | EEUU
textual
La primera copa mundial de futbol en 1930 tuvo sede en este país:
Uruguay
single_choice
El máximo goleador en la historia del fútbol con 1329 goles es
1
Arthur Friedenreic (Brasil)
Maradona (Argentina)
Pelé (Brasil)
El Chunche (Deporái)
single_choice
El puente más alto del mundo, de 402 metros, es
4
Puente Sutong en China
Golden Gate en Estados Unidos
Puente sobre el Río Virilla, Costa Rica
Puente Baluarte en México
single_choice
El primer sistema operativo de la historia de la informática fue creado por
4
Microsoft
IBM
Apple
General Motors
DARPA
American Airlines
textual
Antónimo de: antónimo
sinónimo
textual
Cuál fue la primera compañía en implementar el concepto de ventanas (windows)
Xerox
single_choice
Según Galileo Galilei el movimiento natural de los cuerpos es:
2
Uniformemente acelerado
Rectilíneo uniforme
Elíptico
OndulatorioEl punto de entrada del programa no cambia (bien!):
Listado 69. main.cpp
1
2
3
4
5
6
7
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include "Trivia.hpp"
int main(int argc, char* argv[]) {
return Trivia::getInstance().run(argc, argv);
}
La clase controladora Trivia, casi no cambia. El único método modificado es la fábrica de obejtos createQuestion(type) que recibe un texto con el tipo de pregunta y retorna un puntero a un objeto pregunta correspondiente al tipo dado. Recuérdese que este método contiene lógica de "switch" que se debe evitar a lo largo del programa. Para efectos del curso, este método es el único lugar en el proyecto que puede tener lógica condicional dependiente del tipo de pregunta. De esta manera, en el proyecto sólo habrá un único "switch" y en todos los demás lugares donde un comportamiento dependa del tipo de registro, habrá polimorfismo. De lo contrario, si se agregan varios tipos de pregunta en el futuro, se convertirá en una pesadilla darle mantenimiento al código.
Listado 70. Trivia.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <string>
#include <vector>
#include "common.hpp"
#include "Question.hpp"
class Trivia {
DISABLE_COPY(Trivia);
private:
std::vector<Question*> questions;
score_t score = 0;
public:
static Trivia& getInstance();
int run(int argc, char* argv[]);
void showStatistics() const;
static size_t randomIndex(const size_t count);
private:
Trivia();
~Trivia();
void clear();
void loadQuestions();
bool askQuestion();
void printQuestions() const;
static Question* createQuestion(const std::string& questionType);
};
Listado 71. Trivia.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include <cassert>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <random>
#include <stdexcept>
#include "Trivia.hpp"
const char* const QUESTION_FILENAME = "data/trivia3.txt";
// Try to get a seed from hardware, if available
static std::random_device::result_type seed = std::random_device()();
// This object generates randon numbers using the Mersenne-Twister algoritym
static std::mt19937 randomEngine(seed);
Trivia::Trivia() : score(0) {
}
Trivia& Trivia::getInstance() {
static Trivia trivia;
return trivia;
}
Trivia::~Trivia() {
this->clear();
}
void Trivia::clear() {
for (size_t index = 0; index < this->questions.size(); ++index) {
delete this->questions[index];
}
this->questions.clear();
}
int Trivia::run(int argc, char* argv[]) {
(void)argc;
(void)argv;
try {
std::cout << "Trivia 1.0" << std::endl;
this->loadQuestions();
while (this->askQuestion()) {
std::cout << std::endl;
}
this->showStatistics();
} catch (const std::runtime_error& error) {
std::cerr << "trivia: " << error.what() << std::endl;
}
return EXIT_SUCCESS;
}
void Trivia::loadQuestions() {
std::ifstream file(QUESTION_FILENAME);
if (!file) {
throw std::runtime_error(std::string("could not open ")
+ QUESTION_FILENAME);
}
this->clear();
std::string questionType;
while (std::getline(file, questionType)) {
Question* question = Trivia::createQuestion(questionType);
if (question == nullptr) {
throw std::runtime_error("invalid question type: " + questionType);
}
file >> *question;
this->questions.push_back(question);
}
// this->printQuestions();
}
bool Trivia::askQuestion() {
const size_t index = Trivia::randomIndex(this->questions.size());
assert(index >= 0 && index < this->questions.size());
score_t questionScore = this->questions[index]->ask();
if (questionScore < 0) {
return false;
}
this->score += questionScore;
return true;
}
void Trivia::showStatistics() const {
std::cout << "Final score: " << this->score << std::endl;
}
void Trivia::printQuestions() const {
for (const Question* question : this->questions) {
std::cout << *question << std::endl;
}
}
size_t Trivia::randomIndex(const size_t count) {
// Produce random values with uniform discrete distribution
std::uniform_int_distribution<size_t> randomDistribution(0, count - 1);
// Generate and return a random number using the uniform distribution
return randomDistribution(randomEngine);
}
#include "NumericQuestion.hpp"
#include "TextualQuestion.hpp"
#include "SingleChoiceQuestion.hpp"
Question* Trivia::createQuestion(const std::string& questionType) {
if (questionType == "single_choice") {
return new SingleChoiceQuestion();
} else if (questionType == "textual") {
return new TextualQuestion();
} else if (questionType == "numeric") {
return new NumericQuestion();
} else {
return nullptr;
}
}
El encabezado common.hpp no cambia. Contiene declaraciones que son comunes para todo el proyecto.
Listado 72. common.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#ifndef COMMON_HPP
#define COMMON_HPP
#include <cinttypes>
#include <string>
#define DECLARE_RULE4(Class, action) \
Class(const Class& other) = action; \
Class(Class&& other) = action; \
Class& operator=(const Class& other) = action; \
Class& operator=(Class&& other) = action
#define DISABLE_COPY(Class) \
DECLARE_RULE4(Class, delete)
typedef int64_t score_t;
// Adapted from http://www.martinbroadhurst.com/how-to-trim-a-stdstring.html
static const char* const whitespace = " \t\n\v\f\r";
std::string& ltrim(std::string& str, const std::string& chars = whitespace);
std::string& rtrim(std::string& str, const std::string& chars = whitespace);
std::string& trim(std::string& str, const std::string& chars = whitespace);
std::string& tolower(std::string& str);
std::string& toupper(std::string& str);
#endif // COMMON_HPP
Listado 73. common.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include <algorithm>
#include "common.hpp"
std::string& ltrim(std::string& str, const std::string& chars) {
str.erase(0, str.find_first_not_of(chars));
return str;
}
std::string& rtrim(std::string& str, const std::string& chars) {
str.erase(str.find_last_not_of(chars) + 1);
return str;
}
std::string& trim(std::string& str, const std::string& chars) {
return ltrim(rtrim(str, chars), chars);
}
std::string& tolower(std::string& str) {
std::transform(str.begin(), str.end(), str.begin(), std::tolower);
return str;
}
std::string& toupper(std::string& str) {
std::transform(str.begin(), str.end(), str.begin(), std::toupper);
return str;
}
La clase Question es la que sufre más cambios. Se encarga de cargarse de un archivo (operator>>), imprimirse (operator<<), y efectuar la pregunta al usuario (ask()). El nuevo tipo de pregunta SingleChoiceQuestion tiene formas distintas de realizar estas operaciones. El cargado lo realizaba la subrutina libre operator>>() que no puede comportarse polimóficamente por no tener parámetro oculto this. Se cambia para que invoque un método load() que sí puede polimórfico. Del método ask() se había separado en la versión 2 la funcionalidad isRightAnswer(). Lo mismo se hace con print() dado que las SingleChoiceQuestion deben imprimir sus opciones.
Dado que todos los tipos de preguntas (numéricas, textuales, y de respuesta única) comparan la respuesta de forma diferente, el método isRightAnswer() se convierte en virtual puro. Es decir, se le asigna la dirección de memoria 0 en su declaración y no se provee una implementación en la clase base. Esto provoca que la clase Question se convierta en abstracta. De una clase abstracta no se pueden construir objetos, lo cual tiene sentido, porque en este juego de Trivia "no tienen sentido las preguntas puras". Las clases hijas que no sobrescriban un método virtual puro continuarán siendo abstractas. Las clases que no tengan métodos virtuales puros serán concretas y podrán crear instancias.
Listado 74. Question.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <iostream>
#include <string>
#include "common.hpp"
// template <typename QuestionImpl>
class Question {
public:
DECLARE_RULE4(Question, default);
protected:
// std::string type;
// QuestionImpl impl;
std::string text;
std::string answer;
public:
Question();
virtual ~Question() = default;
virtual std::istream& load(std::istream& input, bool ignoreEmptyLine = true);
virtual void print() const;
friend std::istream& operator>>(std::istream& input, Question& question);
friend std::ostream& operator<<(std::ostream& output
, const Question& question);
score_t ask();
private:
/// pure-virtual method
virtual bool isRightAnswer(const std::string& userAnswer) const = 0;
};
Listado 75. Question.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include <limits>
#include "Question.hpp"
Question::Question() {
}
// Question::~Question() {
// }
std::istream& Question::load(std::istream& input, bool ignoreEmptyLine) {
std::getline(input, this->text);
std::getline(input, this->answer);
if (ignoreEmptyLine) {
input.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
return input;
}
std::istream& operator>>(std::istream& input, Question& question) {
// return question.vtable[1](input);
return question.load(input);
}
std::ostream& operator<<(std::ostream& output, const Question& question) {
return output << question.text << std::endl << question.answer << std::endl;
}
// #include "NumericQuestion.hpp"
// #include "TextualQuestion.hpp"
score_t Question::ask() {
this->print();
std::string userAnswer;
if (!std::getline(std::cin, userAnswer)) {
// User did not answer, pressed Ctrl+D
return -1;
}
if (this->isRightAnswer(userAnswer)) {
std::cout << "Right!" << std::endl;
return 1;
}
std::cout << "Wrong!" << std::endl;
return 0;
}
void Question::print() const {
std::cout << this->text << std::endl;
}
#if 0
bool Question::isRightAnswer(const std::string& userAnswer) const {
return userAnswer == this->answer;
}
#endif
La clase NumericQuestion se encarga de preguntas cuya respuesta es numérica y debe compararse como tal. No cambia respecto a la versión anterior.
Listado 76. NumericQuestion.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <string>
#include "Question.hpp"
class NumericQuestion : public Question {
public:
DECLARE_RULE4(NumericQuestion, default);
protected:
static const double epsilon;
public:
NumericQuestion();
bool isRightAnswer(const std::string& userAnswer) const override;
};
Listado 77. NumericQuestion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include <cmath>
#include "NumericQuestion.hpp"
const double NumericQuestion::epsilon = 0.5;
NumericQuestion::NumericQuestion() {
}
bool NumericQuestion::isRightAnswer(const std::string& userAnswer) const {
// |x1 - x2| < epsilon
return std::fabs(std::stod(userAnswer) - std::stod(this->answer))
< NumericQuestion::epsilon;
}
La clase TextualQuestion que realiza preguntas textuales tampoco cambia en esta versión.
Listado 78. TextualQuestion.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <string>
#include "Question.hpp"
class TextualQuestion : public Question {
public:
DECLARE_RULE4(TextualQuestion, default);
public:
TextualQuestion();
// @Override override != overload
bool isRightAnswer(const std::string& userAnswer) const override;
};
Listado 79. TextualQuestion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include "TextualQuestion.hpp"
TextualQuestion::TextualQuestion() {
}
bool TextualQuestion::isRightAnswer(const std::string& userAnswer) const {
std::string comparableUserAnswer = userAnswer;
::tolower(::trim(comparableUserAnswer));
std::string comparableRightAnswer = this->answer;
::tolower(::trim(comparableRightAnswer));
return comparableUserAnswer == comparableRightAnswer;
}
La clase SingleChoiceQuestion es el nuevo chico de la cuadra, que tiene opciones (también conocidas como categorías o enumeraciones). El jugador debe seleccionar una de las opciones y responder con su número. Al sobrescribir el método virtual puro isRightAnswer(), realiza la comparación usando enteros. El cargado es distinto al resto de preguntas, dado que después de la respuesta vienen las opciones. El cargado invoca la versión de la clase base para reutilizar su código, lo cual es una buena práctica. Sin embargo, la versión de la clase base Question::load() consumía la línea en blanco después de la respuesta. Por tanto se agregó un parámetro discardEmptyLine que las clases hijas pueden ajustar de acuerdo a su necesidad. Al agregar este parámetro, se rompe el polimorfismo en todas las clases hijas. Gracias al marcador override en las clases hijas, el compilador advierte cuando el polimorfismo se rompe, lo que brinda a la persona programadora la conveniencia de detectar el problema de forma muy eficiente.
Listado 80. SingleChoiceQuestion.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#pragma once
#include <string>
#include <vector>
#include "Question.hpp"
class SingleChoiceQuestion : public Question {
public:
DECLARE_RULE4(SingleChoiceQuestion, default);
protected:
std::vector<std::string> choices;
public:
SingleChoiceQuestion();
// This does not work
// friend std::istream& operator>>(std::istream& input, SingleChoiceQuestion& question);
std::istream& load(std::istream& input, bool ignoreEmptyLine = true) override;
void print() const override;
private:
bool isRightAnswer(const std::string& userAnswer) const override;
};
Listado 81. SingleChoiceQuestion.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Copyright 2022 Jeisson Hidalgo ECCI-UCR CCC-BY-4.0
#include "SingleChoiceQuestion.hpp"
SingleChoiceQuestion::SingleChoiceQuestion()
/* : Question(), choices(4) */ {
}
std::istream& SingleChoiceQuestion::load(std::istream& input
, bool /*ignoreEmptyLine*/) {
// (void)ignoreEmptyLine;
// this->Question::text;
// this->SingleChoiceQuestion::load(input);
this->Question::load(input, false);
this->choices.clear();
std::string choice;
while (std::getline(input, choice) && !choice.empty()) {
this->choices.push_back(choice);
}
return input;
}
void SingleChoiceQuestion::print() const {
this->Question::print();
for (size_t index = 0; index < this->choices.size(); ++index) {
std::cout << " " << index + 1 << ". " << this->choices[index] << std::endl;
}
}
bool SingleChoiceQuestion::isRightAnswer(const std::string& userAnswer) const {
return std::stol(userAnswer) == std::stol(this->answer);
}
El Makefile para construir la aplicación no sufre cambios:
Listado 82. Makefile
1
2
3
4
5
6
7
include ../../../../../misc/Makefile
# debug: $(EXEFILE) bin/trivia1.txt
# release: $(EXEFILE) bin/trivia1.txt
# bin/trivia1.txt: data/trivia1.txt
# cp -pf $^ $@
5.5. RunTime Type Information (RTTI)
Cuando se marca un método como vitual, el compilador debe guardar información adicional para saber en tiempo de ejecución cuál versión del método invocar de acuerdo al tipo de registro (clase derivada con que se creó el objeto). Esta información se llama RunTime Type Information (RTTI). Una forma de implementarlo es con tablas de punteros a métodos virtuales:
Para cada clase que tenga al menos un método virtual, se crea (en segmento de código o de datos como se ve arriba) tablas de punteros a métodos virtuales (son simples arreglos de punteros). Los métodos tienen el mismo orden en una clase derivad que su clase base. Los valores en los arreglos son simplemente la dirección en memoria en el segmento de código donde están las instrucciones de ese método, tal como fue definido para esa clase. Si un método virtual en una clase derivada no fue sobrescrito (override), entonces se mantiene la dirección de memoria de la implementación de su clase base. Si un método es virtual puro, su dirección de memoria en su entrada en la tabla será 0 (nullptr), dirección indicada con la asignación = 0 al final de su declaración;
Cuando se crea un objeto de una clase polimórfica (que tiene al menos un método virtual), el compilador le agregará un campo oculto llamado vtable que es un puntero con la dirección de memoria hacia la tabla de punteros a métodos virtuales para esa clase. Este campo siempre es el primero del registro. De esta forma, el programa puede saber en tiempo de ejecución con qué clase fue creado el objeto, sin importar si se tiene simplemente un puntero a la clase base, de ahí el nombre RTTI (tipos de datos en tiempo de ejecución).
Cuando se invoca a una subrutina normal subr() el nombre de la subrutina subr es su dirección de memoria. Por lo tanto, se requiere simplemente un nivel de indirección para llegar a su cuerpo para invocarlo. Sin embargo, cuando se invoca un método virtual, se ocupan tres niveles de indirección. El compilador instrumentaliza cada invocación a un método virtual para acceder a la entrada de ese método en la tabla de punteros a métodos virtuales a través del campo oculto vtable. Por ejemplo, en la figura anterior, el método load() está siempre en la segunda entrada (índice 1) de los objetos Question. El compilador hará el siguiente cambio en cada invocación que se haga de load():
// La invocación en código fuente
question->load(file);
// Será cambiada por el compilador a
question->vtable[1](file)El código instrumentalizado hará que se invoque la versión de load() para cada objeto de acuerdo a los métodos virtuales para su clase. Por ejemplo, para un NumericQuestion se invocará la versión de load() de Question y para un SingleChoiceQuestion se invocará la versión de SingleChoiceQuestion::load(). El polimorfismo incrementa el tamaño de todos los objetos (registros) de la clase en un puntero (8 bytes), y el acceso a los métodos virtuales no es inmediato, sino que requiere acceder al objeto, luego al vtable, y luego a la entrada en el arreglo vtable[i], por lo tanto, se habla de tres niveles de indirección, que requiere más tiempo y recursos que una subrutina normal. Por eso el polimorfismo está desactivado por defecto en C++ y la persona desarrolladora lo activa usando la palabra reservada virtual sólo en los métodos que realmente requieren el comportamiento polimórfico.
