Ordenar por orden alfabético Java Montículos binarios (binary heaps) estructuras

[fitus]

Hola buenas noches, quería preguntaros acerca de una práctica que tengo que realizar de Estructura de Datos:

Me piden lo siguiente:estructura de datos para almacenar los medicamentos comercializados, que consiga que las operaciones de inserción y búsqueda (por nombre de medicamento). Y no se me ocurre como realizar un metodo Inorder que se rellene alfabéticamente, no se si tendría que ir caracter a caracter comparando o como debo realizarlo.

Si me podéis echar un cable os lo agradecería porque la entrego el 4 de mayo y no tengo ni idea de como hacer esa parte!

Saludos!

[César Krall]

Hola fitus copia el enunciado completo, no acabo de entender qué es lo que tienes que hacer. Cuando se habla de árbol binario no se trabaja con orden en lo que es la estructura interna, sí existe orden para los recorridos. Si se quiere orden en la estructura interna estaríamos hablando de montículos (heap), http://es.wikipedia.org/wiki/Mont%C3%ADculo_%28inform%C3%A1tica%29

Saludos

[fitus]

Programa para la gestión de medicamentos.

La aprobación y retirada de los medicamentos en un determinado país son operaciones gestionadas por las agencias nacionales de medicamentos. Las principales funciones de estas agencias son:
- recibir y almacenar solicitudes de medicamentos para su comercialización.

- revisar cada una de las solicitudes para su aprobación o rechazo.

- un medicamento podría ser retirado del mercado por distintas causas, por ejemplo, porque se ha comprobado que causa graves efectos secundarios. En este tipo de casos, la agencia podrá retirar el medicamento.

- en caso de petición por parte de una farmacia u hospital, proporcionar la colección de los distintos medicamentos comerciales aprobados a partir de una fecha, retirados a partir de una fecha, o aquellos que incluyen un determinado principio activo.
En España, la Agencia Española del Medicamento y Productos Sanitarios (AEMPS) es el organismo encargado tanto de gestionar las solicitudes para la aprobación de medicamentos, así como la retirada de medicamentos y proporcionar información sobre los medicamentos aprobados, retirados o que contengan un determinado principio activo.

Aprobación y retirada de medicamentos

Cuando un nuevo medicamento es desarrollado por un laboratorio farmacéutico, la AEMPS recibe una solicitud con la siguiente información:

- Nombre del medicamento (por ejemplo, espidifen).

- Nombre de la empresa farmacéutica que lo comercializa (por ejemplo, zambon).

- Nombre del principio activo (por ejemplo, ibuprofeno). Nota: Para simplificar el problema,

vamos a suponer que un medicamento comercial se corresponde con un único principio
activo. Sin embargo, un principio activo podría ser comercializado por distintos
medicamentos.

- Fecha solicitud: (por ejemplo, 01/04/2015).

- Listado de sus indicaciones (por ejemplo, dolor leve o moderado, fiebre, cuadros inflamatorios, inflamación no reumática, dismenorrea).

- Listado de efectos adversos (por ejemplo, náuseas, pérdida de apetito, urticaria).

- Estado de la solicitud (por ejemplo, pendiente de revisión, aprobado o retirado).

Cada una de estas solicitudes de medicamentos es almacenada por la AEMPS, para su posterior revisión, que se realiza por estricto orden de llegada. Cada vez que se revisa un medicamento, si la agencia decide no aprobar el medicamento, simplemente éste es eliminado de la colección de medicamentos pendientes de revisión. Si por el contrario, el medicamento es aprobado, deberá ser eliminado de la colección de medicamentos pendientes de revisión y almacenado en una colección dedicada a almacenar los medicamentos comercializados. El medicamento aprobado es almacenado en orden alfabético ascendente, de la A a la Z, en dicha colección. Además, será necesario modificar el estado del medicamento de “pendiente de revisión” a “aprobado”, y se almacenará su fecha de aprobación.

