[SOLUCIONADO] Balanceos con Árboles Set

[detective_jd]

Hola a todos, este post en sí es una continuación de este: Balanceos con Árboles Hash

Resulta que estuve probando las funcionalidades básicas y funcionan pero el problema está cuando quiero probar la implementación delegada de los mismas pero pasa esto, si en MyTreeSet en la función iterator pongo esto:

Código Java:

@Override
    public Iterator<E> iterator() {
        return map.navigableKeySet().iterator();
        //return map.keySet().iterator();
    }
 

Sucede esto:

---* Segundo Testing: probando subsets ascending---

--- Probando subSet MyTreeSet---
subSet [Deborah:Franco]: [Deborah, Franco, Manuela, Tomás]
subSet [Franco:Tomás]: [Deborah, Franco, Manuela, Tomás]
subSet [Deborah:nulo]: [Deborah, Franco, Manuela, Tomás]
subSet [nulo:Tomás]: [Deborah, Franco, Manuela, Tomás]
subSet [nulo:nulo]: []
--- Probando subSet TreeSet---
subSet [Deborah:Franco]: [Deborah]
subSet [Franco:Tomás]: [Franco, Manuela]
--- Probando headSet MyTreeSet---
headSet [Deborah]: []
headSet [Franco]: []
headSet [Manuela]: []
headSet [Tomás]: []
--- Probando headSet TreeSet---
headSet [Deborah]: []
headSet [Franco]: [Deborah]
headSet [Manuela]: [Deborah, Franco]
headSet [Tomás]: [Deborah, Franco, Manuela]

Pero cuando pongo de ésta forma:

Código Java:

@Override
    public Iterator<E> iterator() {
        //return map.navigableKeySet().iterator();
        return map.keySet().iterator();
    }
 

El subset funciona pero los headset y tailset no, cómo lo pueden ver:

---* Segundo Testing: probando subsets ascending---

--- Probando subSet MyTreeSet---
subSet [Deborah:Franco]: [Deborah]
subSet [Franco:Tomás]: [Franco, Manuela]
subSet [Deborah:nulo]: [Deborah, Franco, Manuela]
subSet [nulo:Tomás]: [Deborah, Franco, Manuela]
subSet [nulo:nulo]: []
--- Probando subSet TreeSet---
subSet [Deborah:Franco]: [Deborah]
subSet [Franco:Tomás]: [Franco, Manuela]
--- Probando headSet MyTreeSet---
headSet [Deborah]: []
headSet [Franco]: []
headSet [Manuela]: []
headSet [Tomás]: []
--- Probando headSet TreeSet---
headSet [Deborah]: []
headSet [Franco]: [Deborah]
headSet [Manuela]: [Deborah, Franco]
headSet [Tomás]: [Deborah, Franco, Manuela]

Revisé, depuré pero no doy bien con el problema y menos con la solución. Aquí está el código:

https://github.com/detectivejd/TreeS...MyTreeSet.java

Espero sus respustas y saludos.

PD: Una vez que se solucione estas fallas, los test que ven en el repositorio, desaparecerán.

[CalgaryCorpus]

Si cambias la implementacion interna y no te sirve el resultado, esta mal lo que estas usando o como lo estas usando?

Sugiero que tests unitarios apoyen el comportamiento que esperas de las estructuras que estas usando.

He visto tus tests y no se que es lo que esperan, pues es solo imprimir cosas, asi no se hacen los tests.
Los tests tienen que ser MINIMOS, PROBAR 1 SOLA COSA, y detectar ellos mismos si el test pasa o falla.
Cada vez que ejecutas tus tests ellos mismos te tienen que decir que cosa funciona bien y que falla,
o mejor aun, solo los que fallan tienen que decir algo. Asi es facil y rapido iterar.
Tambien ayuda a quien quiere usar tu estructura a saber como usarla y como la has probado.

No puede ser que todas las veces tengas que leer todo para saber que es lo que esta funcionando y que es lo que falla.

Asi lo haces ahora. En mi forma de ver, no te ayuda. Estas solo imprimiendo cosas y quien sabe que.

Parte mejorando tus tests, describe mejor tus problemas. Disminuye el tamano de tus tests hasta hacerlos fallar con pocos datos. Si insertas 10 cosas y falla, falla tambien con 5 cosas? con 3? con 2? Tu test deberia tener el caso mas basico de falla, para que puedas depurarlo. Una vez que este pase, entonces lo haces mas complejo, si es que parece adecuado. Una vez que un test pasa, NO LO BORRAS. Lo dejas alli para que cualquier modificacion futura que este incorrecta, sea descubierta por esos tests.

Haz que ayudarte sea facil, mejora tus tests de lo que haces y de lo que usas.
No publiques nuevamente de la manera que lo estas haciendo. Asi, es imposible, o muy largo ayudarte.

Haz el trabajo que te corresponde antes de pedir ayuda, recortando el problema de modo que sea simple de explicar, facil de reproducir, incluso llega al punto de modificar tu implementacion, con la idea de recortar lo que hace, solo para poder tener el programa minimo que falla.

El camino de los tests unitarios te va a ayudar a ti cuando desarrollas, cuando modificas y cuando tienes que pedir ayuda.

[detective_jd]

Hola CalgaryCorpus gracias por responder.

Si cambias la implementacion interna y no te sirve el resultado, esta mal lo que estas usando o como lo estas usando?

Resulta que fallaba la forma en que lo estaba usando lo que tenía que hacer era la clase interna KeySet estática y en la función navigableKeySet de NavigableSubMap debía retornar una nueva instancia de KeySet pasándole el map que usaba la clase navigable.

Sugiero que tests unitarios apoyen el comportamiento que esperas de las estructuras que estas usando. .......

Resulta que lo que viste mi idea en un principio era comparar el TreeSet casero con el TreeSet original, y si lo que hacía el casero era igual al original me daría cuenta de que está bien. De hecho ese test lo puse porque no me daba cuenta del error ya que es algo mío para luego hacer los test que debería. Pongo el código:

https://github.com/detectivejd/TreeS.../treesetsimple

Espero sus respuestas y saludos.

NOTA: El código sufrirá mucho en especial Cuerpo.java, el resto se mantiene.

[detective_jd]

Hola a todos, acá subí los testeos que hice del TreeSet casero, 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 que quiero borrar lo borra pero el siguiente no, sacando el del error funciona bien, en la línea 43 de la clase DownTest.java 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;
        }
    }
@Override
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);
    }
 

Espero sus respuestas y saludos.

[CalgaryCorpus]

Crea un post nuevo por cada problema. No parece difícil de entender.

Deja de hacer post infinitos que nunca se cierran y que sólo te sirven a ti.
Varios temas pueden servirle a otros, te forzará a poner un nombre distinto, relacionado con.el problema.

Ojalá que todo aquel que quiera ayudarte exija lo mismo, para ayudar a este foro a sobrevivir.

[detective_jd]

Hola CalgaryCorpus gracias por responder, de hecho lo que acabo de escribir es lo que queda por hacer después ya no más. Bueno, haré otro post con el título "problema al borrar en árbol set casero".
Había puesto ese título porque era interesante.

[detective_jd]

Bueno aquí esta el post que había dicho -> Problema al borrar en árbol Set casero

Espero sus respuestas y saludos.