[75.04 - Algoritmos Y Programación Ii] Tp1

Transcript

75.04/95.12 Algoritmos y Programaci´on II Trabajo pr´actico 1: Programaci´on C++ Universidad de Buenos Aires - FIUBA Segundo cuatrimestre de 2014 $Date: 2014/10/05 22:49:17 $ 1. Objetivos Ejercitar conceptos b´ asicos de programaci´on C++ e implementaci´on de TDAs. Escribir un programa en este lenguaje (y su correspondiente documentaci´on) que resuelva el problema que presentaremos m´ as abajo. 2. Alcance Este trabajo pr´ actico es de elaboraci´on grupal, evaluaci´on individual, y de car´acter obligatorio para todos alumnos del curso. 3. Requisitos El trabajo deber´ a ser´ a entregado personalmente, en la fecha estipulada, con una car´atula que contenga los datos completos de todos los integrantes, un informe impreso de acuerdo con lo que mencionaremos en la secci´ on 5, y con una copia digital de los archivos fuente necesarios para compilar el trabajo. 4. Introducci´ on En este trabajo continuaremos desarrollando nuestra herramienta para procesar im´agenes, de forma tal que el programa pueda recibir funciones de transformaci´on arbitrarias. Con esto en mente, nuestro programa deber´a poder: Cargar una imagen a memoria desde un archivo o desde la entrada est´andar. Aplicar una funci´ on arbitraria, pasada por l´ınea de comando, a la imagen. Guardar una imagen en memoria a un archivo o sacarlo por la salida est´andar. 4.1. Interfaz Tanto en este TP, como en el siguiente, la interacci´on con el programa se dar´a a trav´es de la l´ınea de comando. Formato. Por simplicidad se usar´ a un formato de im´agenes basado en archvios de texto: portable graymap o PGM, con codificaci´ on ASCII[1]. Este formato define un mapa de grises: cada pixel va a tener un valor que define su intensidad entre 0 (negro) y cierto n´ umero max (blanco). 1. La primer l´ınea siempre contiene P2, el identificador del tipo de archivo o magic number. 2. Luego puede haber comentarios identificados con # al inicio de la l´ınea. Estos comentarios deben ser ignorados por el programa. 3. Despu´es se presenta el tama˜ no de la imagen. En el ejemplo de m´as abajo, 24 pixels de ancho y 7 de alto. 4. Una vez definido el tama˜ no encontramos el m´aximo valor de intensidad de la imagen. En el ejemplo, 15. 5. Por u ´ltimo est´ a la im´ agen en s´ı: cada n´ umero define la intensidad de un pixel, comenzando en el margen superior izquierdo de la imagen y barri´endola por l´ıneas hacia abajo. Ejemplo. En el siguiente ejemplo se puede ver una imagen en formato pgm (ampliada): Y a continuaci´ on el contenido del archivo correspondiente: P2 # Shows the word "FEEP" (example 24 7 15 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 0 0 7 7 7 7 0 3 0 0 0 0 0 7 0 0 0 0 3 3 3 0 0 0 7 7 7 0 0 3 0 0 0 0 0 7 0 0 0 0 3 0 0 0 0 0 7 7 7 7 0 0 0 0 0 0 0 0 0 0 0 from Netpbm main page on PGM) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 11 11 11 11 0 0 0 11 11 11 0 11 0 0 0 11 11 11 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 15 15 15 15 0 0 15 15 15 15 15 15 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Transformaci´ on. Para modificar la imagen usaremos una funci´on compleja f : C → C. Para esto se asocia cada pixel de la imagen a un n´ umero complejo z = a + b · i. A lo largo de este TP, vamos a suponer que la imagen cubre una regi´ on rectangular del plano complejo, cuyas coordenadas son pasadas por l´ınea de comando. As´ı, los pixels de la imagen conformar´an una grilla de puntos contenida dentro de esta regi´ on. Los pixels de la imagen destino se colorean aplicando la funci´on: para cada punto z de la imagen destino se asocia con un punto f (z) en la imagen origen. Es decir, esta transformaci´on solamente deforma la imagen original sin alterar el color del pixel. Teniendo en cuenta las dimensiones acotadas de nuestras im´agenes, se van a dar los siguientes casos: z pertenece a la imagen destino y f (z) cae dentro de la imagen origen: este es el caso esperable. z pertenece a la imagen destino y f (z) cae fuera de la imagen origen: asumir que z es coloreado de negro. Este tipo de transformaci´ on permite hacer un remapeo de las im´agenes. Si la funci´on involucrada es holomorfa, se trata de una transformaci´on conforme: la imagen transformada conserva los ´angulos de la imagen original [2]. Algoritmo. En este TP, el algoritmo de evaluaci´on de funciones a implementar es el descripto en [3]. El mismo puede ser usado para reescribir expresiones infix en formato RPN para luego ser evaluadas durante el proceso de transformaci´ on. 2 Funciones. La funciones a implementar en este TP son expresiones arbitrarias conformadas por n´ umeros complejos de la forma a + b*j, los operadores aritm´eticos usuales +, -, *, /, ^, las funciones exp(z), ln(z), re(z), im(z), abs(z), phase(z), y par´entesis para agrupar subexpresiones cuando sea conveniente. Se propone a los alumnos pensar e implementar distintas funciones f (z) para usar por fuera del contexto de este. Luego procesar im´ agenes y mandar a la lista de mails de la materia la imagen original, la procesada y la funci´ on involucrada. 4.2. L´ınea de comando Las opciones -i y -o permitir´ an seleccionar los streams de entrada y salida de datos respectivamente. Por defecto, ´estos ser´ an cin y cout. Lo mismo ocurrir´a al recibir “-” como argumento de cada una. La opci´ on -f permite seleccionar qu´e funci´on se quiere usar para procesar la im´agen. Por defecto se usar´ a la funci´ on identidad f (z) = z. Al finalizar, todos nuestros programas retornar´an un valor nulo en caso de no detectar ning´ un problema; y, en caso contrario, devolveremos un valor no nulo (por ejemplo 1). Como comentario adicional, el orden de las opciones es irrelevante. Por este motivo, no debe asumirse un orden particular de las mismas a la hora de desarrollar la toma de argumentos. 4.3. Ejemplos Primero, transformamos la imagen grid.pgm con la funci´on identidad: f (z) = z y guardamos la salida en grid-id.pgm. Ver figura 1. $ ./tp1 -i grid.pgm -o grid-id.pgm -f z Figura 1: grid.pgm y grid-id.pgm Figura 2: grid-exp.pgm Ahora, transformamos con f (z) = ez y guardamos la salida en evolution-exp.pgm. Ver figuras 3 y 4. $ ./tp1 -i evolution.pgm -o evolution-exp.pgm -f exp(z) Figura 3: evolution.pgm Figura 4: evolution-exp.pgm Por u ´ltimo, transformamos la misma imagen con las funciones f (z) = z 2 y f (z) = z 3 , dejando los resultados en evolution-sqr.pgm y evolution-cube.pgm. Ver figuras 5 y 6). 3 $ ./tp1 -i evolution.pgm -o evolution-sqr.pgm -f z^2 $ ./tp1 -i evolution.pgm -o evolution-cube.pgm -f z^3 Figura 5: evolution-sqr.pgm Figura 6: evolution-cube.pgm Como siempre, estos ejemplos deben ser incluidos como punto de partida de los casos de prueba del trabajo pr´ atico. 4.4. Portabilidad Es deseable que la implementaci´ on desarrollada provea un grado m´ınimo de portabilidad. Sugerimos verificar nuestros programas en alguna versi´on reciente de UNIX: BSD o Linux. 5. Informe El contenido m´ınimo del informe deber´a incluir: Una car´ atula que incluya los nombres de los integrantes y el listado de todas las entregas realizadas hasta ese momento, con sus respectivas fechas. Documentaci´ on relevante al dise˜ no e implementaci´on del programa. Documentaci´ on relevante al proceso de compilaci´on: c´omo obtener el ejecutable a partir de los archivos fuente. Las corridas de prueba, con los comentarios pertinentes. El c´ odigo fuente, en lenguaje C++ (en dos formatos, digital e impreso). Este enunciado. 6. Fechas La u ´ltima fecha de entrega y presentaci´on ser´a el jueves 23/10. Referencias [1] Netpbm format (Wikipedia). http://en.wikipedia.org/wiki/Netpbm_format [2] Holomorphic function (Wikipedia). http://en.wikipedia.org/wiki/Holomorphic_function [3] Shunting yard algorithm. algorithm (Wikipedia). http://en.wikipedia.org/wiki/Shunting_yard_ 4 UNIVERSIDAD DE BUENOS AIRES FACULTAD DE INGENIERÍA Año 2014 – 2do Cuatrimestre ALGORITMOS Y PROGRAMACIÓN II (75.04) TRABAJO PRÁCTICO 1 TEMA: Programación C++ FECHA: Miércoles 10 de diciembre de 2014 ENTREGADOS HASTA LA FECHA:  TP0: 23/10/2014  TP1: 10/12/2014 INTEGRANTES: Zaragoza, Juan Manuel - # 92.308 Ferrari Bihurriet, Francisco - # 92.275 Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 1 1 Objetivo El principal objetivo del presente trabajo práctico consiste en implementar una herramienta para procesar imágenes, la cual recibe una imagen y una función de procesamiento no estandarizada para obtener una nueva imagen dependiendo de la tipo de función elegida. El otro objetivo es ejercitar conceptos básicos de programación C++ e implementar TDAs. 2 Descripción y modo de uso de la herramienta El modo de uso de la herramienta mencionada: $ ./tp1 [-i /dirección/a/archivo/entrada/*.png] [-r región] [-o /dirección/a/archivo/salida/*.png] [-f funciones] donde: • /dirección/a/archivo/entrada/*.png: nombre y dirección de la imagen PNG que quiere ser procesada. En caso de no especificarse una, la herramienta adoptará la entrada estándar. • /dirección/a/archivo/entrada/*.png: nombre y dirección de la imagen de salida procesada por la herramienta. En caso de no especificarse una, la herramienta adoptará la salida estándar. • funciones: las funciones soportadas son expresiones algebraicas que opere números complejos. Por ej.: “2*exp(z)+sin(z^2)+5”. • región: región del plano complejo donde se quiere trabajar, expresada como “,,,”. Por ej.: “"2,2,0,0"”, que es la opción por defecto. 3 Diseño e Implementación Se identificaron diferentes maneras de resolver el problema planteado, donde la más conveniente fue creando las clases para las entidades más importantes que involucran al trabajo práctico número 1. Obviamente, algunas clases que se utilizan en este trabajo no serán descriptas porque ya fueron hechas en el trabajo práctico número 0. 3.1 Problemas identificados El primer problema encontrado fue, cómo a partir de un string pasado como parámetro de entrada podíamos convertirlo en una función evaluable. Para resolver este problema utilizamos la notación polaca inversa o RPN e implementamos el algoritmo shunting yard el cual se encarga de convertir una expresión infija en otra postfija. Luego, para implementar el algoritmo mencionado, necesitábamos alguna entidad que se encargara de apilar/acolar los operadores/operandos que recibíamos de la entrada. Para esto se implementaron las clases stack y queue que representan una pila y una cola, respectivamente. Estas clases, se ayudaron de la clase node, la cual representa un nodo que posee un valor y un puntero a otro nodo. Debido a la dificultad de manipular los operadores/operandos/funciones como si fuesen cadenas de texto, se implementó la clase token que representa cualquier elemento que puede intervenir en la expresión algebraica. Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 2 Además, en complemento a estas entidades, se creó la clase optree que representa un árbol en memoria de la expresión RPN que ayuda a calcular la expresión anteriormente mencionada con los valores del píxel a operar entre sus atributos. 3.2 Resolución El programa principal (main) se encarga de delegar la validación de argumentos en línea de comandos, la lectura del archivo de entrada (o en su defecto, la entrada estándar), la creación de la imagen de entrada en memoria y carga con los valores del archivo, la creación de la imagen de salida en memoria, y en cada posición de ésta, la asignación del píxel proveniente de aplicar una función compleja a la posición del píxel en la imagen de entrada, y por último, la grabación de la imagen de salida (o en su defecto, la salida estándar) con el resultado de la transformación mencionada. Para aplicar la función proveniente como argumento en línea de comando, se utilizó un método que la convierte en una cola de tokens que es convertida a la notación RPN para que luego se pueda evaluar cada píxel de la imagen. 3.2.1 Soluciones del trabajo práctico número 0 Las soluciones implementadas en el trabajo práctico 0 sirvieron para el presente trabajo, pero no serán descriptas detalladamente porque el objeto del presente radica en las clases que mencionaremos en los siguientes puntos. El principal problema del trabajo anterior, fue cómo transformar una imagen en un conjunto de puntos ubicados en el plano complejo que fue solucionado con algunas transformaciones matemáticas ya descriptas. La clase complex es nuevamente utilizada para representar un número complejo y para operar con determinadas funciones sobre ellos. Se agregaron los métodos: Operaciones binarias: • const complex operator_add(const complex &, const complex &); suma dos complejos. • const complex operator_subt(const complex &, const complex &); resta dos complejos. • const complex operator_mult(const complex &, const complex &); multiplica dos complejos. • const complex operator_div(const complex &, const complex &); divide dos complejos. • const complex operator_pow(const complex &, const complex &); calcula la potencia entre dos complejos (w^z). Operaciones unarias: • const complex exp(const complex &); función exponencial de un número complejo. • const complex log(const complex &); logaritmo natural de un número complejo. • const complex sin(const complex &); función seno de un número complejo. • const complex cos(const complex &); función coseno de un número complejo. • const complex real_as_complex(const complex &); obtiene la parte real de un número complejo, en la parte real de otro número complejo de salida. Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 3 • const complex imag_as_complex(const complex &); obtiene la parte imaginaria de un número complejo, en la parte real de otro número complejo de salida. • const complex abs_as_complex(const complex &); obtiene el módulo de un número complejo, en la parte real de otro número complejo de salida. • const complex phase_as_complex(const complex &); obtiene el argumento (fase) de un número complejo, en la parte real de otro número complejo de salida. Por último, la clase PGMimage representa una imagen extraída de un archivo PGM en memoria. Posee los siguiente atributos: _magic_number, _width (ancho de la imagen), _height (alto de la imagen), _color_depth (profundidad de color) y _canvas (lienzo en memoria). 3.2.2 Clase Node La clase node representa un nodo. Un nodo posee un valor y un puntero a un nodo. Por lo tanto, es la estructura básica para implementar una pila o una cola. 3.2.2.1 Constructores La clase posee solo un constructor, el cual asigna un valor a su atributo _value y un puntero al siguiente nodo en caso de que se especifique un nodo, sino un puntero a NULL. 3.2.3 Clase Stack Esta clase representa una pila. Una pila es una estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. El único atributo que posee esta clase es un puntero a un nodo denominado _last, que representa el último elemento ingresado en el contenedor. 3.2.3.1 Constructores La clase posee un solo constructor que inicializa a NULL su puntero _last. 3.2.3.2 Destructores La clase implementa un destructor que desapila todos los elementos almacenados en el contenedor. 3.2.3.3 Métodos característicos Existen algunos métodos característicos de la clase Stack: • bool isEmpty() const; informa si la pila se encuentra vacía. • void push(const T& ); agrega (apila) un dato en la pila. • T pop(); devuelve el último dato ingresado y destruye el nodo. • T& topElement(); devuelve el elemento superior de la pila para poder operarlo o consultarlo. Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 4 3.2.4 Clase Queue Esta clase representa una cola. Una pila es una estructura de datos en la que el modo de acceso a sus elementos es de tipo FIFO (del inglés First In First Out, primero en entrar, primero en salir) que permite almacenar y recuperar datos. Posee dos atributos: un puntero a un nodo denominado _last y otro denominado _first. 3.2.4.1 Constructores La clase posee un solo constructor que inicializa a NULL sus punteros _last y _first. 3.2.4.2 Destructores La clase implementa un destructor que desencola todos los elementos almacenados en el contenedor hasta que no _first apunte a NULL. 3.2.4.3 Métodos característicos Existen algunos métodos característicos de la clase Cola: • bool isEmpty() const; informa si la cola se encuentra vacía. • void enqueue(const T& ); agrega (acola) un dato en la cola. • T dequeue(); devuelve el primer dato ingresado y destruye el nodo. • T& frontElement(); devuelve el primero elemento de la cola para ser modificado o consultado. • T& lastAdded(); devuelve el último elemento de la cola para ser modificado o consultado. 3.2.5 Biblioteca Parser Estos archivos (parser.cpp y parser.h) representan un parseador que contiene una clase token que representa un token el cual puede ser un string o un double para almacenar cada uno de los elementos de la expresión infija de entrada algunos de los cuales formarán la expresión RPN. Además, estos archivos contienen utilidades auxiliares que parsean una entrada de string en tokens para luego convertirla a una expresión RPN, y los arreglos de strings asociadas a ciertos tokens, con sus correspondientes arreglos de punteros a función o valores asociados. 3.2.5.1 Clase Token: Constructores La clase posee tres constructores: un constructor que recibe un double y setea un TOKEN_IS_VALUE en su atributo string; otro constructor que recibe un string y setea un NaN en su atributo double; y por último, un constructor por copia. 3.2.5.2 Clase Token: Métodos getters Existen algunos métodos para “traducir” el token: • string getAsString() const; obtiene el token como string (devuelve número en string si es del tipo 'valor') • double getAsDouble() const; obtiene el token como un double (devuelve NaN, si no es del tipo 'valor') Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 5 3.2.5.3 Clase Token: Métodos auxiliares para identificar los tokens Métodos booleanos que permiten definir el token: • bool isValue() const; ¿Es del tipo 'valor'? • bool isParenthesis() const; ¿Es un paréntesis? • bool isOpenParenthesis() const; ¿Es un paréntesis abierto? • bool isClosedParenthesis() const; ¿Es un paréntesis cerrado? • bool isOperator() const; ¿Es un operador? • bool isSpecial() const; ¿Es un token especial? Los token especiales son “j”, “e”, “pi” y “z”. • bool isFunction() const; ¿Es una función? Las funciones pueden ser "exp", "ln", "sin", "cos", "re", "im", "abs" y "phase". 3.2.5.4 Clase Token: Método para utilitario del conversor a RPN El método int precedence() const; es utilizado para informar la precedencia de un token operador o función. 3.2.5.5 Funciones de la biblioteca para la conversión de la expresión de entrada en notación RPN Como se ya se ha mencionado, estas funciones se encuentran dentro del archivo parser.cpp y se encargan de la conversión a RPN: • int find_in_list(const string [], const string &); función para buscar en una lista con centinela de cadena vacía, si no encuentra la string buscada, devuelve NOT_FOUND, que vale -1, si en cambio es encontrada, devuelve su posición en el arreglo de strings. Ésta función es utilizada en conjunto con las macros de función is_operator(), is_special(), is_function(); y dentro de la clase optree_node, para obtener los punteros asociados a las funciones (operadores) o los complejos (operandos especiales). • void parse_expression_in_tokens(const string &, queue &); función que parsea el string de entrada en una cola de tokens. • void convert_to_RPN(stack &, queue &); función que recibe una cola de tokens (proveniente del método anterior) y devuelve una pila que representa la notación polaca inversa (al desapilarla se obtiene una lectura de derecha a izquierda de la misma). 3.2.6 Clase Optree Node Esta clase representa un nodo en el árbol de operaciones. 3.2.6.1 Constructores La clase posee dos constructores: uno por defecto que inicializa todos sus parámetros a NULL: el dato del nodo, las operaciones sobre los mismos, el hijo izquierdo, el hijo derecho y el padre; y otro que inicializa una hoja con un token, y acepta un puntero al padre como argumento opcional. Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 6 3.2.6.2 Destructor El destructor se encarga de eliminar el nodo (su memoria dinámica, si es que utiliza) y sus hijos, tanto izquierdo como derecho (si es que tiene). 3.2.6.3 Métodos disponibles • const complex operate(const complex *z); opera recursivamente el subárbol que cuelga del nodo en cuestión, recibiendo como parámetro un puntero al complejo z de la operación. Devuelve el complejo resultante. • bool simplify(); privado, simplifica el subárbol de operaciones que cuelga del nodo, realizando las operaciones del mismo que no dependen del complejo z de la operación, cuyo resultado no cambiará durante el recorrido de la imagen, esto busca evitar la repetición de cálculos innecesarios. Con una estrategia recursiva se buscan los nodos que no dependen de z, el booleano que devuelve el método es verdadero si el subárbol depende de z (este valor tiene sentido utilizado en las invocaciones recursivas, en la invocación externa puede ser descartado). Una vez encontrado un nodo que no depende de z y a su vez tiene hijos, el subárbol es reemplazado por un único nodo con el resultado de la operación (que no es z dependiente). Ambos procesos, búsqueda y simplificación se realizan en la misma recursión. 3.2.7 Clase Optree Esta clase representa el árbol de operaciones, formado por nodos del tipo optree_node, que contiene información (punteros) de cuál es la raíz del árbol (_root) y cuál es el complejo que cambiará al iterar los píxeles, durante el recorrido de la imagen (_asoc_pixel). 3.2.7.1 Constructores La clase posee un constructor por defecto que genera un árbol vacío (ambos atributos en NULL) . Por otro lado está el constructor optree(stack &, complex &); que carga el árbol a partir de una pila de tokens en formato RPN y una referencia al complejo que se va a utilizar como z, es decir el que va a cambiar en cada evaluación de la expresión para que sea apuntado por _asoc_pixel. Este constructor realiza una simplificación del árbol mediante el método interno simplify() de la clase optree_node (privado, la clase nodo usa el operador friend para la clase optree), descartando su valor booleano de devolución. 3.2.7.2 Destructor Simplemente invoca al destructor de la raíz, que se encargará recursivamente del árbol completo. 3.2.7.3 Operar Invoca al método operar de la raíz, previas validaciones, pasándole como argumento el puntero a z seteado en el constructor. 3.2.8 Programa principal El programa principal realiza los siguientes pasos: 1. Por línea de comando se validan los argumentos, se setean los flujos/archivos de donde se leerán y/o escribirán las imágenes PGM y se arma la expresión RPN en una pila de tokens. Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 7 2. Se abren los archivos en caso de no haberse elegido las entradas/salidas estándar. 3. Se crea una nueva imagen en memoria, se lee desde el flujo/archivo la imagen y se sube a memoria. 4. Se crea una nueva imagen en memoria pero de salida con los tamaños y profundidad de la imagen de entrada o los seleccionados por el usuario por línea de comandos. 5. Se crean dos complejos con constructores por defecto para los planos de entrada y salida. 6. Se genera un árbol de operaciones a través de la pila RPN mencionada en el punto 1), configurando el complejo asociado al píxel en el plano de salida (el z de la expresión de entrada). 7. Se comienza a recorrer la imagen de salida, a los índices se les aplica la función que los convierte en un complejo (plano de salida), para luego aplicar la expresión ingresada por CLA a través del árbol de operaciones. 8. Con el complejo resultante (plano de entrada), se obtiene la posición en el lienzo de entrada y se copia su valor en la nueva imagen (lienzo de salida). Se reinicia el ciclo, continuando el recorrido descripto a partir del punto 7). 9. Por último, el lienzo de salida que se encuentra en memoria se escribe en el flujo/archivo de salida. 4 Proceso de compilación Para compilar los archivos en entornos Unix-like, fue diseñado el Makefile, con las siguientes opciones: ➔ Para generar todos los archivos objeto, más el ejecutable en el directorio ./bin/ ➔ $ make Este comando crea el directorio ./bin/ compilando el código fuente para obtener los siguientes archivos en código objeto: • PGMimage.o: Clase para manejo de imágenes PGM. • complex.o: Clase para manejo de número complejos. • utils.o: Utilidades del programa, como las funciones internas y los parsers de CLA. • cmdline.o: Manejo de CLA, provisto por los docentes, levemente modificado. • parser.o: Biblioteca de parseo de la expresión de entrada. • optree.o: Clase para la creación, simplificación y evaluación del árbol de operaciones. • main.o: Programa principal, propiamente dicho. Luego estos archivos son “linkeados” en el ejecutable ./bin/tp1 ➔ Para crear el ejecutable con la información y las etiquetas de debugging ➔ $ make debug ➔ Para “limpiar” (eliminar todos los binarios, y el directorio ./bin/) ➔ $ make clean Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 8 ➔ Para eliminar sólo los archivos objeto ➔ $ make objclean ➔ Para compilar eliminando los archivos temporarios ➔ $ make deltemps ➔ Para instalar (*) ➔ # make install ➔ Desinstalar (*) ➔ # make uninstall (*): Se requieren permisos de superusuario NOTA: también fue probado en Windows con MinGW, donde las utilidades extra no funcionan, pero sí el comando make a secas. 5 Ejecución y resultados En está sección se describirán los diferentes modo de uso y resultados de las sucesivas pruebas realizadas. 5.1 Pruebas iniciales A continuación se exhiben los resultados al realizar las siguientes acciones: compilación, ejecuciones con mensaje de ayuda, expresiones mal formadas y regiones inválidas. Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 9 5.2 Pruebas con imágenes PGM Se mostrarán los diferentes resultados obtenidos al correr diferentes pruebas. Notar que no es necesario hacer una captura de la consola luego de ejecutarse el comando, por lo tanto, solo mostraremos la imagen origen y destino junto al comando ejecutado. Primero mostraremos la imagen con la función identidad para entender cual es la imagen original y luego mostraremos la imagen transformada. NOTA: imágenes posteriormente convertidas y escaladas para el informe. 5.2.1 Imágenes del enunciado Imagen 1: grid-id.pgm Imagen 2: grid-exp.pgm ./tp1 -i grid.pgm -o grid-id.pgm -f z ./tp1 -i grid.pgm -o grid-exp.pgm -f exp(z) Imagen 3: evolution-id.pgm Imagen 4: evolution-exp.pgm ./tp1 -i evolution.pgm -o evolution-id.pgm -f z ./tp1 -i evolution.pgm -o evolution-exp.pgm -f exp(z) Imagen 5: evolution-sqr.pgm Imagen 6: evolution-cube.pgm ./tp1 -i evolution.pgm -o evolution-sqr.pgm -f z^2 ./tp1 -i evolution.pgm -o evolution-cube.pgm -f z^3 Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 10 5.2.2 Otras imágenes y pruebas Imagen 7: clocks-1.pgm Imagen 8: clocks-2.pgm ./tp1 -i clocks.pgm -r 6.4,4.8,0,0 -o clocks-1.pgm -f z ./tp1 -i clocks.pgm -r 6.4,4.8,0,0 -o clocks-2.pgm -f j*z Imagen 9: clocks-3.pgm Imagen 10: clocks-4.pgm ./tp1 -i clocks.pgm -r 6.4,4.8,0,0 -o clocks-3.pgm -f exp(z^3) ./tp1 -i clocks.pgm -r 6.4,4.8,0,0 -o clocks-4.pgm -f exp(z^j) Imagen 11: clocks-5.pgm Imagen 12: pattern-1.pgm ./tp1 -i clocks.pgm -r 6.4,4.8,0,0 -o clocks-5.pgm -f j^(-z) ./tp1 -i pattern.pgm -r 5,3.75,0,0 -o pattern-1.pgm -f z Imagen 13: pattern-2.pgm Imagen 14: pattern-3.pgm ./tp1 -i pattern.pgm -r 5,3.75,0,0 -o pattern-2.pgm -f (z*1.7*e^(-j*pi/4)) ./tp1 -i pattern.pgm -r 5,3.75,0,0 -o pattern-3.pgm -f (z*1.5)^0.85 Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 11 Imagen 15: 9097x6500-1.pgm Imagen 16: 9097x6500-2.pgm ./tp1 -i 9097x6500.pgm -r 9.097,6.5,0,0 -o 9097x6500-1.pgm -f z ./tp1 -i 9097x6500.pgm -r 9.097,6.5,0,0 -o 9097x6500-2.pgm -f z^(j*sin(z)) 6 Conclusión El trabajo práctico presentado, nos originó diferentes dificultades. Al principio se nos hizo difícil empezar con el parseo de la expresión, y lo hicimos sin tener bien en claro cómo haríamos luego para evaluarla. Después de replantear algunas estructuras y hacer el parseo más robusto, optamos por el camino del árbol de operaciones (la otra alternativa era evaluar utilizando una pila). Al elegir este camino surgieron nuevas problemáticas así como ideas, la primera fue realizar una clase “híbrida” que pudiera ser nodo de éste árbol, teniendo la opción de ser operador u operando, y que sea capaz de auto evaluarse. La segunda vino de la mano de una optimización, realizando las operaciones estáticas que permanecerán constantes al recorrer la imagen primero, simplificando el árbol y evitando cálculos repetitivos sin sentido. Esta optimización sólo es notoria en casos de imágenes muy grandes y/o casos en que la cantidad de operaciones independientes de z a simplificar es alta. Es un trabajo interesante para terminar de aprender algunas técnicas y conceptos de C++, tales como el uso intensivo de clases. También resultó pedagógico en lo que respecta a estructuras de datos, como las pilas, colas y árboles, y sus operaciones más comunes. A esto se suma lo entretenido de la transformación de imágenes mediante funciones holomorfas, que ahora pueden (a diferencia del tp0) ser ingresadas en tiempo de ejecución, haciendo más amena la tarea de resolver las dificultades, permitiendo “jugar” un poco mientras se trabaja. 7 Bibliografía ● Netpbm format (Wikipedia). http://en.wikipedia.org/wiki/Netpbm_format ● Holomorphic function (Wikipedia). http://en.wikipedia.org/wiki/Holomorphic_function ● Conformal pictures (Wikipedia). http://en.wikipedia.org/wiki/Conformal_pictures ● Standard C++ Library reference (cplusplus.com). http://www.cplusplus.com/reference/ Juan Manuel Zaragoza – 92308 Francisco Ferrari Bihurriet – 92275 TP1 - 12 cmdline.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 Página 1 #ifndef _CMDLINE_H_INCLUDED_ #define _CMDLINE_H_INCLUDED_ #include #include #define OPT_DEFAULT 0 #define OPT_SEEN 1 #define OPT_MANDATORY 2 struct option_t { bool has_arg; const char *short_name; const char *long_name; const char *def_value; void (*parse)(std::string const &); int flags; }; class cmdline { // Este atributo apunta a la tabla que describe todas // las opciones a procesar. Por el momento, sólo puede // ser modificado mediante constructor, y debe finalizar // con un elemento nulo. // option_t *option_table; // El constructor por defecto cmdline::cmdline(), es // privado, para evitar construir parsers sin opciones. // cmdline(); int do_long_opt(const char *, const char *); int do_short_opt(const char *, const char *); public: cmdline(option_t *); void parse(int, char * const []); }; #endif cmdline.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 Página 1 // cmdline − procesamiento de opciones en la línea de comando. // // $Date: 2012/09/14 13:08:33 $ // #include #include #include #include "cmdline.h" using namespace std; cmdline::cmdline() { } cmdline::cmdline(option_t *table) : option_table(table) { } void cmdline::parse(int argc, char * const argv[]) { #define END_OF_OPTIONS(p) \ ((p)−>short_name == 0 \ && (p)−>long_name == 0 \ && (p)−>parse == 0) // Primer pasada por la secuencia de opciones: marcamos // todas las opciones, como no procesadas. Ver código de // abajo. // for (option_t *op = option_table; !END_OF_OPTIONS(op); ++op) op−>flags &= ~OPT_SEEN; // Recorremos el arreglo argv. En cada paso, vemos // si se trata de una opción corta, o larga. Luego, // llamamos a la función de parseo correspondiente. // for (int i = 1; i < argc; ++i) { // Todos los parámetros de este programa deben // pasarse en forma de opciones. Encontrar un // parámetro no−opción es un error. // if (argv[i][0] != '−') { cerr << "Invalid non−option argument: " << argv[i] << endl; exit(1); } // // // // // if Usamos "−−" para marcar el fin de las opciones; todo los argumentos que puedan estar a continuación no son interpretados como opciones. // // // // if Finalmente, vemos si se trata o no de una opción larga; y llamamos al método que se encarga de cada caso. (argv[i][1] == '−' && argv[i][2] == 0) break; (argv[i][1] == '−') i += do_long_opt(&argv[i][2], argv[i + 1]); else i += do_short_opt(&argv[i][1], argv[i + 1]); } // Segunda pasada: procesamos aquellas opciones que, // (1) no hayan figurado explícitamente en la línea // de comandos, y (2) tengan valor por defecto. // cmdline.cpp 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 Página 2 for (option_t *op = option_table; !END_OF_OPTIONS(op); ++op) { #define OPTION_NAME(op) \ (op−>short_name ? op−>short_name : op−>long_name) if (op−>flags & OPT_SEEN) continue; if (op−>flags & OPT_MANDATORY) { cerr << "Option " << "−" << OPTION_NAME(op) << " is mandatory." << "\n"; exit(1); } if (op−>def_value == 0) continue; op−>parse(string(op−>def_value)); } } int cmdline::do_long_opt(const char *opt, const char *arg) { option_t *op; // Recorremos la tabla de opciones, y buscamos la // entrada larga que se corresponda con la opción de // línea de comandos. De no encontrarse, indicamos el // error. // for (op = option_table; op−>long_name != 0; ++op) { if (string(opt) == string(op−>long_name)) { // Marcamos esta opción como usada en // forma explícita, para evitar tener // que inicializarla con el valor por // defecto. // op−>flags |= OPT_SEEN; if (op−>has_arg) { // Como se trada de una opción // con argumento, verificamos que // el mismo haya sido provisto. // if (arg == 0) { cerr << "Option requires argument: " << "−−" << opt << "\n"; exit(1); } op−>parse(string(arg)); return 1; } else { // Opción sin argumento. // op−>parse(string("")); return 0; } } } // Error: opción no reconocida. Imprimimos un mensaje // de error, y finalizamos la ejecución del programa. // cerr << "Unknown option: " << "−−" << opt << "." << endl; exit(1); // Algunos compiladores se quejan con funciones que // lógicamente no pueden terminar, y que no devuelven cmdline.cpp 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 Página 3 // un valor en esta última parte. // return −1; } int cmdline::do_short_opt(const char *opt, const char *arg) { option_t *op; // Recorremos la tabla de opciones, y buscamos la // entrada corta que se corresponda con la opción de // línea de comandos. De no encontrarse, indicamos el // error. // for (op = option_table; op−>short_name != 0; ++op) { if (string(opt) == string(op−>short_name)) { // Marcamos esta opción como usada en // forma explícita, para evitar tener // que inicializarla con el valor por // defecto. // op−>flags |= OPT_SEEN; if (op−>has_arg) { // Como se trata de una opción // con argumento, verificamos que // el mismo haya sido provisto. // if (arg == 0) { cerr << "Option requires argument: " << "−" << opt << "\n"; exit(1); } op−>parse(string(arg)); return 1; } else { // Opción sin argumento. // op−>parse(string("")); return 0; } } } // Error: opción no reconocida. Imprimimos un mensaje // de error, y finalizamos la ejecución del programa. // cerr << "Unknown option: " << "−" << opt << "." << endl; exit(1); // Algunos compiladores se quejan con funciones que // lógicamente no pueden terminar, y que no devuelven // un valor en esta última parte. // return −1; } complex.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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Página 1 #ifndef COMPLEJO_H #define COMPLEJO_H #include using namespace std; // Macro para elevar al cuadrado multiplicando por si mismo #define square(x) ((x)*(x)) class complex { private: double _x, _y; public: complex(); complex(double , double); complex(const complex &); ~complex(); double getReal()const; double getImag()const; void setReal(double xx); void setImag(double yy); double getArg()const; double getPha()const; friend ostream& operator<<(ostream&, const complex &); friend istream& operator>>(istream&, complex &); complex& operator=(const complex &); const complex operator+(const double)const; void operator+=(const complex &); void operator−=(const complex &); // Operadores, operaciones binarias static const complex operator_add(const static const complex operator_subt(const static const complex operator_mult(const static const complex operator_div(const static const complex operator_pow(const // Funciones, operaciones unarias static const complex exp(const complex static const complex log(const complex static const complex sin(const complex static const complex cos(const complex static static static static }; #endif const const const const complex complex complex complex complex &, &, &, &, &, const const const const const &); &); &); &); complex real_as_complex(const complex imag_as_complex(const complex abs_as_complex(const complex phase_as_complex(const complex complex complex complex &); &); &); &); complex complex complex complex complex &); &); &); &); &); complex.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 Página 1 #include #define _USE_MATH_DEFINES // Constantes matemáticas al cargar #include #include "complex.h" using namespace std; complex::complex () : _x(0.0) , _y(0.0) {} complex::complex (const complex & c) : _x(c._x) , _y(c._y) {} complex::complex (double a, double b): _x(a) , _y(b) {} complex::~complex() {} ostream& operator<<(ostream &os, const complex &c){ os<<"("<>(istream &is, complex &c){ bool good=false; double r=0,i=0; char ch=0; if(is>>ch && ch=='('){ if(is>>r && is>>ch && ch==',' && is>>i && is>>ch && ch==')'){ good=true; } else{ good=false; } } else if(is.good()){ is.putback(ch); if(is>>r) good=true; else good=false; } if(good){ c._x=r; c._y=i; } else{ is.clear(ios::badbit); } return is; } complex& complex::operator=(const complex & b){ this−>_x = b._x; this−>_y = b._y; return *this; } double complex::getReal()const { return this−>_x; } double complex::getImag()const { return this−>_y; } void complex::setReal(double xx){ this−>_x = xx; } void complex::setImag(double yy){ this−>_y = yy; } double complex::getArg()const { return std::sqrt(square(this−>_x) + square(this−>_y)); complex.cpp 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 Página 2 } double complex::getPha()const { return std::atan2(this−>_y, this−>_x); } /*|////////////| Operadores, solo los utilizados, faltan varios |\\\\\\\\\\\\|*/ const complex complex::operator+(const double f)const { return complex ( this−>_x + f, this−>_y ); } void complex::operator+=(const complex &c) { this−>_x += c._x; this−>_y += c._y; } void complex::operator−=(const complex &c) { this−>_x −= c._x; this−>_y −= c._y; } /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|///////////////////| Operadores, operaciones binarias |\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ const complex complex::operator_add(const complex &w, const complex &z){ return complex ( w._x + z._x, w._y + z._y ); } const complex complex::operator_subt(const complex &w, const complex &z){ return complex ( w._x − z._x, w._y − z._y ); } // (x1+jy1)*(x2+jy2) = x1*x2 − y1*y2 + j( x1*y2 + y1*x2 ) const complex complex::operator_mult(const complex &w, const complex &z){ return complex ( w._x*z._x − w._y*z._y, w._x*z._y + w._y*z._x ); } // (x1+jy1)/(x2+jy2) = ( x1*x2 + y1*y2 + j( y1*x2 − x1*y2 ) ) / ( x1^2 + y2^2 ) const complex complex::operator_div(const complex &w, const complex &z){ double aux = square(z._x) + square(z._y); return complex ( (w._x * z._x + w._y * z._y) / aux, (w._y * z._x − w._x * z._y) / aux ); } //w^z = exp(z * log(w)) const complex complex::operator_pow(const complex &w, const complex &z) { return complex::exp( complex::operator_mult(z, complex::log(w)) ); } /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////| Funciones, operaciones unarias |\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ //exp(z) = exp(x+jy) = exp(x) * exp(jy) = exp(x) * (cos(y) + j sin(y)) const complex complex::exp(const complex &z) { return complex ( std::exp(z._x) * std::cos(z._y), std::exp(z._x) * std::sin(z._y) ); } //ln(z) = ln|z| + j Phase(z) const complex complex::log(const complex &z) { return complex ( std::log(z.getArg()), z.getPha() ); } // sin(z) = sin(x+jy) = sin(x) * cosh(y) + j cos(x) * sinh(y) const complex complex::sin(const complex &z) { return complex ( std::sin(z._x) * std::cosh(z._y), complex.cpp 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 Página 3 std::cos(z._x) * std::sinh(z._y) ); } // cos(z) = cos(x+jy) = cos(x) * cosh(y) − j sin(x) * sinh(y) const complex complex::cos(const complex &z) { return complex ( std::cos(z._x) * std::cosh(z._y), −std::sin(z._x) * std::sinh(z._y) ); } // Adaptaciones a devolución compleja de algunos métodos const complex complex::real_as_complex(const complex &z) { return complex(z.getReal(), 0); } const complex complex::imag_as_complex(const complex &z) { return complex(z.getImag(), 0); } const complex complex::abs_as_complex(const complex &z) { return complex(z.getArg(), 0); } const complex complex::phase_as_complex(const complex &z) { return complex(z.getPha(), 0); } PGMimage.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 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 Página 1 #ifndef PGMIMAGE_H #define PGMIMAGE_H #include #include using namespace std; // Limitación en la profundidad del color para ahorrar memoria usando uchar #define MIN_COLOR_DEPTH 1 #define MAX_COLOR_DEPTH 255 typedef unsigned char pixel_t; /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||| PGMimage |||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ class PGMimage { static const string _magic_number; // Número mágico PGM size_t _width; // Ancho del lienzo (imagen) size_t _height; // Alto del lienzo (imagen) pixel_t _color_depth; // Profundidad del color (niveles) pixel_t **_canvas; // Lienzo, matriz de imagen ///////////////////////// Utilidades internas ////////////////////////// // Ignorar comentarios estilo PGM en un stream static void _ignore_comments(istream &); // Pedir memoria para un lienzo de w x h static pixel_t** _new_canvas(size_t, size_t); // Limitar profundidad de color static void _validate_color_depth(pixel_t &); // Destruir el lienzo sobre el objeto actual static void _canvas_destroy(size_t, pixel_t **); public: // 1) Constructor (con sus argumentos por defecto) PGMimage(size_t w=1, size_t h=1, pixel_t d=MAX_COLOR_DEPTH); // 2) Constructor por copia PGMimage(const PGMimage &); // 3) Destructor ~ PGMimage() { _canvas_destroy(this−>_height, this−>_canvas); }; // 4) Indexación del lienzo (l−value y r−value: c[y][x]) pixel_t* operator[](size_t) const; // 5−7) size_t size_t pixel_t Obtención de ancho, alto, profundidad de color getWidth() const; getHeight() const; getColorDepth() const; // 8) Cambio de profundidad de color void setColorDepth(pixel_t); // 9) Cambio de tamaño de imagen void resize(size_t, size_t); // 10) Impresión en flujo/archivo/stdin friend ostream & operator<<(ostream &, const PGMimage &); // 11) Carga desde flujo/archivo/stdin friend istream & operator>>(istream &, PGMimage &); }; PGMimage.h 74 #endif // PGMIMAGE_H Página 2 PGMimage.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 Página 1 #include "PGMimage.h" // Definición del número mágico const string PGMimage::_magic_number("P2"); #define MAGIC_NUMBER_LENGTH 2 /*|/////////////////////////////////| 1) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////| Constructor |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ PGMimage::PGMimage(size_t w, size_t h, pixel_t d) { this−>_width = w; this−>_height = h; // Limitación en la profundidad de color PGMimage::_validate_color_depth(d); this−>_color_depth = d; // Memoria para el lienzo this−>_canvas = PGMimage::_new_canvas(this−>_width, this−>_height); // Inicialización en 0 for (size_t i = 0; i < h; i++) for (size_t j = 0; j < w; j++) this−>_canvas[i][j] = 0; } /*|/////////////////////////////////| 2) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////////| Constructor por copia |\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ PGMimage::PGMimage(const PGMimage &o) { this−>_width = o._width; this−>_height = o._height; this−>_color_depth = o._color_depth; // Memoria para la copia this−>_canvas = PGMimage::_new_canvas(this−>_width, this−>_height); // Copia de los datos for (size_t i = 0; i < this−>_height; i++) for (size_t j = 0; j < this−>_width; j++) this−>_canvas[i][j] = o._canvas[i][j]; } /*|/////////////////////////////////| 4) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////| Indexación del lienzo (l−value y r−value: c[y][x]) |\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ pixel_t* PGMimage::operator[](size_t y) const { if (y >= this−>_height) // Tope, seguridad en altura return this−>_canvas[this−>_height−1]; return this−>_canvas[y]; } /*|/////////////////////////////////| 5−7) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////| Obtención de ancho, alto, profundidad de color |\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ size_t PGMimage::getWidth() const { return this−>_width; } size_t PGMimage::getHeight() const { return this−>_height; } pixel_t PGMimage::getColorDepth() const { return this−>_color_depth; } PGMimage.cpp 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 Página 2 /*|/////////////////////////////////| 8) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////| Cambio de profundidad de color |\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void PGMimage::setColorDepth(pixel_t d) { PGMimage::_validate_color_depth(d); // Cálculo de factor de escala y actualización de la profundidad float scale = (float) d / (float) this−>_color_depth; this−>_color_depth = d; // Cálculo de los datos con la nueva profundidad for (size_t i = 0; i < this−>_height; i++) for (size_t j = 0; j < this−>_width; j++) this−>_canvas[i][j] *= scale; } /*|/////////////////////////////////| 9) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////////////////| Cambio de tamaño de imagen |\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void PGMimage::resize(size_t w, size_t h) { size_t w_max, h_max; pixel_t **auxcnv; // Memoria para el nuevo lienzo auxcnv = PGMimage::_new_canvas(w, h); // Copiado de los datos, con posible pérdida por recorte w_max = min(w, this−>_width); h_max = min(h, this−>_height); for (size_t i = 0; i < h_max; i++) for (size_t j = 0; j < w_max; j++) auxcnv[i][j] = this−>_canvas[i][j]; // Liberación de la memoria antigua PGMimage::_canvas_destroy(this−>_height, this−>_canvas); // Actualización de los valores this−>_width = w; this−>_height = h; this−>_canvas = auxcnv; } // NOTA: no se realiza un escalado de la imagen, solo se modifica el lienzo, // resultando en posibles recortes o agregado de pixels con eventual basura. /*|/////////////////////////////////| 10) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|///////////////////| Impresión en flujo/archivo/stdin |\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ ostream & operator<<(ostream &os, const PGMimage &c) { // Encabezado del archivo os << c._magic_number << endl; os << c._width << ' ' << c._height << endl; os << (size_t) c._color_depth << endl; // Datos de pixels for (size_t i = 0; i < c._height; i++) { os << (size_t) c._canvas[i][0]; for (size_t j = 1; j < c._width; j++) os << ' ' << (size_t) c._canvas[i][j]; os << endl; } return os; } PGMimage.cpp 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 Página 3 /*|/////////////////////////////////| 11) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|///////////////////| Carga desde flujo/archivo/stdin |\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ istream & operator>>(istream &is, PGMimage &c) { size_t w = 0, h = 0, aux = 0, i, j; pixel_t d = 0, **auxcnv; bool errors = true; char mn[MAGIC_NUMBER_LENGTH + 1]; double scale = 1; // Lectura del encabezado is.get(mn, MAGIC_NUMBER_LENGTH + 1); // Número mágico if ( mn == c._magic_number ) { PGMimage::_ignore_comments(is); // Ancho y alto if (is >> w && is >> h) { PGMimage::_ignore_comments(is); // Profundidad de color if (is >> aux && aux >= MIN_COLOR_DEPTH) { errors = false; // Recorte en profundidad, de ser necesario if (aux > MAX_COLOR_DEPTH) { cerr << "Warning: max color depth is " << MAX_COLOR_DEPTH << ", the image will be adapted." << endl; // Escala para adaptar la imagen scale = (double) MAX_COLOR_DEPTH / (double) aux; d = MAX_COLOR_DEPTH; } else d = aux; } } } // Lectura de los datos de pixel if (!errors) { // Memoria para el lienzo auxcnv = PGMimage::_new_canvas(w, h); // Carga de datos for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { PGMimage::_ignore_comments(is); if (is >> aux) auxcnv[i][j] = scale * aux; else { errors = true; break; } } if (errors) break; } // Si no ha fallado la carga de valores if (!errors) { // Actualización del objeto PGMimage::_canvas_destroy(c._height, c._canvas); c._canvas = auxcnv; c._width = w; c._height = h; c._color_depth = d; } // En caso de falla, se deja el objeto intacto y se destruye auxcnv PGMimage.cpp 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 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 Página 4 else PGMimage::_canvas_destroy(h, auxcnv); } if (errors) // Si hubo errores, se indica en el stream is.clear(ios::badbit); return is; } /*|/////////////////////////////////| *) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////| Utilidades internas |\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ // Ignorar comentarios estilo PGM en un stream void PGMimage::_ignore_comments(istream &s) { char ch; while (s >> ch) { if (ch == '#') { s.ignore(numeric_limits::max(), '\n'); } else { s.putback(ch); break; } } } // Pedir memoria para un lienzo de w x h pixel_t** PGMimage::_new_canvas(size_t w, size_t h) { pixel_t **cnv = new pixel_t* [h]; for (size_t i = 0; i < h; i++) cnv[i] = new pixel_t[w]; return cnv; } // Limitar profundidad de color void PGMimage::_validate_color_depth(pixel_t &d) { if (d > MAX_COLOR_DEPTH) d = MAX_COLOR_DEPTH; if (d < MIN_COLOR_DEPTH) d = MIN_COLOR_DEPTH; } // Destruir el lienzo sobre el objeto actual void PGMimage::_canvas_destroy(size_t h, pixel_t **c) { for (size_t i = 0; i < h; i++) delete [] c[i]; delete [] c; } node.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 Página 1 #ifndef NODE_H #define NODE_H // Clases que utilizarán a la clase nodo template class queue; template class stack; template class node { public: node(const T& v, node *nxt = NULL); private: T _value; node *_next; friend class stack; friend class queue; }; template node::node(const T& v, node *nxt) { _value = v; _next = nxt; } #endif /* NODE_H */ stack.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 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 Página 1 #ifndef STACK_H #define STACK_H #include #include "node.h" #include "stack.h" template class stack { public: stack() : _last(NULL) {}; ~stack(); bool isEmpty() const; void push(const T& ); T pop(); T& topElement(); private: node *_last; }; template stack::~stack() { while(_last) pop(); } template void stack::push(const T& v) { node *new_node; new_node = new node(v, _last); _last = new_node; //asigno el nuevo nodo a la pila } template T stack::pop() { node *auxNode; T v; if(!_last) return T(); //pila vacía auxNode = _last; //primer elemento de la pila _last = auxNode−>_next; //asignamos a la pila toda la pila sin el último nodo v = auxNode−>_value; //guardamos el valor del primero elemento de la pila delete auxNode; //borramos el nodo return v; } template bool stack::isEmpty() const { return _last == NULL; //estar vacía es tener _last en NULL } template T& stack::topElement() { return _last−>_value; stack.h 74 75 76 Página 2 } #endif /* STACK_H */ queue.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 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 Página 1 #ifndef QUEUE_H #define QUEUE_H #include #include "node.h" template class queue { public: queue() : _first(NULL), _last(NULL) {} ~queue(); void enqueue(const T&); T dequeue(); bool isEmpty() const; T& frontElement(); const T& lastAdded() const; private: node *_first, *_last; }; template queue::~queue() { while(_first) dequeue(); } template void queue::enqueue(const T& v){ node *newNode; newNode = new node(v); // creamos un nuevo auxNode // Si la cola no estaba vacía, añadimos el nuevo a continuación del último if(_last) _last−>_next = newNode; _last = newNode; // Ahora, el último elemento de la cola es el nuevo auxNode // Si la cola estaba vacía, ahora el primero también es el nuevo auxNode if(!_first) _first = newNode; } template T queue::dequeue(){ node *auxNode; T v; auxNode = _first; if(!auxNode) return T(); _first = auxNode−>_next; //asignamos al primero el segundo nodo v = auxNode−>_value; delete auxNode; //si la cola quedó vacía, ultimo debe ser NULL también if(!_first) _last = NULL; return v; } template bool queue::isEmpty() const{ queue.h 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 Página 2 return _first == NULL; //estar vacía es tener _first en NULL } template T& queue::frontElement(){ return _first−>_value; } template const T& queue::lastAdded() const{ return _last−>_value; } #endif /* QUEUE_H */ utils.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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 Página 1 #ifndef UTILS_H #define UTILS_H #include #include #include #include #include #include #include #include #include #include "cmdline.h" "stack.h" "queue.h" "complex.h" "parser.h" using namespace std; //////////////////////// Variables globales de main.cpp //////////////////////// extern option_t options_[]; // Opciones CLA extern istream *iss_; // Puntero a stream de entrada extern ostream *oss_; // Puntero a stream de salida extern fstream ifs_; // Archivo de entrada extern fstream ofs_; // Archivo de salida extern char *prog_name_; // Nombre del programa extern double map_w_; // Ancho de la región de mapeo extern double map_h_; // Alto de la región de mapeo extern complex map_c_; // Centro de la región de mapeo extern stack rpn_expr_; // Expresión convertida a RPN /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|||||||||||||||||||||||||||||||| Utilidades ||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ // 1) CLA: Archivo de entrada void opt_input(const string &); // 2) CLA: Archivo de salida void opt_output(const string &); // 3) CLA: Función a aplicar void opt_function(const string &); // 4) CLA: Región del plano complejo void opt_region(const string &); // 5) CLA: Ayuda void opt_help(const string &); // 6) Obtener complejo asociado a los índices void get_complex_from_index(complex &, size_t, size_t, size_t, size_t); // 7) Obtener la fila asociada al complejo ( [i][ ] ) void get_row_from_complex(size_t &, const complex &, size_t); // 8) Obtener la columna asociada al complejo ( [ ][j] ) void get_col_from_complex(size_t &, const complex &, size_t); #endif /* UTILS_H */ utils.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 Página 1 #include "utils.h" /*|/////////////////////////////////| 1) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|///////////////////////| CLA: Archivo de entrada |\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void opt_input(const string &arg) { // Por defecto stdin, o bien archivo if (arg == "−") { iss_ = &cin; } else { ifs_.open(arg.c_str(), ios::in); iss_ = &ifs_; } // Comprobación de errores if ( !iss_−>good() ) { cerr << "Cannot open " << arg << "." << endl; exit(1); } } /*|/////////////////////////////////| 2) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////////| CLA: Archivo de salida |\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void opt_output(const string &arg) { // Por defecto stdout, o bien archivo if (arg == "−") { oss_ = &cout; } else { ofs_.open(arg.c_str(), ios::out); oss_ = &ofs_; } // Comprobación de errores if ( !oss_−>good() ) { cerr << "Cannot open " << arg << "." << endl; exit(1); } } /*|/////////////////////////////////| 3) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////////| CLA: Función a aplicar |\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void opt_function(const string &arg) { queue tokenized_expr; parse_expression_in_tokens(arg, tokenized_expr); convert_to_RPN(rpn_expr_, tokenized_expr); } utils.cpp 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 Página 2 /*|/////////////////////////////////| 4) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////| CLA: Región del plano complejo |\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void opt_region(const string &arg) { double aux; stringstream arg_stream(arg); bool errors = true; // Lectura de los parámetros, ignorando el separador (',' o cualquier char) if (arg_stream >> map_w_) { arg_stream.ignore(); if (arg_stream >> map_h_) { arg_stream.ignore(); if (arg_stream >> aux) { map_c_.setReal(aux); arg_stream.ignore(); if (arg_stream >> aux) { map_c_.setImag(aux); // Si se llegó hasta aquí, se pudieron leer los // 4 parámetros, si hay algo más se ignora errors = false; } } } } // Error de lectura, región inválida if (errors) { cerr << "Invalid region description: " << arg << "." << endl; exit(1); } // Error por ancho o alto no "positivos distintos de cero" if (map_w_ <= 0 || map_h_ <=0) { cerr << map_w_ << "," << map_h_ << ": must be positive nonzero numbers." << endl; exit(1); } } /*|/////////////////////////////////| 5) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////////////////////////| CLA: Ayuda |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void opt_help(const string &arg) { cout << "Usage: " << prog_name_ << " [−i file] [−o file] [−r w,h,x0,y0] [−f expression(z)]" << endl; exit(0); } utils.cpp 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 Página 3 /*|/////////////////////////////////| 6) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|///////////////| Obtener complejo asociado a los índices |\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void get_complex_from_index(complex &z, size_t i, size_t j, size_t h, size_t w) { if ( h && w && i < h && j < w) { z.setReal( map_w_ * ( (j + 0.5)/w − 0.5 ) ); z.setImag( map_h_ * ( 0.5 − (i + 0.5)/h ) ); z += map_c_; } } /*|/////////////////////////////////| 7) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|///////////| Obtener la fila asociada al complejo ( [i][ ] ) |\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void get_row_from_complex(size_t &row, const complex &z, size_t h) { row = h * ( 0.5 − (z.getImag()−map_c_.getImag())/map_h_ ); } /*|/////////////////////////////////| 8) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////| Obtener la columna asociada al complejo ( [ ][j] ) \\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void get_col_from_complex(size_t &col, const complex &z, size_t w) { col = w * ( 0.5 + (z.getReal()−map_c_.getReal()) / map_w_ ); } parser.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 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 Página 1 #ifndef PARSER_H #define PARSER_H #include #include #include #include #define _USE_MATH_DEFINES // Constantes matemáticas al cargar #include #include #include "queue.h" #include "stack.h" #include "complex.h" using namespace std; #define NOT_FOUND −1 // Macros de función para cómoda detección de casos #define is_number_start(s) ( isdigit((s)[0]) || (s) == "." ) #define is_parenthesis(s) ( (s) == "(" || (s) == ")" ) #define is_operator(s) ( find_in_list(operator_tokens_, s) != NOT_FOUND ) #define is_special(s) ( find_in_list(special_tokens_, s) != NOT_FOUND ) #define is_function(s) ( find_in_list(function_tokens_, s) != NOT_FOUND ) // Chequeo de +/− como operador unario: si es el primero o viene luego de '(' #define check_for_unary_op(q) ((q).isEmpty() || \ (q).lastAdded().isOpenParenthesis()) // Punteros a función para las operaciones typedef const complex (*operator_t)(const complex &, const complex &); typedef const complex (*function_t)(const complex &); /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||| Token ||||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ #define TOKEN_IS_VALUE "0v0" class token { double _v; // Valor, vale NaN si no es del tipo 'valor' string _s; // Cadena del token, vale TOKEN_IS_VALUE si es del tipo 'valor' public: // 1) Constructores token(const double &v = 0); // De un token del tipo 'valor', 0 por defecto token(const string &); // De un token que no es del tipo 'valor' token(const token &); // Por copia // 2) Obtener como string (devuelve número en string si es del tipo 'valor') string getAsString() const; // 3) Obtener como double (devuelve NAN, si no es del tipo 'valor') double getAsDouble() const; // 4) Booleanos is... bool isValue() const; bool isParenthesis() const; bool isOpenParenthesis() const; bool isClosedParenthesis() const; bool isOperator() const; bool isSpecial() const; bool isFunction() const; // // // // // // // ¿Es ¿Es ¿Es ¿Es ¿Es ¿Es ¿Es del tipo 'valor'? un paréntesis? un paréntesis abierto? un paréntesis cerrado? un operador? especial? una función? // 5) Precedencia, si es que el token es un operador o función int precedence() const; // 6) Impresión en flujo/archivo/stdin parser.h 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 Página 2 friend ostream & operator<<(ostream &, const token &); }; /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*||||||| Variables especiales para parseo y evaluación de la expresión ||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////| Funciones a interpretar, operaciones unarias |\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ // Cadenas asociadas, el orden importa const string function_tokens_[] = { "exp", "ln", "sin", "cos", "re", "im", "abs", "phase", // No olvidar centinela de cadena vacía "" }; // Punteros a funciones asociados, el orden importa const function_t function_pointers_[] = { complex::exp, complex::log, complex::sin, complex::cos, complex::real_as_complex, complex::imag_as_complex, complex::abs_as_complex, complex::phase_as_complex }; /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////| Operadores a interpretar, operaciones binarias |\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ // Cadenas asociadas, el orden importa const string operator_tokens_[] = { "+", "−", "*", "/", "^", // No olvidar centinela de cadena vacía "" }; // Punteros a funciones asociados, el orden importa const operator_t operator_pointers_[] = { complex::operator_add, complex::operator_subt, complex::operator_mult, complex::operator_div, complex::operator_pow }; /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////| Tokens especiales a interpretar |\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ parser.h 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 Página 3 #define PIXEL_TOKEN "z" // Token simbólico que representa el pixel a transformar // Cadenas asociadas, el orden importa, PIXEL_TOKEN debe ir último const string special_tokens_[] = { "j", "e", "pi", PIXEL_TOKEN, // No olvidar centinela de cadena vacía "" }; // Complejos asociados a tokens especiales (excepto z), el orden importa const complex special_complex_[] = { complex(0, 1), // j complex(M_E, 0), // e complex(M_PI, 0) // pi }; /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|||||||||||||||||||||||||||||||| Utilidades ||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ // 1) Función para buscar en una lista con centinela de cadena vacía int find_in_list(const string [], const string &); // 2) Función para parsear la expresión de entrada partiéndola en tokens void parse_expression_in_tokens(const string &, queue &); // 3) Conversión a notación polaca inversa void convert_to_RPN(stack &, queue &); void error_handler_unexpected_token(const token &); void error_handler_mismatched_parentheses(); #endif /* PARSER_H */ parser.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 Página 1 #include "parser.h" /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||| Token ||||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|/////////////////////////////////| 1) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////| Constructores |\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ // De un token del tipo 'valor', por defecto (tipo 'valor' con valor 0) token::token(const double &v) { this−>_v = v; this−>_s = TOKEN_IS_VALUE; } // De un token que no es del tipo 'valor' token::token(const string &s) { this−>_v = NAN; this−>_s = s; } // Por copia token::token(const token &t) { this−>_v = t._v; this−>_s = t._s; } /*|/////////////////////////////////| 2) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////////////////////| Obtener como string |\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ string token::getAsString() const { if (this−>isValue()) { ostringstream aux; aux << this−>_v; return aux.str(); } return this−>_s; } // NOTA: si bien es capaz de devolver el valor en una string, no utilizar // innecesariamente. /*|/////////////////////////////////| 3) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////////////////////| Obtener como double |\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ double token::getAsDouble() const { return this−>_v; } /*|/////////////////////////////////| 4) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////////////| Booleanos is... |\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ // ¿Es del tipo 'valor'? bool token::isValue() const { return this−>_s == TOKEN_IS_VALUE; } parser.cpp 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 Página 2 // ¿Es un paréntesis? bool token::isParenthesis() const { if (this−>isValue()) return false; return is_parenthesis(this−>_s); } // ¿Es un paréntesis abierto? bool token::isOpenParenthesis() const { if (this−>isValue()) return false; return this−>_s == "("; } // ¿Es un paréntesis cerrado? bool token::isClosedParenthesis() const { if (this−>isValue()) return false; return this−>_s == ")"; } // ¿Es un operador? bool token::isOperator() const { if (this−>isValue()) return false; return is_operator(this−>_s); } // ¿Es especial? bool token::isSpecial() const { if (this−>isValue()) return false; return is_special(this−>_s); } // ¿Es una función? bool token::isFunction() const { if (this−>isValue()) return false; return is_function(this−>_s); } /*|/////////////////////////////////| 5) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|///////| Precedencia, si es que el token es un operador o función |\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ int token::precedence() const { if (this−>isOperator()) { if (this−>_s == "+" || this−>_s == "−") return 0; if (this−>_s == "*" || this−>_s == "/") return 1; if (this−>_s == "^") return 3; } if (this−>isFunction()) return 2; return NOT_FOUND; // Si la precedencia no es aplicable, devuelve NOT_FOUND } /*|/////////////////////////////////| 6) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|///////////////////| Impresión en flujo/archivo/stdin |\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ ostream & operator<<(ostream &os, const token &t) { if (t.isValue()) os << t._v; else os << t._s; return os; parser.cpp 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 Página 3 } /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|||||||||||||||||||||||||||||||| Utilidades ||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|/////////////////////////////////| 1) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////| Función para buscar en una lista con centinela de cadena vacía |\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ int find_in_list(const string l[], const string &s) { for (size_t i = 0; !l[i].empty(); i++) if (l[i] == s) return i; // Si lo encuentra devuelve su posición return NOT_FOUND; // Si no lo encuentra se devuelve NOT_FOUND } /*|/////////////////////////////////| 2) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//| Función para parsear la expresión de entrada partiéndola en tokens |\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void parse_expression_in_tokens(const string &input, queue &output) { stringstream expr(input); string aux_s; double aux_n; while (expr) { // Se intenta cargar un carácter en aux_s aux_s = expr.peek(); // Si es un espacio, se ignora y se vuelve a empezar if ( isblank(aux_s[0]) ) { expr.ignore(); continue; } // Si es el comienzo de un número, se intenta leerlo if ( is_number_start(aux_s) ) { // Si no se logra, se sale con un error if ( !(expr >> aux_n) ) { cerr << "Error: wrong input number in the expression." << endl; exit(1); } // Si se logra, se agrega a la cola de salida output.enqueue(token(aux_n)); } // Si no, puede tratarse de un operador o un paréntesis else if ( is_operator(aux_s) || is_parenthesis(aux_s) ) { // Ya es algo válido, se elimina del stream expr.ignore(); // Caso especial, "−" como operador unario, se agrega un 0 antes if ( aux_s == "−" && check_for_unary_op(output) ) output.enqueue(token(0)); // Caso especial, "+" como operador unario, se ignora if ( aux_s == "+" && check_for_unary_op(output) ) parser.cpp 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 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 Página 4 continue; output.enqueue(token(aux_s)); } // O si no, queda el grupo alfabético de output: funciones o especiales else { // Se levantan todos los caracteres alfabéticos a la cadena auxiliar expr.ignore(); // El primero ya está en la cadena, se ignora while ( isalpha(expr.peek()) ) aux_s += expr.get(); // Si coincide con alguno de estos, se encola if ( is_function(aux_s) || is_special(aux_s) ) { output.enqueue(token(aux_s)); } // Si no es así, y tampoco se terminó la entrada, hay un error else if (expr) { cerr << "Error: malformed expression near of: " << aux_s << "." << endl; exit(1); } } } } /*|/////////////////////////////////| 3) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////| Conversión a notación polaca inversa |\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ void convert_to_RPN(stack &result, queue &tokens){ token tok; stack aux; // Pila auxiliar para la conversión bool expect_operator_flag = false; bool expect_number_flag = false; bool expect_function_flag = true; while (!tokens.isEmpty()) { tok = tokens.dequeue(); //Si el token es un operador, o1, entonces: if (tok.isOperator()){ if (!expect_operator_flag) error_handler_unexpected_token(tok); /* mientras que haya un operador, o2, en el tope de la pila (esto excluye el paréntesis abierto), y * o1 es asociativo izquierdo y su precedencia es menor que (una precedencia más baja) o igual a la de o2, ó * o1 es asociativo derecho y su precedencia es menor que (una precedencia más baja) que la de o2, retire (pop) de la pila el o2, y póngalo en la cola de salida. */ while ( !aux.isEmpty() && ( aux.topElement().isOperator() || aux.topElement().isFunction() ) && aux.topElement().precedence() >= tok.precedence() ) { result.push(aux.topElement()); aux.pop(); } parser.cpp 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 Página 5 //ponga (push) o1 en el tope de la pila. aux.push(tok); expect_operator_flag = false; expect_function_flag = true; expect_number_flag = true; } else if (tok.isFunction()){ if (!expect_function_flag) error_handler_unexpected_token(tok); while ( !aux.isEmpty() && aux.topElement().isOperator() && aux.topElement().precedence() >= tok.precedence() ) { result.push(aux.topElement()); aux.pop(); } //ponga (push) o1 en el tope de la pila. aux.push(tok); expect_operator_flag = false; expect_function_flag = false; expect_number_flag = false; //Si el token es un paréntesis abierto, entonces póngalo en la pila. } else if (tok.isOpenParenthesis()) { //si esperaba un operador if (expect_operator_flag) error_handler_unexpected_token(tok); aux.push(tok); expect_number_flag = false; //Si el token es un paréntesis derecho } else if (tok.isClosedParenthesis()) { //esto debe aparecer después de un numero/función, no de un operador if (!expect_operator_flag) error_handler_unexpected_token(tok); /*Hasta que el token en el tope de la pila sea un paréntesis abierto, retire (pop) a los operadores de la pila y colóquelos en la cola de salida.*/ while ( !aux.isEmpty() && !aux.topElement().isOpenParenthesis() ) { result.push(aux.topElement()); aux.pop(); } //Si la pila se termina sin encontrar un paréntesis abierto, //entonces hay paréntesis sin pareja. if (aux.isEmpty()) error_handler_mismatched_parentheses(); //Retire (pop) el paréntesis abierto de la pila, //pero no lo ponga en la cola de salida. aux.pop(); /* Ahora esperamos un operador */ expect_operator_flag = true; expect_function_flag = true; expect_number_flag = false; //encuentre un numero } else if (tok.isValue() || tok.isSpecial()) { /* If we're expecting an operator, we're very disappointed. */ if (expect_operator_flag && !expect_number_flag) parser.cpp 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 Página 6 error_handler_unexpected_token(tok); //Si el token es un número, se agrega a la cola de salida result.push(tok); expect_operator_flag = true; expect_function_flag = false; expect_number_flag = false; } } //ya se parsearon todos los tokens. Esperamos un operador //ya que lo ultimo fue un valor if (!expect_operator_flag) error_handler_unexpected_token(tok); /* Cuando no hay más tokens para leer: Mientras todavía haya tokens de operadores en la pila: Si el token del operador en el tope de la pila es un paréntesis, entonces hay paréntesis sin la pareja correspondiente. retire (pop) al operador y póngalo en la cola de salida. */ while (!aux.isEmpty()) { if (aux.topElement().isOpenParenthesis()) error_handler_mismatched_parentheses(); result.push(aux.topElement()); aux.pop(); } } // Extra: manejador de error en caso de token inesperado void error_handler_unexpected_token(const token &t) { cerr << "Error: invalid syntax in the expression, near token: " << t << "." << endl; exit(1); } // Extra: manejador de error en caso de paréntesis desbalanceado void error_handler_mismatched_parentheses() { cerr << "Error: mismatched parentheses in the expression." << endl; exit(1); } optree.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 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 Página 1 #ifndef OPTREE_H #define OPTREE_H #include #include #define _USE_MATH_DEFINES // Constantes matemáticas al cargar #include #include "complex.h" #include "stack.h" #include "parser.h" using namespace std; // Tipo de nodo en el árbol de operaciones typedef enum { NODE_UNARY_OP, NODE_BINARY_OP, NODE_STATIC_COMPLEX, NODE_DYNAMIC_COMPLEX, NODE_PIXEL_COMPLEX, NODE_UNDEFINED } node_type; /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|||||||||||||||||||||||||||||||| OptreeNode ||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ class optree_node { node_type complex const operator_t function_t optree_node optree_node optree_node _t; *_c; _bin_op; _un_op; *_left; *_right; *_up; // // // // // // // Tipo de nodo Puntero al complejo para evaluar Puntero a la operación binaria Puntero a la operación unaria Subárbol izquierdo (o hijo en operaciones unarias) Subárbol derecho Padre ///////////////////////// Utilidades internas ////////////////////////// // Simplificar el sub−árbol eliminando las expresiones independientes de z // NOTA: devuelve true si el subárbol depende de z bool simplify(); public: // 1) Constructor por defecto optree_node(); // 2) Constructor a partir de token optree_node(const token &, optree_node *); // 3) Destructor ~optree_node(); // 4) Operar, para realizar la operación const complex operate(const complex *) const; friend class optree; private: // TODO: constructor por copia optree_node(const optree_node &); }; /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|||||||||||||||||||||||||||||||||| Optree ||||||||||||||||||||||||||||||||||*/ optree.h 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 Página 2 /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ class optree { optree_node *_root; // Raíz del árbol complex *_asoc_pixel; // Puntero al complejo asociado al pixel public: // 1) Constructor por defecto optree() { _root = NULL; _asoc_pixel = NULL; } // 2) Constructor desde pila de tokens con RPN + complejo de pixel optree(stack &, complex &); // 3) Destructor ~optree() { delete this−>_root; } // 4) Operar, para realizar la operación const complex operate() const; private: // TODO: constructor por copia optree(const optree &); }; #endif // OPTREE_H optree.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 Página 1 #include "optree.h" /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|||||||||||||||||||||||||||||||| OptreeNode ||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|/////////////////////////////////| 1) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|////////////////////////| Constructor por defecto |\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ optree_node::optree_node() { this−>_t = NODE_UNDEFINED; this−>_c = NULL; this−>_un_op = NULL; this−>_bin_op = NULL; this−>_left = NULL; this−>_right = NULL; this−>_up = NULL; } /*|/////////////////////////////////| 2) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////| Constructor a partir de token |\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ optree_node::optree_node(const token &tok, optree_node *father = NULL) { /* Los tipos de token son: * value: tienen un double y aquí pasan a la parte real de un complejo dinámico. Tipo: NODE_DYNAMIC_COMPLEX. * parenthesis: ya no hay de este tipo luego de pasar a RPN, se imprimirá un error. * operator: serán asociados a operaciones binarias. Tipo: NODE_BINARY_OP. * function: serán asociados a operaciones unarias. Tipo: NODE_UNARY_OP. * special: − z: será asociado al complejo de pixel. Tipo: NODE_PIXEL_COMPLEX. − j, e, pi: serán asociados a complejos miembros estáticos del array special_complex_. Tipo: NODE_STATIC_COMPLEX. */ if (tok.isParenthesis()) { cerr << "Internal Error: the token can't be a parenthesis, " << "RPN convert is required before to make the optree." << endl; exit(2); } // Operandos if (tok.isSpecial() || tok.isValue()) { this−>_un_op = NULL; this−>_bin_op = NULL; // Special Token if (tok.isSpecial()) { // Si es PIXEL_TOKEN (es decir, z) if (tok.getAsString() == PIXEL_TOKEN) { this−>_t = NODE_PIXEL_COMPLEX; optree.cpp 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 Página 2 this−>_c = NULL; } else // Si no es z, se trata de un complejo estático { this−>_t = NODE_STATIC_COMPLEX; this−>_c = &special_complex_[ find_in_list(special_tokens_, tok.getAsString()) ]; } } // Value Token else { this−>_t = NODE_DYNAMIC_COMPLEX; this−>_c = new complex(tok.getAsDouble(), 0); } } // Operaciones if (tok.isOperator() || tok.isFunction()) { this−>_c = NULL; // Operator Token −> Operación binaria if (tok.isOperator()) { this−>_t = NODE_BINARY_OP; this−>_un_op = NULL; this−>_bin_op = operator_pointers_[ find_in_list(operator_tokens_, tok.getAsString()) ]; } // Function Token −> Operación unaria else { this−>_t = NODE_UNARY_OP; this−>_bin_op = NULL; this−>_un_op = function_pointers_[ find_in_list(function_tokens_, tok.getAsString()) ]; } } this−>_left = NULL; this−>_right = NULL; this−>_up = father; } /*|/////////////////////////////////| 3) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////////////////////////| Destructor |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ optree_node::~optree_node() { if (this−>_t == NODE_DYNAMIC_COMPLEX) delete this−>_c; if (this−>_left != NULL) delete this−>_left; if (this−>_right != NULL) delete this−>_right; } /*|/////////////////////////////////| 4) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////////////| Operar, para realizar la operación |\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ const complex optree_node::operate(const complex *z) const { // z es un puntero que apunta al complejo asociado al pixel para operar // Caso base y de corte, operandos. if ( this−>_t == NODE_STATIC_COMPLEX || this−>_t == NODE_DYNAMIC_COMPLEX ) return *(this−>_c); optree.cpp 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 Página 3 if ( this−>_t == NODE_PIXEL_COMPLEX ) return *z; // Operación binaria (operadores) if ( this−>_t == NODE_BINARY_OP ) return this−>_bin_op(this−>_left−>operate(z), this−>_right−>operate(z)); // Operación unaria (funciones) if (this−>_t == NODE_UNARY_OP ) return this−>_un_op(this−>_left−>operate(z)); // Si se llega hasta aquí, el nodo estaba sin definir, error cerr << "Internal Error: there are some node, not setted in the optree." << endl; exit(2); } /*|/////////////////////////////////| *) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////| Utilidades internas |\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ // Simplificar el sub−árbol eliminando las expresiones independientes de z // NOTA: devuelve true si el subárbol depende de z bool optree_node::simplify() { bool pixel_dependent; // Caso base: hoja, entonces depende de él, si es z u otra cosa if (this−>_left == NULL && this−>_right == NULL) return this−>_t == NODE_PIXEL_COMPLEX; // Si tiene único hijo (está a la izquierda, op unaria), depende de éste if (this−>_right == NULL) pixel_dependent = this−>_left−>simplify(); /* Si tiene ambos hijos (op binaria), con que uno dependa de z, suficiente. Pero hay que visitar ambos hijos con simplify(). El operador || no evalúa si ya encontró true a izquierda, por eso se utilizan dos líneas, ubicando en la segunda, el llamado a simplify() a la izquierda. */ else { pixel_dependent = this−>_left−>simplify(); pixel_dependent = this−>_right−>simplify() || pixel_dependent; } // Si no es pixel dependiente, como no es hoja (caso base), se simplifica if (!pixel_dependent) { /* El resultado no depende de z, por eso no hay problema con pasar NULL a operate(). Además, como el nodo actual no es hoja, es una operación, por lo tanto _c está libre (en NULL). */ this−>_c = new complex(this−>operate(NULL)); // Se cambia el tipo del nodo subárbol, ahora convertido en hoja this−>_t = NODE_DYNAMIC_COMPLEX; this−>_un_op = NULL; this−>_bin_op = NULL; // Se destruye el hijo izquierdo (tiene que existir) delete this−>_left; this−>_left = NULL; // Si tiene, se destruye el hijo derecho if (this−>_right != NULL) { delete this−>_right; this−>_right = NULL; } optree.cpp 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 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 Página 4 #ifdef DEBUG cerr << " #endif } Construyendo árbol: simplificación realizada.\n"; return pixel_dependent; } /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*|||||||||||||||||||||||||||||||||| Optree ||||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ #define is_operation(t) ((t) == NODE_UNARY_OP || (t) == NODE_BINARY_OP) /*|/////////////////////////////////| 2) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|/////| Constructor desde pila de tokens con RPN + complejo de pixel |\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ optree::optree(stack &rpn, complex &z) { optree_node *current; // Primer token a la raíz this−>_root = new optree_node(rpn.pop()); // current siempre será una operación, por la construcción del algoritmo, // si no lo fuera, la pila ya está vacía. current = this−>_root; while (!rpn.isEmpty()) { // Si actual es unario if (current−>_t == NODE_UNARY_OP) { // Único hijo libre, se usa _left if (current−>_left == NULL) { // Token al hijo current−>_left = new optree_node(rpn.pop(), current); // Si el token era una operación, bajar if (is_operation(current−>_left−>_t)) current = current−>_left; } // Hijo ocupado, subir else current = current−>_up; } // Si actual es binario else { // Derecha libre if (current−>_right == NULL) { // Token a la derecha current−>_right = new optree_node(rpn.pop(), current); // Si el token era una operación, bajar por derecha if (is_operation(current−>_right−>_t)) current = current−>_right; } // Derecha ocupada else { // Izquierda libre if (current−>_left == NULL) { // Token a la izquierda current−>_left = new optree_node(rpn.pop(), current); // Si el token era una operación, bajar por izquierda if (is_operation(current−>_left−>_t)) current = current−>_left; optree.cpp 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 Página 5 } // Si ambas ramas están ocupadas, subir else current = current−>_up; } } } // Asociación del complejo para iterar los pixel this−>_asoc_pixel = &z; // Simplificación del árbol, eliminando expresiones 'estáticas' this−>_root−>simplify(); } /*|/////////////////////////////////| 4) |\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ /*|//////////////////| Operar, para realizar la operación |\\\\\\\\\\\\\\\\\\|*/ /*|/////////////////////////////////////|\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\|*/ const complex optree::operate() const { // Validaciónes if ( this−>_asoc_pixel == NULL || this−>_root == NULL ) return complex(); return _root−>operate(this−>_asoc_pixel); } 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 64 65 66 67 68 69 70 71 72 73 Página 1 #include #include #include #include #include #include #include #include #include #include #include #include "PGMimage.h" "complex.h" "utils.h" "cmdline.h" "node.h" "queue.h" "stack.h" "parser.h" "optree.h" using namespace std; ////////////////////////////// Variables globales ////////////////////////////// option_t options_[] = // Opciones CLA { {true, "i", "input", "−", opt_input, OPT_DEFAULT}, {true, "o", "output", "−", opt_output, OPT_DEFAULT}, {true, "f", "function", "z", opt_function, OPT_DEFAULT}, {true, "r", "region", "2,2,0,0", opt_region, OPT_DEFAULT}, {false, "h", "help", NULL, opt_help, OPT_DEFAULT}, {0, }, }; istream *iss_ = NULL; // Puntero a stream de entrada ostream *oss_ = NULL; // Puntero a stream de salida fstream ifs_; // Archivo de entrada fstream ofs_; // Archivo de salida char *prog_name_; // Nombre del programa double map_w_; // Ancho de la región de mapeo double map_h_; // Alto de la región de mapeo complex map_c_; // Centro de la región de mapeo stack rpn_expr_; // Expresión convertida a RPN // Macro de función para imprimir mensajes de debugging #ifdef DEBUG #define DEBUG_MSG(m) (cerr << m << "\n") #else #define DEBUG_MSG(m) #endif /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||| Main |||||||||||||||||||||||||||||||||||*/ /*||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||*/ int main(int argc, char** argv) { prog_name_ = argv[0]; // Validación de argumentos cmdline cmdl(options_); cmdl.parse(argc, argv); DEBUG_MSG("Argumentos validados, apertura de archivos, conversión a RPN."); // Lectura del archivo de entrada PGMimage in_image; if ( !(*iss_ >> in_image) ) { cerr << "Invalid PGM formated input." << endl; exit(1); } // Si nada ha fallado, se puede cerrar el archivo if (ifs_) ifs_.close(); DEBUG_MSG("Archivo de entrada cargado."); // Creación de una nueva imagen con las mismas dimensiones size_t h = in_image.getHeight(); size_t w = in_image.getWidth(); main.cpp 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 Página 2 PGMimage out_image(w, h, in_image.getColorDepth()); // Variables para recorrer la imagen complex in_plane, out_plane; size_t i, j, row, col; DEBUG_MSG("Imagen de salida y variables auxiliares creadas."); // Árbol de la operación optree operation(rpn_expr_, out_plane); DEBUG_MSG("Árbol de la operación generado."); // Recorrido de la imagen y transformación for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { // Pixel en la imagen de salida <−> Punto en el plano de salida get_complex_from_index(out_plane, i, j, h, w); // Aplicación de la operación in_plane = operation.operate(); // Punto en el plano de entrada <−> Pixel en la imagen de entrada get_row_from_complex(row, in_plane, h); get_col_from_complex(col, in_plane, w); // Si no se cayó fuera de la imagen, se copia if (row < h && col < w) { out_image[i][j] = in_image[row][col]; } } } DEBUG_MSG("Imagen de salida escrita."); // Volcado en el archivo de salida *oss_ << out_image; if (ofs_) ofs_.close(); DEBUG_MSG("Archivo de salida guardado y cerrado."); return 0; } 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 Página 1 # //////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ # # |||||||||||||||||||||||||||||| Configuraciones ||||||||||||||||||||||||||||| # # \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\////////////////////////////////////// # # Compilador: CC = g++ # Flags para linkeo: LFLAGS = −pedantic −Wall # Flags para compilación: CFLAGS = −ansi −pedantic−errors −Wall −O3 # Flags para debugging: DFLAGS = −g −DDEBUG # Centinela de debugging: DEBUG_CENTINEL = .last_debug DEBUG_CENTINEL_CONTENT = "This file indicates that the last build was made with\ the \'debug\' option." # Nombre de salida del proyecto: OUT = tp1 # Directorio de archivos fuente: SRC_DIR = src # Directorio de archivos binarios: BIN_DIR = bin # Directorio de instalación: INSTALL_DIR = /usr/bin # //////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ # # ||||||||||||||||||||||||| Objetivos y dependencias ||||||||||||||||||||||||| # # \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\////////////////////////////////////// # # |−−−−−−−−−−−−−−−−−−−−−−−−−−−−| Códigos objeto |−−−−−−−−−−−−−−−−−−−−−−−−−−−−| # OBJECTS = $(addprefix $(BIN_DIR)/, \ PGMimage.o \ complex.o \ utils.o \ cmdline.o \ parser.o \ optree.o \ main.o \ ) FULL_OUT = $(BIN_DIR)/$(OUT) # |−−−−−−−−−−−−−−−−−−−−−−−−| Reglas de construcción |−−−−−−−−−−−−−−−−−−−−−−−−| # # Objetivo de fantasía por defecto, para manejar la opción debug .PHONY: $(OUT) ifeq (,$(wildcard $(BIN_DIR)/$(DEBUG_CENTINEL))) # Si no existe el centinela de debug, se procede normalmente $(OUT): $(FULL_OUT) else # Si existe, es necesario limpiar (con lo que también se eliminará el mismo) $(OUT): clean $(FULL_OUT) endif # Construcción del ejecutable de salida $(FULL_OUT): $(OBJECTS) | $(BIN_DIR) $(CC) $(LFLAGS) $(OBJECTS) −o $(FULL_OUT) # Construcción de los archivos objeto $(BIN_DIR)/%.o: $(SRC_DIR)/%.cpp $(CC) −c $(CFLAGS) $< −o $@ # Creación del directorio de binarios $(BIN_DIR): mkdir $(BIN_DIR) # |−−−−−−−−−−−−−−−−−−−−−−−−−−−−−| Dependencias |−−−−−−−−−−−−−−−−−−−−−−−−−−−−−| # Makefile 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 Página 2 $(BIN_DIR)/PGMimage.o: $(addprefix $(SRC_DIR)/, \ PGMimage.cpp \ PGMimage.h \ ) | $(BIN_DIR) $(BIN_DIR)/complex.o: $(addprefix $(SRC_DIR)/, \ complex.cpp \ complex.h \ ) | $(BIN_DIR) $(BIN_DIR)/utils.o: $(addprefix $(SRC_DIR)/, \ utils.cpp \ utils.h \ complex.h \ cmdline.h \ node.h \ stack.h \ queue.h \ parser.h \ ) | $(BIN_DIR) $(BIN_DIR)/cmdline.o: $(addprefix $(SRC_DIR)/, \ cmdline.cpp \ cmdline.h \ ) | $(BIN_DIR) $(BIN_DIR)/parser.o: $(addprefix $(SRC_DIR)/, \ parser.cpp \ parser.h \ node.h \ queue.h \ stack.h \ complex.h \ ) | $(BIN_DIR) $(BIN_DIR)/optree.o: $(addprefix $(SRC_DIR)/, \ optree.cpp \ optree.h \ complex.h \ node.h \ stack.h \ parser.h \ ) | $(BIN_DIR) $(BIN_DIR)/main.o: main.cpp PGMimage.h complex.h utils.h cmdline.h node.h queue.h stack.h parser.h optree.h ) | $(BIN_DIR) $(addprefix $(SRC_DIR)/, \ \ \ \ \ \ \ \ \ \ \ # //////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ # # ||||||||||||||||||||||||||||| Utilidades extras |||||||||||||||||||||||||||| # # \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\////////////////////////////////////// # # |−−−−−−−−−−−−−−−−−−| Debug (compilar con flags de debug) |−−−−−−−−−−−−−−−−−| # .PHONY: debug debug: CFLAGS += $(DFLAGS) debug: LFLAGS += $(DFLAGS) ifeq (,$(wildcard $(BIN_DIR)/$(DEBUG_CENTINEL))) # Si no existe el centinela de debug, hay que limpiar y crearlo debug: clean $(FULL_OUT) @ echo "$(DEBUG_CENTINEL_CONTENT)" > $(BIN_DIR)/$(DEBUG_CENTINEL) Makefile 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 Página 3 else # Si existe, solo actualizar si es necesario debug: $(FULL_OUT) endif # |−−−−−−−−−−−−−−−−−−−−−−−−−−−−| Limpiar (todo) |−−−−−−−−−−−−−−−−−−−−−−−−−−−−| # .PHONY: clean clean: rm −rf $(BIN_DIR) # |−−−−−−−−−−−−−−−−−−−−−−−−| Limpiar códigos objeto |−−−−−−−−−−−−−−−−−−−−−−−−| # .PHONY: objclean objclean: rm −f $(BIN_DIR)/*.o # |−−−−−−−−−−−−−−−| Construir y eliminar archivos temporales |−−−−−−−−−−−−−−−| # .PHONY: deltemps deltemps: $(FULL_OUT) objclean # |−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−| Instalar |−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−| # .PHONY: install install: $(FULL_OUT) cp $(FULL_OUT) "$(INSTALL_DIR)" # |−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−| Desinstalar |−−−−−−−−−−−−−−−−−−−−−−−−−−−−−| # .PHONY: uninstall uninstall: rm −f "$(INSTALL_DIR)/$(OUT)"