Nota: Para simular la revisión de un medicamento, se podrían mostrar los datos del medicamento y preguntar por consola si el medicamento debe ser aprobado o no.
A partir del nombre de un medicamento, la AEMPS puede buscar dicho medicamento en la colección de medicamentos comercializados. Si el medicamento no existe, se deberá mostrar un mensaje informando que no se ha encontrado. En caso contrario, se mostrarán sus datos y además se preguntará si se desea retirar dicho medicamento (si el medicamento ya estuviera retirado, se preguntará si se desea volver a aprobar). La retirada de un medicamento consiste simplemente en modificar su estado de aprobado a retirado, y almacenar la fecha en la que se retira el medicamento. La fecha de aprobación debería modificarse para ser nula. Es importante notar que el medicamento no es eliminado de la colección de medicamentos comercializados, sino que simplemente se modifica su estado y se actualiza su fecha de retirada. Si la AEMPS decide volver a aprobar el medicamento, el programa deberá actualizar la fecha de aprobación y modificar el estado de retirado a aprobado. La fecha de retirada debería modificarse para ser nula. En caso de que se intente aprobar una medicamento que no existe en la colección de medicamentos comercializados, el programa deberá mostrar un mensaje informando que dicho medicamento no existe en la colección de medicamentos
comercializados.


Consulta de Información

En algunas ocasiones, la AEMPS podrá consultar los medicamentos que hayan sido retirados a partir de una determinada fecha, mostrando su información por pantalla. Si no se indica una fecha, el programa mostrará la colección de todos los medicamentos retirados. De forma similar, también se podrán mostrar todos los medicamentos aprobados a partir de una determinada fecha. Si no se indica la fecha, el programa deberá mostrar la colección de todos los medicamentos aprobados en la actualidad. La AEMPS también es la encargada de proporcionar información relacionada con un principio activo. En particular, la AEMPS debería ser capaz de proporcionar la colección de
medicamentos que comercializan un determinado principio activo. En este caso, el programa mostrará por pantalla la información de cada uno de los medicamentos que se corresponden a dicho principio activo. En todos los casos anteriores, se podrá seleccionar el orden en el que se deben mostrar los medicamentos, alfabético ascendente o descendente (de la Z a la A).


Fase 1

Se pide desarrollar todas las estructuras de datos necesarias para implementar una solución correcta y completa al problema planteado en el enunciado. Esta primera fase es de prototipado, no contemplando un gran número de medicamentos. Los puntos que se muestran a continuación son pautas y cuestiones, que te ayudarán a diseñar la solución.

1.1 Desarrolla la estructura de datos adecuada para almacenar la información del medicamento. Para guardar la información sobre las indicaciones y efectos adversos de un medicamento, está permitido utilizar arrays o alguna de las clases para implementar colecciones proporcionadas por el API de Java (por ejemplo, ArrayList o LinkedList). Del mismo modo, otra opción posible sería usar las clases de la librería EdaLib (SList o DList).

1.2 Teniendo en cuenta que los medicamentos serán revisados en estricto orden de llegada, ¿qué estructura de datos de las estudiadas durante este curso crees que es la más adecuada para almacenar la colección de medicamentos pendientes de revisión?

Desarrolla dicha estructura. Para su implementación, el alumno podrá desarrollar su propia estructura o bien utilizar alguna de las estructuras de la librería EdaLib. En ningún caso se permitirá utilizar un array ni ninguna de las clases del API de Java para implementar colecciones, como por ejemplo, ArrayList, LinkedList, etc.


1.3 Implementa una estructura lineal para almacenar la colección de medicamentos comercializados.

Nótese que en esta colección se almacenan tanto los medicamentos que están aprobados, como aquellos que fueron aprobados y posteriormente retirados. Para su implementación, el alumno podrá desarrollar su propia estructura o bien utilizar alguna de las estructuras de la librería EdaLib. En ningún caso se permitirá utilizar un array ni ninguna de las clases del API de Java para implementar colecciones, como por ejemplo, ArrayList, LinkedList, etc.


1.4 Con el enunciado del caso práctico, se ha entregado la interfaz IAgencia que específica las funcionalidades de las agencias de medicamentos. Crea la estructura de datos adecuada para implementar la funcionalidad de la AEMPS. Añade los atributos que sean necesarios para almacenar la información que la agencia debe gestionar y mantener. Implementa los métodos.


