Guión de Algoritmos y Estructura de Datos

Algoritmos y estructura(s) de datos:

• [GT(I)'10] M. T. Goodrich y R. Tamassia. Data Structures and Algorithms in Java – International Edition, Wiley, 5a edición, 2010. (Buenas explicaciones. Horrendo código y horrendas transparencias. El código ha mejorado en la 6a edición americana.)
• [CLRS'01] Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms, 2nd Edition, MIT Press 2001. (Un estándar, hay 3a edición.)
• [ALT'03] Moshe Augenstein, Yedidyah Langsam, Aaron M. Tenenbaum. Data Structures Using Java, Prentice Hall 2003. (Buenas descripciones pero las implementaciones no usan genéricos.)
• [AHU'83] Alfred Aho, John Hopcroft, Jeffrey Ullman. Data Structures and Algorithms, Addison-Wesley 1983. (Un clásico de los 80.)

Java:

• [JLS'3E] Java Language Specification, 3th edition. http://docs.oracle.com/javase/specs/jls/se7/html/index.html
• [JPSE] Java Platform Standard Edition (incluye JCF). http://docs.oracle.com/javase
• [EJ'01] Joshua Bloch. Effective Java, Addison-Wesley, 2001. (Hay 2a edición)
• [JT7] Java Tutorials http://docs.oracle.com/javase/tutorial/index.html
• [GenTut] Gilad Bracha. "Generics in the Java Programming Language" (tutorial en línea, disponible en [JT7])
• [JP'05] Peter Sestoft. Java Precisely, 2ed, MIT Press, 2005.
• Collected Java Practices: http://www.javapractices.com/home/HomeAction.do

Programación orientada a objetos:

• Timothy Budd. Introduction to Object-Oriented Programming 3rd ed., Addison-Wesley.
• Bertrand Meyer. Object-Oriented Software Construction, Prentice-Hall.
• Cardelli, Wegner. "On understanding types, data abstraction, and polymorphism".
• Los libros de introducción a los fundamentos de programación y a la programación orientada a objetos de Luis Joyanes Aguilar.

• Las expresiones se evalúan a un valor de un tipo.

  Son expresiones los literales, las constantes (entre ellas "this", "super", "null"), las variables (atributos de clase, parámetros de métodos, variables locales a un bloque), operadores aplicados a argumentos, la invocación de un método, el upcasting, etc. Por ejemplo, el siguiente fragmento es una expresión booleana:

  (a = b = 1 + c * y.scale() - ((Automóvil)vehículo).getPrice()) != 0
  
  

  Los operadores pueden ser aritméticos, lógicos (estrictos o en cortocircuito), el operador condicional, el operador de asignación, el operador "." de acceso a un campo de un objeto (atributo o método), el operador de acceso a un elemento de un "array", el operador "new", "instanceof", etc.

  Recordad que los operadores lógicos evaluados en cortocircuito son diferentes a los operadores de la lógica convencional.

  'A && B' no es la conjunción de los predicados 'A' y 'B'. Su significado es "si A es cierto entonces el valor de A && B es el valor de B, pero si A es falso entonces el valor de A && B es falso". Más resumido:

  A && B = "si A entonces B pero si no A entonces no A (y B o no B)"

  A || B = "si A entonces A (y B o no B) pero si no A entonces B"

  Entre otras cosas, esto permite en '&&' usar A como condición preliminar a la comprobación de B, y en '||' usar !A como condición preliminar a la comprobación de B.

  Por ejemplo, si 'v' es null entonces 'v[i]' lanza 'NullPointerException' pero estas dos expresiones no lanzan la excepción. La primera es falsa si 'v' es null mientras que la segunda es cierta.

  v != null && v[i] == 0
  
  v == null || v[i] == 0
  
  

  Veremos más abajo las leyes de "de Morgan" en cortocircuito.

  Los operadores tienen una precedencia y una asociación (no confundir con "asociatividad" que es la propiedad de que la asociación del operador no afecta el resultado). Hay que conocer la tabla de precedencia y asociación de Java para evitar paréntesis explícitos que indiquen dicha precedencia o asociación. La expresión anterior es equivalente a la siguiente según las tablas de precedencia y asociación de Java y los paréntesis son por tanto innecesarios:

  (a = (b = ((1 + (c * (y.scale()))) - ((Automóvil)vehículo).getPrice()))) != 0
  
  

• Los comandos o mandatos afectan el estado del programa, es decir, el flujo de control o los valores de las variables. Son comandos:
  • Las expresiones seguidas de ";". Por ejemplo: la asignación, la invocación de un método, la creación de un objeto con "new", expresiones de incremento y decremento, etc. Algunas expresiones cambian el estado del programa.
  • Declaraciones e inicializaciones de variables — no confundir estas últimas con asignaciones.

    La inicialización por defecto es sólo para atributos de clase (la hace el constructor por defecto de la clase). No hay inicialización por defecto para variables locales a un método o a un bloque. Éstas tienen que tener valor obligatoriamente antes de usarse. Para ello pueden inicializarse o asignarse antes de usarse en una expresión.

  • Bloques: comienzan por "{" y terminan con "}". Se permiten bloques vacíos y anidados ("nesting").
  • Flujo de control:
    • Condicional: if-then, if-then[-else], switch. (¿Qué es if-else-if?)
    • Bucles: while, do-while, for.
    • Otros: return, throw, try-catch-finally, assert.

    Pueden anidarse.

  • Mandato vacío (";") usado en bucles.

    Por ejemplo, este método indica si el array de enteros 'arr' tiene un 0. El bucle contiene un mandato vacío:

    public static boolean hayCero(int arr []) {
      int i;
      for (i = 0; i < arr.length && arr[i] != 0; i++)
        ;
      return i < arr.length;
    }
    
    

    El bucle termina cuando el índice 'i' está fuera de rango (es mayor o igual que el tamaño del array) o bien cuando está en rango pero se encuentra el primer cero. Ambas condiciones son excluyentes.

    i >= arr.length || i < arr.length && arr[i] == 0
    
    

    La condición de terminación es la negada de la de continuación del bucle, la una se obtiene de la otra usando las leyes de "de Morgan" en cortocircuito:

    ! (A && B)          = !A || A && !B
    
    ! (!A || A && ! B)  = A && B
    
    

    La condición 'i < arr.length' es verdadera en el segundo caso donde también es verdadero que se ha encontrado el cero. Por tanto basta con devolver el valor de verdad de esa expresión.

    Se prefiere el bucle anterior al siguiente que usa una variable booleana innecesaria. Se puede comenzar usando la variable booleana pero es preferible sustituir variables booleanas por las expresiones que significan. El uso indiscriminado de variables booleanas puede ser peligroso (al confundirlas) y hacer menos legible el programa.

    boolean encontrado = false;
    for (int i = 0; i < arr.length && !encontrado; i++)
      encontrado = arr[i] == 0;
    return encontrado;
    
    

    Lo siguiente es equivalente pero mucho peor:

    boolean encontrado = false;
    for (int i = 0; i < arr.length && !encontrado; i++)
      if (arr[i] == 0)
        encontrado = true;
    return encontrado;
    
    

    Lo siguiente todavía peor:

    boolean encontrado = false;
    for (int i = 0; i < arr.length && !encontrado; i++)
      if (arr[i] == 0)
        encontrado = true;
      else
        encontrado = false;
    return encontrado;
    
    

    Lo siguiente todavía más:

    for (int i = 0; i < arr.length; i++)
      if (arr[i] == 0) return true;
      else return false;
    
    

    No es recomendable salir de bucles con "break", "continue", o "return" porque entonces la condición de salida del bucle no es la negada de la condición de continuación. Puede no respetarse la invariante del bucle (la propiedad que se cumple en cada paso del bucle) y hay que leer todo el bloque para determinar todas las condiciones de salida que no están en la condición de terminación. Se complica la comprensión y el mantenimiento del código. En este ejemplo el código del bucle es corto pero hay bucles muy grandes. En la práctica no tiene por qué ser necesario leer el bloque. Dentro del bucle pueden modificarse muchas variables del programa, pero una vez terminado el bucle, se puede escribir junto con la negada de la condición de continuación la condición que se cumple sobre todas las variables afectadas por el bucle. El programador no necesita saber qué hace el bucle sino qué condiciones se cumplen antes y después.

    Se puede corregir el código mediante transformación a código equivalente.

    for (int i = 0; i < arr.length; i++)
      if (arr[i] == 0) return true;
      else return false;
    
    
    // Sustituimos el condicional que retorna un booleano por el retorno
    // del valor de la expresión booleana.
    
    for (int i = 0; i < arr.length; i++)
      return arr[i] == 0;
    
    // Subimos la negada de la expresión a la condición de continuación
    
    for (int i = 0; i < arr.length && arr[i] !=0; i++)
      ;
    
    // Aplicamos las leyes de "de Morgan" en cortocirtuito y sacamos la
    // variable local al bucle en una declaración para poder preguntar sobre
    // la negada de la condición de continuación.
    
    int i;
    for (i = 0; i < arr.length && arr[i] !=0; i++)
      ;
    return i < arr.length;
    
    

• Las variables tienen un tipo ("type") y un ámbito ("scope"). El tipo se indica al declarar la variable. El ámbito es el trozo del programa en el que la variable es visible. Concepto importante: "shadowing" (ensombrecido). El lenguaje Java tiene unas reglas de ámbito y visibilidad establecidas. Algunos compiladores o entornos integrados como Eclipse pueden ser más restrictivos.

  EJERCICIO: Determina el ámbito de las distintas declaraciones de la variable 'x':

  public class C {
    int x;
  
    public C(int x) { x = x; }
  
    public void m1(int x) {
      for (int x = 1; x < 10; x++)
         x++;
      if (x < 0) {
        int x = 1;
        this.x = x;
      }
    }
  
    public void m2(int c) { x = c; }
  }
  
  

  Entornos como "Eclipse" pueden protestar sin razón por algo como ésto:

  int x;
  
  if (2 == 1 + 1)
    x = 1;
  
  System.out.println(x);
  
  

• Hay dos familias de tipos: primitivos (o básicos) y referencias ("arrays", clases, interfaces, enumerados).
  • Las variables de tipo básico almacenan directamente el valor al que son inicializadas o asignadas.
  • Las variables de tipo referencia almacenan una referencia al (es decir, la dirección de memoria del) objeto o array, cuyos datos están situados en otra parte de la memoria.
• EJERCICIO: Dibuja las variables como cajas y dibuja dentro los valores que toman durante la ejecución.

  public static void main(String [] args) {
    int v1 = 3;
    int v2 = 5;
    int v3;
  
    v3 = v1;
    v1 = v2;
    v3 = v1 = 6;
    v3 = 6 = v5;   // ¿dónde está el error?
    v3 = 7;
  }
  
  

  public static void main(String [] args) {
    int v1 = 3;
    int v2 = v1;
  
    if (v1 == v2)  // cierto
      System.out.println("Las variables almacenan el mismo valor");
  
    v2 = 3;
  
    if (v1 == v2)  // cierto
      System.out.println("Las variables almacenan el mismo valor");
  
    v2 = 4;
  
    if (v1 == v2)  // falso
      System.out.println("Las variables almacenan el mismo valor");
  }
  
  

  Si escribiéramos 'v1.equals(v2)' el programa compilaría y devolvería 'true' pero ¿qué estaría pasando? (Ver clases envoltorio.)

  El siguiente fragmento de código intercambia el valor de dos variables utilizando una variable auxiliar:

  public static void main(String [] args) {
    int x = 5;
    int y = 4;
  
    int tmp = x;    // código del intercambio ("swapping")
    x = y;
    y = tmp;
  }
  
  

  El siguiente método que pretende reutilizar el código del intercambio no funciona:

  public static void swap(int a, int b) {
    int tmp = a;
    a = b;
    b = tmp;
  }
  
  public static void main(String [] args) {
    int x = 5;
    int y = 4;
  
    this.swap(x,y); // no funciona
  
    int z = 7;
    int k = 8;
  
    this.swap(z,k); // no funciona
  }
  
  

  EJERCICIO: ¿Se te ocurre alguna forma posible de programarlo?

• Arrays, que también los llamaremos "vectores" en el guión. (No confundirlos con los 'Vector<E>' de la Java Collection Framework.)

  EJERCICIO: Dibuja con cajas y flechas las variables y los arrays que resultan de estas declaraciones.

  int [] a;
  
  int [] a2 = null;
  
  int [] b = new int[20];
  
  b[0] = 7;
  
  int [] c = new int[getIntegerFromUser()];
  
  String [] d = new String[10];   // aquí no hay ningún String todavía
  
  d[0] = new String("Hola");
  
  int [] e = new int[0];
  
  int [] f = { };
  
  int [] g = { 7, 9, 8 };
  
  Clase [] h = new SubClase[5];
  
  

• EJERCICIO: Dibuja los diagramas de flujo de ejecución de los bucles "while", "do-while" y "for". Recuerda que el bloque puede ser vacío.

  Equivalencia "while" y "do-while":

  BODY
  while (COND)
    BODY
  
  

  do BODY while (COND);
  
  

  El "for" es un tipo de "while":

  for (INIT ; COND ; POST) BODY
  
  

  {
    INIT
    while (COND) {
      BODY
      POST
    }
  }
  
  

• Hacemos en clase algún ejercicio de arrays para poner en práctica el uso de expresiones lógicas, bucles, y arrays.

  Importante: condición de parada o de continuación de un bucle. Aplicar leyes de "de Morgan" en cortocircuito, etc.

  El siguiente ejemplo encuentra la posición de la primera aparición de un asterisco en un array, buscando desde la posición 0.

  inicializa variable índice "i" a posición 0.
  
  mientras (el índice "i" esté dentro de rango y
            el elemento en la posición "i" del vector "v" no es un asterisco)
    incrementa la variable índice en 1.
  
  deja en "i" la posición donde se ha encontrado el asterisco, o "-1" si no
  se ha encontrado ningún asterisco.
  
  
  int i = 0;
  while (i < v.length && v[i] != '*')
    i++;
  
  // ! (i < v.length && v[i] != '*')
  // i >= v.length || i < v.length && v[i] == '*'        de Morgan
  
  if (i >= v.length) i = -1;
  
  

• Recordad que No es recomendable salir de bucles con "break", "continue", o "return".

• Las clases definen los métodos y atributos, ambos denominados campos ("fields") en el argot de Java, que tendrán los objetos (instancias) de la clase.

  Ejemplo:

  public class Vehículo {
    protected int ancho;
    protected int largo;
    protected int alto;
  
    /** Constructor por defecto */
    public Vehículo() { ancho = largo = alto = 0; }
  
    public Vehículo(int a, int l, int h) {
      ancho  = a;
      largo  = l;
      alto   = h;
    }
  
    /** Constructor de copia */
    public Vehículo(Vehículo v) {
      ancho = v.ancho;
      largo = v.largo;
      alto  = v.alto;
    }
  
    /** "Getter" */
    public int getDimension() { return ancho * largo * alto; }
  
    /** "Setter" */
    public void setAncho(int a) { ancho = a; }
  
    public boolean equals(Object o) {
      if (o == this) return true;
      if (o instanceof Vehículo) {
        Vehículo v = (Vehículo) o; // downcasting
        return ancho == v.ancho && largo == v.largo && alto == v.alto;
      } else return false;  // también si o == null
    }
  }
  
  

• Los objetos se crean en tiempo de ejecución con new. Las variables de tipo clase referencian objetos. Se puede cambiar el objeto al que referencia una variable mediante una asignación de ésta a otro objeto. El recolector de basura recogerá los objetos que no son referenciados por ninguna variable o posición de array, etc.

  EJERCICIO: Dibuja las variables, los objetos, y las flechas (referencias) entre variables y objetos que resultan de ejecutar el siguiente código:

  public static void main(String [] args) {
    Vehículo v1 = new Vehículo(10,10,10);
    Vehículo v2 = new Vehículo(20,20,20);
    Vehículo v3;
  
    v3 = v1;
    v1 = v2;
    v3 = new Vehículo(10,10,10);
  }
  
  

• Objetos, variables, referencias, e igualdad:

  public static void main(String [] args) {
    Vehículo v1 = new Vehículo(10,10,10);
    Vehículo v2 = v1;
  
    if (v1.equals(v2))  // cierto
      System.out.println("Los vehículos son iguales según equals");
  
    if (v1 == v2)       // cierto
      System.out.println("Las variables referencian el mismo objeto");
  
    v2 = new Vehículo(10,10,10);
  
    if (v1.equals(v2))  // cierto
      System.out.println("Los vehículos son iguales según equals");
  
    if (v1 == v2)       // falso
      System.out.println("Las variables referencian el mismo objeto");
  }
  
  

• En el argot técnico, se habla de identidad y estado de un objeto. Las variables referencian la identidad (generalmente la dirección de memoria donde está el objeto) mientras que los valores de los atributos (contenido) del objeto determinan su estado.

  El método 'equals' se usa para comparar el estado mientras que el operador '==' se usa para comparar identidades.

  Cuidado: para expresiones de tipo primitivo sólo puede usarse '=='.

  Véase http://www.javapractices.com/topic/TopicAction.do?Id=17

  Véase el libro de Timothy Budd or el de Joshua Bloch para saber más sobre la dificultad de programar el método 'equals'.

• El siguiente fragmento de código intercambia el valor de dos variables referencia utilizando una variable auxiliar:

  Vehículo x = new Vehículo(10,10,10);
  Vehículo y = new Vehículo(20,20,20);
  
  Vehículo tmp = x;    // código del intercambio ("swapping")
  x = y;
  y = tmp;
  
  

  El siguiente método que pretende reutilizar el código del intercambio no funciona:

  public static void swap(Vehículo a, Vehículo b) {
    Vehículo tmp = a;
    a = b;
    b = tmp;
  }
  
  public static void main(String [] args) {
    Vehículo x = new Vehículo(10,10,10);
    Vehículo y = new Vehículo(20,20,20);
  
    this.swap(x,y); // no funciona
  }
  
  

• Clases envoltorio ("wrapper classes") 'Integer', 'Character', 'Boolean', etc, y sus conversiones automáticas ("autoboxing", "boxing", "unboxing").

  Mira qué curioso:

  public static void main(String[] args) {
    Integer a, b;
  
    a = b = 3;
    System.out.println("Case 1: " + (a == b ? "equal" : "different"));
  
    a = 3;
    b = 3;
    System.out.println("Case 2: " + (a == b ? "equal" : "different"));
  
    a = b = 300;
    System.out.println("Case 3: " + (a == b ? "equal" : "different"));
  
    a = 300;
    b = 300;
    System.out.println("Case 4: " + (a == b ? "equal" : "different"));
  }
  
  

  Salida por pantalla:

  Case 1: equal
  Case 2: equal
  Case 3: equal
  Case 4: different
  
  

  EJERCICIO: ¿Qué está pasando? Consultad "5.1.7. Boxing Conversion" en [JLS'3E].

• La palabra reservada 'this' es una constante, no puede modificarse.

  Para recordar qué es 'this' analiza éstos fragmentos de código, algunos de los cuales compilan pero son incorrectos y otros directamente ni compilan.

  public class C {
    public int x;
  
    public C(int x) {
      this.x = x;
    }
  }
  
  

  public class C {
    public int x;
  
    public C(int y) {
      x = y;
    }
  }
  
  

  public class C {
    public int x;
  
    public C(int x) {
      x = x;
    }
  }
  
  

  public class C {
    public int x;
  
    public C(int x) {
      this.x = this.x;
    }
  }
  
  

  public class C {
    public int x;
  
    public C(C c2) {
      this = c2;
    }
  }
  
  

public class Automóvil { ... }

public class Alumno {
  private Automóvil a;
  ...
}

Un objeto de clase 'Alumno' "tiene-un" objeto de clase 'Automóvil' como atributo. En el ejemplo anterior el atributo es privado.

Diagrama de clases que usaremos en éste guión:

Alumno <>--- Automóvil
       U

U: Usa.

• Es-un
  
  • Un ejemplo típico:

    public class Vehículo { ... }
    public class Automóvil extends Vehículo { ... }
    
    

    Diagrama de clases que usaremos en éste guión:

     Vehículo
        ^
        | E
        |
    Automóvil
    
    E: Extiende.
    
    

    Un objeto de clase 'Automóvil' también "es-un" objeto de clase 'Vehículo'. La palabra clave "extends" dice que la clase 'Automóvil' extiende la clase 'Vehículo', la hace más específica aportando nuevos atributos o métodos (o también sobrescribiendo métodos).

    EJERCICIO: ¿Se pueden sobrescribir atributos en Java? Buscar la respuesta en en [JLS'3E].

  • Primera utilidad de la herencia: La herencia permite reusar código: un objeto de la clase 'Automóvil' tiene todos los atributos y métodos de la clase 'Vehículo' (a no ser que los sobrescriba). Veremos la otra gran utilidad en *Segunda utilidad de la herencia.
  • Hay muchos aspectos técnicos: subclase vs subtipo, leyes semánticas, monotonía, sobrescritura, reemplazo vs refinamiento, Principio de Sustitución de Liskov, co-varianza y contra-varianza, etc. Leed los libros de Timothy Budd y Bertrand Meyer.

• "Upcasting"
  
  • Mecanismo de compilación para convertir el tipo ("cast") yendo hacia arriba ("up") en la jerarquía de clases. La conversión la hace el compilador automáticamente. No es necesario que el programador escriba una expresíon de "casting".

    Más concretamente:

    • Se puede asignar un objeto de una subclase a una variable de tipo superclase:

      Vehículo v = new Automóvil();  // upcasting
      
      

      El tipo de una variable en tiempo de compilación es aquel con el que la variable ha sido declarada. En este ejemplo el tipo de 'v' es 'Vehículo'.

      Pero en tiempo de ejecución, al crearse el objeto con 'new' la variable 'v' referencia un objeto de clase 'Automóvil'.

      La línea compila porque el compilador ha realizado la conversión de tipo de forma automática en la asignación: a la derecha del '=' se tiene una expresión que evalúa a un objeto de tipo 'Automóvil' y a la izquierda se tiene una variable de tipo 'Vehículo'.

      Para el compilador, la variable 'v' es y será de tipo 'Vehículo'. El objeto no se ha convertido. De hecho, no existe pues se crea en ejecución.

      En tiempo de ejecución todo objeto almacena internamente una representación de su tipo.

    • La variable 'v' es una variable polimórfica: puede referenciar objetos de clase 'Vehículo' así como objetos de cualquiera de las subclases de 'Vehículo'.
    • También se puede hacer "upcasting" en el paso de parámetros. Por ejemplo, el siguiente método puede invocarse pasándole como parámetro un objeto de clase 'Automóvil':

      public void metodo(Vehículo v) { ... }
      
      

    • Un método puede devolver un objeto de la subclase cuando su tipo de retorno es la superclase:

      public Vehículo metodo() { return new Automóvil(); }
      
      

    • Se pueden combinar éstos dos aspectos. Supongamos que disponemos de los siguientes métodos:

      public Automóvil m1() { return new Automóvil(); }
      public Vehículo  m2() { return new Automóvil(); }
      public void      m3(Vehículo v) { ... }
      
      

      Los siguientes son todos "upcastings" válidos (asumid que 'o' es un objeto de la clase donde se definen los métodos 'm1', 'm2' y 'm3' anteriores):

      Vehículo v1 = o.m1();
      Vehículo v2 = o.m2();
      o.m3(new Automóvil());
      
      

  • ¿Para qué sirve el "upcasting"? Hay varios usos, pero el principal tiene que ver con el enlazado dinámico *Segunda utilidad de la herencia.

• "Downcasting"
  
  • Mecanismo de compilación para convertir el tipo ("cast") yendo hacia abajo ("down") en la jerarquía de clases. La conversión debe especificarla explícitamente el programador anotando el tipo deseado entre paréntesis (una expresión de "casting").
  • Supongamos que tenemos:

    public class Vehículo { ... }
    public class Automóvil extends Vehículo { ... }
    public class Aeroplano extends Vehículo { ... }
    
    

    Diagrama de clases:

          Vehículo
             ^
            / \
           /   \
    Automóvil  Aeroplano
    
    

    Veamos:

    Vehículo v = new Automóvil(); // upcasting
    
    Automóvil a1 = v;  // no compila
    
    

    Para convertir el tipo en tiempo de compilación deberíamos tener la garantía de que en tiempo de ejecución la variable 'v' referencia un objeto de clase 'Automóvil' y no de clase 'Aeroplano'.

    En este ejemplo se da el caso, pero en general en tiempo de compilación el compilador no puede determinar el tipo del objeto al que referenciará una variable en tiempo de ejecución. Más concretamente, un compilador no puede para todos los casos determinar los valores que tendrán las variables en tiempo de ejecución para todos los posible programas. ¡Para eso hay que ejecutar los programas! Esto es así variables de cualquier tipo.

    Es responsabilidad del programador indicar la conversión explícitamente. El "downcasting" es decirle al compilador "créeme, sé lo que hago".

    Si el programador se equivoca, puesto que el compilador no puede ayudarle, descubrirá su error en tiempo de ejecución.

  • Ejemplos de downcasting:

    Vehículo v   = new Automóvil(); // upcasting
    
    Automóvil a2 = (Automóvil) v;   // downcasting, compila y correcto
    
    Aeroplano p2 = (Aeroplano) v;   // downcasting, compila pero incorrecto
    
    

    Al ejecutar el programa el último "casting" lanzará la excepción 'ClassCastException'.

  • Java ofrece instanceof al programador para averiguar el "Run-Time Type Information" (RTTI), es decir, para preguntar el tipo en tiempo de ejecución del objeto. Como hemos dicho antes, los objetos almacenan una representación de su tipo.

    Vehículo v = new Automóvil(); // upcasting
    
    if (v instanceof Automóvil)
    
      Automóvil a = (Automóvil) v;
    
    else if (v instanceof Aeroplano)
    
      Aeroplano p = (Aeroplano) v;
    
    

    Pero 'instanceof' tiene dos limitaciones horribles:

    1. No fuerza a que la pregunta y la acción estén coordinadas. El siguiente código erróneo compila con consecuencias desastrosas al ejecutar:

       Vehículo v = new Automóvil(); // upcasting
       
       if (v instanceof Automóvil)
         Aeroplano p = (Aeroplano) v;
       
       

       En otros lenguajes sí se fuerza. Por ejemplo C++ ofrece un método genérico "dynamic cast" que recibe una clase y un objeto y pregunta si el objeto es una instancia de la clase. En caso positivo devuelve el objeto tras un casting a dicha clase. En caso negativo, devuelve null.

    2. Se pueden crear modularmente (sin tener que recompilar las clases ya compiladas) nuevas subclases de la superclase. Pero el código donde está "instanceof" no puede extenderse modularmente para tener en cuenta esos nuevos casos. Por cada nueva clase hay que editar el código, añadir nuevas ramas "if" y recompilar.

       Este problema se llama "Expression Problem" y hay soluciones, algunas muy buenas en otros lenguajes.

• Herencia múltiple y "Diamond of Death"
  
  • Herencia múltiple:

    public class Vehículo { ... }
    public class Automóvil extends Vehículo { ... }
    public class Aeroplano extends Vehículo { ... }
    public class Batmóvil  extends Automóvil, Aeroplano { ... }
      // La última línea no compila en Java
    
    

    Se produce el "Diamond of Death":

           Vehículo
              ^
             / \
            /   \
    Automóvil    Aeroplano
            \   /
             \ /
           Batmóvil
    
    

    Las clases 'Automóvil' y 'Aeroplano' heredarían los atributos y métodos públicos y protegidos de 'Vehículo'. ¿De quién los hereda 'Batmóvil' el atributo 'ancho' común a 'Vehículo', 'Automóvil' y 'Aeroplano'? Hay una ambigüedad que debe resolverse.

    Solución de Java: se introducen los interfaces para permitir herencia múltiple. Los interfaces no definene atributos ni código, unicamente nombres de métodos. Los veremos en *Clases, interfaces y herencia.

    Esta es la motivación principal de los interfaces, y no la separación entre especificación e implementación para TADs, aunque hay una relación débil, como veremos más adelante.

• Enlazado dinámico y sobrescritura
  
  • Segunda utilidad de la herencia
    
    • Ya vimos la Primera utilidad de la herencia.
    • La segunda utilidad es poder invocar un método sobre una variable polimórfica de forma que el método seleccionado dependa del tipo del objeto que referencia la variable en tiempo de ejecución.

      Un ejemplo:

      public static void main (String [] args) {
        Vehículo v[] = new Vehículo[3];
        v[0] = new Automóvil();
        v[1] = new Aeroplano();
        v[2] = new Barco();
      
        for (int i = 0; i < v.length; i++)
          v[i].display();    // dibuja el objeto en pantalla
      }
      
      

    • El objetivo es poder utilizar una variable de tipo superclase que referencie objetos de subclases (por tanto una variable polimórfica) e invocar un método sobrescrito en las subclases de forma que el comportamiento se adecúe a lo esperado para las subclases.

      El ejemplo asume que el método 'display' está definido en la clase 'Vehículo'. Supongamos que lo que dibuja es un cubo del tamaño de las dimensiones dadas por los atributos 'ancho', etc.

      Si las clases 'Automóvil', 'Aeroplano' y 'Barco' no sobrescriben el método 'display' para dibujar respectivamente un automóvil, un aeroplano y un barco, entonces en tiempo de ejecución se invocará el método 'display' heredado de 'Vehículo'. Es decir, se dibujarán tres cubo. Pero si todas sobrescriben adecuadamente el método 'display' entonces se dibujará respectivamente un automóvil, un aeroplano y un barco.

    • Si se añaden nuevas subclases a 'Vehículo' entonces se podrían almacenar en el vector objetos de las nuevas subclases. Pero habría que modificar las inicializaciones para almacenar los objetos y habría que recompilar. (Como en el caso de 'instanceof', se pueden añadir nuevas clases de forma modular pero el código ya escrito no puede extenderse de forma modular—sin utilizar trucos, claro.)
  • Terminología
    
    • Sobrescritura ("overriding"): Cuando una subclase redefine un método o atributo de una superclase. (Debe usarse la anotación "@Override" de Java sobre las cabeceras de los atributos y métodos sobrescritos.)
    • Hay que diferenciar la sobrescritura ("overriding") de la sobrecarga ("overloading"). No son lo mismo y es fundamental comprender la interacción entre ambas *Herencia y sobrecarga.
    • Enlazado dinámico ("dynamic dispatching"): Dada una variable que referencia un objeto, a través de la cual se accede a un atributo público o se invoca un método del objeto, qué atributo se accede y qué método se invoca está determinado por el tipo en tiempo de ejecución del objeto al que referencia la variable, no por el tipo con que ésta se declara en tiempo de compilación. Esto es así para atributos o métodos sobrescritos.

      Es decir, en

      Vehículo v = new Automóvil();
      v.display();
      
      

      El método 'display' invocado será el de la clase 'Automóvil' si dicho método se herada de 'Vehículo' y se sobrescribe en 'Automóvil'.

      Este concepto no tiene nada que ver con otro de similar nombre: el enlazado dinámico de librerías (dynamic linking).

      "Enlazado dinámico" no es la traducción más precisa del Inglés. Por un lado tenemos "dynamic dispatching (elegir la implementación de un método en tiempo de ejecución) y por otro dynamic binding (también llamado "late binding": asociar un nombre en tiempo de ejecución). "Bind" se suele traducir por "enlazar o asociar". En Java, la asociación del nombre del método se hace en tiempo de compilación pero la elección de la implementación del método se hace en tiempo de ejecución.

      Más concretamente, la asociación de un método a una variable polimórfica se fija en tiempo de compilación. Por ejemplo, 'v.display()' compila si el método 'display' está definido en la clase 'Vehículo'. En tiempo de ejecución se elige la implementación del método 'display' de la clase del objeto al que referencia 'v'.

  • No hay enlazado dinámico sin sobrescritura
    

    public class Vehículo {
      public void display() { ... }
    }
    public class Automóvil extends Vehículo {
      public int matrícula() { ... }  // método que no está en 'Vehículo'
    }
    
    

    Vehículo v = new Automóvil(); // upcasting
    v.display();     // compila, invoca el método 'display' heredado.
    v.matrícula();   // no compila: 'Vehículo' no tiene un método 'matrícula'
    
    Automóvil a = new Automóvil();
    a.display();    // compila, invoca el método 'display' heredado.
    a.matrícula();  // compila, invoca el método 'matrícula' de 'Automóvil'
    
    

    En 'v.display()' la variable 'v' almacena un 'Automóvil'. Por tanto se invoca al objeto 'Automóvil' el método heredado de 'Vehículo'. El comportamiento será el mismo que si en 'v' hubiera un objeto de clase 'Vehículo': se dibujará un cubo.

  • Enlazado dinámico con sobrescritura
    

    public class Vehículo {
      public void display() { ... }
    }
    public class Automóvil extends Vehículo {
      @Override
        public void display() { ... }   // sobrescribe el de 'Vehículo'
    
      public int matrícula() { ... }  // método que no está en 'Vehículo'
    }
    
    

    Suponemos que el método 'display' de 'Automóvil' se sobrescribe para que dibuje un automóvil.

    Vehículo v = new Automóvil(); // upcasting
    v.display();   // compila, invoca el método sobrescrito, no el heredado.
    v.matrícula(); // no compila, 'Vehículo' no tiene un método 'matrícula'
    
    Automóvil a = new Automóvil();
    a.display();    // compila, invoca el método sobrescrito, no el heredado.
    a.matrícula();  // compila, invoca el método 'matrícula' de 'Automóvil'
    
    

    En 'v.display()' la variable 'v' almacena un 'Automóvil'. Por tanto se invoca al objeto 'Automóvil' su método 'display' sobrescrito. La invocación 'v.display()' dibujará el automóvil.

    El comportamiento no es el mismo que si 'v' referenciara un 'Vehículo' pues en este caso se dibujaría un cubo. El comportamiento sí es el mismo que el de la invocación 'a.display()' posterior.

    • Repetimos: La idea es utilizar una variable de tipo superclase a la que se asignan objetos de subclases. A esa variable se le invoca un método común sobrescrito en las subclases.
  • ¿Se podría conseguir lo mismo usando "downcastings"?
    
    • Uno puede preguntarse si con "downcastings" sería suficiente y no haría falta el enlazado dinámico.

      public class Vehículo {
        public void display() { ... }
      }
      public class Automóvil extends Vehículo {
        @Override
          public void display() { ... }
      }
      public class Aeroplano extends Vehículo {
        @Override
          public void display() { ... }
      }
      
      

      La sobrescritura es necesaria para que el compilador acepte invocar el método 'display' a una variable de tipo 'Vehículo'.

      Podríamos pensar que con "downcastings" es suficiente:

      public static void main (String [] args) {
        Vehículo v[] = new Vehículo[2];
        v[0] = new Automóvil();
        v[1] = new Aeroplano();
      
        ((Automóvil)v[0]).display();  // dibuja un automóvil
        ((Aeroplano)v[1]).display();  // dibuja un aeroplano
      }
      
      

      El problema es que esto no nos permite escribir código uniforme. Por ejemplo no podemos invocar 'display' en un bucle:

      public static void main (String [] args) {
        Vehículo v[] = new Vehículo[2];
        v[0] = new Automóvil();
        v[1] = new Aeroplano();
      
        for (int i = 0; i < v.length; i++)
          ((¿QUE_CASTING_PONGO_AQUI?)v[i]).display();
      }
      
      

      El enlazado dinámico permite no tener que utilizar "downcastings".

  • Peligros con la herencia y el enalzado dinámico
    
    • El siguiente ejemplo ilustra el comportamiento del enlazado dinámico que puede llevar a confusión si no se conoce. Se tiene una clase 'Padre' con un método 'ricosuave' que invoca los métodos 'rico' y 'suave' de dicha clase. (Los alumnos nacidos después de 1990 probablemente no reconocerán la alusión a la "curiosa" canción del peculiar rapero Gerardo Mejía.) La clase 'Hijo' extiende la clase padre sobrescribiendo todos los métodos, refinándolos. La clase 'Main' crea objetos de clase 'Padre' y de clase 'Hijo'. La variable 'phijo' es de tipo 'Padre' pero referencia en ejecución un objeto de clase 'Hijo'.

      public class Padre {
      
        public void rico() {
          System.out.print("Rico. ");
        }
      
        public void suave() {
          System.out.print("Suave.");
        }
      
        public void ricosuave() {
          this.rico();
          this.suave();
        }
      }
      
      public class Hijo extends Padre {
      
        @Override
          public void rico() {
          System.out.print("Muy ");
          super.rico();
        }
      
        @Override
          public void suave() {
          System.out.print("Muy ");
          super.suave();
        }
      
        @Override
          public void ricosuave() {
          System.out.print("Muy ");
          super.ricosuave();
        }
      }
      
      public class Main {
        public static void main(String [] args) {
          Padre padre = new Padre();
          padre.ricosuave();
          System.out.println();
      
          Hijo hijo  = new Hijo();
          hijo.ricosuave();
          System.out.println();
      
          Padre phijo = new Hijo();
          phijo.ricosuave();
          System.out.println();
        }
      }
      
      

      La salida por pantalla no es:

      Rico. Suave.
      Muy Rico. Suave.
      Muy Rico. Suave.
      
      

      La salida por pantalla es:

      Rico. Suave.
      Muy Muy Rico. Muy Suave.
      Muy Muy Rico. Muy Suave.
      
      

      El comportamiento para 'hijo' y 'phijo' es el mismo, como cabe esperar por el enlazado dinámico.

      Esta es la traza de ejecución de la invocación hijo.ricosuave():

      • se muestra "Muy" por pantalla.
      • se invoca super.ricosuave()
        • se invoca this.rico() pero 'this' es el objeto al que referencia 'hijo' es decir, se invoca el método 'rico' de 'Hijo'.
          • se muestra "Muy" por pantalla.
          • se invoca super.rico()
          • se muestra "Rico" por pantalla.
        • se invoca this.suave() pero 'this' es el objeto al que referencia 'hijo' es decir, se invoca el método 'suave' de 'Hijo'.
          • se muestra "Muy" por pantalla.
          • se invoca super.suave()
          • se muestra "Suave" por pantalla.

• Herencia y sobrecarga
  
  • Un atributo está sobrecargado cuando aparece declarado con distinto tipo en la misma clase. En esta asignatura no usaremos atributos sobrecargados.
  • Un método está sobrecargado cuando aparece declarado en la misma clase con algún tipo distinto en sus parámetros. Por ejemplo:

    public class Vehículo {
      ...
      public int  display() { ... }
      public void display(Window w)  { ... }
    }
    
    

  • La sobrecarga de atributos y métodos se resuelve en tiempo de compilación. Para los métodos, la sobrecarga se resuelve en función del tipo de los parámetros del método.

    Cuando el programador escribe 'v.display(w)' con 'v' de tipo 'Vehículo' o subclase de 'Vehículo' entonces el compilador determina que tiene que invocarse el segundo método si 'w' es de clase 'Window' o de cualquier subclase de 'Window'.

    Si no puede resolverse la sobrecarga porque hay ambigüedad, entonces el el compilador indica el problema y el programa no compila correctamente.

  • La sobrescritura es una especie de sobrecarga que se resuelve trivialmente mediante el ámbito y el enlazado dinámico.

    public class Vehículo {
      public void display(Window w)  { ... }
    }
    
    public class Automóvil extends Vehículo {
      @Override
        public void display(Window w) { ... }
      public int  display() { ... }
    }
    
    

    Cuando el programador escribe 'v.display(w)', qué método se invoca depende del tipo del objeto al que referencia 'v' en tiempo de ejecución.

  • EJERCICIO: ¿Qué pasa si 'Automóvil' no sobrescribe el método 'void display(Window w)'?
  • EJERCICIO: ¿Qué pasa con la invocación 'v.display()' si 'v' es de tipo 'Vehículo' pero referencia un objeto 'Automóvil'?
  • La interacción entre sobrecarga y herencia complica la resolución de la sobrecarga:

    public class Vehículo {
      public int  display(Vehículo v)   { ... }
      public void display(Automóvil a)  { ... }
    }
    
    

    ¿Cómo se resuelve la sobrecarga en los siguientes casos (suponiendo que 'Automóvil' no sobrescribe ni sobrecarga 'display')?

    Vehículo  v = new Vehículo();
    Automóvil a = new Automóvil();
    v.display(v);
    v.display(a);
    
    Vehículo  v = new Automóvil();
    Automóvil a = new Automóvil();
    v.display(v);
    v.display(a);
    
    

  • Ejemplo de interacción entre sobrecarga y sobrescritura:

    public class Vehículo {
      public void chocar(Vehículo v) { ... }
    }
    
    public class Automóvil extends Vehículo {
      public void chocar(Automóvil a) { ... }
    }
    
    public class Main {
      public static void main (String args []) {
    
        Vehículo v  = new Automóvil();  /* upcasting */
        Automóvil a = new Automóvil();
    
        v.chocar(a);  // compila y
                      // ¡se invoca el método chocar heredado de 'Vehículo'!
      }
    }
    
    

    El método 'chocar' no está 'sobrescrito' en 'Automóvil', está sobrecargado, pues 'Automóvil' hereda 'chocar' de 'Vehículo' y tiene por tanto dos métodos 'chocar' que toman parámetros de distinto tipo.

    La sobrecarga se resuelve en tiempo de compilación: 'v' es de tipo 'Vehículo' (aunque referencia un objeto de tipo 'Automóvil'). El compilador determina que se invoca el 'chocar' de 'Vehículo', que en tiempo de ejecución es el 'chocar' que el objeto 'Automóvil' hereda de 'Vehículo'.

  • EJERCICIO: Probar y explicar lo que sucede al cambiar el código del 'main' anterior según distintas combinaciones:

    Vehículo v  = new Vehículo();
    Automóvil a = new Automóvil();
    v.chocar(a);
    a.chocar(v);
    
    

    Vehículo v1 = new Vehículo();
    Vehículo v2 = new Automóvil();
    v1.chocar(v2);
    v2.chocar(v1);
    
    

    Vehículo v1 = new Automóvil();
    Vehículo v2 = new Automóvil();
    v1.chocar(v2);
    v2.chocar(v1);
    
    

    Automóvil a = new Automóvil();
    Vehículo  v = new Automóvil();
    v.chocar(a);
    a.chocar(v);
    
    

    Automóvil a1 = new Automóvil();
    Automóvil a2 = new Automóvil();
    a1.chocar(a2);
    a2.chocar(a1);
    
    

    Vehículo v1 = new Automóvil();
    Vehículo v2 = new Automóvil();
    v1.chocar((Automóvil)v2);
    v2.chocar(v1);
    
    

  • Hay lenguajes en los que la herencia lleva pareja la "covarianza" del tipo de los parámetros de los métodos, que van hacia abajo en la jerarquía de interfaces/clases cuando éstos van hacia abajo. En Java no hay covarianza, pero si la hubiera:

    public class Vehículo {
      public void chocar(Vehículo v) { ... }
    }
    
    public class Automóvil extends Vehículo {
      /* hereda 'void chocar(Automóvil v)'
       * con el tipo del parámetro 'v' yendo hacia abajo en la jerarquía.
       */
    
      public void chocar(Automóvil v) { ... }
      /* ya no sería una sobrecarga sino una sobrescritura */
    }
    
    public class Main {
      public static void main (String args []) {
    
        Vehículo v  = new Automóvil();  /* upcasting */
        Automóvil a = new Automóvil();
    
        v.chocar(a);  // compila, enlazado dinámico, invoca el sobrescrito
      }
    }
    
    

  • EJERCICIO: ¿Permite Java la covarianza en el tipo del valor de retorno de un método?

    public class Vehículo {
       public Vehículo m() { ... }
    }
    
    public class Automóvil {
       public Automóvil m() { ... }
    }
    
    

    El método 'm' devuelve un objeto de tipo diferente, ¿se trata de sobrecarga, sobrescritura, puede el "upcasting" tener algo que ver aquí?

    Pista: ¿se toma en cuenta el tipo del valor de retorno del método en la resolución de la sobrecarga?

• Interfaces
  
  • Son conjuntos de cabeceras de métodos sin código.

    public interface Vehículo {
      public float  pesoKg() ;
      public String matricula() ;
      public void display();
    }
    
    

    A partir de esta sección 'Vehículo' es un interfaz, no una clase.

  • EJERCICIO: Buscar en [JLS'3E] si se permiten los modificadores de visibilidad 'protected' y 'private'.
  • Un interfaz puede extender ('extends') otros interfaces añadiendo nuevos métodos:

    public interface VehículoPesado extends Vehículo {
      public int taraKg();
    }
    
    

  • El interfaz 'VehículoPesado' tiene los métodos de 'Vehículo' más el método 'tara'.
  • EJERCICIO: Descubre qué pasa si 'VehículoPesado' redeclara una cabecera de método de 'Vehículo'. Busca en [JLS'3E] la explicación. Por ejemplo:

    public interface VehículoPesado extends Vehículo {
      public int taraKg();
      public void display();
    }
    
    

  • EJERCICIO: Descubre qué pasa si 'VehículoPesado' sobrecarga una cabecera de método de 'Vehículo'. Busca en [JLS'3E] la explicación. Por ejemplo:

    public interface VehículoPesado extends Vehículo {
      public int taraKg();
      public void display(Window w);
    }
    
    

  • No se pueden crear objetos de tipo interfaz: no hay código, no hay constructores.

    Vehículo v = new Vehículo(); // ¡Suspenso: Vehículo es un interfaz!
    
    

• Clases que implementan interfaces
  
  • Una clase puede extender ('extends') otra clase.
  • Una clase puede implementar ('implements') un interfaz, dando código para todos sus métodos. Por ejemplo:

    public class Automóvil implements Vehículo {
      private int ancho, alto, largo;
      private float pesoKg;
      private String matrícula;
      private float caballosVapor;
    
      public Automóvil(...) {
        ...
      }
    
      public float pesoKg()  { return pesoKg; }
    
      ... // etc
    }
    
    

  • La clase puede añadir más métodos de los listados en el interfaz. Y puede ser necesario sobrescribir los heredados de 'Object' tales como 'toString', 'equals', etc.
  • No es exacto decir que una clase "hereda" de un interfaz. Las clases sólo heredan de otras clases. Realmente las palabras adecuadas son "extender" para clases e "implementar" para interfaces.
  • Sin embargo, 'implements' satisface la relación "es-un" y son aplicables las nociones de "upcasting" y enlazado dinámico como veremos en la sección *Interfaces, herencia y enlazado dinámico.
  • Cuidado de no olvidarse de 'implements':

    public class Automóvil { ... }
    
    

    La siguiente línea no compila si 'Automóvil' no implementa vehículo (recordad que 'Vehículo' es un interfaz, no una clase):

    Vehículo v = new Automóvil();     // no compila, no hay "upcasting"
    
    

  • Cuidado: un interfaz puede ser implementado por "bazura":

    public class Bazura implements Vehículo {
      public float pesoKg() { return 120; }
    
      public String matrícula() { return "PitonisaTV"; }
    
      public void display() {
        System.out.println("Tú lo que ereh eh bazura");
      }
    }
    
    

    EJERCICIO; ¿Puede el compilador (o Eclipse) indicar si se trata de una implementación correcta? ¿Qué mecanismos puede ofrecer el lenguaje Java para que un compilador pueda indicar si una clase implementa un interfaz correctamente?

• Interfaces, herencia y enlazado dinámico
  
  • Entre la clase que implementa un interfaz y el interfaz hay una relación "es-un" y por tanto existe "upcasting".

    public interface Vehículo {
      public void display();   /* no hay código */
    }
    
    public class Automóvil implements Vehículo {
      public void display() { ... }  // implementa el método del interfaz.
      public int ccmotor()  { ... }  // método que no está en el interfaz.
    }
    
    

    Vehículo v = new Automóvil(); // upcasting
    v.display();           // compila, invoca el implementado en Automóvil.
    int i = v.ccmotor();   // no compila, el interfaz no tiene el método.
    
    Automóvil a = new Automóvil();
    a.display();           // compila, invoca el implementado en Automóvil.
    int i = a.ccmotor();   // compila, invoca el implementado en Automóvil.
    
    

  • Las estructuras de datos que veremos en la asignatura suelen consistir de uno o varios interfaces y de una o varias clases que los implementan.
  • EJERCICIO: Definir la clase 'Fórmula1' que extiende 'Automóvil'. ¿Puede dicha clase sobrescribir 'display'? En caso positivo, ¿cuál debería ser el comportamiento relativo al "upcasting" y el enlazado dinámico si 'v' de tipo 'Vehículo' almacena un objeto de clase 'Fórmula1'?

• Clases e interfaces genéricos
  
  • Las variables de tipo genéricas se usan para generalizar el tipo de los elementos de los TADs contenedores ("containers", nada que ver con los TADs concucharas). Por ejemplo, dados un interfaz para productos cartesianos de enteros y cadenas de caracteres:

    public interface Pair {
      public int    getX();
      public String getY();
      public void   putX(int x);
      public void   putY(String y);
      public void   replaceBy(Pair p);
    }
    
    

    y un interfaz para productos cartesianos de booleanos y enteros:

    public interface Pair {
      public boolean getX();
      public int     getY();
      public void    putX(boolean x);
      public void    putY(int y);
      public void    replaceBy(Pair p);
    }
    
    

    donde lo único que cambia son las declaraciones de tipo de los elementos componente, podemos generalizar y tener un único interfaz para cualquier par de tipos parámetro 'X' e 'Y':

    public interface Pair<X,Y> {
      public X    getX();
      public Y    getY();
      public void putX(X x);
      public void putY(Y y);
      public void replaceBy(Pair<X,Y> p);
    }
    
    

    Las variables 'X' e 'Y' son variables de tipo y son diferentes a las variables ordinarias (variables de valores) porque sólo pueden aparecer en una expresión de tipo: al declarar una clase, un interfaz, en el tipo de un atributo o de una variable local, en el tipo de un método, en el tipo de un parámetro de un método, etc.

    Las variables de tipo serán instanciadas a valores de tipo concretos (interfaces o clases no genéricas) en tiempo de compilación cuando se compile el código donde se crean objetos de clases que implementan el interfaz.

  • Las clases que implementan el interfaz también toman parámetros genéricos:

    public class CartesianPair<X,Y> implements Pair<X,Y> {
      private X x;
      private Y y;
    
      public CartesianPair(X x, Y y) {
        this.x = x;
        this.y = y;
      }
      public CartesianPair(Pair<X,Y> p) { // constructor de copia
        this.x = p.getX();  // no podemos acceder a p.x;
        this.y = p.getY();
      }
      public X getX() { return this.x; }
    
      public Y getY() { return this.y; }
    
      public void putX(X x) { this.x = x; }
    
      public void putY(Y y) { this.y = y; }
    
      public void replaceBy(Pair<X,Y> p) {
        this.x = p.getX();
        this.y = p.getY();
      }
    
      public String toString() {
        return "(" + this.x.toString() + " , " + this.y.toString() + ")";
      }
    
      public boolean equals(Object o) {
        if (o == this) return true;
        if (o instanceof Pair<?,?>) {
          Pair<X,Y> p = (Pair<X,Y>) o;
          return this.x.equals(p.getX()) && this.y.equals(p.getY());
        } else
          return false;  // también si o == null
      }
    }
    
    

    Gracias al "downcasting" al tipo interfaz y al uso de "getters" del mismo, el método 'equals' compara 'this' con un objeto 'o' de cualquier clase que implemente el interfaz 'Pair<X,Y>' para cualquier 'X' e 'Y'.

    La razón del "downcasting" a 'Pair<?,?>' en vez de a 'Pair<X,Y>' se debe a cómo se implementan los genéricos en Java ("type erasure").

    EJERCICIO: ¿Qué diferencia hay entre el constructor de copia y el método 'replaceBy'?

  • EJERCICIO: Investigar en [JLS'3E] si se permite la instanciación parcial y las posibles utilidades de ésta. Por ejemplo:

    public class WithString<X> implements Pair<String,X> {
     ...
    }
    
    

  • Al instanciar las variables de tipo a tipos concretos podemos tener pares de diversos tipos de elementos con un mismo interfaz.

    public static void main (String [] args) {
      Pair<Integer,Integer> pii = new CartesianPair<Integer,Integer>(3,0);
      Pair<Integer,String>  pis = new CartesianPair<Integer,String>(3,"Hola");
    
      pii.putY(3);
      pis.putY("Adios");
    
      int i    = pii.getY();
      String s = pis.getY();
    }
    
    

    El compilador garantiza que los tipos concuerdan:

    String i = pis.getX();  // no compila, error de tipos
    
    

    Los tipos básicos 'int', 'char', 'boolean', etc, no pueden ser parámetros de genéricos. Hay que usar las clases envoltorio ("wrapper classes") 'Integer', 'Character', 'Boolean', etc, y sus conversiones automáticas ("autoboxing").

    En el ejemplo anterior encontramos los siguientes autoboxing:

    • En 'pii.putY(3)' el entero 3 de tipo 'int' se mete ("boxing") en un nuevo objeto creado automáticamente de clase 'Integer'. Es como si hubiéramos escrito 'pii.putY(new Integer(3))'.
    • En 'int i = pii.getY()' el método 'getY' devuelve un objeto 'Integer' del que se saca ("unboxing") el entero de tipo 'int' que se asigna a 'i'. Es como si hubiéramos escrito 'pii.getY().intValue()' donde el método 'intValue' devuelve un valor de tipo 'int'.
  • ¿Cómo implementa Java los genéricos?

    Después de hacer la comprobación de tipos se hace "type erasure" (borrado de tipos): se sustituyen las variables genéricas por 'Object' y se introducen "upcastings" y "downcastings" automáticos. Es como si el interfaz que hubiésemos declarado fuera:

    public interface Pair {
      public Object getX();
      public Object getY();
      public void   putX(Object x);
      public void   putY(Object y);
      public void   replaceBy(Pair p);
    }
    
    

    También se reemplaza el parámetro genérico por 'Object' en las clases que implementan el interfaz, si las hubiera.

    public class CartesianPair implements Pair {
      private Object x;
      private Object y;
    
      public CartesianPair(Object x, Object y) {
        this.x = x;
        this.y = y;
      }
      public CartesianPair(Pair p) {
        this.x = p.getX();
        this.y = p.getY();
      }
      public Object getX() { return this.x; }
    
      public Object getY() { return this.y; }
    
      public void putX(Object x) { this.x = x; }
    
      public void putY(Object y) { this.y = y; }
    
      public void replaceBy(Pair p) {
        this.x = p.getX();
        this.y = p.getY();
      }
    
      public String toString() {
        return "(" + this.x.toString() + " , " + this.y.toString() + ")";
      }
    
      public boolean equals(Object o) {
        if (o == this) return true;
        if (o instanceof Pair) {
          Pair p = (Pair) o;
          return this.x.equals(p.getX()) && this.y.equals(p.getY());
        } else return false;  // también si o == null
      }
    }
    
    

    Ahora se entiende el "downcasting" a 'Pair<?,?>' en el código de la clase genérica. El tipo de los elementos 'X' e 'Y' desaparece. Por tanto un "downcasting" a 'Pair' es lo mismo que un "downcasting" a 'Pair<?,?>', no importa lo que sean 'X' e 'Y' pues sus valores se desconocen.

    El compilador introduce "castings" y "autoboxing" automáticos en el código donde se declaran y usan los objetos:

    public static void main (String [] args) {
      Pair pii = new CartesianPair(new Integer(3), new Integer(0));
      Pair pis = new CartesianPair(new Integer(3),"Hola");
    
      pii.putY(new Integer(3));
      pis.putY("Adios");
    
      int i    = ((Integer)pii.getY()).intValue();
      String s = (String)pis.getY();
    }
    
    

  • EJERCICIO: Se tiene una clase para cajas que contienen elementos genéricos:

    public class Box<X> {
      private X x;
    
      public Box()    { this.x = null; }
    
      public Box(X x) { this.x = x; }
    
      public X getX() { return this.x; }
    
      public void setX(X x) { this.x = x; }
    
      public boolean equals(Object o) {
        if (o == this) return true;
        if (o instanceof Box<?>) {
          Box<X> p = (Box<X>) o;
          return this.x == null && p.getX() == null ||
                 this.x != null && this.x.equals(p.getX());
        } else
          return false;  // también si o == null
      }
    }
    
    

    ¿Qué valor muestra por pantalla el siguiente código? ¿Os parece correcto? ¿En caso negativo, se os ocurre alguna manera de hacerlo correcto?

    public class Main {
      public static void main (String [] args) {
    
        Box<Integer> bi = new Box<Integer>();
        Box<String>  bs = new Box<String>();
    
        System.out.println("iguales:" + bi.equals(bs));
      }
    }
    
    

• Métodos genéricos
  
  • Java permite métodos genéricos, que usaremos en ocasiones en este guión:

    public class UnaClase {
      public <E> E identidad(E elem) { return elem; }
    }
    
    

    La clase no es genérica. El método sí lo es. Esto lo indica la aparición de '<E>' antes del tipo de retorno.

  • Se determina en tiempo de compilación el tipo del elemento en función del valor pasado al método. El mecanismo de resolución es el de la sobrecarga:

    public static void main(String [] args) {
      UnaClase u = new UnaClase();
    
      System.out.println(u.identidad(3).toString());       // E es Integer
      System.out.println(u.identidad("Hola").toString());  // E es String
    }
    
    

    Hay casos en los que puede haber ambigüedad en la sobrecarga, consultad [JLS'3E].

  • Otro ejemplo de método genérico últil:

    public <E> boolean eqNull(E e1, E e2) {
      return e1 == e2 || e1 != null && e1.equals(e2);
    }
    
    

    Este código podríamos haberlo usado en la clase CartesianPair<X,Y> cuyo método 'equals' no tiene en cuenta la posibilidad de que los valores de 'this.x', 'this.y', 'p.getX()' y 'p.getY()' sean null.

  • Un método genérico puede declararse dentro de una clase genérica:

    public class UnaClase<X> {
      public X getter();
      public <E> E identidad(E elem) { return elem; }
    }
    
    

  • Incluso se pueden especificar relaciones entre parámetros genéricos:

    public class UnaClase<X> {
      public X getter();
      public <E extends X> E identidad(E elem) { return elem; }
    }
    
    

    Para más detalles consultad [JLS'3E].

  • Los métodos genéricos pueden ser "static" para no tener que crear objetos y poder invocarlos usando directamente el nombre de clase. Las clases estáticas suelen usarse como colecciones de métodos.

    public class UnaClase {
      public static <E> E identidad(E elemento) { return e; }
    }
    
    

    public static void main(String [] args) {
    
      System.out.println(UnaClase.identidad(3).toString());
      System.out.println(UnaClase.identidad("Hola").toString());
    }
    
    

• Arrays genéricos
  
  • Estamos apañados
    
    • No pueden crearse en Java arrays de tipo genérico:

      public class ArraySolito<X> {
        private X [] xs;
      
        public ArraySolito(int size) {
          this.xs = new X[size];              // no compila
        }
      
        public void put(int i, X x) throws IndexOutOfBoundsException {
          if (i >= this.xs.length)
            throw new IndexOutOfBoundsException();
          else this.xs[i] = x;
        }
      
        public X get(int i) throws IndexOutOfBoundsException {
          if (i >= this.xs.length)
            throw new IndexOutOfBoundsException();
          else return this.xs[i];
        }
      }
      
      

      En Java el tipo "array de B" o 'B []' es subtipo de ("es-un") array de A o 'A []' si 'B' es subtipo de ("es-un") 'A'.

      Vehículo [] v = new Automóvil[20];  // upcasting
      
      

      Esta propiedad debe garantizarse en tiempo de ejecución, lanzándose 'ClassCastException' de no cumplirse. Pero debido al "type erasure" no puede garantizarse que un 'X []' "es-un" de algo, porque lo que hay es 'Object []' que no "es-un" más que de sí mismo.

    • Pero hay otras formas de crear los arrays que vemos a continuación.
  • Crear un array de 'Object' y hacer "downcasting"
    
    • Es lo más sencillo y bastante común:

      public ArraySolito(int size) {
        this.xs = (X []) new Object[size];
      }
      
      

      El "downcasting" es sólo para el compilador. En tiempo de ejecución 'this.xs' referencia un array de 'Object' y nos podemos llevar sorpresas.

      Supongamos que añadimos a la clase 'ArraySolito<X>' el método

      public X [] dameTodoTuAmol() {
        return this.xs;
      }
      
      

      Sorpresa, sorpresa:

      public class NoEraLoQueParecía {
        public static void main (String args []) {
      
          ArraySolito<String> as = new ArraySolito<String>(10);
          as.put(0,"hola");
      
          String [] as2 = as.dameTodoTuAmol();
        }
      }
      
      

      La última línea compila: según el código, 'dameTodoTuAmol' devuelve un array de 'String' porque 'X' se instancia a 'String'. Pero en ejecución se lanza la excepción 'ClassCastException' porque al ejecutar se devuelve un array de 'Object''. El error no se soluciona añadiendo un "downcasting" explícito de 'Object []' a 'String []', dicho "downcasting" es innecesario pues el compilador ya ha deducido que el método devuelve un array de 'String'.

      En ejecución lo que contiene el array son objetos 'String' y puede hacerse el "downcasting" sobre los elementos.

      public class EraLoQueParecía {
        public static void main (String args []) {
      
          ArraySolito<String> as = new ArraySolito<String>(10);
          as.put(0,"hola");
      
          Object [] as2 = as.dameTodoTuAmol();
      
          System.out.println( (String) as2[0] );
        }
      }
      
      

  • Usar 'Array.newInstance'
    
    • El método 'newInstance' de la clase 'Array' permite crear en tiempo de ejecución un array cuyo tipo lo especifica un objeto que representa una clase (API de reflexión). Aunque su cabecera dice que devuelve un array de 'Object' en tiempo de ejecución, realmente el array tiene objetos de la clase especificada. El problema es que se necesita saber el nombre de la clase de los elementos o bien tener un elemento al que pedirle su clase con el método 'getClass':

      this.xs = (X []) Array.newInstance("hola".getClass(),size);
      
      

      Pero en 'ArraySolito<X>' el tipo de los elementos no lo sabemos y el código anterior nos crea un array de 'String' siempre.

      Se puede postponer la creación del array hasta la primera llamada a 'put' pero esto nos complica el código al tener que considerar que un 'ArraySolito' puede no estar inicializado.

  • Usar 'Array.newInstance' pero pasar el tipo de la clase al constructor
    
    • El API de reflexión tiene objetos de clase 'Class<X>' que representan el tipo 'X' en tiempo de ejecución:

      import java.lang.reflect.Array;
      import java.util.Arrays;
      
      public class ArraySolito<X> {
        private X [] xs;
      
        public ArraySolito(int size, Class<X> clazz) {
          this.xs = (X []) Array.newInstance(clazz, size);
        }
      
        public void put(int i, X x) throws IndexOutOfBoundsException {
          if (i >= this.xs.length)
            throw new IndexOutOfBoundsException();
          else this.xs[i] = x;
        }
      
        public X get(int i) throws IndexOutOfBoundsException {
          if (i >= this.xs.length)
            throw new IndexOutOfBoundsException();
          else return this.xs[i];
        }
      
        public X [] dameTodoTuAmol() {
          return this.xs;
        }
      }
      
      

      Le pasamos al constructor en tiempo de ejecución un objeto 'clazz' que representa el tipo (la clase) de los elementos, es decir lo que sea 'X' que se ha borrado por "type erasure".

      El código principal ahora funciona porque en tiempo de ejecución sí se tiene un array de 'String':

      public class EraLoQueParecía {
        public static void main (String args []) {
      
          ArraySolito<String> as = new ArraySolito<String>(10,String.class);
          as.put(0,"hola");
      
          String [] as2 = as.dameTodoTuAmol();
        }
      }
      
      

public class ComplejoCart {
  private double re, im;

  public ComplejoCart(double re, double im) {
    this.re = re;
    this.im = im;
  }

  public ComplejoCart(double re) {  // real a complejo
    this.re = re;
    im      = 0.0;
  }

  public ComplejoCart(ComplejoCart c) { // constructor de copia
    re = c.getRe();
    im = c.getIm();
  }

  // "getters"

  public double getRe() { return re; }

  public double getIm() { return im; }

  public double getMod() {
    return ... // Aquí va una fórmula sobre 're' e 'im'
               // para obtener el módulo.
  }
  public double getAng() {
    return ... // Aquí va una fórmula sobre 're' e 'im'
               // para obtener el ángulo.
  }

  public ComplejoCart suma(ComplejoCart c) {
    return new ComplejoCart(this.re + c.getRe(), this.im + c.getIm()) ;
  }

  public ComplejoCart resta(ComplejoCart c) {
    return new ComplejoCart(this.re - c.getRe(), this.im - c.getIm()) ;
  }

  public String toString() {
    return new String("(" + this.re + ", " + this.im + ")");
  }

  public boolean equals(Object o) {
    if (o == this) return true;
    if (o instanceof ComplejoCart) {
      return this.re == c.getRe() && this.im == c.getIm();
      ComplejoCart c = (ComplejoCart) o; // downcasting
    } else
      return false;
  }
}

Los métodos 'suma' y 'resta' no modifican el objeto sobre el que se invocan, devuelven un objeto nuevo. Esta es la forma natural de operar con valores matemáticos:

public static void main(String [] args) {
  ComplejoCart c1 = new ComplejoCart(1.0, 2.0);
  ComplejoCart c2 = new ComplejoCart(2.0, 3.0);

  ComplejoCart c3 = c1.suma(c2);

  System.out.println(c3.toString());
}

Acorde con la implementación del método 'suma', 'c1' no queda modificado al invocarle el método 'suma' sino que el método devuelve un nuevo objeto de clase 'ComplejoCart' con la suma de los atributos de 'c1' y 'c2'. En el ejemplo hemos "guardado" (la referencia a) dicho objeto en otra variable 'c3'.

Observad además que no hay métodos "setters" para modificar el estado (los atributos) del objeto.

Los objetos cuyo estado no se modifica se llaman objetos inmutables. Las entidades matemáticas como los números se suelen implementar como objetos inmutables. Leed la discusión en los libros Timothy Budd, Bertrand Meyer y [EJ'01] sobre las ventajas e inconvenientes de los mismos.

Otros ejemplos de objetos inmutables son los de clase envoltorio (Integer, Boolean, etc.) y los de clase 'String'.

Los TADs no tienen por qué consistir de objetos inmutables. En esta sección estamos usando un ejemplo con objetos inmutables por comenzar por algo sencillo, pero el concepto de TAD es independiente de si los objetos que lo implementan son inmutables o no.

public ComplejoCart suma(ComplejoCart c) {
  return new ComplejoCart(this.re + c.re, this.im + c.im) ;
}

En la siguiente sección veremos la ventaja de usar "getters".

• El código fuente revela la implementación. El cliente de la clase (en este ejemplo, el programador del método 'main') no está interesado en conocer los detalles de implementación sino en crear objetos 'ComplejoCart' e invocarles métodos. Si le damos la clase pre-compilada en un ejecutable entonces el cliente no sabe qué métodos tiene que usar porque están en código binario. Habría que ofrecerle algún tipo de documentación (p.ej., Javadoc) aparte.
• Si deseamos cambiar a una implementación con representación polar de complejos mediante módulo y ángulo entonces tenemos que reescribir la clase entera, o definir otra 'ComplejoPolar'. Este sería el esquema de la implementación polar:

  public class ComplejoPolar {
    private double mod, ang;
  
    public ComplejoPolar(double mod, double ang) {
      this.mod = mod;
      this.ang = ang;
    }
  
    ... // aquí van más constructores
  
    public double getRe() { mod * Math.cos(ang) ; }
    public double getIm() { mod * Math.sin(ang) ; }
    public double getMod() { return mod; }
    public double getAng() { return ang; }
  
    public ComplejoPolar suma(ComplejoPolar c) {
      // la suma tiene un código diferente también.
    }
  
    ... // etc
  }
  
  

  ¡Cambia toda la implementación! Sin embargo el "cliente" de la clase (el código de 'main') cambiaría ligeramente:

  public static void main(String [] args) {
    ComplejoPolar c1 = new ComplejoPolar(...);  // nuevos constructores
    ComplejoPolar c2 = new ComplejoPolar(...);
  
    ComplejoPolar c3 = c1.suma(c2);
  
    System.out.println(c3.toString());
  }
  
  

  El cambio sería todavía menor si cada clase ofreciera métodos para transformar un cartesiano en polar y viceversa.

  EJERCICIO: ¿Ves en este ejemplo la desventaja de tener en Java los nombres de los constructores de una clase sobrecargados?

• No se pueden combinar implementaciones diferentes. Sería cómodo poder sumar un objeto 'ComplejoPolar' a un objeto 'ComplejoCartesiano' pues ambos son números complejos aunque cambie la representación.

public interface Complejo {

  /**  Devuelve la parte real */
  public double getRe();

  /** Devuelve la parte imaginaria */
  public double getIm();

  /** Devuelve el módulo */
  public double getMod();

  /** Devuelve el ángulo */
  public double getAng();

  /** Devuelve un nuevo Complejo haciendo la suma con 'c' */
  public Complejo suma(Complejo c);

  /** Devuelve un nuevo Complejo haciendo la resta con 'c' */
  public Complejo resta(Complejo c);

}

La semántica (es decir, la descripción precisa de qué debe hacer cada método) debe documentarse, bien informalmente mediante comentarios en lenguaje natural, en Javadoc, o mejor todavía, usando una notación formal.

public class ComplejoCart implements Complejo {

  ... // los atributos, constructores, y "getters" no cambian.

  public Complejo suma(Complejo c) {  // ¡ "Complejo" es un interfaz !
    return new ComplejoCart(this.re + c.getRe(), this.im + c.getIm()) ;
  }

  // ... tampoco cambia toString

  public boolean equals(Object o) {
    if (o == this) return true;
    if (o instanceof Complejo) {
      Complejo c = (Complejo) o;       // ¡downcasting al interfaz!
      return this.re == c.getRe() && this.im == c.getIm();
    } else return false;
  }
}

Los métodos 'suma' y 'resta' toman como parámetro un objeto de cualquier clase que implementa el interfaz Complejo. Por tanto, la implementación de dichos métodos debe tener ésto en cuenta. Por ejemplo, el parámetro 'c' del método 'suma' o bien es null (no hay que olvidarse nunca de null, en nuestro ejemplo que se lance 'NullPointerException' es razonable) o bien referencia un objeto de una clase que implementa el interfaz Complejo. Por otro lado, el método 'suma' devuelve un objeto de una clase que implementa el interfaz Complejo.

De igual manera, una declaración 'Complejo c1' lo que dice es que 'c1' almacenará o bien null o bien una referencia a un un objeto de una clase que implementa el interfaz Complejo. Recordad:

Complejo c1 = new Complejo();   ¡ suspenso !

No tiene sentido y no compila. *Clases, interfaces, y herencia.

Gracias al uso de "getters", tanto el constructor de copia, como el método 'suma' y el método 'equals' funcionan cuando 'c' es un objeto de cualquier clase que implemente el interfaz. Observad que en 'equals' el "downcasting" se hace de 'Object' a 'Complejo', que es un interfaz, no una clase.

public static void main(String [] args) {
  Complejo c1 = new ComplejoCart(1.0, 2.0);
  Complejo c2 = new ComplejoPolar(8.4, 60.0);

  Complejo c3 = c1.suma(c2);

  System.out.println(c3.toString());

  System.out.println(c2.suma(c1).toString());
}

Las variables que utilizamos son de tipo interfaz pero en tiempo de ejecución referencian objetos de clases que implementan el interfaz.

La "librería" o paquete de números complejos consta de un interfaz y dos clases. El cliente de la librería sólo tiene que conocer cuáles son y qué hacen los métodos del interfaz, así como los nombres de las clases y los constructores. El resto de detalles de implementación no son necesarios.

Observad que 'c1.suma(c2)' es un objeto de clase 'ComplejoCart' mientras que 'c2.suma(c1)' es un objeto de tipo 'ComplejoPolar'.

Volvamos a la clase 'ComplejoCart'. En la siguiente versión modificamos el código del método 'suma' para que sólo sume con objetos de la clase 'ComplejoCart', accediendo directamente a los atributos de la case vía "downcasting":

public class ComplejoCart implements Complejo {

  ...

  public Complejo suma(Complejo c) throws IllegalArgumentException {
    if (c instanceof ComplejoCart)

       return new ComplejoCart( this.re + ((ComplejoCart)c).re
                              , this.im + ((ComplejoCart)c).im );

    else

       throw new IllegalArgumentException();
  }

}

"Separar por medio de una operación intelectual las cualidades de un objeto para considerarlas aisladamente o para considerar el mismo objeto en su pura esencia o noción." (Diccionario de la Real Academia Española, 22ª edición)

• La función se describe mediante un interfaz (p.ej., un interfaz de Java) y una especificación del comportamiento (semántica o contrato) que suele darse bien en lenguaje natural, bien en una notación semiformal (p.ej., Javadoc), bien en una notación formal (p.ej., lógica de orden superior).
• La estructura/representación interna se describe en una implementación (p.ej., una clase de Java) que realiza la funcionalidad acorde al contrato.

• Encapsulación (ocultación de información): sólo es necesario conocer la función, la estructura puede quedar oculta.

  Ejemplo: el cliente de un TAD sólo necesita conocer los interfaces y los nombres y constructores de las clases que implementan los interfaces. Los detalles de implementación de las clases pueden quedar ocultos.

• Independencia de la representación: la misma función puede ser realizada por diferentes representaciones. Por ejemplo, el interfaz puede ser implementado por distintas clases.
• Modularidad: un módulo o cápsula realiza una funcionalidad. Debe tener alta cohesión (ser autocontenido) y bajo acoplamiento (no depender de cambios en otros módulos).

Por ejemplo, los enteros son un TAD. Son un conjunto de datos cuya representación interna en la máquina no conocemos y que tienen una serie de operaciones (suma, resta, división, etc.) donde cada una cumple propiedades (conmutativa, distributiva, etc.).

Pero esto no es siempre así. Hay interfaces que por los parámetros que toman los métodos sugieren una implementación concreta y un cambio implica cambiar el interfaz: "interface coupling".

Ejemplo:

public class Main {
  public static void main (String[] args) {
    Complejo c = new ComplejoCart(3.32, 5.21);
    Complejo s = c.suma(c);
  }
}

Para cambiar a representación polar hay que cambiar el constructor 'ComplejoCart' por 'ComplejoPolar' y recompilar.

Existen patrones de diseño para solucionar este problema, como el patrón factoría. La idea es de nuevo usar encapsulación. Se puede crear una clase intermedia que hace las veces de "interfaz" para los constructores.

Ejemplo: lista de la compra escrita con un editor de textos. Se puede insertar un elemento en cualquier posición de la lista, por ejemplo entre otros dos elementos. La lista no tiene por qué estar ordenada.

Primero nos centramos en el interfaz y en el uso del mismo, ilustrando así la importancia y los beneficios de la abstracción de datos: escribiremos código que usa el interfaz de listas de posiciones sin saber realmente cómo se implementan dichas listas.

Observamos que la inserción, búsqueda y borrado de elementos usando índices puede ser costosa y complicada de usar:

list.insert(0, "vais");        // ["vais"]

list.insert(1, "a");           // ["vais", "a"]

list.insert(2, "aprobar");     // ["vais", "a", "aprobar"]

list.insert(0, "no");          // ["no", "vais", "a", "aprobar"]

list.set(3, "suspender");      // ["no", "vais", "a", "suspender"]

list.remove(2);                // ["no", "vais", "suspender"]

list.set(1, "quiero");         // ["no", "quiero", "suspender"]

Los métodos 'insert', 'remove' y 'set' tienen que posicionarse en el nodo con número correspondiente, y el programador debe recordar y llevar actualizada la correspondencia entre números y nodos. Además está el tema del control de rango, p.ej., 'list.set(200,"Fuera de rango")'.

• Interrogadores: 'size', 'isEmpty'.
• Acceso ("getters"): 'first', 'last', 'next' y 'prev'. Permiten moverse por las posiciones de la lista. Devuelven 'null' si no existe el nodo al que se pretende acceder. De esta forma se puede usar null como valor centinela en bucles *Recorridos de listas de posiciones.
• Inserción: 'addFirst', 'addLast', 'addBefore' y 'addAfter'.
• Borrado: 'remove' borra una posición, dejando las otras posiciones "conectadas".
• Modificación: 'set' modifica el elemento de una posición.
• Conversión: el método 'toArray' devuelve un vector (array) con los elementos de la lista en el mismo orden posicional de izquierda a derecha. Devuelve un vector de 'Object' *Arrays genéricos.

Por defecto, todos los interfaces que veremos en la asignatura asumen copia superficial, dejando al usuario del interfaz la responsabilidad de hacer copias profundas. Para poder hacer copia profunda los objetos elemento deben tener constructor de copia (o el método 'clone', si bien el uso de dicho método es cuestionado, ved por ejemplo http://www.javapractices.com/topic/TopicAction.do?Id=71).

El uso de copia superficial puede ser problemático ya que la referencia al objeto elemento podría estar compartida. A este problema se le llama "aliasing".

Por ejemplo, supongamos que insertamos un mismo contacto en dos listas distintas.

Contacto c = new Contacto("LuisMi");

list1.addFirst(c);
list2.addFirst(c);

c.setName("LuisMa");

Ambas listas comparten el mismo elemento que ha quedado modificado desde "fuera" de la lista.

Además, el elemento puede modificarse desde "dentro" de la primera lista quedando también modificado en la segunda:

Contacto c = new Contacto("LuisMi");

list1.addFirst(c);
list2.addFirst(c);

list1.first().element().setName("Luisito");

Para evitar alias el usuario del interfaz debe hacer copia profunda explícita con el constructor de copia:

Contacto c = new Contacto("LuisMi");

list1.addFirst(new Contacto(c));
list2.addFirst(new Contacto(c));

c.setName("LuisMa");
list1.first().element().setName("Luisito")

Ahora 'c' referencia un objeto "LuisMa", el primer elemento de 'list1' referencia un objeto "Luisito" y el primer elemento de 'list2' referencia un objeto "LuisMi".

• Disponemos del *Interfaz Position<E> y del *Interfaz PositionList<E> documentado con lo que hace cada método.
• Se nos dice que disponemos de una clase que implementa el interfaz. De momento desconocemos los detalles de dicha clase (los veremos más adelante), y como clientes del interfaz, realmente no nos interesan. Nos basta con conocer los constructores. Se nos dice que hay un constructor que crea una lista vacía (sin nodos).

PositionList<String> list = new NodePositionList();  // lista vacía

Position<String> cursor;          // cursor a nodos

list.addFirst("vais");            // ["vais"]

list.addLast("a");                // ["vais", "a"]

list.addLast("aprobar");          // ["vais", "a", "aprobar"]

list.addFirst("no");              // ["no", "vais", "a", "aprobar"]

cursor = list.last();

list.set(cursor, "suspender");    // ["no", "vais", "a", "suspender"]

cursor = list.prev(cursor);

list.remove(cursor);              // ["no", "vais", "suspender"]

cursor = list.prev(list.last());

list.set(cursor, "quiero");       // ["no", "quiero", "suspender"]

El programador tiene que seguir llevando cuenta de dónde está cada elemento, pero no es necesario recordar la correspondencia entre nodos e índices. Además, los métodos no tienen que empezar a operar desde el comienzo o el fin de la lista sino desde la posición dada.

• Observad el uso de 'null' como posición centinela en la condición del bucle. Observad que usamos *Métodos genéricos en los ejemplos.

  // con bule while
  
  public static <E> void show(PositionList<E> list) {
    Position<E> cursor = list.first();
    while (cursor != null) {
      System.out.println(cursor.element());
      cursor = list.next(cursor);
    }
  }
  
  
  // con bucle for
  
  public static <E> void show(PositionList<E> list) {
    for (Position<E> cursor = list.first();
         cursor != null;
         cursor = list.next(cursor))
      System.out.println(cursor.element());
  }
  
  

  Nota: éstos métodos son estáticos y genéricos porque no están dentro de la clase que implementa el interfaz.

• Se recorren las listas de forma secuencial usando bucles y nodos cursor.
• La inicialización consistirá en hacer que el cursor referencie la primera (o la última) posición de la lista. Si la lista está vacía entonces el cursor será null.
• La condición de parada (la contraria de la de continuación) del bucle la marca el problema, pero suele incluir la condición de control de rango: el cursor debe ser distinto de null.
• El incremento consistirá en avanzar el cursor a la siguiente (o anterior) posición.
• En la práctica se usan *Iteradores para recorrer listas, pero para entender cómo funcionan tenemos que aprender a recorrer listas mediante cursores. Un iterador es una abstracción de un cursor.
• Cuidado: en ocasiones 'cursor.element().equals(x)' puede ser preferible a 'x.equals(cursor.element())'. Hay que tener en cuenta si la lista puede contener elementos null, y si los elementos a comparar (los 'x') pueden ser null. Si la lista no contiene elementos null entonces 'cursor.element().equals(x)' es seguro. En otro caso 'cursor.element() != null && cursor.element().equals(x)' es seguro.

• El siguiente método toma como argumento una lista 'list' y dos elementos 'a' y 'e'. El método añade a la lista el elemento 'a' antes de la primera aparición en la lista del elemento 'e'. Si 'e' no está en la lista entonces el método deja la lista intacta:

  public static <E> void addBeforeElement(PositionList<E> list, E e, E a) {
      Position<E> cursor;
      for (cursor = list.first();
           cursor != null && !cursor.element().equals(e);
           cursor = list.next(cursor))
         ;
      // cursor == null || cursor != null && cursor.element().equals(e);
      if (cursor != null) list.addBefore(cursor,a);
    }
  }
  
  

• Recordad: antes de borrar hay que avanzar.

  public static <E> void deleteAll(E elem, PositionList<E> list) {
    Position<E> cursor = list.first();
    while (cursor != null) {
      if (cursor.element().equals(elem)) {
        Position<E> borrar = cursor;
        cursor = list.next(cursor);       // avanza
        list.remove(borrar);              // borra
      } else
        cursor = list.next(cursor);       // avanza
    }
  }
  
  

• Variante que invoca 'list.next' una vez:

  public static <E> void deleteAll(E elem, PositionList<E> list) {
    Position<E> cursor = list.first();
    while (cursor != null) {
      Position<E> nxt = list.next(cursor);  // avanza
      if (cursor.element().equals(elem))
        list.remove(cursor);                // borra
      cursor = nxt;
    }
  }
  
  

• Variantes del condicional anterior que no funcionan:

  if (cursor.element().equals(elem)) {
     list.remove(cursor);
     cursor = list.next(cursor);      // IllegalArgumentException
  } ...
  
  
  if (cursor.element().equals(elem)) {
     cursor = list.next(cursor);
     list.remove(list.prev(cursor));  // IllegalArgumentException
  } ...
  
  
  if (cursor.element().equals(elem)) {
    Position<E> borrar = cursor;
    list.remove(cursor);
    cursor = list.next(borrar);       // IllegalArgumentException
  } ...
  
  

• Usar un contador de elementos recorridos no es necesario y puede ser peligroso dependiendo del problema a resolver:

  // no funciona
  public static <E> void show(PositionList<E> list) {
    for (int i = 0; i < list.size(); i++)
      System.out.println(cursor.element());
  }
  
  
  // redundante
  public static <E> void show(PositionList<E> list) {
    Position<E> cursor = list.first();
    for (int i = 0; i < list.size(); i++) {
      System.out.println(cursor.element());
      cursor = list.next(cursor);
    }
  }
  
  // redundante y no funciona
  public static <E> void deleteAll(E elem, PositionList<E> list) {
    Position<E> cursor = list.first();
    int i = 0;
    while (i < list.size()) {
      Position<E> nxt = list.next(cursor);
      if (cursor.element().equals(elem))
        list.remove(cursor);
      cursor = nxt;
      i++;
    }
  }
  
  

• El siguiente método toma como parámetros dos listas y devuelve una nueva lista con los elementos de las dos listas intercalados hasta terminar de recorrer la lista más pequeña. Si alguno de los parámetros es null o referencia una lista vacía entonces el método devuelve una nueva lista vacía.

  public static <E> PositionList<E> shuffleShorter(PositionList<E> list1,
                                                   PositionList<E> list2) {
  
    PositionList<E> result = new NodePositionList<E>();
  
    if (list1 == null || list2 == null || list1.isEmpty() || list2.isEmpty())
      return result;
  
    Position<E> cursor1 = list1.first();
    Position<E> cursor2 = list2.first();
  
    while (cursor1 != null && cursor2 != null) {
      result.addLast(cursor1.element());
      result.addLast(cursor2.element());
      cursor1 = list1.next(cursor1);
      cursor2 = list2.next(cursor2);
    }
  
    return result;
  }
  
  

• EJERCICIO: Modificar el código para que añada al final de la lista resultado los elementos sobrantes de la lista de mayor tamaño. Hay que modificar también la condición frontera: si una lista es null o vacía y la otra no entonces el método debe devolver una copia de la lista no null y no vacía.

• El siguiente método toma una lista y devuelve una nueva lista con los elementos de la primera en orden inverso. Si la lista parámetro es null entonces el método devuelve null. Si la lista parámetro es vacía entonces el método devuelve una nueva lista vacía.

  public static <E> PositionList<E> reverseList(PositionList<E> list) {
    if (list == null) return null;
    PositionList<E> result = new NodePositionList<E>();
    if (list.isEmpty()) return result;
  
    Position<E> cursor = list.first();
    while (cursor != null) {
      result.addFirst(cursor.element());
      cursor = list.next(cursor);
    }
  
    /* Otra posibilidad es recorrer la lista de derecha a izquerda:
  
    Position<E> cursor = list.last();
    while (cursor != null) {
      result.addLast(cursor.element());
      cursor = list.prev(cursor);
    }
  
    */
  
    /* Podemos en ambos casos usar un bucle for, por ejemplo:
  
       for (Position<E> cursor = list.last();
            cursor != null;
            cursor = list.prev(cursor))
         result.addLast(cursor.element());
    */
  
    return result;
  }
  
  

• El siguiente método invierte los elementos de la lista parámetro directamente sin devolver una nueva lista. Usa los métodos 'remove' y 'addFirst' y por tanto borra nodos (no todos) de la lista y crea nuevos nodos. Recorre la lista desde el final.

  public static <E> void reverseInPlace(PositionList<E> list) {
    if (list != null && !list.isEmpty() && list.size() > 1) {
      Position<E> cursor = list.last();
      Position<E> end    = list.first();
      while (cursor != end) {
        Position<E> prv = list.prev(cursor);
        E element       = list.remove(cursor);
        list.addFirst(element);
        cursor = prv;
      }
    }
  }
  
  

  La condición frontera 'list.size() > 1' se añade por claridad, el código funciona igualmente sin ella.

  Si modificamos el código anterior para recorrer la lista desde el principio el resultado es erróneo, tanto si se usa 'addFirst' como 'addLast'.

  public static <E> void reverseInPlace(PositionList<E> list) {
    if (list != null && !list.isEmpty() && list.size() > 1) {
      Position<E> cursor = list.first();      // MAL
      Position<E> end    = list.last();
      while (cursor != end) {
        Position<E> nxt = list.next(cursor);  // MAL
        E element       = list.remove(cursor);
        list.addLast(element);                // MAL
        cursor = nxt;
      }
    }
  }
  
  

• Una versión correcta que recorre la lista desde el principio. Usa 'addAfter' sobre el último nodo.

  public static <E> void reverseInPlace(PositionList<E> list) {
    if (list != null && list.isEmpty() && list.size() > 1) {
      Position<E> cursor = list.first();
      Position<E> end    = list.last();
      while (cursor != end) {
        Position<E> nxt = list.next(cursor);
        E element = list.remove(cursor);
        list.addAfter(end, element);
        cursor = nxt;
      }
    }
  }
  
  

• Una versión alternativa que surge de observar en la solución anterior que el nodo a borrar (el que referencia 'cursor') siempre es el primero, y que despúes del borrado la variable 'cursor' referencia el objeto que referencia 'nxt', que siempre es el primero. Por tanto 'cursor' y 'nxt' no son necesarios y se puede usar directamente 'list.first()'.

  public static <E> void reverseInPlace(PositionList<E> list) {
    if (list != null && list.isEmpty() && list.size() > 1) {
      Position<E> end = list.last();
      while (list.first() != end) {
        list.addAfter(end, list.first().element());
        list.remove(list.first());
      }
    }
  }
  
  

• Esta versión invierte los elementos de la lista sin crear nodos nuevos. Modifica los elementos de los nodos existentes.

  public static <E> void reverseSwap(PositionList<E> list) {
    if (list != null && list.isEmpty() && list.size() > 1) {
      Position<E> start = list.first();
      Position<E> end   = list.last();
      while (start != end) {
        // swap elements
        E tmp = start.element();
        list.set(start,end.element());
        list.set(end,tmp);
        // move
        if (list.next(start) == end)
          start = end;
        else {
          start = list.next(start);
          end   = list.prev(end);
        }
      }
    }
  }
  
  

• El siguiente método borra de una lista desde el nodo número 'i' hasta el nodo número 'j'. Los nodos se numeran de 0 a list.size()-1.

   public static <E> void removeRange(PositionList<E> list,
                                      int i,
                                      int j)
     throws InvalidArgumentException {
  
     if (! (0 <= i && i <= j && j < list.size()) )
         throw new IllegalArgumentException("Invalid range");
  
     if (list != null && !list.isEmpty()) {
       Position<E> cursor = list.first();
       int pos = 0;
       while (pos != i) {  // posicionarse
         cursor = list.next(cursor);
         pos++;
       }
       while (pos <= j) {  // borrar
         Position<E> nxt = list.next(cursor);
         list.remove(cursor);
         cursor = nxt;
         pos++;
      }
    }
  }
  
  

• La siguiente variación se posiciona y borra en un único bucle:

   public static <E> void removeRange(PositionList<E> list,
                                      int i,
                                      int j)
     throws InvalidArgumentException {
  
     if (! (0 <= i && i <= j && j < list.size()) )
         throw new IllegalArgumentException("Invalid range");
  
     if (list != null && !list.isEmpty()) {
       Position<E> cursor = list.first();
       int pos = 0;
       while (pos <= j) {
         Position<E> nxt = list.next(cursor);
         if (pos >= i) list.remove(cursor);
         cursor = nxt;
         pos++;
      }
    }
  }
  
  

• El siguiente método modifica una lista para quedarse con los 'size' primeros nodos. Si 'size' es negativo deja la lista intacta. Si 'size' es 0 entonces deja la lista vacía. Si size es mayor que el tamaño de la lista entonces deja la lista intacta. El método recorre la lista desde el final para dejar los 'size' primeros nodos en la lista.

  public static <E> void trimToSize(PositionList<E> list, int size) {
    if (list != null && !list.isEmpty() && size >= 0 && size < list.size()) {
      Position<E> cursor = list.last();
      size = list.size() - size;
      while (size > 0) {
        Position<E> prv = list.prev(cursor);
        list.remove(cursor);
        cursor = prv;
        size--;
      }
    }
  }
  
  

interface PositionList<E> <>-- U -- interface Position<E>
       ^                                 ^
       |                                 |
     I |                                 | I
       |                                 |
class NodePositionList<E> <>-- U -- class Node<E>

• U: Usa. I: Implementa.

• La clase de los objetos nodo de la lista.
• La clase implementa el interfaz 'Position<E>' y por tanto provee código para el método 'element' declarado en dicho interfaz.
• Atributos:
  • 'owner' es un entero que identificará unívocamente la lista a la que pertenece el nodo. Está declarado como 'final', lo que significa que una vez inicializado su valor por el constructor ya no podrá modificarse.
  • 'prev' y 'next' son respectivamente referencias al nodo previo y al nodo siguiente en la lista.
  • 'elem' referencia el elemento que se almacena en el nodo.
• La clase provee un constructor y también "getters" y "setters" para 'prev', 'next' y 'elem'. (El método 'element' es el "getter" de 'elem'.)
• Intencionalmente, no hay constructor de copia ni se sobrescribe 'equals'.
• No hay "setter" para 'owner' ya que este atributo no puede modificarse al ser declarado como 'final'.
• No hay "getter" para 'owner'. Solamente un objeto nodo puede determinar usando el método 'kinOf' si otro objeto nodo tiene el mismo 'owner' ("kin" significa "pariente" en Inglés). Por ejemplo, dado un nodo 'n1' distinto de null y un nodo 'n2', la invocación 'n1.kinOf(n2)' indicará si 'n1' y 'n2' tienen el mismo valor de 'owner'.
• Los "setters" 'setPrev' y 'setNext' de los atributos 'prev' y 'next' pueden tomar como parámetros válidos tanto el valor null como una referencia a un nodo con el mismo 'owner'. En otro caso lanzan la excepción 'IllegalArgumentException'. (¿Qué pasa si el nodo parámetro es 'this'?)

  Como veremos en la *Clase NodePositionList<E>, permitir null tiene sentido si queremos borrar un nodo de la lista desenlazándolo de su nodo previo y de su nodo siguiente poniendo 'next' y 'prev' a null. Por otro lado el constructor también permite que los parámetros que se le pasan sean null. Uno de los constructores de la clase 'NodePositionList<E>' tiene que crear un nodo con un atributo temporalmente a null para poder enlazar los nodos centinela.

• EJERCICIO: ¿Podríamos usar la clase 'Node<E>' para implementar cadenas simplemente enlazadas? En caso positivo, ¿cómo se haría?

• Tiene tres atributos: el tamaño o número de nodos de la lista, representado mediante un entero, y los dos nodos centinela 'header' y 'trailer' que no almacenan elementos y son usados para marcar el principio y el fin de la lista.

  El propósito de los nodos centinela es que al insertar/borrar siempre haya un nodo previo y otro siguiente al que enlazar/desenlazar. El código de inserción/borrado (métodos 'addFirst', 'addBefore', 'remove', etc.) resulta más sencillo y uniforme que si tuviéramos referencias al primer y último nodo útiles. Por ejemplo, cuando se inserta un nodo por primera vez, el nodo previo es el 'header' y el nodo siguiente es el siguiente al 'header' que en esta ocasión es el nodo 'trailer'. Si inmediatamente después se inserta otro nodo al principio de la lista, de nuevo el nodo previo es el 'header' y el nodo siguiente es el siguiente al 'header' que en esta ocasión es el nodo insertado anteriormente.

• El tamaño de la lista está acotado por la memoria disponible, en concreto, por la memoria dinámica disponible para crear nuevos objetos nodo en los métodos de inserción 'addFirst', etc.
• Idealmente el tipo del atributo 'size' debería ser concordante con la memoria dinámica disponible. Hemos considerado que 'int' es suficiente. En Java 'int' es un entero de 32 bits con valor máximo 2.147.483.647. Para los propósitos de esta asignatura es suficiente. También está disponible el tipo 'long' de enteros de 64 bits cuyo valor máximo es 9.223.372.036.854.775.807. La memoria dinámica disponible depende de la arquitectura y de otros factores circunstanciales como el número de procesos ejecutándose, etc. La correspondencia entre 'size' y la memoria dinámica (número de nodos que podemos insertar) no es una cuestión meramente teórica. Los enteros de tamaño fijo puede sufrir desbordamiento ("overflow"). Por ejemplo:

  int i = 2147483647;
  System.out.println(++i);
  
  

  el valor mostrado por consola es -2147483648.

  Por tanto, la inserción con éxito (hay memoria disponible) de un elemento en una lista con 2147483647 elementos conllevaría a un valor negativo de 'size'.

  Esta problemática afecta a otras estructuras de datos. No volveremos a incidir en ella pero tenedla presente.

• El primer constructor crea una lista vacía que consiste en 'header' y 'trailer' encadenados.
• El segundo constructor construye la lista tomando los elementos de un array. Usa el "for-each" de java que veremos en detalle en el tema de *Iteradores.
• El tercer constructor (constructor de copia) toma los elementos (¡no los nodos!) de otra lista. No se copian los elementos, se copian sus referencias, es decir, hace "shallow copy".
• Los constructores segundo y tercero no comprueban si el vector o la lista es null ya que en ese caso sí debe lanzarse 'NullPointerException'.
• El primer constructor y los métodos de inserción 'addFirst', 'addLast', 'addBefore' y 'addAfter' son los únicos que crean nodos. Al crearlos los marcan como pertenecientes a la lista. En concreto, le pasan al constructor de nodos un entero generado por un método privado 'iayf' ("I am your father") que encapsula la forma de generar el entero con que marcar los nodos. (Si quisiéramos cambiar el método de marcado sólo tenemos que modificar el método 'iayf'.)

  En la implementación actual, el método 'iayf' llama al método 'hashCode' de la superclase de 'NodePositionList', esto es, de 'Object'. Según la especificación del lenguaje Java, el método 'hashCode' de 'Object' genera un entero único para cada objeto de clase 'Object'. Por tanto, el valor de 'owner' de un nodo será un entero que identifica unívocamente el objeto lista al que pertenece.

  Observad que 'NodePositionList<E>' podría sobrescribir el método 'hashCode' sin problema porque 'iayf' invoca explícitamente el 'hashCode' de 'Object' usando 'super'.

  El método 'hashCode' de un objeto arbitrario debe generar un entero que puedan usar las tablas de dispersión ("hash tables") como valor de dispersión ("hash") del objeto. Más información sobre 'hashCode'.

• El método privado 'checkNode' comprueba si una posición es realmente un nodo válido de la lista:
  • No es 'null'.
  • Es de clase 'Node<E>'.
  • Es un nodo de la lista (se comprueba haciendo 'kinOf' con el 'header').
  • Está encadenado a un nodo previo y a un nodo siguiente.

  EJERCICIO: ¿Hay algún caso que no estemos considerado y debamos hacerlo?

  EJERCICIO: Ningún método comprueba si el elemento a almacenar o el ya almacenado en el nodo es null. ¿Debería hacerse esta comprobación? En caso positivo, ¿en qué métodos?

• El método 'iterator', los métodos sobrescritos 'toString' e 'equals', así como el método 'toArray' los explicaremos cuando veamos el tema de *Iteradores.

  Simplemente observamos que el método 'equals' compara 'this' con cualquier objeto 'o' que implemente el interfaz 'PositionList<E>', el cual no tiene que ser de clase 'NodePositionList' necesariamente. El concepto de iterador nos permitirá implementar este tipo de comparación de igualdad general en otros TADs donde los métodos ofrecidos por del interfaz no son suficientes para recorrerlo *Pilas LIFO y Colas FIFO. En el caso de las listas se podría haber implementado el 'equals' general usando el cursor como en 'toString' porque el interfaz 'PositionList<E>' ofrece métodos para recorrer la lista.

• De momento nos contentamos con una definición informal de la complejidad de un método. Estudiaremos la complejidad en *Introducción a la complejidad.
• Nos interesa la complejidad (coste) en tiempo (de ejecución) y espacio (consumo de memoria) en el "caso peor" (el peor escenario posible).
  • O(1) significa: la complejidad en tiempo del método en el caso peor se mantiene constante independientemente de lo que aumente el tamaño de la lista
  • O(n) significa: la complejidad en tiempo del método en el caso peor es linealmente proporcional al tamaño 'n' de la lista. Es decir, si la lista tiene 'n' elementos entonces la complejidad es 'n'. Si el tamaño es 'n+1' entonces la complejidad es 'n+1', etc.
• La complejidad temporal en el caso peor de todos los métodos (excepto los de iteración) es O(1). Por ejemplo, en la inserción y el borrado se le proporciona al los métodos 'addAfter', 'addBefore' y 'remove' el nodo con el elemento a insertar. Los métodos únicamente tienen que modificar los enlaces de los nodos, cuyo coste es constante respecto de (o "no depende de") el tamaño de la lista. Los métodos 'addFirst' y 'addLast' toman elementos, no nodos, pero crear un objeto nodo también tiene complejidad constante.
• EJERCICIO: Dado un elemento, si no se tiene su posición entonces habría que buscarla. Añadir a la clase e implementar el método:

  public Position<E> getPos(E e)
  
  

  que debe devolver la primera posición en la lista que contiene el elemento 'e', o null si el elemento no está en la lista. ¿Cuál sería la complejidad en el caso peor de dicho método?

• Usado en muchas aplicaciones reales.
• El código fuente de las clases no está disponible y por tanto no podemos usarlo para docencia.
• Se ofrecen muchos métodos útiles: conversión a array y viceversa, reordenación ('sort', 'shuffle', 'reverse', etc), computación con segmentos, búsqueda por patrones, etc.
• 'Collection<E>' extiende 'Iterable<E>' pero 'Map<K,V>' no. Veremos las consecuencias de ésto en *Iteradores.

• Interfaces: 'List<E>' (usa índices) y 'ListIterator<E>'. Hay además clases abstractas intermedias: 'AbstractList<E>', 'AbstractSequentialList<E>', etc.
• Implementaciones: 'ArrayList<E>', 'LinkedList<E>', y otras más 'AttributeList', 'CopyOnWriteArrayList', 'RoleList', 'RoleUnresolvedList', 'Vector', etc.

• Una pila ("stack") o LIFO es un TAD contenedor que consiste en una secuencia lineal de elementos de forma que el último elemento "apilado" ("push") es el primero en ser "desapilado" ("pop").
• Pensad en una pila de platos.
• Escribiremos las pilas horizontalmente de izquierda a derecha, siendo el primer elemento apilado el más a la derecha. También se suelen escribir verticalmente, siendo el primer elemento apilado el más profundo:

  Pila en la que se apila A, después B y finalmente C:

     +---+---+---+---+---+
  ...|   |   | C | B | A |
     +---+---+---+---+---+
  
               .
               .
               .
             |---|
             |   |
             |---|
             |   |
             |---|
             | C |
             |---|
             | B |
             |---|
             | A |
             |---|
  
  

• No existe una operación de búsqueda. Sólo se puede apilar, desapilar, o devolver el elemento en la cima de la pila ('top').
• Igual que en el caso de las listas, el tamaño de la pila está acotado por la memoria disponible del computador. Podrá producirse una excepción de insuficiente memoria al invocar el método 'push', lo que en el caso de la pila se conoce como "desbordamiento de pila" o "stack overflow". (Ahora ya sabéis de dónde le viene el nombre a vuestra página web de consulta preferente, después de Google creo, en cuestiones de programación.)
• Veremos dos formas de implementar pilas: usando listas de posiciones y usando arrays.

• El interfaz 'LIFO<E>' extiende 'Iterable<E>': ignoramos ésto, volveremos sobre ello en el tema *Iteradores.
• Vemos el código del interfaz en clase:
  • Interrogadores: 'size', 'isEmpty'.
  • Inserción: 'push' apila un elemento.
  • Borrado: 'pop' desapila un elemento.
  • Acceso ("getters"): 'top' devuelve el elemento en la cima de la pila. El comportamiento de 'top' es equivalente a desapilar ('pop') y volver a a pilar ('push') el elemento.
  • Conversión: el método 'toArray' devuelve un vector (array) con los elementos de la pila. Devuelve un vector de 'Object' *Arrays genéricos. El método 'toPositionList' devuelve una lista de posiciones con los elementos de la pila.

    Siguiendo la convención descrita en *¿Qué es un LIFO? el primer elemento del vector y de la lista será el primer elemento desapilado, etc.

• El siguiente método indica si en una cadena de caracteres que contiene una expresión de Java los paréntesis están equilibrados.

  El método recorre la cadena. Los paréntesis izquierdos se apilan. Al encontrar un paréntesis derecho la pila debe no ser vacía y se desapila el paréntesis izquierdo que le corresponde. Al terminar de recorrer la cadena la pila debe ser vacía.

  Por ejemplo, dada la cadena "((3 * 5) + (8 * (5 - 1))":

                                                            pila
  ((3 * 5) + (8 * (5 - 1))
  ^                                                          (
  
  ((3 * 5) + (8 * (5 - 1))                                 ( (
   ^
  
  ((3 * 5) + (8 * (5 - 1))                                   (
         ^
  
  ((3 * 5) + (8 * (5 - 1))                                 ( (
             ^
  
  ((3 * 5) + (8 * (5 - 1))                               ( ( (
                  ^
  
  ((3 * 5) + (8 * (5 - 1))                                 ( (
                        ^
  
  ((3 * 5) + (8 * (5 - 1))                                   (
                         ^
  
  ((3 * 5) + (8 * (5 - 1))                                   (
  
  
  

  El código del método:

  public static boolean balance(String str) {
    LIFO<Character> lifo = new .... ;
    boolean error = false;
  
    for (int i = 0; i < str.length() && !error; i++)
      switch (str.charAt(i)) {
  
        case '(': lifo.push('(');   // para equilibrar con ')'
                  break;
  
        case ')': if (lifo.isEmpty()) error = true;
                  else lifo.pop();
                  break;
  
        default:  break;
      }
    return !error && lifo.isEmpty();
  }
  
  

  Observad que no importa el elemento que se apila. Lo que importa es si la pila está o no vacía al encontrar un paréntesis derecho y al terminar de recorrer la cadena. Se podría haber apilado un asterisco, un entero, etc.

• Implementa una pila usando una lista de posiciones.
• Tiene la lista como único atributo. El tamaño de la pila será el tamaño de la lista. La operación de apilar consistirá en insertar el elemento al principio de la lista y la operación de desapilar consistirá en borrar el primer nodo de la lista.
• Tiene cuatro constructores:
  • El primero construye una pila vacía cuya lista interna está vacía.
  • El segundo toma como parámetro un vector y construye una pila cuya lista contiene los elementos del vector parámetro apilados de izquierda a derecha. Por ejemplo, si el vector parámetro es [A,B,C] entonces la lista es [C,B,A]. El bucle es un tipo especial de "for" denominado "for-each" que veremos en detalle en el tema de *Iteradores.
  • El tercero toma como parámetro una lista de posiciones y construye una pila cuya lista contiene los elementos de la lista apilados de izquierda a derecha.
  • El cuarto es el constructor de copia que respeta el orden posicional de los elementos de la pila parámetro.
• Los constructores segundo a cuarto no comprueban que sus parámetros son null porque en ese caso sí debe lanzarse 'NullPointerException'.
• El método 'top' lanza la excepción si la pila es vacía. En caso contrario devuelve el elemento en el primer nodo de la lista.
• El método 'pop' lanza la excepción si la pila es vacía. En caso contrario borra el primer nodo de la lista.
• El método 'push' inserta el elemento en un nuevo primer nodo de la lista.
• El método 'iterator' y el método 'equals' los explicaremos en más detalle cuando veamos el tema de *Iteradores.

  Simplemente observamos que el método 'equals' compara 'this' con cualquier objeto 'o' que implemente el interfaz 'LIFO<E>', el cual no tiene que ser de clase 'LIFOList<E>' necesariamente. El concepto de iterador nos permite implementar este tipo de comparación de igualdad general.

• Los métodos 'toString' y 'toArray' simplemente invocan los métodos homónimos de la lista. El orden posicional de elementos se corresponde con la convención de escritura vista en *¿Qué es un LIFO?.
• El método 'toPositionList' utiliza el constructor de copia de listas para crear una copia de la lista atributo. El orden posicional de elementos también se corresponde con la convención de escritura.

• Implementa una pila usando un vector. Cuando el vector se llena entonces crea un nuevo vector de mayor tamaño, copia ("shallow copy") los elementos, y reemplaza el antiguo vector por el nuevo. A esto lo llamamos informalmente "aumentar el vector".
• Tiene tres atributos:
  • 'arr' es el vector donde se apilan los elementos. El tamaño del vector 'arr.length' es la capacidad actual de la pila, es decir, el número de elementos que pueden apilarse sin tener que "aumentar el vector".
  • 'size' es el tamaño de la pila, es decir el número de elementos apilados. También es la posición en el vector donde se apilará el siguiente elemento. Por tanto, el primer elemento apilado está en la posición 0 del vector.

    La convención de apilado es la opuesta a la convención de escritura descrita en *¿Qué es un LIFO?. Los métodos de conversión y el método 'toString' de la clase tienen esto en cuenta.

  • 'defaultCapacity' es la capacidad por defecto con la que se construyen objetos pila. Al declararse como 'static' dicho atributo es compartido por todos los objetos pila. Al declararse como 'final' e inicializarse directamente y no en los constructores, el valor de dicho atributo es constante y no puede modificarse.

    Se usa una capacidad por defecto para evitar tamaños iniciales pequeños y que se llene rápidamente la pila.

• Tiene cinco constructores:
  • El primero construye una pila vacía cuyo vector (el atributo 'this.arr') tiene la capacidad por defecto.
  • El segundo toma como parámetro una capacidad y construye una pila cuyo vector tiene el máximo de esa capacidad y de la capacidad por defecto. La capacidad parámetro puede ser negativa o cero sin problema.

    Por ejemplo, si se invoca este constructor pasando una capacidad de 20 y después se apilan los elementos A, seguido de B, y finalmente C, entonces se tiene el vector 'arr' siguiente:

    +---+---+---+---+---+--               -+
    | A | B | C |   |   |...... hasta 1024 |
    +---+---+---+---+---+--               -+
    
    

    El valor de 'size' es 3, que es el tamaño de la pila y la siguiente posición del vector donde apilar. La capacidad del vector es 'arr.length' que es 1024. Los huecos vacíos del vector contienen 'null'.

  • El tercero toma como parámetro un vector y construye una pila cuyo vector contiene los elementos del vector parámetro apilados de izquierda a derecha. Por ejemplo, si el vector parámetro es [A,B,C] entonces el vector de la pila será como el mostrado en el punto anterior.
  • El cuarto toma como parámetro una lista de posiciones y construye una pila cuyo vector contiene los elementos de la lista apilados de izquierda a derecha.
  • El quinto es el constructor de copia que respeta el orden posicional de los elementos de la pila parámetro.
• Los constructores tercero a quinto no comprueban que sus parámetros son null porque en ese caso sí debe lanzarse 'NullPointerException'.
• El método 'top' lanza la excepción si la pila es vacía. En caso contrario devuelve el elemento en la cima, que es el elemento en la posición 'size-1'.
• El método 'pop' lanza la excepción si la pila es vacía. En caso contrario pone a null la posición del elemento cima y decrementa 'size'.

  Recordad del tema de *Genéricos que 'E' se instancia a un tipo referencia (una clase) y que por tanto los elementos del vector son objetos. Se pone a null la posición para ayudar al recolector de basura [EJ'01].

• El método 'push' comprueba si la pila está a la máxima capacidad, "aumentando el vector" en caso positivo. Se apila el elemento en el vector y se incrementa 'size'.
• El método 'iterator' y el método 'equals' los explicaremos en más detalle cuando veamos el tema de *Iteradores.

  Simplemente observamos que el método 'equals' compara 'this' con cualquier objeto 'o' que implemente el interfaz 'LIFO<E>', el cual no tiene que ser de clase 'LIFOArray<E>' necesariamente. El concepto de iterador nos permite implementar este tipo de comparación de igualdad general.

• El método 'toString' escribe el vector en una cadena de caracteres pero al revés, en concordancia con la convención de escritura de la pila descrita en *¿Qué es un LIFO?.
• Los métodos 'toArray' y 'toPositionList' copian los elementos a un vector y a una lista respectivamente en concordancia con la convención de escritura de la pila descrita en *¿Qué es un LIFO?. El resultado es el mismo que desapilar los elementos uno a uno insertándolos en el vector o lista.

• Una cola ("queue") FIFO es un TAD contenedor que consiste en una secuencia lineal de elementos de forma que el primer elemento "encolado" ("enqueue") es el primero en ser "desencolado" ("dequeue"), …, y el último elemento "encolado" es el último en ser "desencolado". (Sí, aquí estoy haciendo un uso anglicista y espurio de la palabras "encolar" y "desencolar".)
• Pensad en la cola de la parada del bus. El primero en llegar es el primero en subir … y el último en llegar es el último en subir.
• Escribiremos las colas horizontalmente de izquierda a derecha, siendo el primer elemento encolado el más a la izquierda.

  Cola en la que se encola A, después B y finalmente C:

  +---+---+---+---+---+
  | A | B | C |   |   |
  +---+---+---+---+---+
  
  

  Estado de la cola al desencolar:

  +---+---+---+---+---+
  | B | C |   |   |   |
  +---+---+---+---+---+
  
  

• No existe una operación de búsqueda. Sólo se puede encolar, desencolar, o devolver el elemento a desencolar ('first').
• Al igual que con las listas y pilas, el tamaño de la cola está acotado por la memoria del computador. (Por razones estéticas no diremos que hay "desbordamiento de cola" cuando la cola esté llena.)
• Veremos dos formas de implementar colas: usando listas de posiciones y usando arrays.

• El interfaz 'FIFO<E>' extiende 'Iterable<E>': ignoramos ésto, volveremos sobre ello en el tema *Iteradores.
• Vemos el código del interfaz en clase:
  • Interrogadores: 'size', 'isEmpty'.
  • Inserción: 'enqueue' encola un elemento.
  • Borrado: 'dequeue' desencola un elemento.
  • Acceso ("getters"): 'first' devuelve el primer elemento a desencolar de la cola. El comportamiento de 'first' NO es equivalente a desencolar y volver a encolar el elemento. Esto sólo se cumple cuando el elemento es el único de la cola.
  • Conversión: el método 'toArray' devuelve un vector (array) con los elementos de la cola. Devuelve un vector de 'Object' *Arrays genéricos. El método 'toPositionList' devuelve una lista de posiciones con los elementos de la cola.

    Siguiendo la convención descrita en *¿Qué es un FIFO? el primer elemento del vector y de la lista será el primer elemento desencolado, etc.

• Supongamos que la variable 'fifo' referencia una cola FIFO de objetos de clase 'Process' de procesos del sistema operativo. La clase 'Process' ofrece entre otros los métodos 'run' y 'suspend'. El método 'run' permite ejecutar un proceso durante un número máximo de milisegundos indicados como parámetro. El proceso puede parar su ejecución antes de ese tiempo, bien porque ha terminado, bien porque ha recibido alguna interrupción o está a la espera de un evento, etc. El método 'run' devuelve un número negativo si el proceso ha terminado. El método 'suspend' salva el estado de un proceso parado que no ha terminado de forma que pueda reanudarse su ejecución en la próxima invocación a 'run'. El siguiente bucle ejecuta los procesos con planificación circular o "round robin".

  while(!fifo.isEmpy()) {
      Process p = fifo.first();
      fifo.dequeue();
      int status = p.run(20);
      if (status < 0) {
        p.suspend();
        fifo.enqueue(p);
      }
  }
  
  

  Este ejemplo es meramente ilustrativo. En un sistema operativo real hay comunicación y sincronización entre procesos y la planificación es más sofisticada.

• Implementa una cola usando una lista de posiciones.
• Tiene la lista como único atributo. El tamaño de la cola será el tamaño de la lista. La operación de encolar consistirá en insertar el elemento al final de la lista y la operación de desencolar consistirá en borrar el primer nodo de la lista.
• Tiene cuatro constructores:
  • El primero construye una cola vacía cuya lista interna está vacía.
  • El segundo toma como parámetro un vector y construye una cola cuya lista contiene los elementos del vector parámetro encolados de izquierda a derecha.
  • El tercero toma como parámetro una lista de posiciones y construye una cola cuya lista contiene los elementos de la lista encolados de izquierda a derecha.
  • El cuarto es el constructor de copia que respeta el orden posicional de los elementos de la cola parámetro.
• Los constructores segundo a cuarto no comprueban que sus parámetros son null porque en ese caso sí debe lanzarse 'NullPointerException'.
• El método 'first' lanza la excepción si la cola es vacía. En caso contrario devuelve el elemento en el primer nodo de la lista.
• El método 'enqueue' encola el elemento en un nuevo nodo final de la lista.
• El método 'dequeue' lanza la excepción si la cola es vacía. En caso contrario borra el primer nodo de la lista.
• El método 'iterator' y el método 'equals' los explicaremos en más detalle cuando veamos el tema de *Iteradores.

  Simplemente observamos que el método 'equals' compara 'this' con cualquier objeto 'o' que implemente el interfaz 'FIFO<E>', el cual no tiene que ser de clase 'FIFOList<E>' necesariamente. El concepto de iterador nos permite implementar este tipo de comparación de igualdad general.

• Los métodos 'toString' y 'toArray' simplemente invocan los métodos homónimos de la lista. El orden posicional de elementos se corresponde con la convención de escritura vista en *¿Qué es un FIFO?.
• El método 'toPositionList' utiliza el constructor de copia de listas para crear una copia de la lista atributo. El orden posicional de elementos también se corresponde con la convención de escritura.

• Implementa una cola usando un vector. Cuando el vector se llena entonces "aumenta el vector".
• Tiene cuatro atributos:
  • 'arr' es el vector donde se guardan los elementos. El tamaño del vector 'arr.length' es la capacidad actual de la cola, es decir, el número de elementos que pueden encolarse sin tener que "aumentar el vector".
  • 'size' es el tamaño de la cola, es decir el número de elementos encolados.
  • 'first' es el índice del vector donde está el elemento a desencolar.
  • 'last' es el índice del vector donde ha de encolarse un elemento.
  • 'defaultCapacity' es la capacidad por defecto con la que se construyen objetos cola. Al declararse como 'static' dicho atributo es compartido por todos los objetos cola. Al declararse como 'final' e inicializarse directamente y no en los constructores, el valor de dicho atributo es constante y no puede modificarse. Se usa una capacidad por defecto para evitar tamaños iniciales pequeños y que se llene rápidamente la cola.
• La implementación usa el vector de forma circular ("circular array").

  La cola está vacía cuando 'first' y 'last' son 0. Los huecos vacíos del vector contienen 'null'.

  +---+---+---+---+
  |   |   |   |   |
  +---+---+---+---+
    ^
  first
  last
  
  

  Se encolan elementos en la posición 'last' y se incrementa el valor de 'last':

  +---+---+---+---+
  | A |   |   |   |
  +---+---+---+---+
    ^   ^
  first last
  
  +---+---+---+---+
  | A | B |   |   |
  +---+---+---+---+
    ^       ^
  first    last
  
  +---+---+---+---+
  | A | B | C |   |
  +---+---+---+---+
    ^           ^
  first        last
  
  

  Si se encola un nuevo elemento 'D' entonces la cola se llena y 'last' estaría fuera de rango ('last == arr.length'):

  +---+---+---+---+
  | A | B | C | D |
  +---+---+---+---+
    ^               ^
  first            last
  
  

  Sin embargo, si al encolar se incrementa 'last' de forma "circular" entonces 'last' volverá a ser igual a 'first'.

  +---+---+---+---+
  | A | B | C | D |
  +---+---+---+---+
    ^
  first
  last
  
  

  El incremento circular se hace usando la suma modular:

  last = (last + 1) % arr.length ;
  
  

  Observad que la cola está llena también cuando first y last tienen el mismo valor (en este caso valen 0).

  El atributo 'size' nos permite distinguir el caso vacío ('size == 0') del caso lleno ('size == arr.length').

  Si la siguiente operación es de encolar entonces hay que "aumentar" el vector. (Volveremos sobre cómo "aumentar" el vector más abajo al explicar el código del método 'enqueue'.)

  Si la siguiente operación es desencolar entonces se incrementa 'first' de forma "circular":

  +---+---+---+---+
  | A | B | C | D |
  +---+---+---+---+
    ^
  first
  last
  
  +---+---+---+---+
  |   | B | C | D |
  +---+---+---+---+
    ^   ^
  last first
  
  

  Este ejemplo ilustra que, al usar el vector de manera circular, 'last' puede ser menor que 'first'.

  Si la siguiente operación es de encolar entonces se llena de nuevo la cola y 'last' y 'first' vuelven a ser iguales (pero en este caso valdrían 1). Pero si la siguiente operación es de desencolar entonces:

  +---+---+---+---+
  |   | B | C | D |
  +---+---+---+---+
    ^   ^
  last first
  
  +---+---+---+---+
  |   |   | C | D |
  +---+---+---+---+
    ^       ^
  last    first
  
  

  Encolemos otro elemento:

  +---+---+---+---+
  | F |   | C | D |
  +---+---+---+---+
       ^    ^
     last  first
  
  

  Desencolemos dos veces:

  +---+---+---+---+
  | F |   | C | D |
  +---+---+---+---+
       ^    ^
     last  first
  
  +---+---+---+---+
  | F |   |   | D |
  +---+---+---+---+
       ^        ^
     last      first
  
  +---+---+---+---+
  | F |   |   |   |
  +---+---+---+---+
    ^   ^
  first last
  
  

  Finalmente encolemos otro elemento:

  +---+---+---+---+
  | F | G |   |   |
  +---+---+---+---+
    ^       ^
  first    last
  
  

• La clase FIFOArray<E> tiene cinco constructores:
  • El primero construye una cola vacía cuyo vector (el atributo 'this.arr') tiene la capacidad por defecto.
  • El segundo toma como parámetro una capacidad y construye una cola vacía cuyo vector tiene el máximo de esa capacidad y de la capacidad por defecto. La capacidad parámetro puede ser negativa o cero sin problema. Los atributos 'size', 'first' y 'last' se inicializan a 0.
  • El tercero toma como parámetro un vector y construye una cola cuyo vector contiene los elementos del vector parámetro apilados de izquierda a derecha.
  • El cuarto toma como parámetro una lista de posiciones y construye una cola cuyo vector contiene los elementos de la lista apilados de izquierda a derecha.
  • El quinto es el constructor de copia que respeta el orden posicional de los elementos de la cola parámetro.
• Los constructores tercero a quinto no comprueban que sus parámetros son null porque en ese caso sí debe lanzarse 'NullPointerException'.
• El método 'first' lanza la excepción si la cola es vacía. En caso contrario devuelve el elemento en la posición 'first' del vector.
• El método 'incMod' realiza el incremento circular de su parámetro. Lo utilizan los métodos 'enqueue', 'dequeue' y 'toString' para incrementar circularmente los índices 'first' y 'last' según proceda.
• El método 'dequeue' lanza la excepción si la pila es vacía. En caso contrario pone a null la posición 'first' del vector e incrementa circularmente 'first' a la posición del siguiente elemento a desencolar. Igual que en la *Clase LIFOArray<E>, se pone a null la posición 'first' del vector para ayudar al recolector de basura [EJ'01]. Finalmente actualiza 'size'.
• El método 'enqueue' comprueba si la cola está a la máxima capacidad, "aumentando el vector" en caso positivo. Tanto si se aumenta el vector como si no, añade el elemento en el vector.
  1. Aumento del vector: primero crea un vector con el doble de capacidad en una variable temporal 't'. Después copia los elementos al nuevo vector.

     Puesto que puede darse el caso que 'last' es menor que 'first', no puede usarse el siguiente bucle para copiar los elementos:

     for (int i = this.first; i < this.last; i = incMod(i))
       t[i] = this.arr[i];
     
     

     Tampoco podría usarse ésto:

     for (int i = this.first; i != this.last; i = incMod(i))
       t[i] = this.arr[i];
     
     

     El bucle termina al llegar a la posición 'last', que es igual a 'first' porque la cola está llena. No se entra en el bucle.

     Lo que podemos hacer es avanzar y después preguntar si hemos llegado al final:

     int i = this.first;
     do {
       t[i] = this.arr[i];
       i = incMod(i);
     } while (i != this.last)  // también i != this.first
     
     

     Sin embargo, esto copia el vector antiguo al principio del nuevo:

     +---+---+---+---+
     | C | D | A | B |
     +---+---+---+---+
              ^
             first
             last
     
     +---+---+---+---+---+---+---+---+
     | C | D | A | B |   |   |   |   |
     +---+---+---+---+---+---+---+---+
               ^
              first
              last
     
     

     ocurriendo que 'first == last' pero la pila ni está vacía ni está llena.

     Lo que haremos es copiar los elementos llevando el 'first' del antiguo al 0 del nuevo … y el 'last-1' del antiguo al 'size()-1' del nuevo.

     Se necesitan dos índices. Un índice que va de 0 a 'size()-1' para almacenar los elementos de la cola en el nuevo vector 't'. Otro índice que debe comenzar en 'first' e ir incrementando circularmente hasta llegar a 'last-1'. Pero eso ocurre cuando el primer índice es igual a 'size()-1'.

     Una vez copiados los elementos se desecha el vector antiguo haciendo que 'this.arr' referencie el nuevo, y se modifican los valores de 'first' al comienzo del nuevo vector y de 'last' al primer hueco vacío.

     EJERCICIO: ¿Debería haberse escrito un bucle para poner los elementos del viejo vector a 'null' y así ayudar al recolector de basura?

  2. Inserción: se almacena el elemento parámetro en la posición 'last' de la cola, se incrementa circularmente dicha posición, y se incrementa 'size'.
• El método 'iterator' y el método 'equals' los explicaremos en más detalle cuando veamos el tema de *Iteradores.

  Simplemente observamos que el método 'equals' compara 'this' con cualquier objeto 'o' que implemente el interfaz 'FIFO<E>', el cual no tiene que ser de clase 'FIFOArray<E>' necesariamente. El concepto de iterador nos permite implementar este tipo de comparación de igualdad general.

• El método 'toString' escribe el vector en una cadena de caracteres, recorriendo el vector de forma similar a como lo recorre el método 'enqueue' en el "aumentado" del vector.

  EJERCICIO: Razonar por qué la siguiente versión alternativa de 'toString' que itera usando sólo un índice es incorrecta. Modificarla para hacerla correcta:

  public String toString() {
    String s = "[";
    int i = this.first;
    do {
      if (this.arr[i] == null)
        s += "null";
      else
        s += this.arr[i].toString();
      i = incMod(i);
      if (i != this.last) s += ", ";
    } while (i != this.last);
    s += "]";
    return s;
  }
  
  

• Los métodos 'toArray' y 'toPositionList' copian los elementos a un vector y a una lista respectivamente en concordancia con la convención de escritura de la cola descrita en *¿Qué es un FIFO?. El resultado es el mismo que desencolar los elementos uno a uno insertándolos en el vector o lista. Se recorre el vector de forma similar a como lo recorre el método 'enqueue' en el "aumentado" del vector.
• Existen otras formas alternativas de implementar una cola FIFO con un vector [GT(I)'10]. Por ejemplo, en vez de tener un atributo 'size' se puede reservar un hueco vacío en el vector (almacenando como máximo 'arr.length-1' elementos) de forma que la cola está vacía cuando 'first == last'. El método 'size' calcula el número de elementos a partir de 'first' y 'last':

  public int size() {
    return (this.arr.length - this.first + this.last) % this.arr.length;
  }
  
  

  Finalmente, la cola está llena cuando 'size() == arr.length - 1'.

  Con esto nos ahorramos 'size' a costa de complicar el cálculo del tamaño y de gastar un hueco del array. El hueco almacena una dirección de memoria que suele tener el mismo tamaño de un entero (32 bits) o más (64 bits). Así que el ahorro no es tal.

Recordad lo visto en *Recorridos de listas de posiciones.

*Ejemplo: mostar por pantalla todos los elementos de una lista

Ese código tiene varios problemas:

1. Es específico para listas de posiciones porque se usan datos y métodos específicos de su interfaz: cursor de tipo 'Position<E>', métodos 'first' y 'next', y uso de 'null' como centinela. No se puede adaptar el código fácilmente para iterar sobre otros TADs como, por ejemplo, colas FIFO.
2. El programador tiene que declarar el cursor, inicializarlo adecuadamente, e incrementarlo adecuadamente. Hay varias oportunidades para cometer errores y generar una 'IllegalArgumentException'.

1. La iteración no se realiza usando los métodos del interfaz del TAD sino usando los métodos del interfaz del iterador.
2. Se puede reusar el código para iterar otros TADs.

Mostramos un ejemplo con 'show':

public static <E> void show(PositionList<E> list) {

  Position<E> cursor = list.first();        // Inicialización.

  while (cursor != null) {                  // Bucle mientras el cursor
                                            // referencie a donde hay
                                            // un elemento.

    System.out.println(cursor.element());   // Se hace algo con el elemento.

    cursor = list.next(cursor);             // Se avanza el cursor.

  }
}

He aquí una forma de abstraer el cursor en un objeto iterador:

public static <E> void show(PositionList<E> list) {

  Iterator<E> it = list.iterator();   // La lista nos da un objeto iterador
                                      // (un cursor) ya inicializado.

  while (it.hasNext())                // Bucle mientras el cursor
                                      // referencie a donde hay un elemento.

     System.out.println(it.next());   // Se hace algo con el elemento
                                      // y queda el cursor avanzado.

}

El método 'it.next()' devuelve el elemento accesible desde el cursor (no devuelve un nodo), y además dejará el cursor avanzado, lo que constituye un efecto secundario o "side effect" parecido a un post-incremento del índice en la iteración de un vector:

int i = 0;                         // Inicialización

while (i < arr.length)             // Bucle mientras el índice está en rango

  System.out.println(arr[i++]);    // Se hace algo con el elemento
                                   // y queda el índice avanzado.

public static <E> void show(FIFOQueue<E> queue) {

  Iterator<E> it = queue.iterator();  // La cola nos da un objeto iterador
                                      // (un cursor) ya inicializado.

  while (it.hasNext())                // Bucle mientras el cursor
                                      // referencie a donde hay un elemento.

     System.out.println(it.next());   // Se hace algo con el elemento
                                      // y queda el cursor avanzado.

}

for (Iterator<E> it = list.iterator(); it.hasNext();  )
  System.out.println(it.next());

No hay incremento en el bucle porque el método 'next' realiza el incremento como efecto secundario.

public interface Iterator<E> {
  public E next() ;            /* obligatorio implementarlo */
  public boolean hasNext() ;   /* obligatorio implementarlo */
  public void remove() ;       /* no obligatorio, ¡problemático! */
}

public interface Iterable<E> {
  public Iterator<E> iterator() ;
}

Una interpretación válida es: "¿referencia el cursor algo donde hay un elemento, el cual todavía no te he pedido con 'next'?". Usando la metáfora de una frutería, cuando el frutero dice "¿hay siguiente?" si hay alguien entonces levanta la mano el que está primero, cuando atiende al primero ('next') y vuelve a decir "¿hay siguiente?", levanta la mano el que estaba segundo, etc. En una secuencia de elementos, el primer "siguiente" es el primer elemento.

Otra interpretación válida de 'hasNext' es "¿es el cursor distinto de null?".

Una interpretación válida es "dame el elemento del cursor y deja el cursor avanzado (o a null si no se puede avanzar más)".

*Método remove del iterador.

Al crearse el objeto iterador, el cursor referencia el primer elemento porque el TAD no es vacío.

 {A,B}
  ^
  |
cursor

 hasNext() devuelve true.
 next()    avanza el cursor a B y devuelve A.


 {A,B}
    ^
    |
  cursor

 hasNext() devuelve true.
 next()    avanza el cursor a null y devuelve B.

 {A,B}

  cursor -> null

 hasNext() devuelve false.
 next()    lanza NoSuchElementException.

• Si el TAD está vacío:

  hasNext() devuelve false.
  next()    lanza NoSuchElementException.
  
  

• Si el TAD no está vacío:

  hasNext() devuelve true.
  next()    avanza el cursor al segundo elemento (si hay) o a null (si no
            hay) y devuelve el primer elemento.
  
  

for (Iterator<E> it1 = list.iterator(); it1.hasNext(); ) {
  E e = it1.next();
  for (Iterator<E> it2 = list.iterator(); it2.hasNext(); it2.next())
   System.out.println(e);
}

if (!it.hasNext())
  it.remove();     // Incorrecto, no hay elementos.

if (it.hasNext())
  it.remove();     // Incorrecto, no hay 'next' previo.

while (it.hasNext()) {
  it.next();
  it.remove();     // Correcto
}

it.next();         // Correcto si 'hasNext' es cierto, sino incorrecto.
it.remove();       // Correcto si no falló el 'next' anterior

it.next();         // Correcto si 'hasNext' es cierto, sino incorrecto.
it.remove()        // Correcto si no falló el 'next' anterior
it.next();         // Correcto si 'hasNext' es cierto, sino incorrecto.
it.remove();       // Correcto si no falló el 'next' anterior

it.next();         // Correcto si 'hasNext' es cierto, sino incorrecto.
it.next();         // Correcto si 'hasNext' es cierto, sino incorrecto.
it.remove();       // Correcto si no falló el 'next' anterior

it.next();         // Correcto si 'hasNext' es cierto, sino incorrecto.
.                                                                 ^
.                  // Mucho código aquí sin ningún 'remove'       |
.                                                                 |
it.remove();       // Correcto si no falló el 'next' anterior ----/

it.remove();       // Incorrecto, no hay 'next' previo.

public static <E> E tenth(PositionList<E> list)
throws NoSuchElementException {
  if (list.size() < 10) throw new NoSuchElementException();
  else {
    Iterator<E> it = list.iterator();
    for (int i = 1; i < 10; i++)
      it.next();
    return it.next();
  }
}

public static <E> void deleteAll(PositionList<E> list) {
  Iterator<E> it = list.iterator();
  while (it.hasNext()) {
    it.next();
    it.remove();
  }
}

Recordad que el método 'remove' debe invocarse después de 'next' y que 'remove' borra el nodo donde está el elemento que ha devuelto el 'next' anterior.

• Versión que asume que los elementos nunca son null:

  public static int sumaElems(PositionList<Integer> list) {
    Iterator<E> it = list.iterator();
    int suma = 0;
    while (it.hasNext())
      suma += it.next();
    return suma;
  }
  
  

• Versión que asume que los elementos pueden ser null. Se necesita una variable donde guardar el elemento:

  public static int sumaElems(PositionList<Integer> list) {
    Iterator<E> it = list.iterator();
    int suma = 0;
    while (it.hasNext()) {
      Integer e = it.next();
      if (e != null) suma += e;
    }
    return suma;
  }
  
  

• Aquí también asumimos que los elementos no son null.

  public static int maximum(PositionList<Integer> list)
  throws EmptyListException {
    if (!it.hasNext()) throw new EmptyListException();
    int m = it.next();
    while (it.hasNext())
      m = Math.max(m, it.next());
    return m;
  }
  
  

• Versión sin iterador:

  public static <E> boolean member(E e, PositionList<E> list) {
    Position<E> cursor = list.first();
    while (cursor != null && !e.equals(cursor.element()))
      cursor = list.next(cursor);
  
    // cursor == null || cursor != null && e.equals(cursor.element())
    return cursor != null;
  }
  
  

• La siguiente implementación con iterador es errónea:

  public static <E> boolean member(E e, PositionList<E> list) {
    Iterator<E> it = list.iterator();
    while (it.hasNext() && !e.equals(it.next()))
      ;                    // el "incremento" del cursor lo hace 'next'
  
    // !it.hasNext() || it.hasNext() && e.equals(it.next())
    return it.hasNext();
  }
  
  

  Para saber por qué es errónea ejecutad el código en papel sobre una lista con un único nodo con elemento igual a 'e'. Recordad que 'it.next()' produce un efecto secundario: también avanza el cursor.

• La siguiente implementación correcta utiliza una variable booleana 'found' para guardar el estado de la última comparación.

  public static <E> boolean member(E e, PositionList<E> list) {
    Iterator<E> it = list.iterator();
    boolean found = false;
    while ( it.hasNext() && !(found = e.equals(it.next())) )
      ;
  
    // !it.hasNext() || it.hasNext() && found
    return found;
  }
  
  

• Para simplificar asumimos que el elemento no es null.

  public static <E> void borra(E e, PositionList<E> list) {
     Iterator<E> it = list.iterator();
     boolean found = false;
     while ( it.hasNext() && !(found = e.equals(it.next())) )
       ;
     if (found) it.remove();
  }
  
  

public static <E> void borra(E e, PositionList<E> list) {
   Iterator<E> it = list.iterator();
   while (it.hasNext())
      if (e.equals(it.next()))
        it.remove();
}

public static <E> void borra(E e, PositionList<E> list) {
  Iterator<E> it = list.iterator();
  while (it.hasNext()) {
    E elem = it.next();
    if (e == null && elem == null || e != null && e.equals(elem))
      it.remove();
  }
}

public static <E> boolean sublist(PositionList<E> l1, PositionList<E> l2) {
  if (l1 == null || l2 == null) return false;
  if (l1 == l2) return true;
  Iterator<E> it1 = l1.iterator();
  boolean res = false;
  while ( it1.hasNext() && (res = this.member(it1.next(),l2)) )
    ;
  return res;
}

• Dos listas son iguales si contienen los mismos elementos de izquerda a derecha.

  Versión 1 con varias variables auxiliares:

  public static <E> boolean iguales (PositionList<E> list1,
                                     PositionList<E> list2) {
    if (list1 == list2) return true;
    // El caso anterior incluye list1 == null && list2 == null
    if (list1 == null || list2 == null || list1.size() != list2.size())
      return false;
  
    Iterator<E> it1 = list1.iterator();
    Iterator<E> it2 = list2.iterator();
    E e1, e2;
    boolean iguales = true;
  
    while (it1.hasNext() && iguales) {
      e1 = it1.next();
      e2 = it2.next();
      iguales = e1 == null && e2 == null || e1 != null && e1.equals(e2);
    }
  
    return iguales;
  }
  
  

  Creamos un método auxiliar para comparar elementos:

  private static <E> boolean igualesElem(E e1, E e2) {
    return e1 == null && e2 == null || e1 != null && e1.equals(e2);
  }
  
  public static <E> boolean iguales (PositionList<E> list1,
                                     PositionList<E> list2) {
    .
    .
    .
    Iterator<E> it1 = list1.iterator();
    Iterator<E> it2 = list2.iterator();
    E e1, e2;
    boolean iguales = true;
  
    while (it1.hasNext() && iguales) {
      e1      = it1.next();
      e2      = it2.next();
      iguales = igualesElem(e1,e2);
    }
  
    return iguales;
  }
  
  

  Eliminamos las variables elemento y subimos la comparación al bucle:

  public static <E> boolean iguales (PositionList<E> list1,
                                     PositionList<E> list2) {
    .
    .
    .
    Iterator<E> it1 = list1.iterator();
    Iterator<E> it2 = list2.iterator();
    boolean iguales = true;
  
    while (it1.hasNext() && (iguales = igualesElem(it1.next(),it2.next())))
      ;
    return iguales;
  }
  
  

  No podemos eliminar la variable booleana, pues ésta guarda el estado de la última comparación. Necesitamos dicho estado porque 'next' avanza el cursor. El siguiente código no funciona:

  while (it1.hasNext() && igualesElem(it1.next(),it2.next()))
    ;
  // !it1.hasNext() || it1.hasNext && !igualesElem(it1.next(),it2.next())
  return !it1.hasNext();
  
  

  Este tampoco:

  while (it1.hasNext() && igualesElem(it1.next(),it2.next()))
    ;
  // !it1.hasNext() || it1.hasNext && !igualesElem(it1.next(),it2.next())
  return igualesElem(it1.next(),it2.next());
  
  

  Probadlo con dos listas que contienen un único elemento distinto el uno del otro.

• El código está en el fichero NodePositionList.java.

EJERCICIO: intentad programar con un iterador el 'addBeforeElement' visto en *Ejemplo: insertar un elemento antes de la primera aparición de otro.

1. El objeto iterador itera ("mueve el cursor") usando los métodos del interfaz del TAD para obtener el siguiente elemento. De esta forma el iterador puede usarse para iterar sobre objetos de cualquier clase que implemente el interfaz. En otras palabras, dado el interfaz 'I', el iterador puede iterar sobre cualquier clase que implemente 'I' si usa únicamente métodos de 'I' para "mover" el cursor.
2. El objeto iterador itera ("mueve el cursor") accediendo a los atributos de la clase que implementa el TAD. Estos iteradores únicamente pueden usarse para iterar sobre objetos de las clases concretas. En otras palabras, dada la clase 'C' que implementa el interfaz 'I', el iterador definido para objetos de 'C' sólo puede usarse sobre objetos de 'C' y no sobre objetos de otras clases que implementan 'I'.

En *Iteradores sobre interfaces detallaremos la primera alternativa.

En *Iteradores sobre clases detallaremos la segunda, pero el contenido de esa sección no será evaluado en el examen de teoría. Incluimos el material para los alumnos que desean profundizar en la materia.

La primera alternativa es más deseable desde el punto de vista de abstracción y reusabilidad, pero puede no ser posible realizarla porque no hay suficientes métodos observadores en el interfaz, o porque la iteración usando métodos del interfaz es ineficiente.

Damos una receta para implementar iteradores sobre TADs de forma que los iteradores invocan los métodos de los interfaces de los TADs.

1. El interfaz del TAD debe extender 'Iterable<E>' para indicar que las clases que implementen el interfaz tendrán que implementar el método 'iterator', el cual deberá devolver un objeto iterador (un objeto que implementa el interfaz 'Iterator<E>') para dicho TAD.

   import java.util.Iterator;
   public interface TAD<E> extends Iterable<E> {
   
     ... /* métodos del TAD */
   
     public Iterator<E> iterator() ;
     public Iterable<E> snapshot() ; /* no obligatorio pero útil */
   }
   
   

   El método 'snapshot' no se hereda de 'Iterable<E>'. Estrictamente, no forma parte del patrón de diseño de iteradores, pero es útil: vale para hacer copias o "snapshots" [GT(I)'10, p.257] y garantizar persistencia y mutabilidad [JP'05, p.102]. Este método devuelve un iterable con todos los elementos del TAD. Si el iterable es del mismo tipo que el TAD entonces se tiene una copia. Si el iterable es de distinto tipo entonces se tiene una foto o "snapshot". En ambos casos el iterable se puede recorrer mediante un iterador al mismo tiempo que modificamos el TAD original.

   El *Interfaz PositionList<E> extiende 'Iterable<E>'.

2. Se implementa una clase iterador cuyos métodos usan los métodos del interfaz del TAD para "mover el cursor":

    import java.util.Iterator;
    public class TADIterator<E> implements Iterator<E> {
      TAD<E> tad;  /* el TAD sobre el que itera es un atributo */
      CursorTAD<E> cursor;
   
      public TADIterator(TAD<E> t) {
        tad = t;
        ... /* código aquí que inicializa el valor del cursor */
      }
      public boolean hasNext()     { /* código aquí */ }
      public E next()              { /* código aquí */ }
      public void remove()         { /* código aquí */ }
   }
   
   

   El constructor del objeto iterador toma como parámetro el objeto TAD sobre el que debe iterar.

   El tipo de 'cursor' depende del TAD concreto. Puede ser directamente un elemento:

   E cursor;
   
   

   También puede ser una referencia a un objeto que contiene un elemento (como en el caso de EJEMPLO: PositionListIterator.java):

   Position<E> cursor;
   
   

   También puede ser un valor de algún tipo, a partir del cual se puede localizar el elemento en el TAD, etc.

3. Implementar el método 'iterator' en todas las clases que implementan el interfaz 'TAD<E>'. Dicho método devuelve un objeto iterador.

   import java.util.Iterator;
   public class TADClass1<E> implements TAD<E> {
     ...
     public Iterator<E> iterator() { return new TADIterator<E>(this); }
   }
   
   

   import java.util.Iterator;
   public class TADClass2<E> implements TAD<E> {
     ...
     public Iterator<E> iterator() { return new TADIterator<E>(this); }
   }
   
   

4. Diagrama de clases:

       TAD<E>  ----- E -----> Iterable<E> <>---- U ----> Iterator<E>
       ^ ^                                                ^
     I | | I                                              | I
       |  \                                               |
       |    TADClass2<E> <>----------- U ---------------> TADIterator<E>
    TADClass1<E> <>------------------- U --------------/
   
   E: Extiende.
   I: Implementa.
   U: Usa.
   
   

   Los interfaces y clases del diagrama deben ser declarados dentro de un paquete.

5. EJEMPLO: PositionListIterator.java:
   • Esta clase implementa 'Iterator<E>' para 'PositionList<E>'.
   • El cursor no referencia un elemento de tipo 'E' sino una posición 'Position<E>' porque los métodos del *Interfaz PositionList<E> tales como 'next' y 'prev' (que se usan para "mover el cursor") toman como parámetros posiciones, no elementos.
   • 'NodePositionList<E>' implementa el método 'iterator' y usa el iterador en el método 'equals'.

El material de esta sección es opcional y no será evaluado en el examen de teoría. Incluimos el material para los alumnos que desean profundizar en la materia.

1. Se puede iterar sobre un TAD declarando el método 'iterator' como método propio de 'TAD<E>' sin extender de 'Iterable<E>':

   import java.util.Iterator;
   public interface TAD<E> {
     ...
     public Iterator<E> iterator();
   }
   
   

   Las clases que implementen el interfaz tendrán que implementar 'iterator'.

   Sin embargo esto no es recomendable porque 'TAD<E>' no es 'Iterable<E>'. No podemos usar 'TAD<E>' en contextos donde se espera un iterable, por ejemplo, no podemos hacer *Iteración con bucle "for-each" con ese 'TAD<E>'.

2. Se puede asociar un iterador a una clase en vez de a un interfaz:
   • Código del interfaz 'TAD<E>':

     public interface TAD<E> /* no extiende Iterable<E> */ { ... }
     
     

   • Código de una clase:

     public class TADClass1<E> implements TAD<E>, Iterable<E> {
       ...
       public Iterator<E> iterator() { return new TADClass1Iterator<E>(this); }
     }
     
     

   • Código del iterador asociado a la clase 'TADClass1<E>':

     public class TADClass1Iterator<E> implements Iterator<E> {
       TADClass1<E> tadClass1;
       CursorTAD<E> cursor;
       public TADClass1Iterator(TADClass1<E> t) {
         tadClass1 = t;
         ... /* código aquí que inicializa el valor del cursor */
       }
       public boolean hasNext()     { /* código aquí */ }
       public E next()              { /* código aquí */ }
       public void remove()         { /* código aquí */ }
     }
     
     

     El constructor del iterador toma como parámetro un objeto de la clase 'TADClass1<E>', no un objeto de tipo 'TAD<E>'. Los métodos 'hasNext' y 'next' pueden implementarse o bien usando los métodos del interfaz 'TAD<E>' (porque 'TADClass1<E>' implementa los métodos de 'TAD<E>') o bien accediendo directamente a los atributos de 'TADClass1<E>' si son públicos.

3. Finalmente, una variación de lo anterior es definir 'TADClass1Iterator<E>' como una clase anidada no estática ("non-static") dentro de 'TADClass1<E>', pudiendo la primera acceder a los atributos privados de la segunda. Consultar en la [JLS'3E] los conceptos de clases 'nested', 'inner', 'local', y 'anonymous', así como la siguiente URL:

   http://download.oracle.com/javase/tutorial/java/javaOO/nested.html

4. En los dos últimos casos (2 y 3) el iterador 'TADClass1Iterator<E>' sólo puede usarse con objetos de clase 'TADClass1<E>'. No puede usarse con objetos de otras clases que implementen 'TAD<E>'. Esas clases deben tener su propio iterador.

       TAD<E>                                         Iterator<E>
       ^ ^                                                ^
     I | | I                                              | I
       |  \                                               |
       |    TADClass1<E> <>--------- U ----------> TADClass1Iterator<E>
    TADClass2<E>
   
   E: Extiende.
   U: Usa.
   I: Implementa.
   
   

   En este diagrama, 'TADClass2<E>' ni usa ni puede usar 'TADClass1Iterator<E>'.

public static <E> void show(PositionList<E> list) {
  Iterator<E> it = list.iterator();
  while (it.hasNext())
    System.out.println(it.next());
}

usamos for-each para escribirlo mejor:

public static <E> void show(PositionList<E> list) {
  for (E e : list)
    System.out.println(e);
}

Consultad [JP'05, p.50] y también la siguiente URL

http://docs.oracle.com/javase/specs/jls/se7/html/jls-14.html#jls-14.14.2

Patrón de sintaxis:

for (type elem : expr) { stmts }

Donde:

• La variable 'elem' tiene tipo 'type' y no aparece en la expresión 'expr'.
• La expresión 'expr' tiene tipo 'Iterable<T>' o tipo "array de T", con T un subtipo o un "boxing" de 'type'. Es decir, se puede usar for-each con arrays o con objetos iterables (objetos de clases que implementan el interfaz 'Iterable<E>'.)
• Dentro de 'stmt' no se tiene acceso al iterador (a una variable que referencie el objeto iterador), sólo al elemento 'elem'. No se pueden invocar 'next', 'hasNext', ni 'remove'. Los dos primeros son invocados por el bucle de forma automática.

for (Iterator<E> it = list.iterator(); it.hasNext(); ) {
  E e = it.next();
  System.out.println(e);
}

La variable 'it' local al bucle la genera el propio compilador.

• Suma de elementos de una lista de enteros, los elementos pueden ser null:

  public static int sumaElems(PositionList<Integer> list) {
    int suma = 0;
    for (Integer e : list)
      if (e != null)
        suma += e;
    return suma;
  }
  
  

• Dos de los constructores de la *Clase NodePositionList están escritos con for-each.
• Reescribimos el 'toString' de la *Clase NodePositionList usando for-each:

  public String toString() {
    String s = "[";
    for (E e : this)) {
      if (e == null)
        s += "null";
      else
        s += e.toString();
      if (cursor != last())
        s += ", ";
    }
    s += "]";
    return s;
  }
  
  

1. Cuando 'expr' es de tipo Iterable<T> el bucle se lee como "ejecuta 'stmt' para todo elemento 'elem' del iterable 'expr'". En este caso el bucle for-each es una abreviatura de:

   for (Iterator<type> it = expr.iterator(); it.hasNext(); ) {
     type elem = it.next();
     stmts
   }
   
   

   donde 'it' es una variable oculta nueva que no aparece en 'stmts'.

   Nótese que 'elem' se declara después de usarse 'expr' y por eso 'elem' no puede ocurrir en 'expr'.

   Si no hay elementos para iterar ('hasNext' devuelve falso) no se ejecuta el código del for-each.

   La variable 'elem' puede declararse localmente dentro del bloque del bucle 'for'.

   También se puede expresar el for-each con un bucle 'while':

   {
     Iterator<type> it = expr.iterator();
     type elem;
     while (it.hasNext()) {
       elem = it.next();
       stmts
     }
   }
   
   

2. Cuando 'expr' es de tipo array de T entonces el bucle for-each es una abreviatura de:

   for (int j = 0; j < expr.length; j++) {
     type elem = v[j];
     stmts
   }
   
   

   Donde 'j' es una nueva variable que no aparece en 'stmts'.

3. Ejemplos de for-each con vectores:
   • Sumar los elementos de un vector:

     public int sumaArray(int [] v) {
       int suma = 0;
       for (int e : v)
         suma += e;
       return suma;
     }
     
     

   • Ejemplo de MAL uso: mostrar los 'n' primeros elementos de un array de caracteres 'v'. Usando for-each se recorre innecesariamente todo el array:

     for (char c : v)
       if (n > 0) {
         System.out.println(c);
         n--;
       }
     
     

     Usar 'break' es un error de estilo y va contra la razón de ser de for-each que sirve para recorrer todo el vector:

     for (char c : v) {
       if (n == 0) break;         // Suspenso
       if (n > 0) {
         System.out.println(c);
         n--;
       }
     }
     
     

     La solución idónea es no usar el for-each.

   • Aunque se puede usar for-each con vectores, éstos no tienen iteradores porque no son objetos de una clase que extienda 'Iterable<T>' y por tanto no tienen un método 'iterator':

     for (Iterator<Character> it = v.iterator(); n > 0 && it.hasNext(); n--)
       System.out.println(it.next());   // este código no compila
     
     

Un ejemplo típico y sencillo es el método que calcula el 'factorial' de un entero positivo.

El factorial de un entero positivo n > 0 se define como el valor de la expresión 'n * (n-1) * … * 1'. Para n <= 0 el factorial se define como 1.

Mostramos dos posibles soluciones iterativas. Ambas usan una variable acumulador, en la que se acumulan las multiplicaciones. La primera solución itera desde 'n' hasta '2'. La segunda desde '2' hasta 'n'.

public static int factorial(int n) {
  int r = 1;
  while (n > 1) {
    r = n * r;
    n--;
  }
  return r;
}

public static int factorial(int n) {
  int r = 1;
  for (int i = 2; i <= n; i++)
    r = i * r;
  return r;
}

Dejemos a un lado el problema de que en Java el tipo 'int' tiene un rango de valores limitado (probad qué pasa por ejemplo con 'factorial(100)'). Dejemos también a un lado cómo solucionarlo (¿qué otros tipos primitivos o clases podríais usar?).

Observad que la expresión '(n-1) * (n-2) * … * 1' calcula 'factorial(n-1)'. Por tanto se puede definir 'factorial(n)' en función de 'factorial(n-1)':

n * (n-1) * (n-2) * ... * 1
    \______________________/
         factorial(n-1)
\__________________________/
       factorial(n)

factorial(n) = n * factorial(n-1)

En código:

public static int factorial(int n) {
  if (n <= 1) return 1;
  else        return n * factorial(n-1);
}

que queda más escueto usando una expresión condicional:

public static int factorial(int n) {
  return n <= 1 ? 1 : n * factorial(n-1);
}

factorial(4)
4 *   factorial(3)
4 *   3 *  factorial(2)
4 *   3 *  2 *   factorial(1)
4 *   3 *  2 *   1
4 *   3 *  2
4 *   6
24

En el diagrama anterior, observamos que las llamadas recursivas se van "apilando". Una vez se ha llegado al caso base, se calcula la multiplicación al retornar de la llamada recursiva, así hasta llegar a la primera invocación.

Mostramos cómo podría optimizar un compilador el método 'factorial'.

Recordamos la versión original:

public static int factorial(int n) {
  if (n <= 1) return 1;
  else        return n * factorial(n-1);
}

Se invoca 'factorial' recursivamente sobre 'n-1'. Cuando éste retorna el valor, se multiplica por 'n'.

Sin embargo, se podría invocar 'factorial' recursivamente pero pasándole además un parámetro extra que indique qué tiene que hacer cuando termine de computar el factorial de n-1. Es decir, se podría invocar 'factorial' diciéndole:

1. Computa el valor del factorial de n-1.
2. Después multiplica ese valor por n y entonces retorna el resultado.

De esta forma 'factorial' tendría recursión de cola: la llamada recursiva sería el último mandato del método y no habría que multiplicar después.

Paso 1: Se añade un parámetro de acumulación que hace la multiplicación. El parámetro 'r' puede verse como el resultado de la llamada recursiva original.

public static int factorial(int r, int n) {
 if (n <= 1) return r;
 else        return factorial(n*r, n-1);
}

El parámetro de acumulación nos lleva cuenta de la "continuación", es decir, de qué hay que hacer (qué debe "continuar") al terminar la llamada recursiva. (La transformación CPS es más general, permite llevar funciones como parámetros de acumulación.)

Paso 2: Se reemplazan en todo el código la invocaciones de la forma 'factorial(exp)', donde 'exp' es una expresión, por 'factorial(1,exp)'. Por ejemplo, donde antes teníamos 'factorial(100)' ahora tendremos 'factorial(1,100)' puesto que se ha añadido un parámetro extra.

Paso 3: Se reemplaza la recursión de cola por un salto, tratando los parámetros como variables locales que se modifican mediante asignación.

public static int factorial(int r, int n) {
  START:
  if (n <= 1) return r;
  else  {
    r = n*r;
    n = n-1;
    goto START;
  }
}

Paso 3: Se convierte el salto en un bucle negando la condición de salida.

public static int factorial(int r, int n) {
  while (n > 1) {
    r = n*r;
    n = n-1;
  }
  return r;
}

Comparad este código con la versión iterativa que dimos al principio.

En el ejemplo del factorial el orden bien fundado es el de los enteros positivos (n > n-1 > … > 1) y se llega al caso base.

Las siguientes variantes son incorrectas:

public static int factorial(int n) {
  if (n == 1) return 1;
  else        return n * factorial(n-2);    // no alcanza el caso base
}

public static int factorial(int n) {
   return n * factorial(n-1);               // no hay caso base.
}

El último ejemplo es equivalente a un bucle infinito. Si el compilador implementa la recursión con una pila, puesto que el computador no tiene memoria infinita, eventualmente se producirá un error de desbordamiento de pila o "stack overflow". Con la optimización de recursión de cola no habrá desbordamiento y se quedará colgado como en un bucle infinito.

Mostramos el código equivalente iterativo de los ejemplos anteriores:

public static int factorial(int n) {
 int r = 1;
 while (n != 1) {
   r = n * r;
   n -= 2;
 }
 return r;
}

public static int factorial(int n) {
 int r = 1;
 while (true) {
   r = n * r;
   n--;
 }
 return r;
}

• Caso base: factorial(1) = 1
• Hipótesis de inducción: factorial(n) = n * (n-1) * … * 1

  Demostramos que se cumple factorial(n+1) = (n+1) * n * (n-1) * … * 1

    factorial(n+1)
  
  = { por la definición de factorial con n > 0}
  
    (n+1) * factorial((n+1)-1)
  
  = { aritmética }
  
    (n+1) * factorial(n)
  
  = { por la hipótesis de inducción "factorial(n) = n * (n-1) * ... * 1 }
  
    (n+1) * n * (n-1) * ... * 1
  
  

public static int mcd(int n, int m) {
  if (m == 0) return n;
  else        return mcd(m, n % m);
}

public static int mcd(int n, int m) {
  while (m != 0) {
    int tmp = m;
    m       = n % m;
    n       = tmp;
  }
return n;
}

public static int fib(int n) {
  if (n < 0)  return 0;
  if (n <= 1) return n;   /* dos casos base */
  return fib(n-1) + fib(n-2);
}

EJERCICIO: Escribe la versión iterativa.

Versión iterativa:

public static boolean member(int elem, int [] arr) {
  if (arr == null   || arr.length == 0 ||
      elem < arr[0] || elem > arr[arr.length - 1])
    return false;
  int start = 0;
  int end   = arr.length - 1;
  int m;
  while (start <= end && arr[(m = (start + end) / 2)] != elem) {
    if (elem < arr[m])
      end   = m-1;
    else
      start = m+1;
  }
  // start > end || start <= end && arr[m] == elem
  return start <= end;
}

Versión recursiva:

public static boolean member(int elem, int [] arr) {
  if (arr == null   || arr.length == 0 ||
      elem < arr[0] || elem > arr[arr.length - 1])  /* no es caso base */
    return false;
  else
    return memberRec(elem, arr, 0, arr.length-1);
}

private static boolean memberRec(int elem, int [] arr, int start, int end) {
  if (start > end)    return false;   /* caso base */
  int m = (start + end) / 2;
  if (elem == arr[m]) return true;    /* caso base */
  if (elem < arr[m])  return memberRec(elem, arr, start, m-1);
                      return memberRec(elem, arr, m+1, end);
}

El método principal no es recursivo, únicamente trata los casos frontera e invoca el método auxiliar (y por ello privado) recursivo que toma todos los parámetros necesarios para resolver el problema.

Podemos simplificar el número de casos base en uno:

private static boolean memberRec(int elem, int [] arr, int start, int end) {
  if (start >= end) return elem == arr[start];
  else {
    int m = (start + end) / 2;
    if (elem <= arr[m])
      return memberRec(elem, arr, start, m);
    else
      return memberRec(elem, arr, m+1, end);
  }
}

Observad que al unificar los dos casos base, en la primera llamada recursiva 'm' no puede decrementarse, de lo contrario el código sería incorrecto.

• Una lista de posiciones puede definirse de forma recursiva como una secuencia de nodos que es o bien vacía (caso base) o bien está formada por un nodo seguido de una secuencia de nodos.
• Los métodos recursivos sobre listas explotarán esta definición.

• Versión iterativa:

  public static <E> void show(PositionList<E> list) {
    if (list != null) {
      Position<E> cursor = list.first();
      while (cursor != null) {
        System.out.println(cursor.element());
        cursor = list.next(cursor);
      }
    }
  }
  
  

• Versión recursiva. El método principal no es recursivo, únicamente trata los casos frontera e invoca el método auxiliar (y por ello privado) recursivo. Los casos base se dan cuando el parámetro cursor es 'null' (caso en que la lista es vacía y caso en que se ha llegado al final de la lista).

  public static <E> void show(PositionList<E> list) {
    if (list != null) showRec(list, list.first());
  }
  
  private static <E> void showRec(PositionList<E> list, Position<E> cursor) {
    if (cursor == null) return;
    else {
      System.out.println(cursor.element());
      showRec(list, list.next(cursor));
    }
  }
  
  

  Como el método recursivo no devuelve ningún valor, es habitual no hacer uso del 'return' explícito y dejar únicamente la rama que hace algo distinto de simplemente retornar.

  private static <E> void showRec(PositionList<E> list, Position<E> cursor) {
    if (cursor != null) {
      System.out.println(cursor.element());
      showRec(list, list.next(cursor));
    }
  }
  
  

  Se puede subir el caso base de "lista vacía" del método recursivo auxiliar al método principal para ahorrarse una llamada recursiva:

  public static <E> void show(PositionList<E> list) {
    if (list != null && !list.isEmpty())
      showRec(list, list.first());
  }
  
  

• Versión iterativa

  public String toString() {
    String s = "[";
    for (Position<E> cursor = first(); cursor != null; cursor = next(cursor)) {
      if (cursor.element() == null)
        s += "null";
      else
        s += cursor.element().toString();
      if (cursor != last()) s += ", ";
    }
    s += "]";
    return s;
  }
  
  

  Versión recursiva con método auxiliar privado:

  public String toString() {
     return "[" + toStringRec(first()) + "]";
  }
  
  private String toStringRec(Position<E> cursor) {
     if (cursor == null) return "";
     String s;
     if (cursor.element() == null)
       s = "null";
     else
       s = cursor.element().toString();
     if (cursor != last())
       s += ", ";
     return s + toStringRec(next(cursor));
  }
  
  

  Versión anterior con expresiones condicionales:

  public String toString() {
     return "[" + toStringRec(this.first()) + "]";
  }
  
  private String toStringRec(Position<E> cursor) {
     if (cursor == null) return "";
     return (cursor.element() == null ? "null" ? cursor.element().toString())
          + (cursor != last() ? ", " : "")
          + toStringRec(this.next(cursor));
  }
  
  

• Versión recursiva con parámetro de acumulación:

  public String toString() {
    return toStringRec("[", first());
  }
  
  private String toStringRec(String acum, Position<E> cursor) {
    if (cursor == null) return acum + "]";
    if (cursor.element() == null)
      acum += "null";
    else
      acum += cursor.element().toString();
    if (cursor != last())
      acum += ", ";
    return toStringRec(acum, list.next(cursor));
  }
  
  

  El código anterior puede simplificarse separando los casos de lista vacía y final de lista:

  public String toString() {
    if (isEmpty()) return "[]";
    else return toStringRec("[", first());
  }
  
  private String toStringRec(String acum, Position<E> cursor) {
    if (cursor.element() == null)
      acum += "null";
    else
      acum += cursor.element().toString();
  
    if (cursor == last())
      return acum + "]";
    else
      return toStringRec(acum + ",", list.next(cursor));
  }
  
  

• Consideramos que los elementos pueden ser null:

  public static int sumaElems(PositionList<Integer> list) {
    if (list == null) return 0;
    else return sumaRec(list, list.first());
  }
  
  private static int sumaRec( PositionList<Integer> list
                            , Position<Integer> cursor) {
    if (cursor == null)
      return 0;
    else if (cursor.element() == null)
      return sumaRec(list,list.next(cursor));
    else
      return cursor.element() + sumaRec(list, list.next(cursor));
  }
  
  

  Evitamos una llamada recursiva subiendo el caso base al método principal:

  public static int sumaElems(PositionList<Integer> list) {
    if (list == null || list.isEmpty()) return 0;
    else return sumaRec(list, list.first());
  }
  
  

  También podemos simplificar el método recursivo:

  private static int sumaRec( PositionList<Integer> list
                            , Position<Integer> cursor) {
    if (cursor == null) return 0;
    return (cursor.element() == null ? 0 : cursor.element())
           + sumaRec(list, list.next(cursor));
  }
  
  

  Otra versión que utiliza una variable auxiliar donde se acumula la suma (veremos el parecido con la versión con parámetro de acumulación de la siguiente sección):

  private static int sumaRec( PositionList<Integer> list
                            , Position<Integer> cursor) {
    int r = 0;
    if (cursor != null)
      r = (cursor.element() == null ? 0 : cursor.element())
          + sumaRec(list, list.next(cursor));
    return r;
  }
  
  

public static int sumaElems(PositionList<Integer> list) {
  if (list == null || list.isEmpty()) return 0;
  else return sumaRec(0, list, list.first());
}

private static int sumaRec( int r
                          , PositionList<Integer> list
                          , Position<Integer> cursor) {
  if (cursor == null)
    return r;
  else if (cursor.element() == null)
    return sumaRec(r, list, list.next(cursor));
  else
    return sumaRec(r + cursor.element(), list, list.next(cursor));
}

El código del método recursivo auxiliar puede simplificarse:

private static int sumaRec( int r
                          , PositionList<Integer> list
                          , Position<Integer> cursor) {
  if (cursor != null)
    r = sumaRec( r + (cursor.element() == null ? 0 : cursor.element())
               , list
               , list.next(cursor))
  return r;
}

EJERCICIO: Eliminar la recursión de cola de forma similar a cómo se eliminó para el método factorial en *Métodos recursivos.

public static void borra(PositionList<E> list, E elem) {
  if (list != null) borraRec(list, elem, list.first());
}

private static void borraRec( PositionList<E> list,
                            , E elem
                            , Position<E> cursor) {
  if (cursor != null) {
    if (cursor.element() != null && cursor.element().equals(elem))
      list.remove(cursor);
    else
      borraRec(list, elem, list.next(cursor));
  }
}

public static void borra(PositionList<E> list, E elem) {
  if (list != null) borraRec(list, elem, list.first());
}

private static void borraRec( PositionList<E> list
                            , E elem
                            , Position<E> cursor) {
  if (cursor != null) {
    Position<E> aux = cursor;
    cursor = list.next(cursor);
    if (aux.element() != null && aux.element().equals(elem))
      list.remove(aux);
    borraRec(list, elem, cursor);
  }
}

Código alternativo del método recursivo:

private static void borraRec( PositionList<E> list
                            , E elem
                            , Position<E> cursor) {
  if (cursor != null) {
    Position<E> nxt = list.next(cursor);
    if (cursor.element() != null && cursor.element().equals(elem))
      list.remove(cursor);
    borraRec(list, elem, nxt);
  }
}

• Para simplificar asumimos que los elementos no son null:

  public static void insertOrden(PositionList<Integer> list, E elem) {
    if (list != null) insertRec(list, elem, list.first());
  }
  
  private static void insertRec( PositionList<Integer> list
                               , E elem
                               , Position<E> cursor) {
    if (cursor == null)
      list.addLast(elem);
    else if (elem <= cursor.element())
      list.addBefore(cursor, elem);
    else
      insertRec(list, elem, list.next(cursor));
  }
  
  

• EJERCICIO: Añadir el código necesario para considerar elementos null.
• EJERCICIO: Optimiza el código de forma que no se haga la llamada recursiva si el elemento a insertar es mayor que el último elemento de la lista. En ese caso hay que añadir el elemento al final de la lista sin más.

• Interfaces: java.util.Comparator<T> y java.lang.Comparable<T>.

• Interfaces: Entry.java, PriorityQueue.java.
• Clases: EmptyPriorityQueueException.java, InvalidKeyException.java

• Cola del supermercado donde la prioridad del cliente es su pertenencia a algún colectivo (personas mayores, discapacidad, etc.)
• Sala de urgencias de un hospital donde la prioridad del paciente es la gravedad de la urgencia.
• Cola de procesos en memoria para ejecutar usada por el núcleo del sistema operativo, donde la prioridad del proceso es determinada por el propio sistema operativo, el usuario o el administrador.

Para los elementos de igual prioridad se sigue un esquema FIFO.

• Dos o más entradas pueden tener la misma clave pero distintos valores. En otras palabras, valores distintos pueden tener la misma prioridad. Ejemplo: dos pacientes diferentes pueden tener dolencias de igual gravedad.
• Dos o más entradas pueden tener los mismos valores pero distintas claves. En otras palabras, el mismo valor puede tener distintas prioridades en distintas entradas. Ejemplo: el mismo paciente puede tener dos dolencias, una grave y otra menos grave.
• Puede modificarse la clave o el valor de una entrada. En el primer caso estamos diciendo que la prioridad de un valor puede cambiarse para esa entrada.

public interface Entry<K,V> {
  public K getKey();
  public V getValue();
}

No hay "setters", por tanto no es posible modificar una entrada a través de los métodos del interfaz.

public class MyEntry<K,V> implements Entry<K,V> {
  private K k;
  private V v;

  public MyEntry(K k, V v) {
    this.k = k;
    this.v = v;
  }

  public MyEntry(Entry<K,V> e) { // copy constructor
    this.k = e.getKey();
    this.v = e.getValue();
  }

  public K getKey()   { return k; }

  public V getValue() { return v; }

  public String toString() {
    return "(" + k.toString()  + "," + v.toString() + ")";
  }

  public boolean equals(Object o) {
    if (o == this) return true;
    if (o instanceof MyEntry<?,?>) {
      MyEntry<K,V> m = (MyEntry<K,V>) o;
      return this.k.equals(m.getKey()) && this.v.equals(m.getValue());
    } else return false;
  }
}

public class Price {
  private int units;
  private int cents;

  public Price(int u, int c) {
    this.units = u;
    this.cents = c;
  }

  public Price(int u) {
    this(u,0);
  }
  ...
}

public class Book {
   private Price  price;
   private String title;

   public Book(Price p, String t) {
     price = p;
     title = t;
   }

   public Price getPrice() { return price; }
   ...
}

public class Main {
  public static void main (String args []) {

    Book b = new Book(new Price(0), "Guión AED");

    Entry<Price,Book> e = new MyEntry<Price,Book>(b.getPrice(), b);

    ...

  }
}

• El método 'insert' devuelve el objeto entrada insertado en la cola. Dicho objeto es construido por la propia cola, pues 'insert' recibe por separado la clave y el valor. De dicho objeto sólo podemos obtener la clave y el valor a través de los métodos del *Interfaz Entry<K,V>.
• El método 'min' devuelve el objeto entrada de menor clave (mayor prioridad) sin quitarlo de la cola. Es un método "observador".
• El método 'removeMin' devuelve el objeto entrada de menor clave (mayor prioridad) y lo quita de la cola. Es un método "observador" con un efecto secundario "modificador".

• 'EmptyPriorityQueueException' se lanza cuando se intenta obtener o borrar la entrada de clave mínima en una cola vacía.
• 'InvalidKeyException' se lanza cuando la clave no es válida, por ejemplo si es null o no tiene igualdad o orden total definido para ella (esto lo veremos en *Ordenes totales).

public static void main(String args[]) {

  PriorityQueue<Integer,String> cola = new UnaClaseParaPQ<Integer,String>();

  Alumno alumno = new Alumno("Alumno de la ETSIINF");

  cola.insert(1, "Programación II");
  cola.insert(4, "Algorítmica Numérica");
  cola.insert(3, "Lenguajes y Autómatas");
  cola.insert(0, "AED");

  while (cola.size() > 0)
    alumno.estudiar(cola.removeMin());
}

• Definirán clases y objetos para claves y valores.
• Podrán definir varios comparadores para objetos clave (esta parte la vemos en *Interfaces Comparable<T> y Comparator<T>).
• Construirán una o varias colas.
• Invocarán los métodos de la cola según las necesidades de la aplicación.

K x V = { (k,v) | k está en K y v está en V }

1. Hay una relación de igualdad computable (existe un programa que la computa) en K que permite determinar si una clave es igual o no a otra. (El requisito de computabilidad es obvio pero importante, pues según el famoso resultado de Alan Turing, existen funciones de naturales a naturales que no son computables, es decir, no existe un programa que compute sus valores.)

   La relación de igualdad es una relación de equivalencia, es decir, cumple las siguientes reglas:

   • Reflexiva: para toda clave k se cumple k = k.
   • Simétrica: para toda k₁ y k₂, si k₁ = k₂ entonces k₂ = k₁.
   • Transitiva: para toda k₁, k₂ y k₃, si k₁ = k₂ y k₂ = k₃ entonces k₁ = k₃.
2. Hay una relación total computable (hay un programa que la computa) que satisface las siguientes reglas:
   • Totalidad: para toda k₁ y k₂, o bien k₁ <= k₂ o bien k₂ <= k₁, una de ellas debe ser cierta.
   • Antisimétrica: para toda k₁ y k₂, si k₁ <= k₂ y k₂ <= k₁ entonces k₁ = k₂.
   • Transitiva: para toda k₁, k₂ y k₃, si k₁ <= k₂ y k₂ <= k₃ entonces k₁ <= k₃.

   Totalidad y antisimétrica implican reflexiva.

  {0,1,2}
   /   \
{0,1}  {0,2}
   \   /
    {0}

Sabemos que {0} <= {0,2} es cierto y que {0,2} <= {0} es falso.

Pero {0,1} <= {0,2} es falso y {0,2} <= {0,1} es falso.

Un orden parcial define un retículo. Un orden total define una recta.

• Clave mínima: si para toda k se tiene k_min <= k entonces k_min es una clave mínima.
• Clave máxima: si para toda k se tiene k <= k_max entonces k_max es una clave máxima.
• Las claves mínimas y máximas son únicas porque el orden es total.
• Supremo: se toma la unión de K con un conjunto formado por un único elemento sup, se extiende la relación de orden a esa unión, y se postula que k <= sup para toda k.

public interface Comparable<T> {
  public int compareTo(T t);
}

public interface Comparator<T> {
   public int compare(T t1, T t2);
}

• La implementación de 'Comparable<T>' por la clase 'T' hace que ésta tenga que implementar el método 'compareTo' para comparar dos objetos de 'T'. Ese método de comparación queda fijo para todos los objetos de 'T' y se le llama orden natural.

  Dados 't1' y 't2' objetos de 'T', la invocación t1.compareTo(t2) debe devolver un entero 'i' tal que:

  • i < 0 si t1 es menor que t2.
  • i == 0 si t1 es igual que t2.
  • i > 0 si t2 es menor que t1.
• El orden natural es consistente con equals cuando se cumple que 't1.compareTo(t2) == 0' si y sólo si 't1.equals(t2)'. El método 'equals' debe ser simétrico cuando t1 != null y t2 != null, por tanto 'compareTo' también debe ser simétrico en ese caso: la expresión 't1.compareTo(t2) == t2.compareTo(t1)' debe ser cierta.
• Ejemplo: la clase 'String' de Java implementa 'Comparable<String>' y por tanto implementa el método 'compareTo' que se puede usar para comparar cadenas de caracteres. El método de comparación elegido computa el orden lexicográfico de las cadenas.

  public class String implements Comparable<String> {
    public int compareTo(String s) {
      /* Comparación lexicográfica entre la cadena de este objeto y la
       * cadena 's' pasada como argumento
       */
      ...  // código aquí que no nos interesa ahora
    }
  }
  
  

• Ejemplo de uso:

  public static void main(String [] s) {
    String s1 = "Terabyte";   /* 10^12 bytes.  */
    String s2 = "Terapeuta";  /* 10^12 peutas. */
  
    int r = s1.compareTo(s2);
    if (r < 0)
      System.out.println(s1 + " es menor que " + s2);
    else if (r == 0)
      System.out.println(s1 + " es igual que " + s2);
    else
      System.out.println(s1 + " es mayor que " + s2);
  }
  
  

  El siguiente método indica si una clave está en una lista de entradas, el código asume que 'Comparable<K>' está implementado por la clase 'K' de las claves:

  public static <K,V> boolean search(K k, PositionList<Entry<K,V>> list) {
    boolean found = false;
    Iterator<Entry<K,V>> it = list.iterator();
    while (it.hasNext() && !found)
      found = it.next().getKey().compareTo(k) == 0 ;
    return found;
  }
  
  

• Usando 'compareTo' sólo hay una forma de comparar cadenas. Para poder comparar cadenas de otra forma habría que reescribir el código de 'compareTo' y recompilar.

• Los objetos de aquellas clases que implementen el interfaz 'Comparator<T>' implementan un método de comparación 'compare' para objetos de la clase 'T'.
• Dados 't1' y 't2' objetos de 'T' y 'c' un objeto comparador, la invocación c.compare(t1,t2) debe devolver un entero 'i' tal que:
  • i < 0 si t1 es menor que t2.
  • i == 0 si t1 es igual que t2.
  • i > 0 si t2 es menor que t1.

  El comparador es consistente con equals cuando se cumple que 'c.compare(t1,t2) == 0' si y sólo si 't1.equals(t2)'. El método 'equals' debe ser simétrico cuando t1 != null y t2 != null, por tanto 'compare' también debe ser simétrico en ese caso: la expresión 'c.compare(t1,t2) == c.compare(t2,t1)' debe ser cierta.

• Se pueden usar diferentes objetos comparadores para comparar objetos de clase 'T'. Por ejemplo: podemos definir varios comparadores para la clase 'String': comparador lexicográfico, tamaño, coste de compresión bajo zip, etc.

  Una clase de comparadores de cadenas de caracteres que las comparan según su longitud:

  public class SizeStringComparator implements Comparator<String> {
    public int compare(String s1, String s2) {
      return s1.length() - s2.length();
    }
  }
  
  

  Una clase de comparadores de cadenas de caracteres que las comparan según el orden lexicográfico:

  public class LexicographicStringComparator implements Comparator<String> {
    public int compare(String s1, String s2) {
      int minLength = Math.min(s1.length(),s2.length());
      for (int i = 0; i < minLength && s1.charAt(i) == s2.charAt(i); i++) ;
      if (i < minLength)
        return s1.charAt(i) < s2.charAt(i) ? -1 : 1 ;
      else
        return s1.length() - s2.length();
    }
  }
  
  

• Ejemplo de uso:

  public static void main(String [] s) {
    String  s1 = "Terabyte";
    String  s2 = "Terapeuta";
    SizeStringComparator          sc = new SizeStringComparator();
    LexicographicStringComparator lc = new LexicographicStringComparator();
    int r;
  
    r = lc.compare(s1,s2);
    if (r < 0)
      System.out.println(s1 + " es menor que " + s2);
    else if (r == 0)
      System.out.println(s1 + " es igual que " + s2);
    else
      System.out.println(s1 + " es mayor que " + s2);
  
    r = sc.compare(s1,s2);
    if (r < 0)
      System.out.println(s1 + " es menor que " + s2);
    else if (r == 0)
      System.out.println(s1 + " es igual que " + s2);
    else
      System.out.println(s1 + " es mayor que " + s2);
  }
  
  

  El siguiente método indica si una clave está en una lista de entradas, el código recibe un comparador para la clase 'K' de las claves:

  public boolean <K,V> search(K k, PositionList<Entry<K,V>> list, Comparator<K> c) {
    boolean found = false;
    Iterator<Entry<K,V>> it = list.iterator();
    while (it.hasNext() && !found)
      found = c.compare(it.next().getKey(),k) == 0 ;
    return found;
  }
  
  

• Comparadores y 'static':

  El código 'main' anterior crea un único objeto para cada clase comparador (crea un objeto de clase 'SizeStringComparator' y otro objeto de clase 'LexicographicStringComparator'). Cualquier nuevo objeto de la clase 'SizeStringComparator' será idéntico en funcionalidad a los anteriores: todos implementan el método 'compare' de igual forma. Y lo mismo pasa con 'LexicographicStringComparator'. Parece razonable poder declarar 'compare' como 'static' para no tener que crear objetos comparadores. Más concretamente, en vez de crear un objeto e invocarle 'compare':

  SizeStringComparator sc = new SizeStringComparator();
  int r = sc.compare("Hola", "Hora");
  
  

  tendría sentido no tener que crear objetos e invocar 'compare', podríamos usar el nombre de la clase si 'compare' se declara como 'static':

  int r = SizeStringComparator.compare("Hola", "Hora");
  
  

  Para eso el método 'compare' tiene que declarase como 'static':

  public class SizeStringComparator implements Comparator<String> {
    public static int compare(String s1, String s2) { ... }
  }
  
  

  public class LexicographicStringComparator implements Comparator<String> {
    public static int compare(String s1, String s2) { ... }
  }
  
  

  Sin embargo,

  1. No es posible: no podemos declarar el método 'compare' como 'static' porque no está declarado así en el interfaz 'Comparator'. El compilador dará un error. (El error no se soluciona declarando la clase del comparador como 'static': que una clase sea 'static' no significa que sus métodos sean 'static', son cosas diferentes, consultad [JLS'3E]).
  2. No es correcto: en general los comparadores tienen que ser objetos pues a veces tienen que recibir parámetros a través de un constructor.

     Ejemplo: un comparador lexicográfico de listas de posiciones:

     public class PositionListComparator implements Comparator<PositionList<E>> {
       private Comparator<E> elemComp;  // comparador de elementos
     
       public PositionListComparator(Comparator<E> elemComp) {
         this.elemComp = elemComp;
       }
     
       public int compare(PositionList<E> l1, PositionList<E> l2) {
         if (l1 == null && l2 == null || l1.isEmpty() && l2.isEmpty())
           return 0;
     
         Iterator<E> it1 = l1.iterator();
         Iterator<E> it2 = l2.iterator();
         int r = 0;
     
         while ( it1.hasNext() &&
                 it2.hasNext() &&
                 (r = elemComp.compare(it1.next(),it2.next())) == 0 )
           ;
     
         if (r != 0) return r;
         else return l1.size() - l2.size();
       }
     }
     
     

     El método 'compare' del comparador de listas tiene que utilizar el método 'compare' de los elementos para determinar si una lista es menor, igual o mayor que otra. Se pueden tener distintos objetos comparadores de listas donde cada uno utiliza distintos comparadores de elementos.

• Comparador lexicográfico de puntos en dos dimensiones:

  public class Lexicographic2DPointComparator implements Comparator<2DPoint> {
    private int xa, ya, xb, yb;
    public int compare(2DPoint a, 2DPoint b) {
      return a.getX() != b.getX() ? b.getX() - a.getX() : b.getY() - a.getY();
    }
  }
  
  

• Si un objeto es de una clase que implementa el interfaz 'Comparable<T>' entonces se puede crear un objeto 'Comparator<T>' por defecto para dicha clase:

  import java.util.Comparator;
  import java.lang.Comparable;
  
  public class DefaultComparator<T> implements Comparator<T> {
    public int compare(T a, T b) throws UnsupportedOperationException {
      if (a instanceof Comparable<?>)
        return ((Comparable<T>) a).compareTo(b);
      else throw new UnsupportedOperationException();
    }
  }
  
  

• Si 'T' implementa 'Comparable<T>' entonces dispone de 'compareTo' que puede usarse para comparar. En otro caso se lanza la excepción.
• Ejemplo de uso:

  public class Main {
    public static void main (String [] arg) {
      DefaultComparator<String> c = new DefaultComparator<String>();
      String s1 = new String("aa");
      String s2 = new String("bb");
      System.out.println(c.compare(s1,s2));
  
      DefaultComparator<Object> o = new DefaultComparator<Object>();
      try {
        System.out.println(o.compare(new Object(), new Object()));
      } catch (UnsupportedOperationException e) {
        System.out.println("Object no implementa Comparable<Object>");
      }
    }
  }
  
  

• El problema de este comparador por defecto es que la excepción se lanza al invocarse 'compare'. Sería mejor que la excepción se lanzase al crear el objeto comparador. Para hacer bien esto hay que usar trucos de java, en particular el API de reflexión que nos permite pasar a un constructor un valor en tiempo de ejecución que representa el tipo 'T' de un elemento. El constructor puede entonces comprobar si ese tipo implementa 'Comparable<?>' y lanzar la excepción en caso negativo.

public class PositionListPriorityQueue<K,V> implements PriorityQueue<K,V> {

  private PositionList<Entry<K,V>> lista;
  private Comparator<K> comp;

  public PositionListPriorityQueue(Comparator<K> comp) {
    this.lista = new NodePositionList<Entry<K,V>>();
    this.comp  = comp;
  }
  ...
}

Se pueden dar más constructores y se puede intentar usar un comparador por defecto *'Comparator<T>' a partir de 'Comparable<T>'.

Complejidad:

public class PositionListPriorityQueue<K,V> implements PriorityQueue<K,V> {

  private PositionList<Entry<K,V>> lista;
  private Comparator<K> comp;
  private Entry<K,V> minEntry;

  public PositionListPriorityQueue(Comparator<K> comp) {
    this.lista    = new NodePositionList<Entry<K,V>>();
    this.comp     = comp;
    this.minEntry = null;
  }

  public Entry<K,V> min() throws EmptyPriorityQueueException {
    if (this.isEmpty()) throw new EmptyPriorityQueueException();
    return minEntry;
  }

  public Entry<K,V> insert(K k, V v) {
    Entry<K,V> e = new MyEntry<K,V>(k,v);
    if (this.isEmpty())
      minEntry = e;
    else if (comp.compare(e.getKey(),minEntry.getKey()) < 0)
      minEntry = e;
    ...  // resto del código de insert
  }
  ...
}

Complejidad:

Aunque 'min' es constante, el borrado sigue teniendo O(n) porque hay que buscar la siguiente entrada más pequeña en la lista para actualizar el atributo 'minEntry'. Cuando la lista es vacía, 'minEntry' es null.

Complejidad:

public static <E> void pqSort(PositionList<E> list, Comparator<E> c) {
  PriorityQueue<E,Object> pq = new UnaClaseAquí<E,Object>(c);

  while (list.size() > 0)
    pq.insert(list.remove(list.first()),null);

  while (pq.size() > 0)
    list.addLast(pq.removeMin().getKey());
}

En esta versión se usan los elementos de la lista como claves y se ignoran los valores.

Versión alternativa que usa los elementos como clave y valor:

public static <E> void pqSort(PositionList<E> list, Comparator<E> c) {
  PriorityQueue<E,E> pq = new UnaClaseAquí<E,E>(c);

  while (list.size() > 0) {
    E e = list.first().element();
    pq.insert(list.remove(list.first()),e);
  }

  while (pq.size() > 0)
    list.addLast(pq.removeMin().getValue());
}

Versión que ordena arrays:

public static <E> void pqSort(E [] v, Comparator<E> c) {
  PriorityQueue<E,E> pq = new UnaClaseAquí<E,E>(c);

  for (E e : v)
    pq.insert(e,e);

  for (int i = 0; pq.size() > 0; i++)
    v[i] = pq.removeMin().getValue();
}

1. Si la cola con prioridad se implementa mediante una lista desordenada tenemos el algoritmo selection-sort cuya complejidad es O(n²) con n el tamaño de la lista. Se llama así porque la complejidad está en 'removeMin', es decir, en seleccionar la entrada con clave mínima en la lista desordenada atributo de la cola.
2. Si la cola con prioridad se implementa mediante una lista ordenada tenemos el algoritmo insertion-sort cuya complejidad es O(n²) con n el tamaño de la lista. Se llama así porque la complejidad está en 'insert', es decir, en insertar la entrada de forma ordenada en la lista ordenada atributo de la cola.
3. Si la cola con prioridad se implementa usando un montículo (que veremos en el tema *Montículos) tenemos el algoritmo heap-sort cuya complejidad es O(n*log(n)) con n el tamaño de la lista a ordenar.

• Complejidad temporal: complejidad del tiempo de ejecución.
• Complejidad espacial: complejidad del espacio de memoria utilizado.

Al crecer el tamaño de la entrada la complejidad del programa o bien se mantiene constante o bien crece en función de dicho tamaño. No puede decrecer, incluso si se usa más espacio, porque se introduce el problema de buscar en el espacio.

EJEMPLO: un método que indica si un elemento está o no en un array. El "tamaño de la entrada" en este caso es el tamaño del array donde se hace la búsqueda. Cuanto más grande el tamaño del array más tarda el método en encontrar el elemento. El tamaño del elemento no es importante, incluso si se trata de un dato de gran tamaño en bits, pues sólo afecta la complejidad en tiempo total en un valor constante, es decir, sólo suma un valor constante al valor de complejidad total.

EJEMPLO: un método que toma un elemento 'elem' y dos arrays 'arr1' y 'arr2' tal que 'arr2.length >= arr1.length'. El método busca 'elem' en 'arr1'. Si no está entonces termina y devuelve null. Si está, sea 'i' la posición de 'arr1' tal que 'elem == arr1[i]', entonces el método devuelve el elemento en 'arr2[i]'. Aquí el "tamaño de la entrada" es 'arr1.length' pues el segundo array no es usado en la búsqueda. Cuanto más grande es el tamaño de 'arr1' más tarda el método en encontrar el elemento. El tamaño de 'arr2' no afecta el tiempo, pues el acceso directo a un array se asume que tiene complejidad en tiempo constante (es constante respecto al tamaño del array *Complejidad: algunos comentarios y ejercicios.)

• El elemento a buscar es siempre el primero.
• El elemento a buscar está por el medio, o a veces está el primero y a veces en medio y a veces está el último o no está (y consideramos estos casos como equiprobables).
• El elemento a buscar está siempre el último o no está.
• El elemento a buscar está más veces el primero que en otra posición.

Por tanto, se estudia la complejidad en caso mejor, caso (pro)medio, caso peor, y caso amortizado.

Hay que considerar cuál es la entrada que daría el caso peor. En el ejemplo anterior, la peor entrada son arrays donde el elemento está siempre el último o no está, pues el programa siempre recorre el array completo.

1. Análisis experimental [analysis.pdf pp.3-4]. Se escribe el programa en un lenguaje de programación concreto. Requiere análisis estadístico (con buen muestreo de datos de entrada) y probabilístico (distribución de datos). Los resultados dependen del entorno de ejecución (lenguaje de programación, compilador, sistema operativo, arquitectura, entorno dinámico, etc.)
2. Análisis teórico [analysis.pdf p.5-8]. Se estudian los programas independientemente del entorno de ejecución. El lenguaje utilizado puede ser pseudocódigo, una notación que abstrae (alto nivel) las particularidades de un paradigma de programación.

   Se asume que la complejidad de las operaciones del lenguaje pseudocódigo es proporcional en una constante a la complejidad real de su implementación en un lenguaje de programación concreto y ejecutándose en entorno concreto. Por tanto, la complejidad del programa en pseudocódigo es proporcional en una constante a la complejidad de su implementación. Dicho de otro modo, los factores a tener en cuenta en una implementación real afectan la complejidad teórica en un factor constante [analysis.pdf 14].

   De esta forma, podemos estudiar programas en un entorno de ejecución concreto (p.ej., programa escrito en Java compilado con Eclipse y ejecutándose en las Aulas Informáticas) asumiendo que la complejidad del entorno es una función constante del programa en pseudocódigo.

Pero un interfaz puede exigir que ciertos métodos se implementen con una complejidad determinada, forzando así una representación y familia de algoritmos para el TAD. Finalmente, la elección de métodos en los interfaces puede sugerir o descartar ciertas implementaciones.

• [GT(I)'10 Sección 4.1]:
  • Función constante: f(n) = c con c constante, p.ej., f(n) = 10.
  • Función polinomial: f(n) = c₁ * n^e₁ + … + c_m * n^e_m donde c_i (coeficientes) y e_i (exponentes) son enteros, p.ej.,

    f(n) = 2 * n² + 7 * n - 20.

    El grado del polinomio se define como el exponente de mayor valor. Por ejemplo, el polinomio anterior tiene grado 2.

    Entre las funciones polinomiales encontramos la lineal (grado 1), cuadrática (grado 2) y cúbica (grado 3).

  • Función logarítmica, será casi siempre en base 2, por tanto en vez de 'log₂(n)' escribiremos 'log(n)'.
  • Función exponencial: f(n) = cⁿ con c constante, p.ej., f(n) = 2ⁿ.
  • La funciones 'log(n)' y '2ⁿ' son inversas: log₂(x) = y <=> 2^y = x.
    • log₂(2^x) = x
    • 2^log₂(x) = x
  • Función n-log-n: f(n) = n * log₂(n)
  • Sumas aritméticas y geométricas.
  • Razones de crecimiento.
  • Funciones techo ('ceiling') y suelo ('floor').
• Algunas cifras comparativas:

  Función	n = 32	n = 64	n = 128
  log2(n)	5	6	7
  n	32	64	128
  n * log2(n)	160	384	896
  n2	1.024	4.096	16.384
  n3	32.768	262.144	2.097.152
  2n	4.294.967.296	18.446.744.073.709.551.616	(no cabe)

  • 2ⁿ para n = 128 : 340.282.366.920.938.463.463.374.607.431.768.211.456
  • nⁿ para n = 32 :

    1.461.501.637.330.902.918.203.684.832.716.283.019.655.932.542.976

• Problemas intratables: polinomiales a partir de un 'n' medio, exponenciales a partir de un 'n' relativamente bajo, etc.

• Intuición: establecer la complejidad de una función de 'n' indicando otra función proporcional que la acota asintóticamente.
• Definición Matemática:

  Sean f y g dos funciones de naturales a reales. Se dice que f(n) es del orden de g(n), o f(n) es O(g(n)), si existe una constante real c > 0 y una constante natural n₀ >= 1 tal que f(n) <= c * g(n) para n >= n₀

• Intuición: a partir de un valor n₀ de la entrada, la función c * g(n) acota los valores de la función f(n) cuando n tiende a infinito.
• Ver tabla en [analysis.pdf p.21].
• O(0) no tiene sentido.
• Una escala de complejidad de menor a mayor:
  1. Constante: O(1)
  2. Logarítmica: O(log(n))
  3. Lineal: O(n)
  4. N-Log-N: O(n*log(n))
  5. Cuadrática O(n²)
  6. Cúbica: O(n³)
  7. Polinomial: O(n^m) de orden m
  8. Exponencial: O(2ⁿ) .. O(mⁿ)
• Ejemplos [analysis.pdf p.20].
• Todas las funciones constantes son O(1): Sea f(n) = c función constante. Entonces f(n) <= c * g(n) con g(n) = 1 y n₀ = 1.
• Todas las funciones polimórficas son O(n^e₁) donde e₁ es el exponente de mayor grado: Sea f(n) = c₁ * n^e₁ + … + c_m * n^e_m tal que e₁ es el exponente de mayor grado. Entonces existe un coeficiente c y un n₀ tal que f(n) <= c * n^e₁ para n >= n₀. Es decir, multiplicando n^e₁ un número c de veces podemos hacer el resultado mayor que lo que vale el resto del polinomio c₂ * n^e₂ + … + c_m * n^e_m, pues n^e₁ crece mucho más rápido que n^e₂, …, n^e_m.
• En las funciones polinomiales, se ignoran factores constantes y de orden inferior [analysis.pdf pp.20-23]. Esto viene justificado por el algebra de O():
  • O(c*f(n)) es O(f(n))
  • O(f(n) + g(n)) es O(f(n)) si g(n) es O(f(n))
  • O(f(n) + g(n)) es O(g(n)) si f(n) es O(g(n))

  Pero CUIDADO: [GT(I)'10, p.176, "Some Words of Caution"]: "we should at least be somewhat mindful of the constant factors and lower order terms we are 'hiding'". Ejemplo: O(10^100*n).

• Análisis de complejidad: se calcula f(n) y se determina la g(n) más cercana en la jerarquía de complejidad tal que f(n) es O(g(n)). [analysis.pdf pp.20-23] [GT(I)'10, p.173, "Characterizing Functions in Simplest Terms"]

• [analysis.pdf pp.29-31] [GT(I)'10, p.174]

El indexado de un array se hace en base a expresiones y es asimismo una expresión. El acceso a un array mediante un índice se hace mediante aritmética. Sea 'arr' una referencia a un array, sea 'i' un índice tal que 'i < arr.length'. La expresión 'arr[i]' es equivalente a "obtén el elemento en la dirección de memoria arr + i * elemTypeSize", donde 'arr' es la dirección de memoria donde está el primer elemento del array, y 'elemTypeSize' es el tamaño de memoria que ocupa un elemento en el array.

              i
|---+---+---+---+---...........+---|
|   |   |   | X |                  |
|---+---+---+---+---...........+---|
  ^ \___/
  |   ^
 arr  |
      |
   elemTypeSize

public static int factorial(int n) {
  if (n <= 1) return 1;
  else        return n * factorial(n-1);
}

La complejidad temporal T(n) en caso peor de 'factorial(n)' para un entero 'n' dado puede darse a partir de la definición:

T(n) =  | c               si n <= 1
        | T(n-1) + d(n)   en otro caso

donde:

• 'c' es la complejidad del caso base y es una constante mayor que cero.
• 'd(n)' es la complejidad de multiplicar por 'n' que es una función de 'n'. La complejidad depende de la representación de los enteros y del algoritmo de multiplicación utilizado, en general el de la unidad aritmética del computador.

Tenemos una ecuación de recurrencia que expandimos hasta encontrar el patrón, y resolvemos cuando se llega al caso base:

T(n) =  T(n-1) + d(n)
     =  T(n-2) + d(n-1) + d(n)
     =  T(n-3) + d(n-2) + d(n-1) + d(n)
     =  ...

El patrón es T(n-k) + SUMA desde i=n-k+1 hasta i=n de d(i)

El caso base se alcanza en T(1), es decir, cuando n - k = 1, es decir, cuando k = n - 1.

Sustituimos el valor de k en el patrón:

T(n-(n-1)) =  T(1) + SUMA desde i=2 hasta i=n de d(i)
           =  c    + SUMA desde i=2 hasta i=n de d(i)

Sabiendo que 'SUMA desde i=2 hasta i=n de d(i)' está acotado por 'n * d(n)' podemos establecer que T(n) es O(n * d(n)).

Escribimos la ecuación de recurrencia para la versión de 'member' en la que hay un único caso base. El tamaño de la entrada 'n' es el tamaño marcado entre 'start' y 'end', que cuando son iguales (caso base) marcan una posición del vector:

T(n) =  | c            si n <= 1
        | T(n/2) + d   en otro caso

donde

• 'c' es la complejidad del caso base y es una constante mayor que 0.
• 'd' es la complejidad de determinar si 'elem <= arr[m]'.
• 'T(n/2)' es la complejidad de cada llamada recursiva, pero son excluyentes y sólo se ejecutará una en cada paso recursivo.

Expandimos la ecuación:

T(n) =  T(n/2) + d
     =  T(n/4) + d + d
     =  T(n/4) + 2 * d
     =  T(n/8) + d + 2 * d
     =  T(n/8) + 3 * d
     =  ...

El patrón es T(n/2^k) + k * d.

El caso base se alcanza en T(1), es decir, cuando n/2^k = 1, es decir, cuando k = log₂(n).

Sustituimos el valor de k en el patrón:

  T(n/2^{log_2(n)}) + log_2(n) * d

=

  T(1) + log_2(n) * d

=

  c    + log_2(n) * d

Lo que indica que T(n) es O(log₂(n)).

T(n) =  | c                si n <= 1
        | 2 * T(n/2) + d   en otro caso

Expandimos la ecuación:

T(n) =  2 * T(n/2) + d
     =  2 * 2 * T(n/4) + d + d
     =  4 * T(n/4) + 2 * d
     =  ...

El patrón es 2^k * T(n/2^k) + k * d.

El caso base se alcanza en T(1), es decir, cuando n/2^k = 1, es decir, cuando k = log₂(n).

Sustituimos el valor de k en el patrón:

  2^(log_2(n)) * T(n/2^{log_2(n)}) + log_2(n) * d

=

  n            * T(1)              + log_2(n) * d

=

  n            * c                 + log_2(n) * d

Lo que indica que T(n) es O(n).