miércoles, 2 de septiembre de 2009

Anillo inmutable

Se me presentó un caso para el que necesité un tipo de colección que no está en la librería estándar de Java ni la de Scala: una lista circular. Que se la pueda recorrer en ambos sentidos, que no tenga fin. Seguramente hay implementaciones por ahí pero lo tomé como un ejercicio.

Ya me acostumbré a usar estructuras inmutables por default, así que este anillo será inmutable. Primer paso: definir el API. 
trait Ring[T]
{
  def get: T
  def next: Ring[T]
  def previous: Ring[T]
}
Bien simple. La idea es que una instancia de Ring me da acceso al elemento "actual" únicamente, con el método get. Con next y previous obtengo un nuevo Ring, con el mismo contenido, donde el elemento "actual" es el próximo o el anterior respectivamente.

Cualquier implementación de una colección inmutable debe contemplar alguna manera de establecer el contenido. Una alternativa es proveer el contenido en una colección más "básica" como sería un Array[T], donde los elementos están en un orden determinado. El anillo nos da una vista de ese contenido en la que los extremos están unidos. En este caso, el Array, aparte de ser el proveedor de contenido para el anillo, es la estructura subyacente de la implementación: con next y previous se reinstancia Ring pero siempre compartiendo la misma instancia del Array. El trabajo del anillo es escencialmente mantener un índice al elemento actual. Una implementación que promete eficiencia.
class ArrayRing[T](elems: Array[T], curIndex: Int) extends Ring[T]
{
    def this(elems: Array[T]) = this(elems, 0)
    
    if(elems == null) throw new IllegalArgumentException
    if(curIndex < 0 || curIndex >= elems.size) throw new IndexOutOfBoundsException

    def get: T = elems(curIndex)
    
    def next: Ring[T] = new ArrayRing(elems, if(curIndex < elems.size - 1) curIndex + 1 else 0)
 
    def previous: Ring[T] = new ArrayRing(elems, if(curIndex > 0) curIndex - 1 else elems.size - 1) 
}
Al instanciar ArrayRing, se puede indicar qué índice corresponde al elemento actual; si no, se asume el primero (0).

Me vino bien para lo que necesitaba, pero no incluiría esta clase en una librería para terceros porque cometí un sutil pecado. Si lo presento como un anillo inmutable, y de hecho eso se desprende del API, no puedo usar como estructura subyacente una colección mutable (Array) que está fuera de mi control. La clase se comporta como si el Array nunca cambiara, cuando nada garantiza tal cosa. Desde el punto de vista del usuario de la clase, nada revela que el Array se utiliza para algo más que para proveer los elementos al anillo; uno supondría que, una vez instanciado el ArrayRing, éste pierde toda dependencia con el Array informado.

Entonces, hagan lo que yo digo, no lo que yo hago. Una mejor implementación debería pedir una colección inmutable (y en ese caso no importa si se utiliza como estructura subyacente o no), o bien tomar el Array pero pasar sus elementos a alguna otra estructura interna. En éste último caso sería conveniente reutilizar esa estructura interna al reinstanciar el anillo con next y previous, para no perder en eficiencia.

3 comentarios:

  1. Bueno, la mayo ria de las colecciones de Scala, están respaldadas internamente por estructuras mutables, ya que son mas eficientes.
    Es un problema interesante el como lograr un anillo inmutable "puro". Es bastante famoso el libro de Okasaki "Purely Functional Data Structures" que trata de estructuras funcionales puras y (bastante) eficientes. Capaz que ahí hay algo :)

    ResponderEliminar
  2. @Gabriel, es cierto, de hecho me parece bien que la implementación use mutabilidad. El problema (y esto espero que no ocurra en las colecciones estándar de Scala) es que me basé en un Array provisto por el cliente y simplemente asumí que no cambiaría. Si hago una estructura inmutable, toda la mutabilidad de la implementación debe estar bajo su estricto control.
    Saludos!

    ResponderEliminar
  3. Igual aclaremos que esta implementación no depende de la mutabilidad como factor de eficiencia, y de hecho no muta nada. Mientras la estructura sea de acceso O(1), será eficiente.

    ResponderEliminar