Aventuras de DoHITB: DoHITB vs. JavaScript(V)

¡Hola Hola!

Os aseguro que llevo tiempo queriendo escribir, porque acabamos la historia de cómo vencí a JS...

:-)

Luego ya vendrán más entradas, estad atentos!

Así, en esta entrada toca ver el tema de la eliminación de duplicados, y como colorario, haremos una bonita clase que haga de todo con arrays

¡Vamos allá!

Partimos de la base de que tenemos el array ordenado, ¿recordáis? Si no os acordáis, aquí tenéis toda la historia.

Pues vamos a ver cómo eliminar duplicados en una pila ordenada.

Partimos del siguiente ejemplo:

5, 3, 5, 8, 3, 4, 1, 2, 9, 8, 7, 6, 5

Tras ordenarlo, tendríamos:

1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9

Ahora pensemos rápidamente en esto:

"El siguiente elemento a uno dado solo puede ser o él mismo o uno (mayor o menor)"

Los paréntesis son para remarcar que será uno de los dos tipos (nunca los dos a la vez). Entonces, es lógico pensar que si el ítem "1" es diferente que el ítem "0", entonces el ítem "0" no tiene repetidos, puesto que al estar ordenados no se puede volver a encontrar un ítem igual al ítem "0".

De esta manera, solamente tenemos que ir recorriendo los ítems y revisar su vecino.

Un ejemplo gráfico:

Cada color representa una pasada del bucle, y cada línea representa una comparación. Así, se compara:

• Pasada 1:
• 1 - 2
• Pasada 2:
• 2 -3
• Pasada 3:
• 3 - 3
• 3 - 4
• ...

El tema está en saber llevar los "offset" (diferencia entre la pasada actual y el vecino que inspeccionamos), ya sea para saber qué vecino estamos mirando, o bien para saber cuántos hay iguales (y por tanto cuántas posiciones tenemos que saltar cuando encontremos uno diferente).

Veamos ahora el código JS:

returnA = new Array();

arrayI = array.length();

inc = 1;

returnAI = 0;

for(i=0;i<arrayI;i++){

ac = array[i];

if((i + 1) == arrayI){

returnA[returnAI] = array[i];

break;

}else{

an = array[i + inc];

}

if(ac == an){

i--;

inc++;

}else{

returnA[returnAI] = array[i];

returnAI++;

i += (inc - 1);

inc = 1;

}

}

Expliquemos como va esto:

En "array" tenemos los datos ordenados. Definimos "returnA" como el array a retornar, "inc" será el incremento (para saber qué vecino miramos), y por su parte "arrayI" y "returnAI" son los contadores de sendos arrays "array" y "returnA".

Entonces, desde 0 (primer ítem) hasta arrayI (último ítem) iremos recorriendo "array". Para el caso actual guardamos el valor del ítem en "ac".

Si el ítem siguiente es el último es que estamos al final (recordad que es imposible acceder a "array[arrayI]"), por lo que guardamos el valor que tenemos, y salimos del bucle. En caso contrario, guardamos en "an" el vecino correspondiente a el ítem actual más el incremento.

Si el actual es igual al vecino, retrocedemos "i" para que se mantenga en la siguiente vuelta (ya que se incrementará), y a su vez incrementamos el incremento (bingo, capitán obvio). Así, a la siguiente vuelta seguiremos con el mismo ítem, pero con el vecino siguiente.

En caso que sean contrarios, se guarda el ítem en "returnA", se incrementa el índice de "returnA", se incrementa el índice "i" en el "incremento menos uno" (para que tras el paso quede con el valor adecuado), y reiniciamos el incremento.

Al salir del bucle, tendremos en "returnA" todos los valores sin repetición.

Ahora, lo añadimos a la anterior clase:

var Sortable = function(){

 this.toSort = false;

 this.isInverse = false;

 //variable para indicar si se eliminan

 this.noDuplicates = false;

 this.sortFunction = '';

 this.setToSort = function(toSort){

  this.toSort = toSort;

 };

 this.setIsInverse = function(isInverse){

  this.isInverse = isInverse;

 };

 this.setSortFunction = function(sortFunction){

  this.sortFunction = sortFunction;

 };

 this.setNoDuplicates = function(noDuplicates){

  this.noDuplicates = noDuplicates;
 };

 this.sort = function(){
  tokenJ = 'this.toSort[j]';
  tokenM = 'this.toSort[m]';
  
  if(!this.toSort){
   return false;
  }

  if(this.isInverse){
   r = ' <= ';
  }else{
   r = ' >= ';
  }
  
   for(i=0;i<this.toSort.length;i++){
  m = i;
  
  for(j=i+1;j<this.toSort.length;j++){
    if(eval(tokenJ + this.sortFunction + r + tokenM + this.sortFunction)){
   m = j;
    }
  }
  
  a = this.toSort[m];
  this.toSort[m] = this.toSort[i];
  this.toSort[i] = a;
   }
 };

 this.deleteDuplicates = function(){
  //simple control de errores
  if(!this.toSort || !this.noDuplicates){
    return false;
  }

  returnA = new Array();
  arrayI = this.toSort.length();
  inc = 1;
  returnAI = 0;

  for(i=0;i<arrayI;i++){
ac = array[i];

if((i+1) == arrayI){
 returnA[returnAI] = array[i];
 break;
}else{
 an = array[i + inc];
}

if(ac == an){
 i--;
 inc++;
}else{
 returnA[returnAI] = array[i];
 returnAI++;
 i += (inc - 1);
 inc = 1;
    }
  }
  
  return returnA;
 };
};

Esta clase hará las delicias de todos vosotros. Tened en cuenta que el array que "limpiemos" tiene que ser ordenado, porque sino no funcionará...

Y ahora, la puntilla: ¿y si quiero borrar los duplicados pero no quiero ordenar?

Para ello tenemos lo que yo llamo "array de transición".

Es un array anexo que contiene los índices originales, pero ordenados.

¿Qué?

Ejemplo rápido, ¡Marchando!

Tenemos este array:

5[0], 3[1], 4[2], 1[3]

Entre corchetes está su posición.

Tras ordenarlo, tenemos este array:

1[0], 3[1], 4[2], 5[3]

Si usamos un array de transición, éste tendrá:

3[0], 1[1], 2[2], 0[3]

Es decir, que el ítem que en el array ordenado tiene la posición "0", en el original tiene la posición "3" (3[0])

Entonces, no tenemos más que ordenar, eliminar duplicados (actualizando el array de transición) y luego aplicar el orden inverso, y ¡voliá! Array sin duplicados y sin ordenar

:-)

Esta parte no la incluiré en la clase, puesto que hay métodos más "directos" para eliminar duplicados sin que esté ordenado el array, pero que sirva como curiosidad.

En fin, la próxima entrada ya veréis de qué va.

Saludos, y como siempre digo.

¡Hasta la próxima!