menu.cpp - CB100 - Notas, resueltos y tps de la materia Algoritmos y Estructuras de Datos

tps/2/menu.cpp (14657B)
Line numbers
   1 #include "menu.h"
   2 
   3 #include <iostream>
   4 #include <fstream>
   5 #include <string>
   6 #include <sstream>
   7 #include <cstdlib>
   8 #include <vector>
   9 #include <cmath>
  10 #include <iomanip>
  11 #include <cctype>
  12 
  13 void Menu::imprimirCantidadDeParadasPorBarrio() {
  14     Barrio *barrio;
  15 
  16     std::cout << std::endl;
  17     std::cout << std::setw(10);
  18     std::cout.fill(' ');
  19 
  20     std::cout << std::left << std::setw(18) << std::left << "Barrio";
  21     std::cout << std::right << std::setw(20) << "Cantidad de Paradas" << std::endl;
  22     std::cout.fill('=');
  23     std::cout << std::left << std::setw(38) << std::left << "=" << std::endl;
  24 
  25     std::cout.fill('.');
  26     this->barrios->startCursor();
  27     while(this->barrios->forwardCursor()) {
  28         barrio = this->barrios->getCursorData();
  29         std::cout << std::left << std::setw(18) << barrio->getNombre()
  30                  << std::right << std::setw(20) << barrio->getSizeListaDeParadas()
  31                  << std::endl;
  32     }
  33 
  34     std::cout << std::endl;
  35 }
  36 
  37 Parada *Menu::paradaMasCercanaPorCoordenada(double coordX, double coordY) {
  38     double distanciaMin;
  39     double distancia;
  40 
  41     Parada *res, *parada;
  42     Barrio *barrio;
  43 
  44     res = NULL;
  45     this->barrios->startCursor();
  46     while(this->barrios->forwardCursor()) {
  47         barrio = this->barrios->getCursorData();
  48 
  49         if(res == NULL) {
  50             res = barrio->paradaMasCercana(coordX, coordY);
  51             distanciaMin = getDistancia(coordX, coordY, res->getCoordX(), res->getCoordY());
  52         }
  53         else {
  54             parada = barrio->paradaMasCercana(coordX, coordY);
  55             distancia = getDistancia(coordX, coordY, parada->getCoordX(), parada->getCoordY());
  56 
  57             if(distanciaMin > distancia) {
  58                 distanciaMin = distancia;
  59                 res = parada;
  60             }
  61         }
  62     }
  63 
  64     return res;
  65 }
  66 
  67 void Menu::agregarElementoSinRepetir(std::vector<int> *lineas, std::vector<int> *vectorLineasAux) {
  68     size_t lineaTope = vectorLineasAux->size();
  69 
  70     for(size_t i = 0; i < lineaTope; i++) {
  71         bool seRepite = false;
  72         for(size_t j = 0; j < lineas->size(); j++) {
  73             if((*vectorLineasAux)[i] == (*lineas)[j]) {
  74                 seRepite = true;
  75             }
  76         }
  77         if(seRepite == false) {
  78             lineas->push_back((*vectorLineasAux)[i]);
  79         }
  80     }
  81 }
  82 
  83 void Menu::lineasPorParada(List<Parada*> *paradas) {
  84     Parada *paradaAux;
  85     std::vector<int> *vectorLineasAux;
  86 
  87     paradas->startCursor();
  88     while(paradas->forwardCursor()){
  89         paradaAux = paradas->getCursorData();
  90 
  91         vectorLineasAux = paradaAux->getLineas();
  92         agregarElementoSinRepetir(this->lineas, vectorLineasAux);
  93     }
  94 }
  95 
  96 void Menu::cantidadDeParadasPorLinea() {
  97     Barrio *barrio;
  98 
  99     this->lineas->clear();
 100     this->barrios->startCursor();
 101 
 102     while(this->barrios->forwardCursor()){
 103         barrio = this->barrios->getCursorData();
 104 
 105         lineasPorParada(barrio->getParadas());
 106     }
 107 }
 108 
 109 Menu::Menu() {
 110     this->barrios = new List<Barrio*>;
 111     this->lineas = new std::vector<int>;
 112 }
 113 
 114 std::string strToLowercase(std::string str) {
 115     std::string res;
 116     for(size_t i = 0; i < str.size(); ++i) {
 117         res += std::tolower(str[i]);
 118     }
 119 
 120     return res;
 121 }
 122 
 123 void delSurroundingChar(std::string &str, char c) {
 124     str.erase(0, 1);
 125     str[str.size() - 1] = '\0';
 126 }
 127 
 128 size_t getTokens(std::string line, std::vector<std::string> &tokens) {
 129     std::string token;
 130     std::stringstream lineStream;
 131     size_t field;
 132 
 133     lineStream.clear();
 134     lineStream.str(line);
 135     token.clear();
 136 
 137     for(field = CALLE; std::getline(lineStream, token, CSV_DELIM); ++field) {
 138         // solucion a `token` es una cadena que contiene CSV_DELIM
 139         while((token[0] == '"') && (token[token.size() - 1] != '"')) {
 140             std::string nextToken;
 141             std::getline(lineStream, nextToken, CSV_DELIM);
 142             token += CSV_DELIM + nextToken;
 143         }
 144         if(token[0] == '"' && token[token.size() - 1] == '"') {
 145             delSurroundingChar(token, '"');
 146         }
 147         tokens.push_back(token);
 148     }
 149 
 150     return field;
 151 }
 152 
 153 List<Parada*> *Menu::buscarParadas(List<Barrio*> *barrios, int linea) {
 154     List<Parada*> *resultado, *paradasPorBarrio;
 155     Barrio *barrio;
 156 
 157     resultado = new List<Parada*>;
 158 
 159     barrios->startCursor();
 160     while(barrios->forwardCursor()) {
 161         barrio = barrios->getCursorData();
 162         paradasPorBarrio = barrio->listaDeParadasPorLinea(linea);
 163         if(paradasPorBarrio == NULL) {
 164             // no hay paradas de la linea
 165             continue;
 166         }
 167 
 168         paradasPorBarrio->startCursor();
 169         while(paradasPorBarrio->forwardCursor()) {
 170             resultado->insert(paradasPorBarrio->getCursorData());
 171         }
 172 
 173         delete paradasPorBarrio;
 174     }
 175 
 176     if(resultado->getSize() == 0) {
 177         delete resultado;
 178         return NULL;
 179     }
 180 
 181     return resultado;
 182 }
 183 
 184 // busca el barrio en la lista de barrios, si no lo encuentra devuelve NULL
 185 Barrio *Menu::getBarrioPorNombre(std::string nombre) {
 186     Barrio *res, *barrio;
 187 
 188     res = NULL;
 189     this->barrios->startCursor();
 190 
 191     while(this->barrios->forwardCursor()) {
 192         barrio = this->barrios->getCursorData();
 193         if(strToLowercase(barrio->getNombre()) == strToLowercase(nombre)) {
 194             res = this->barrios->getCursorData();
 195             break;
 196         }
 197     }
 198 
 199     return res;
 200 }
 201 
 202 double gradosARadianes(double grados) {
 203     return grados * M_PI / 180.0;
 204 }
 205 
 206 // lat -> y; lon -> x;
 207 // calcula la distancia en km entre dos coordenadas usando la formula de Lambert
 208 double getDistanciaEnKilometros(double x1, double y1, double x2, double y2) {
 209     const double R = 6371.0;  // radio de la tierra
 210 
 211     double x1Rad = gradosARadianes(x1);
 212     double y1Rad = gradosARadianes(y1);
 213     double x2Rad = gradosARadianes(x2);
 214     double y2Rad = gradosARadianes(y2);
 215 
 216     double dLon = x2Rad - x1Rad;
 217     double dLat = y2Rad - y1Rad;
 218 
 219     double a = sin(dLat / 2) * sin(dLat / 2) + cos(y1Rad) * cos(y2Rad) * sin(dLon / 2) * sin(dLon / 2);
 220     double c = 2 * atan2(sqrt(a), sqrt(1 - a));
 221     double distancia = R * c;
 222 
 223     return distancia;
 224 }
 225 
 226 double Menu::getDistancia(double x1, double y1, double x2, double y2) {
 227     double dX = (x2 - x1);
 228     double dY = (y2 - y1);
 229 
 230     return std::sqrt(dX*dX + dY*dY);
 231 }
 232 
 233 void ordenarParadasPorDistanciaACoordenada(List<Parada*> *paradas, double x, double y) {
 234     Node<Parada*> *actual, *min, *sig;
 235     Parada *tmp;
 236 
 237     double distMin, distSig;
 238 
 239     paradas->startCursor();
 240     while(paradas->forwardCursor()) {
 241         actual = paradas->getCursor();
 242         min = actual;
 243 
 244         distMin = getDistanciaEnKilometros(min->getData()->getCoordX(), min->getData()->getCoordY(), x, y);
 245 
 246         sig = actual->getNext();
 247         while (sig != NULL) {
 248             distSig = getDistanciaEnKilometros(sig->getData()->getCoordX(), sig->getData()->getCoordY(), x, y);
 249 
 250             if (distSig < distMin) {
 251                 min = sig;
 252                 distMin = distSig;
 253             }
 254             sig = sig->getNext();
 255         }
 256 
 257         if (min != actual) {
 258             tmp = actual->getData();
 259             actual->setData(min->getData());
 260             min->setData(tmp);
 261         }
 262     }
 263 }
 264 
 265 int Menu::cargarDatos() {
 266     std::ifstream inputFile;
 267     std::string token, line;
 268     std::vector<std::string> tokens;
 269     std::vector<int> lineasEnParada;
 270     float coordX, coordY;
 271     Barrio *barrio;
 272 
 273     const char *inputFilePath = "paradas-de-colectivo.csv";
 274 
 275     int fields, linea;
 276     std::string barrioNombre, calle, direccion;
 277 
 278     inputFile.open(inputFilePath);
 279     if(!inputFile.is_open()) {
 280         std::cout << "No se pudo abrir el archivo `" << inputFilePath << "`\n";
 281         return -1;
 282     }
 283 
 284     coordX = coordY = 0.0f;
 285 
 286     std::getline(inputFile, line); // saltea la primer linea
 287 
 288     while(std::getline(inputFile, line)) {
 289         tokens.clear();
 290         lineasEnParada.clear();
 291         fields = getTokens(line, tokens);
 292 
 293         for(int field = CALLE; field <= fields; ++field) {
 294             token = tokens[field];
 295             switch(field) {
 296                 case CALLE:
 297                     calle = token;
 298                     break;
 299                 case ALT_PLANO:
 300                     break;
 301                 case DIRECCION:
 302                     if(token == "") {
 303                         break;
 304                     }
 305                     direccion = token;
 306                     break;
 307                 case COORD_X:
 308                     coordX = std::atof(token.c_str());
 309                     break;
 310                 case COORD_Y:
 311                     coordY = std::atof(token.c_str());
 312                     break;
 313                 case COMUNA:
 314                     break;
 315                 case BARRIO:
 316                     barrioNombre = token;
 317                     if(barrioNombre == "") {
 318                         barrioNombre = "NOMBRE SIN DEFINIR";
 319                     }
 320                     break;
 321                 case LINEA_1:
 322                 case LINEA_2:
 323                 case LINEA_3:
 324                 case LINEA_4:
 325                 case LINEA_5:
 326                 case LINEA_6:
 327                     if(token == "") {
 328                         break;
 329                     }
 330                     linea = std::atoi(token.c_str());
 331                     lineasEnParada.push_back(linea);
 332                     break;
 333                 case LINEA_1_SENTIDO:
 334                 case LINEA_2_SENTIDO:
 335                 case LINEA_3_SENTIDO:
 336                 case LINEA_4_SENTIDO:
 337                 case LINEA_5_SENTIDO:
 338                 case LINEA_6_SENTIDO:
 339                     break;
 340                 default:
 341                     break;
 342             }
 343         }
 344 
 345         barrio = getBarrioPorNombre(barrioNombre);
 346         if(barrio == NULL) {
 347             barrio = new Barrio(barrioNombre);
 348             barrio->addParada(calle, direccion, coordX, coordY, lineasEnParada);
 349             barrios->insert(barrio);
 350         } else {
 351             // barrio ya existe
 352             barrio->addParada(calle, direccion, coordX, coordY, lineasEnParada);
 353         }
 354     }
 355 
 356     inputFile.close();
 357     return 0;
 358 }
 359 
 360 void Menu::mostrarMenu() {
 361     bool terminarPrograma = false;
 362     int linea;
 363     double lat, lon; // lat -> Y; lon -> X;
 364     double distanciaEnKm;
 365 
 366     std::string opcion, barrioNombre, lineaAImprimir, distanciaUnidad;
 367     List<Parada*> *paradas, *paradasDeLaLinea;
 368     Parada *actual;
 369     Barrio *barrio;
 370 
 371     while(!terminarPrograma) {
 372         std::cout << "`1` Cantidad de paradas por barrio\n";
 373         std::cout << "`2` Parada mas cercana a una coordenada\n";
 374         std::cout << "`3` Listado de paradas de una linea de colectivo\n";
 375         std::cout << "`4` Listado de cantidad de paradas por linea de colectivo\n";
 376         std::cout << "`5` Listado de paradas de una linea mas cercano a una coordenada\n";
 377         std::cout << "`b` Imprimir barrios\n";
 378         std::cout << "`q` Salir\n";
 379         std::cout << "opcion> ";
 380 
 381         opcion.clear();
 382         std::cin >> opcion;
 383 
 384         if(opcion[0] == '\n') {
 385             continue;
 386         }
 387         switch(opcion[0]) {
 388             case 'b':
 389                 this->barrios->startCursor();
 390                 while(this->barrios->forwardCursor()) {
 391                     std::cout << "`" << this->barrios->getCursorData()->getNombre() << "`\n";
 392                 }
 393                 std::cout << std::endl;
 394                 break;
 395             case '1':
 396                 imprimirCantidadDeParadasPorBarrio();
 397                 break;
 398             case '2':
 399                 // TODO: verificar que `latitud` y `longitud` sean validas
 400                 std::cin.clear();
 401                 std::cout << "latitud> ";
 402                 std::cin >> lat;
 403 
 404                 std::cin.clear();
 405                 std::cout << "longitud> ";
 406                 std::cin >> lon;
 407 
 408                 // std::cout << "latitud: " << lat << "; longitud: " << lon << "\n";
 409 
 410                 Parada *parada;
 411                 parada = paradaMasCercanaPorCoordenada(lon, lat);
 412                 if(parada == NULL) {
 413                     std::cout << "Parada inaccessible";
 414                     break;
 415                 }
 416 
 417                 distanciaEnKm = getDistanciaEnKilometros(lon, lat, parada->getCoordX(), parada->getCoordY());
 418 
 419                 if(distanciaEnKm < 1) {
 420                     distanciaEnKm *= 1000.0f;
 421                     distanciaUnidad.assign("metros");
 422                 } else {
 423                     distanciaUnidad.assign("kilometros");
 424                 }
 425 
 426                 std::cout << "Parada mas cercana: `" << parada->getDireccion()
 427                         << "` (" << parada->getCoordX() << ", " << parada->getCoordY()
 428                         << ") a " << std::fixed << std::setprecision(2) << distanciaEnKm
 429                         << " " << distanciaUnidad << "\n";
 430                 break;
 431             case '3':
 432                 // TODO: verificar que `linea` sea valida
 433 
 434                 std::cin.clear();
 435                 std::cout << "linea> ";
 436                 std::cin >> linea;
 437 
 438                 paradas = buscarParadas(barrios, linea);
 439                 if(paradas == NULL) {
 440                     std::cout << "no hay paradas de la linea indicada\n";
 441                     break;
 442                 }
 443                 std::cout << "La linea `" << linea << "` tiene `"
 444                     << paradas->getSize() << "` paradas en CABA\n";
 445 
 446                 paradas->startCursor();
 447                 while(paradas->forwardCursor()) {
 448                     std::cout << " · " << paradas->getCursorData()->getDireccion() << "\n";
 449                 }
 450                 delete paradas;
 451                 break;
 452             case '4':
 453                 cantidadDeParadasPorLinea();
 454 
 455                 std::cout << std::endl;
 456                 std::cout << std::setw(10);
 457                 std::cout.fill(' ');
 458 
 459                 std::cout << std::left << std::setw(18) << std::left << "Linea";
 460                 std::cout << std::right << std::setw(20) << "Cantidad de Paradas" << std::endl;
 461                 std::cout.fill('=');
 462 
 463                 std::cout << std::left << std::setw(38) << std::left << "=" << std::endl;
 464                 std::cout.fill('.');
 465 
 466                 paradas = NULL;
 467                 for(size_t i = 0; i < this->lineas->size(); ++i) {
 468                     paradas = buscarParadas(barrios, (*this->lineas)[i]);
 469                     if(paradas == NULL) {
 470                         std::cout << "no hay paradas de la linea indicada\n";
 471                         continue;
 472                     }
 473 
 474                     std::ostringstream sstream;
 475                     sstream << "Linea " << (*this->lineas)[i];
 476                     lineaAImprimir = sstream.str();
 477 
 478                     std::cout << std::left << std::setw(18) << lineaAImprimir
 479                              << std::right << std::setw(20) << paradas->getSize()
 480                              << std::endl;
 481                 }
 482 
 483                 std::cout << std::endl;
 484                 if(paradas != NULL) {
 485                     delete paradas;
 486                 }
 487                 break;
 488             case '5':
 489                 std::cout << "barrio> ";
 490                 std::cin.ignore(1);
 491                 std::getline(std::cin, barrioNombre, '\n');
 492 
 493                 std::cin.clear();
 494                 std::cout << "linea> ";
 495                 std::cin >> linea;
 496         
 497                 // TODO: verificar que `latitud` y `longitud` sean validas
 498                 std::cin.clear();
 499                 std::cout << "latitud> ";
 500                 std::cin >> lat;
 501 
 502                 std::cin.clear();
 503                 std::cout << "longitud> ";
 504                 std::cin >> lon;
 505 
 506                 if((barrio = getBarrioPorNombre(barrioNombre)) == NULL) {
 507                     std::cout << "No se encontro el barrio `" << barrioNombre << "`\n";
 508                     break;
 509                 }
 510 
 511                 paradasDeLaLinea = barrio->listaDeParadasPorLinea(linea);
 512                 if(paradasDeLaLinea == NULL) {
 513                     std::cout << "La linea `" << linea
 514                         << "` no tiene paradas en el barrio `" << barrioNombre << "`\n";
 515                     break;
 516                 }
 517 
 518                 // ordenar de mayor a menor distancia a `lat, lon` la lista `paradasDeLaLinea`
 519                 ordenarParadasPorDistanciaACoordenada(paradasDeLaLinea, lon, lat);
 520 
 521                 std::cout << std::endl;
 522                 std::cout.fill(' ');
 523                 std::cout << std::left << std::setw(18) << std::left << "Direccion"
 524                         << std::right << std::setw(35) << "Distancia en Kilometros"
 525                         << std::right << std::setw(30) << "Coordenadas (lat, lon)" << std::endl;
 526                 std::cout.fill('=');
 527                 std::cout << std::left << std::setw(83) << std::left << "=" << std::endl;
 528 
 529                 paradasDeLaLinea->startCursor();
 530                 while(paradasDeLaLinea->forwardCursor()) {
 531                     actual = paradasDeLaLinea->getCursorData();
 532                     distanciaEnKm = getDistanciaEnKilometros(lon, lat, actual->getCoordY(), actual->getCoordX());
 533 
 534                     std::string coord;
 535                     coord += actual->getCoordX();
 536 
 537                     std::cout.fill('.');
 538                     std::cout << std::left << std::setw(33) << actual->getDireccion()
 539                                 << std::right << std::setw(20)
 540                                 << std::fixed << std::setprecision(2)
 541                                 << distanciaEnKm;
 542 
 543                     std::cout.fill('.');
 544                     std::cout << std::right << std::setw(10) << std::setprecision(4)
 545                                 << "(" << actual->getCoordX();
 546 
 547                     std::cout.fill(' ');
 548                     std::cout << "," << std::right << std::setw(10) << std::setprecision(4)
 549                                 << actual->getCoordY() << ")" << std::endl;
 550                 }
 551                 std::cout << std::endl;
 552 
 553                 delete paradasDeLaLinea;
 554                 break;
 555             case 'q':
 556                 terminarPrograma = true;
 557                 break;
 558             default:
 559                 std::cout << "opcion `" << opcion[0] << "` no definida\n";
 560                 break;
 561         }
 562     }
 563 }
 564 
 565 Menu::~Menu() {
 566     Barrio *delBarrio;
 567 
 568     this->barrios->startCursor();
 569     while(this->barrios->forwardCursor()){
 570         delBarrio = this->barrios->getCursorData();
 571         delete delBarrio;
 572     }
 573 
 574     delete this->barrios;
 575     delete this->lineas;
 576 }