1.5 ¿Cuál es la complejidad de buscar un determinado medicamento en la colección de
medicamentos?, ¿y la de añadir el medicamento a la colección cuando es aprobado?


1.6 ¿Cuál es la complejidad del algoritmo que permite imprimir por pantalla la colección de medicamentos que contienen un determinado principio activo?


Fase 2

Debido al gran número de medicamentos, los programas utilizados por las agencias han presentado problemas a la hora de gestionar y mantener de forma eficiente la información de estos medicamentos.

En reuniones recientes, la agencia española del medicamento ha planteado la necesidad de mejorar la eficiencia de su programa. Así la agencia nos propone las siguientes cuestiones y tareas:

2.1 Adecuar el programa de la AEMPS proponiendo otra estructura de datos para almacenar los medicamentos comercializados, que consiga que las operaciones de inserción y búsqueda (por nombre de medicamento) de medicamentos sean más eficientes. Implementa dicha solución. Recuerda añadir los métodos necesarios que permitan volcar la información almacenada en la colección de medicamentos comercializados a esta nueva estructura.


2.2 En el caso de los principios activos, ¿se te ocurre alguna otra forma de almacenar la información para que la búsqueda y consulta de un determinado principio activo sea más eficiente?.

Nota: La solución propuesta para la fase 2 debe incluir la implementación todos los métodos descritos en la fase 1. Es decir, las soluciones de ambas fases deben implementar la interfaz IAgencia que proporcionamos junto con este enunciado.

Nota: El proyecto debe incluir una clase Test que permita probar cada una de las
funcionalidades que se describen en el caso práctico.


Algunos comentarios:

Los alumnos deberá implementar los métodos necesarios para implementar de forma completa la funcionalidad que se describe en el caso práctico. De esta forma, aunque una gran mayoría de estos métodos se piden de forma explícita en los apartados anteriores, otros no se han descrito, y son los alumnos los responsables de definirlos e implementarlos.

El código debería incluir comentarios sobre las decisiones tomadas. A continuación se muestra un ejemplo de comentario que se deberá incluir en el código para explicar las decisiones tomadas:

/*** DECISION ***
En los métodos de consulta, hemos decidido que además de mostrar los
medicamentos, los métodos devuelvan la lista.*/

Las cuestiones 1.5 y 1.6 deben ser contestadas directamente en los comentarios de los métodos a los que se refieren dichas cuestiones.



La fase 1 la tenemeos mi compañero y yo, pero la fase dos que es con árboles no sabemos como hacerla! Gracias de antemano

[César Krall]

