[SOLUCIONADO] Problema al borrar en árbol Set casero

[detective_jd]

Esta es la continuación de este post: Balanceos con árboles set.

Este es el problema, resulta que tengo el siguiente error:

java.lang.Exception
at treesetsimple.test.Test.comprobar_que(Test.java:6)
at treesetsimple.test.DownTest.probando_borrado(DownT est.java:36)
at treesetsimple.test.DownTest.test(DownTest.java:44)
at treesetsimple.interfaz.Cuerpo.main(Cuerpo.java:13)

Lo que no me doy cuenta es dónde está la falla del remove de MyTreeMap porque el primer elemento lo borra pero el siguiente no, sacando a Franco de la línea 43 de la clase DownTest.java anda, por alguna razón no me borra Franco:

Código Java:

probando_borrado(restart(), new Object[]{"Deborah","Franco","Denisse"});
 

Este es el remove de MyTreeSet (en las líneas 52, 53 y 54) que delega de MyTreeMap:

Código Java:

@Override
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
 

Es el remove de MyTreeMap.java dónde supuestamente estaría el error:

Código Java:

@Override
    public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null) {
            return null;
        } else {
            V oldValue = p.value;
            deleteEntry(p);            
            return oldValue;
        }
    }
private void deleteEntry(Entry<K,V> p) {
        size--;
        Entry<K,V> tmp = new Entry();
        Entry<K,V> y = (leftOf(p) == null || rightOf(p) == null) ? p : higherEntry(p.getKey());
        Entry<K,V> x = (leftOf(y) != null) ? leftOf(y) : (rightOf(y) != null ? rightOf(y) : tmp);        
        x.parent = parentOf(y);
        if (parentOf(y) == null) {
            root = (x == tmp ? null : x);
        } else {
            if (y == leftOf(parentOf(y))) {
                y.parent.left = (x == tmp) ? null : x;
            } else {
                y.parent.right = (x == tmp) ? null : x; 
            }
        }
        if (y != p){
            p = y;
        }
        if (colorOf(y) == BLACK) {
            fixDown(x);
        }
    }