Si puedes utilizar el api de Java la clase java.util.PriorityQueue viene representando un montículo binario, que es una estructura eficiente para la inserción y búsqueda. Si no puedes usarla tendrías que implementarla, o guiarte por alguna implementación disponible en la red comprobándola antes (pej http://courses.cs.washington.edu/courses/cse326/03au/projects/project2/code/BinaryHeap.java)

Crear clases para manejar árboles binarios requiere tiempo, en el caso de montículos más tiempo todavía porque tienes que implementar operaciones adicionales para mantener el orden ante la inserción o borrado de datos.

Saludos

[fitus]

Tengo clases que implemento con los metodos de los arboles, pero necesito saber concretamente el de como ordenar alfabeticamente. No se como crear el metodo InOrden para ir comparando las letras de los medicamento.Si un medicamento, se llama Aspirina y el otro Ibuprofeno quiero que aspirina entre antes que ibuprofeno en el arbol y no se como hacerlo.
Gracias de antemano

[César Krall]

Hola, para comparar objetos en base a un atributo como el nombre debes comparar los objetos con un comparador y determinar cuál es "mayor o menor", por ejemplo puedes implementar que los que tengan el atributo nombre comenzando por la letra a se consideren mayores que los que empiezan por la letra b, de ese modo mantendrías un orden basado en el orden alfabético.

Para crear un orden natural entre objetos debes implementar la interface Comparable y el método compareTo:

Interface Comparable y compareTo: https://www.aprenderaprogramar.com/index.php?option=com_content&view=article&id=587:ejercicio-ejemplo-resuelto-interface-comparable-y-metodo-compareto-api-java-comparar-objetos-cu00911c&catid=58:curso-lenguaje-programacion-java-nivel-avanzado-i&Itemid=180

Si necesitas poder establecer varios criterios de orden debes implementar la interface Comparator, aquí hay un ejemplo de cómo hacerlo: https://www.aprenderaprogramar.com/index.php?option=com_content&view=article&id=599:interface-comparator-api-java-diferencia-con-comparable-clase-collections-codigo-ejemplo-cu00915c&catid=58:curso-lenguaje-programacion-java-nivel-avanzado-i&Itemid=180


Para las formas de recorrido de árboles y su implementación: https://www.aprenderaprogramar.com/foros/index.php?topic=1367.0


Para definir una comparación de Strings puedes usar el método compareTo de la clase String (https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#compareTo-java.lang.String-) aunque te recomiendo probar que el funcionamiento de este método sea correcto ya que se basa en los valores de los códigos unicode y esto puede no ser siempre correcto (depende de lo preciso que tengas que ser).

Si necesitas comparaciones de String más precisas necesitas implementaciones como este ejemplo

Código: [Seleccionar]

import java.text.Collator;
import java.util.*;

/**
 Use Collator to sort and compare text.
*/
public final class SimpleCollator {

  /** Simple harness to exercise the code.  */
  public static void main (String[] Arguments) {
    //This data is based on an example in Java Class Libraries,
    //by Chan, Lee, and Kramer
    List<String> words = Arrays.asList(
      "Äbc", "äbc", "Àbc", "àbc", "Abc", "abc", "ABC"
    );
   
    log("Different 'Collation Strength' values give different sort results: ");
    log(words + " - Original Data");
    sort(words, Strength.Primary);
    sort(words, Strength.Secondary);
    sort(words, Strength.Tertiary);
   
    log(EMPTY_LINE);
    log("Case kicks in only with Tertiary Collation Strength  : ");
    List<String> wordsForCase = Arrays.asList("cache", "CACHE", "Cache");
    log(wordsForCase + " - Original Data");
    sort(wordsForCase, Strength.Primary);
    sort(wordsForCase, Strength.Secondary);
    sort(wordsForCase, Strength.Tertiary);
   
    log(EMPTY_LINE);
    log("Accents kick in with Secondary Collation Strength.");
    log("Compare with no accents present: ");
    compare("abc", "ABC", Strength.Primary);
    compare("abc", "ABC", Strength.Secondary);
    compare("abc", "ABC", Strength.Tertiary);
   
    log(EMPTY_LINE);
    log("Compare with accents present: ");
    compare("abc", "ÀBC", Strength.Primary);
    compare("abc", "ÀBC", Strength.Secondary);
    compare("abc", "ÀBC", Strength.Tertiary);
  }

  // PRIVATE //
  private static final String EMPTY_LINE = "";
  private static final Locale TEST_LOCALE = Locale.FRANCE;
 
  /** Transform some Collator 'int' consts into an equivalent enum. */
  private enum Strength {
    Primary(Collator.PRIMARY), //base char
    Secondary(Collator.SECONDARY), //base char + accent
    Tertiary(Collator.TERTIARY), // base char + accent + case
    Identical(Collator.IDENTICAL); //base char + accent + case + bits
   
    int getStrength() { return fStrength; }
   
    private int fStrength;
    private Strength(int aStrength){
      fStrength = aStrength;
    }
  }
 
  private static void sort(List<String> aWords, Strength aStrength){
    Collator collator = Collator.getInstance(TEST_LOCALE);
    collator.setStrength(aStrength.getStrength());
    Collections.sort(aWords, collator);
    log(aWords.toString() + " " + aStrength);
  }
 
  private static void compare(String aThis, String aThat, Strength aStrength){
    Collator collator = Collator.getInstance(TEST_LOCALE);
    collator.setStrength(aStrength.getStrength());
    int comparison = collator.compare(aThis, aThat);
    if ( comparison == 0 ) {
      log("Collator sees them as the same : " + aThis + ", " + aThat + " - " + aStrength);
    }
    else {
      log("Collator sees them as DIFFERENT  : " + aThis + ", " + aThat + " - " + aStrength);
    }
  }
 
  private static void log(String aMessage){
    System.out.println(aMessage);
  }
} 


Saludos