private void fixDown(Entry<K,V>x){
        while(x != root && colorOf(x) == BLACK) {
            if(x == parentOf(leftOf(x))) {                
                Entry<K,V> sib = parentOf(rightOf(x));
                if(colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateLeft(x.parent);
                    sib = parentOf(rightOf(x));
                }
                if(colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {
                    if(colorOf(rightOf(sib)) == BLACK) {
                        setColor(leftOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateRight(sib);
                        sib = rightOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(rightOf(sib), BLACK);
                    rotateLeft(x.parent);
                    x = root;
                }
            } else {
                Entry<K,V> sib = leftOf(parentOf(x));                
                if(colorOf(sib) == RED) {
                    setColor(sib, BLACK);
                    setColor(parentOf(x), RED);
                    rotateRight(x.parent);
                    sib = leftOf(parentOf(x));
                }
                if(colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK){
                    setColor(sib, RED);
                    x = parentOf(x);
                } else {                    
                    if(colorOf(leftOf(sib)) == BLACK) {
                        setColor(rightOf(sib), BLACK);
                        setColor(sib, RED);
                        rotateLeft(sib);                        
                        sib = leftOf(parentOf(x));
                    }
                    setColor(sib, colorOf(parentOf(x)));
                    setColor(parentOf(x), BLACK);
                    setColor(leftOf(sib), BLACK);
                    rotateRight(x.parent);
                    x = root;
                }
            }
        }
        setColor(x, BLACK);
    }
 

Puse los métodos que usa internamente remove por si la falla está en dónde menos espero.
Espero sus respuestas y saludos.

[CalgaryCorpus]

Haz (sl menos) 1 test minimo que falle.
No insertes 5 elementos si falla con 2.
Has probado la implementacion de tu Map? Funciona bien? Esta es una pregunta retorica. Claramente no has probado bien la implementacion que estas usando para construir tu Set.

Cuando publiques, sirve mas que expliques que tests estas haciendo EXPLICANDOLO lo que pruebas, no haciendo referencia a lineas de codigo o a cosas que solo tu entiendes.

Ejemplo de explicacion malo:
(COPIAR EL STACK TRACE) y luego ...
"Lo que no me doy cuenta es dónde está la falla del remove de MyTreeMap porque el primer elemento lo borra pero el siguiente no, sacando a Franco de la línea 43 de la clase DownTest.java anda, por alguna razón no me borra Franco:"

Ejemplo de explicacion mejor:
Para probar, inserto inicialmente varios elementos en un set, y luego borro 1 por 1, preguntando una vez que se borra si el elemento sigue en el set.
El test pasa si para todos los elementos que borro, se cumple esa condicion.
Si el elemento sigue alli despues de insertar, el test falla.

Esto es para que tengas material para que descubras tu mismo tus errores, o bien que lo puedas testear y explicar mejor.

[detective_jd]

Hola CalgaryCorpus gracias por responder, en base a lo que escribiste va esto:

Has probado la implementacion de tu Map? Funciona bien? Esta es una pregunta retorica. Claramente no has probado bien la implementacion que estas usando para construir tu Set.

Resulta que la línea 351 de MyTreeMap.java es la del problema pero ahora la pregunta es: ¿cómo cambio esa línea para que se adapté la funcionalidad? porque en estos momentos no sé me ocurre nada al respecto.

Haz (sl menos) 1 test minimo que falle.

En la línea 43 cuando llamo al método probando_borrado con sus parámetros es el único que anda mal, ya que comenté esa línea, corre el código y lo demás anda bien.

No insertes 5 elementos si falla con 2.

En las líneas 48, 50 y 51 de DownTest.java agrega probando menos cantidad de elementos, comentando la 43 como había dicho funciona bien el resto.
Lo demás que escribíste me sirve, porque un defecto que tengo es que me digo a mi mismo "no hace falta tanta explicación debido que para otros es muy obvio lo que hago" y en eso estoy equivocado, en pocas no soy muy expresivo.

Pongo el código, porque está todo ahí para ver lo que digo: TreeSet Casero

Espero sus respuestas y saludos.

[CalgaryCorpus]

Yo no voy a resolver esto por ti,

Te voy a explicar por n+1 vez y espero que no sea otra vez que decides que no tienes que hacer nada y tu respuesta sea un monton de numeros de linea de codigo como lo hiciste recien.

Si tienes un test que usa 5 elementos (recuerdas que te he dicho esto de los 5 elementos antes?), pero tambien ese mismo test fallaria con menos elementos, entonces tu test de 5 elementos esta metiendo ruido no mas. Tienes que hacer que tus tests sean MINIMOS, si tu problema se presenta con 2 elementos, entonces 2 elementos tiene que tener tu test. Entiendes por que tienen que ser minimos? Por que asi es mas facil depurarlos, seguirle la pista. Ademas tienen que probar solo 1 cosa, si prueban varias cosas simultaneamente tambien es un ruido. Solo 1 cosa y minimos.

Dices que el error se presenta con 5 elementos y si borras tal linea funciona y si borras alla o incluyes alla otra linea de codigo no funciona? Esto NO ES manera de depurar. A mi no me importa esto.

Haz que tus tests sean MINIMOS.

Una vez que tus tests sean minimos, usa esos test minimos para depurar.

Si tu problema esta en los Maps, y no en los Sets que usan los maps, de nuevo te pregunto, tienes tests minimos para esta estructura? Seguro que no, porque esos tests deberian fallar y con eso resolverias tu problema con el set.

Yo apostaria que los otros tests que tienes son del mismo estilo, conjunto de datos gigantes, que prueban varias cosas, etc. Asi que una vez que todos tus tests pasen, lo mas probable es que no haya certeza aun que has probado correctamente.

Te habia dicho que los tests tienen que ser minimos?
Y que da lo mismo si el test que tienes falla si pones una linea aqui o borras una linea alla?

Voy a esperar tu respuesta para ver que dices esta vez.

Si resuelves el problema, vuelve al foro y explica que' era el problema y como lo resolviste, pero por favor que no sea diciendo, "borre esta linea", o "la linea 43 la movi 2 lineas arriba y la 58 la movi hacia abajo", eso no es explicar.

que sea algo como
"estaba insertando 2 veces y esta duplicacion afectaba aqui o alla",
"internamente tenia los datos desordenados y el codigo suponia que los datos estaban ordenados"

Tambien sirve poner codigo RELEVANTE antes de la modificacion, codigo RELEVANTE despues. No kilometros de codigo y vea usted estimado lector donde estaba el error.

[detective_jd]

Buenas GalgaryCorpus, resulta que el error estaba dónde menos lo pensaba y es a la hora de ordenar las entradas a eliminar:

Sí lo mando a eliminar en este orden:

Código Java:

probando_borrado(restart(), new Object[]{"Deborah","Franco","Denisse"});
 

Me da el error:

java.lang.Exception
at treesetsimple.test.Test.comprobar_que(Test.java:6)
at treesetsimple.test.DownTest.probando_borrado(DownT est.java:35)
at treesetsimple.test.DownTest.test(DownTest.java:43)
at treesetsimple.interfaz.Cuerpo.main(Cuerpo.java:13)

Pero si lo pongo en este orden:

Código Java:

probando_borrado(restart(), new Object[]{"Deborah","Denisse","Franco"});
 

Funciona sin problemas, lo que tendremos que ver es cómo hacer para que permita borrar sin que interfiera el órden de entradas a borrar, otra las claves son strings si me entiendes.

Espero sus respuestas y saludos.

PD: n+2;

[Fuzzylog]

Me da en el hocico que en algún momento estás modificando el tamaño de algún set (añadiendo o quitando elementos) a la vez que lo iteras. Deberías usar una copia del set para modificarlo y luego sustituir la copia modificada una vez finalizada la iteración.

[detective_jd]

Hola FuzzyLog por responder, hice lo que me dijiste y no funcionó:

Código Java:

private void probando_borrado(Object[]arreglo, Object[]criterio) throws Exception{
            set.clear();
            for (Object obj : arreglo) {
                set.add(obj.toString());
            }            
            MyTreeSet<String>aux = set;
            for(Object c : criterio){
                if(c == null){
                    aux.remove(null);
                    this.comprobar_que(!set.contains(null));
                } else {
                    aux.remove(c.toString());
                    this.comprobar_que(!set.contains(c.toString()));
                }                        
            }
        }
 

Depuré el código y aquí esta el resultado:

El órden después de insertar los string al set:

"Deborah" < - > "Denisse" < - > "Franco" < - > "Manuela" < - > "Miguel" < - > "Tommy"

Cuando quiero borrar a "Franco"

línea 343 : decrementa el tamaño a 1 menos
línea 351 : y tiene la entrada "Manuela"
línea 359 : x es nulo
línea 361 : el pariente de x pasa a ser Miguel
linea 367 : como el pariente de x no es nulo, entra en la contradicción (else)
línea 377 : como y es igual al izquierdo del pariente de y, entra en la condición (if)
línea 378 : el izquierdo del pariente de y, pasa a ser nulo
línea 389 : al ser distintos (y) y (p), entra en la condición
línea 390 : p toma el valor de y
línea 395 : como el color de y no es negro, no entra en el if.

El problema parece ser el órden de los datos a eliminar y ahí es dónde no me doy cuenta que arreglar si el deleteEntry (que parece lo más evidente a arreglar) o que.

Pondré el código del deleteEntry de MyTreeMap.java, ya que puede que no mires el repositorio de github, pero otro lado por dónde mirarlo no se me ocurre:

Código Java:

private void deleteEntry(Entry<K,V> p) {
        // Decrementa la cantidad de elementos en el árbol.
        size--;
        // Creamos una nueva entrada vacía.
        Entry<K,V> tmp = new Entry();
        /*
            Creamos una entrada llamada y y mediante un operador ternario si 
            la izquierda o derecha de p es nula que y tenga el valor de p de 
            lo contrario de obtenga al siguiente de p.
        */
        Entry<K,V> y = (leftOf(p) == null || rightOf(p) == null) ? p : higherEntry(p.getKey());
        /*
            Luego creo otra entrada llamada x y mediante operador ternario
            si la izquierda de y no es nula, x tendrá como valor la izquierda
            de y de lo contrario otro operador ternario dentro del primero que
            si la derecha de y no es nula que x obtenga como valor la derecha
            de y  de lo contrario obtendrá la entrada vacía.
        */
        Entry<K,V> x = (leftOf(y) != null) ? leftOf(y) : (rightOf(y) != null ? rightOf(y) : tmp);        
        // Al pariente de x se le asignará como valor el pariente de y
        x.parent = parentOf(y);
        /*
            Sí el pariente de y es nulo, la raíz del árbol se le asignará como
            valor mediante operador ternario que si x es una entrada vacía
            la raíz será nula de lo contrario x será el valor de la raíz
        */
        if (parentOf(y) == null) {
            root = (x == tmp ? null : x);
        } else {
            /*
                Ahora si el pariente de y no es nulo, entramos en otra
                condición que si y es igual al izquierdo del pariente de y
                el izquierdo del pariente de y tendrá como valor mediente
                operador ternario si x es una entrada vacía será nulo sino
                su valor será x
            */
            if (y == leftOf(parentOf(y))) {
                y.parent.left = (x == tmp) ? null : x;
            } else {
                /*
                    De lo contrario el derecho del pariente de y tendrá como
                    valor por operador ternario si x es una entrada vacía
                    su valor será nulo sino será x
                */
                y.parent.right = (x == tmp) ? null : x; 
            }
        }
        // Si y es distinto de p, a p se le asignará como valor y
        if (y != p){
            p = y;
        }
        /*  Y si el color de y es negro, el árbol será balanceado para 
            actualizarse luego de la eliminación
        */
        if (colorOf(y) == BLACK) {
            fixDown(x);
        }
    }
 

Espero sus respuestas y saludos.

[CalgaryCorpus]

Sugiero una de dos opciones:

- que revises bien en que parte te has desviado de la implementacion de la openjdk que ese codigo evidentemente esta inspirado. Haciendo un diff visual del codigo de la openjdk con tu implementacion, sin entenderlo siquiera, noto que hay unos desvios evidentes que posiblemente expliquen por que' tu codigo no funciona.

o bien

- Reimplementa el arbol que esta detras de esto. Esta vez si' lo haces tu, desde cero. Con ello vas a poder realmente explicar el codigo, sera "casero" como le has llamado, y no vas a hacer ingenieria reversa para poder entenderlo. Olvidate del balanceo inicialmente. Puedes volver a esto una vez que el arbol ya funcione. En esa implementacion haz test minimos. Creo que vas a aprender mas asi.

[Fuzzylog]

Si quieres respuestas mejor aclara las preguntas.

Escribes sobre cosas muy diversas y en apariencia inconexas.

Por ejemplo tu método deleteEntry no tiene que ver con la excepción de la que hablabas al inicio del post.

Por tanto...

1. Cuál es el problema que tienes. Si es más de uno explícalos por separado.
2. Acostúmbrate a hacer debug desde tu entorno de desarrollo y ver los valores que tienen los objetos antes de que salte el error. Así tendrás una idea de por qué pasan.

[detective_jd]

CalgaryCorpus y FuzzyLog gracias por responder, resolví el problema resulta que era un error al escribir código, revisé el código que tenía con el de Chuck McManis en la parte del borrar, lo adapté y funcionó.

Bueno esto será todo con los Hashing casero, lo último que me queda por hacer es una pequeña inspiración tuve para adaptar a MyLinkedMap y MyLinkedSet, y después de eso sí.
Empezaré lo que quería hacer desde un principio pero no sabía cómo funcionaban bien los Map y Set.

Muchas gracias por su tiempo y saludos.

Repositorio TreeMap casero -> http://bit.ly/2BDgpVb

Repositorio TreeSet casero -> http://bit.ly/2Si7YnU

PD: ¿cómo se inicia un post para hacer aportes en foros del web?

[detective_jd]

Bueno aquí esta la inspiración que tuve resulta que logré simular las versiones actuales de LinkedHashMap y LinkedHashSet al ponerles dobles punteros de inicio y fin y hacerlo tipo lista doble enlazada además de poner funciones para acceder a los mismos.

Repositorio LinkedHashMap casero -> http://bit.ly/2G7V2zC

Repositorio LinkedHashSet casero -> http://bit.ly/2RL3BSl

Saludos.