Foros del Web » Programación para mayores de 30 ;) » Java »

[SOLUCIONADO] Balanceos con Árboles Hash

 Estas en el tema de Balanceos con Árboles Hash en el foro de Java en Foros del Web. Hola a todos, empecé a investigar los árboles hash como TreeMap y TreeSet, empecé a implementar el TreeMap casero, tengo el siguiente problema: Las inserciones ...
Página 1 de 2 1 2

  #1 (permalink)  
Antiguo 12/06/2018, 20:18
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Balanceos con Árboles Hash
Hola a todos, empecé a investigar los árboles hash como TreeMap y TreeSet, empecé a implementar el TreeMap casero, tengo el siguiente problema:

Las inserciones andan pero cuando quiero pasar de un map a otro se me borra un elemento, esto es lo que me muestra por consola:

run:
* tamaño mapa 1: 5
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2: 4
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

Este es el código para las inserciones y para mostrar:

Código Java: 
Ver original
  1. package treemapsimple;
  2. import java.util.AbstractCollection;
  3. import java.util.AbstractSet;
  4. import java.util.Collection;
  5. import java.util.Comparator;
  6. import java.util.Iterator;
  7. import java.util.Map;
  8. import java.util.Set;
  9. /**
  10.  *
  11.  * @author detectivejd
  12.  * @param <K>
  13.  * @param <V>
  14.  */
  15. public class MyTreeMap<K,V> implements Map<K, V>
  16. {
  17.     private final Comparator<? super K> comparator;
  18.     private final boolean RED   = true;
  19.     private final boolean BLACK = false;
  20.     private Entry<K,V> root;
  21.     private int size;
  22.     public MyTreeMap() {
  23.         clear();
  24.         this.comparator = null;
  25.     }
  26.     public MyTreeMap(Comparator<? super K> xcomparator) {
  27.         clear();
  28.         this.comparator = xcomparator;
  29.     }
  30.     public MyTreeMap(Map<? extends K, ? extends V> m) {
  31.         clear();
  32.         this.comparator = null;
  33.         putAll(m);
  34.     }
  35.     .......
  36.     @Override
  37.     public V put(K key, V value) {
  38.         if(key != null){
  39.             Entry<K,V> t = root;        
  40.             if(t == null){
  41.                 root = new Entry(key, value,null);
  42.                 size = 1;
  43.                 return null;
  44.             }
  45.             int cmp = 0;
  46.             Entry<K,V> parent = null;
  47.             if(comparator != null){
  48.                 while (t != null) {
  49.                     parent = t;
  50.                     cmp = comparator.compare(key,t.key);
  51.                     if(cmp < 0){
  52.                         t = t.left;
  53.                     } else if(cmp > 0) {
  54.                         t = t.right;
  55.                     } else {
  56.                         t.value = value;
  57.                         return value;
  58.                     } 
  59.                 }
  60.             } else {
  61.                 while (t != null) {
  62.                     parent = t;
  63.                     Comparable<? super K> k = (Comparable<? super K>) key;
  64.                     cmp = k.compareTo(t.key);
  65.                     if(cmp < 0){
  66.                         t = t.left;
  67.                     } else if(cmp > 0) {
  68.                         t = t.right;
  69.                     } else {
  70.                         t.value = value;
  71.                         return value;
  72.                     } 
  73.                 }
  74.             }
  75.             Entry<K,V> e = new Entry(key, value, parent);
  76.             if (cmp < 0)
  77.                 parent.left = e;
  78.             else
  79.                 parent.right = e;
  80.             rbInsertFixup(e);
  81.             size++;
  82.         }
  83.         return null;
  84.     }
  85.     private void rbInsertFixup(Entry<K,V> x) {
  86.         x.color = RED;
  87.         while (x.parent != null && x != root && x.parent.color == RED) {
  88.             if (x.parent == x.parent.parent.left) {
  89.                 // x's parent is a left child.
  90.                 Entry<K,V> y = x.parent.parent.right;
  91.                 if (y != null && y.color == RED) {
  92.                     // Case 1: x's uncle y is red.
  93. //                  System.out.println("rbInsertFixup: Case 1 left");
  94.                     x.parent.color = BLACK;
  95.                     y.color = BLACK;
  96.                     x.parent.parent.color = RED;
  97.                     x = x.parent.parent;
  98.                 } else {
  99.                     if (x == x.parent.right) {
  100.                         // Case 2: x's uncle y is black and x is a right child.
  101.                         // System.out.println("rbInsertFixup: Case 2 left");
  102.                         x = x.parent;
  103.                         leftRotate(x);
  104.                     }
  105.                     // Case 3: x's uncle y is black and x is a left child.
  106.                     //System.out.println("rbInsertFixup: Case 3 left");
  107.                     x.parent.color = BLACK;
  108.                     x.parent.parent.color = RED;
  109.                     rightRotate(x.parent.parent);
  110.                 }
  111.             } else {
  112.                 // x's parent is a right child.  Do the same as when x's
  113.                 // parent is a left child, but exchange "left" and "right."
  114.                 Entry<K,V> y = x.parent.parent.left; 
  115.                 if (y != null && y.color == RED) {
  116.                     // Case 1: x's uncle y is red.
  117.                     // System.out.println("rbInsertFixup: Case 1 right");
  118.                     x.parent.color = BLACK;
  119.                     y.color = BLACK;
  120.                     x.parent.parent.color = RED;
  121.                     x = x.parent.parent;
  122.                 } else {
  123.                     if (x == x.parent.left) {
  124.                         // Case 2: x's uncle y is black and x is a left child.
  125.                         // System.out.println("rbInsertFixup: Case 2 right");
  126.                         x = x.parent;
  127.                         rightRotate(x);
  128.                     }
  129.                     // Case 3: x's uncle y is black and x is a right child.
  130.                     // System.out.println("rbInsertFixup: Case 3 right");
  131.                     x.parent.color = BLACK;
  132.                     x.parent.parent.color = RED;
  133.                     leftRotate(x.parent.parent);
  134.                 }
  135.             }
  136.         }
  137.         // The root is always black.
  138.         root.color = BLACK;
  139.     }
  140.     /**
  141.      * Do a right rotation around this node.
  142.     */
  143.     private void rightRotate(Entry<K,V> y) {
  144.         Entry<K,V> x = y.left;
  145.         y.left = x.right;
  146.         if (x.right != null)
  147.             x.right.parent = y;
  148.         x.parent = y.parent;
  149.         if (y.parent == null) {
  150.             root = (Entry)x;
  151.         } else if (y == y.parent.right){ 
  152.             y.parent.right = x;
  153.         } else {
  154.             x.parent.left = x;
  155.         }
  156.         x.right = y;
  157.         y.parent = x;
  158.     }
  159.     /**
  160.      * Do a left rotation around this node.
  161.     */
  162.     private void leftRotate(Entry<K,V> x) {            
  163.         Entry<K,V> y = x.right;
  164.         x.right = y.left;
  165.         if (y.left != null)
  166.             y.left.parent = x;
  167.         y.parent = x.parent;
  168.         if (x.parent == null) {
  169.             root = (Entry)y;
  170.         } else if (x == x.parent.left) {
  171.             x.parent.left = y;
  172.         } else {
  173.             x.parent.right = y;
  174.         }
  175.         y.left = x;
  176.         x.parent = y;        
  177.     }    
  178.     @Override
  179.     public void putAll(Map<? extends K, ? extends V> m) {
  180.         m.entrySet().forEach((e) -> {
  181.             put(e.getKey(), e.getValue());
  182.         });
  183.     }
  184.     @Override
  185.     public String toString(){
  186.         if (root == null)
  187.             return "";
  188.         else
  189.             return print(root, 0);
  190.     }
  191.     private String print(Entry<K,V> x, int depth) {
  192.         if (x == null)
  193.             return "";
  194.         else
  195.             return print(x.right, depth + 1) + 
  196.                 indent(depth) + x.toString() + 
  197.                 "\n"+ print(x.left, depth + 1);
  198.             
  199.     }
  200.     private String indent(int s) {
  201.         String result = "";
  202.         for (int i = 0; i < s; i++)
  203.             result += "  ";
  204.         return result;
  205.     }    
  206. }

Y este es el método que estoy probando:

Código Java: 
Ver original
  1. Persona p1 = new Persona(Persona.getMaxId(), "Juan", 56);
  2.         Persona.maxIdUp();
  3.         Persona p2 = new Persona(Persona.getMaxId(), "Alberto", 73);
  4.         Persona.maxIdUp();
  5.         Persona p3 = new Persona(Persona.getMaxId(), "Julia", 62);
  6.         Persona.maxIdUp();
  7.         Persona p4 = new Persona(Persona.getMaxId(), "Luis", 71);
  8.         Persona.maxIdUp();
  9.         Persona p5 = new Persona(Persona.getMaxId(), "Maria", 18);
  10.         Persona.maxIdUp();
  11.         Persona p6 = new Persona(Persona.getMaxId(), "Pedro", 16);
  12.         Persona.maxIdUp();
  13.         Persona p7 = new Persona(Persona.getMaxId(), "Deborah", 26);
  14.         Persona.maxIdUp();
  15.         Persona p8 = new Persona(Persona.getMaxId(), "Nelson", 37);
  16.         Persona.maxIdUp();
  17.         Persona p9 = new Persona(Persona.getMaxId(), "Tommy", 22);
  18.         Persona.maxIdUp();
  19.         Persona p10 = new Persona(Persona.getMaxId(), "Manuela", 15);
  20.         Persona.maxIdUp();
  21.         MyTreeMap<Integer,Persona> map = new MyTreeMap();
  22.         map.put(p1.getId(), p1);
  23.         map.put(p2.getId(), p2);
  24.         map.put(p3.getId(), p3);
  25.         map.put(p4.getId(), p4);
  26.         map.put(p5.getId(), p5);
  27.         MyTreeMap<Integer,Persona> map2 = new MyTreeMap(map);
  28.         //map2.put(p6.getId(), p6);
  29.         //map2.put(p7.getId(), p7);
  30.         //map2.put(p8.getId(), p8);
  31.         //map2.put(p9.getId(), p9);
  32.         //map2.put(p10.getId(), p10);
  33.         System.out.println("* tamaño mapa 1: " + map.size());
  34.         System.out.println(map.toString());
  35.         System.out.println("* tamaño mapa 2: " + map2.size());
  36.         System.out.println(map2.toString());
  37.     }

Hace unos días que no le encuentro la vuelta a esto, espero sus respuestas y saludos.

PD: Todavía no lo subí a github.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #2 (permalink)  
Antiguo 13/06/2018, 02:23
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
Yo que tú haría debug aquí

public MyTreeMap(Map<? extends K, ? extends V> m) {
clear();
this.comparator = null;
putAll(m);
}

y también dentro del método putAll

a ver si es ahí donde se hace algo que no debería y se pierde el elemento.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #3 (permalink)  
Antiguo 13/06/2018, 20:47
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Hola Fuzzylog, primero que todo gracias por responder y segundo hice lo que me dijiste:

Resulta que el 3er elemento se pierde en sí cuando insertas a p5 en el árbol, en el listado te lo conserva pero se pierde en la estructura del árbol, en estos métodos parece que está el truco:

Código Java: 
Ver original
  1. private void rbInsertFixup(Entry<K,V> x) {
  2.         x.color = RED;
  3.         while (x.parent != null && x != root && x.parent.color == RED) {
  4.             if (x.parent == x.parent.parent.left) {
  5.                 // x's parent is a left child.
  6.                 Entry<K,V> y = x.parent.parent.right;
  7.                 if (y != null && y.color == RED) {
  8.                     // Case 1: x's uncle y is red.
  9. //                  System.out.println("rbInsertFixup: Case 1 left");
  10.                     x.parent.color = BLACK;
  11.                     y.color = BLACK;
  12.                     x.parent.parent.color = RED;
  13.                     x = x.parent.parent;
  14.                 } else {
  15.                     if (x == x.parent.right) {
  16.                         // Case 2: x's uncle y is black and x is a right child.
  17.                         // System.out.println("rbInsertFixup: Case 2 left");
  18.                         x = x.parent;
  19.                         rotateLeft(x);
  20.                     }
  21.                     // Case 3: x's uncle y is black and x is a left child.
  22.                     //System.out.println("rbInsertFixup: Case 3 left");
  23.                     x.parent.color = BLACK;
  24.                     x.parent.parent.color = RED;
  25.                     rotateRight(x.parent.parent);
  26.                 }
  27.             } else {
  28.                 // x's parent is a right child.  Do the same as when x's
  29.                 // parent is a left child, but exchange "left" and "right."
  30.                 Entry<K,V> y = x.parent.parent.left; 
  31.                 if (y != null && y.color == RED) {
  32.                     // Case 1: x's uncle y is red.
  33.                     // System.out.println("rbInsertFixup: Case 1 right");
  34.                     x.parent.color = BLACK;
  35.                     y.color = BLACK;
  36.                     x.parent.parent.color = RED;
  37.                     x = x.parent.parent;
  38.                 } else {
  39.                     if (x == x.parent.left) {
  40.                         // Case 2: x's uncle y is black and x is a left child.
  41.                         // System.out.println("rbInsertFixup: Case 2 right");
  42.                         x = x.parent;
  43.                         rotateRight(x);
  44.                     }
  45.                     // Case 3: x's uncle y is black and x is a right child.
  46.                     // System.out.println("rbInsertFixup: Case 3 right");
  47.                     x.parent.color = BLACK;
  48.                     x.parent.parent.color = RED;
  49.                     rotateLeft(x.parent.parent);
  50.                 }
  51.             }
  52.         }
  53.         // The root is always black.
  54.         root.color = BLACK;
  55.     }
  56.     /**
  57.      * Do a right rotation around this node.
  58.     */
  59.     private void rotateRight(Entry<K,V> y) {
  60.         if(y != null){
  61.             Entry<K,V> x = y.left;
  62.             y.left = x.right;
  63.             if (x.right != null)
  64.                 x.right.parent = y;
  65.             x.parent = y.parent;
  66.             if (y.parent == null) {
  67.                 root = (Entry)x;
  68.             } else if (y == y.parent.right){ 
  69.                 y.parent.right = x;
  70.             } else {
  71.                 x.parent.left = x;
  72.             }
  73.             x.right = y;
  74.             y.parent = x;
  75.         }
  76.     }
  77.     /**
  78.      * Do a left rotation around this node.
  79.     */
  80.     private void rotateLeft(Entry<K,V> x) {
  81.         if(x != null){
  82.             Entry<K,V> y = x.right;
  83.             x.right = y.left;
  84.             if (y.left != null)
  85.                 y.left.parent = x;
  86.             y.parent = x.parent;
  87.             if (x.parent == null) {
  88.                 root = (Entry)y;
  89.             } else if (x == x.parent.left) {
  90.                 x.parent.left = y;
  91.             } else {
  92.                 x.parent.right = y;
  93.             }
  94.             y.left = x;
  95.             x.parent = y;
  96.         }        
  97.     }

Y ahí es cuando no me doy cuenta en cómo resolverlos. ¿Cómo resuelvo esta falla?

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #4 (permalink)  
Antiguo 14/06/2018, 05:07
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
Prueba esto:

1. Introducir 2 o 3 elementos en vez de todos los que introduces e ir añadiendo cada vez más elementos a ver si se pierde e imprimir solo el size sin llamar a toString para ninguno de los 2 mapas.

2. Ejecutar solo este código:

System.out.println("* tamaño mapa 2: " + map2.size());
System.out.println(map2.toString());

pero no el equivalente para map1 (Sospecho que map1.toString() puede interferir en el contenido de map2).

Si fuese éste el problema tendrías que revisar el punto de ejecución donde se elimina el elemento del primer map y corregirlo.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #5 (permalink)  
Antiguo 14/06/2018, 19:23
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Hola FuzzyLog gracias por responder y le diste al blanco, verás uso este código para probar:

Código Java: 
Ver original
  1. private static void insertAllWithClass(){
  2.         Persona p1 = new Persona(Persona.getMaxId(), "Juan", 56);
  3.         Persona.maxIdUp();
  4.         Persona p2 = new Persona(Persona.getMaxId(), "Alberto", 73);
  5.         Persona.maxIdUp();
  6.         Persona p3 = new Persona(Persona.getMaxId(), "Julia", 62);
  7.         Persona.maxIdUp();
  8.         Persona p4 = new Persona(Persona.getMaxId(), "Luis", 71);
  9.         Persona.maxIdUp();
  10.         Persona p5 = new Persona(Persona.getMaxId(), "Maria", 18);
  11.         Persona.maxIdUp();
  12.         MyTreeMap<Integer,Persona> map = new MyTreeMap();
  13.         map.put(p1.getId(), p1);
  14.         map.put(p2.getId(), p2);
  15.         map.put(p3.getId(), p3);
  16.         map.put(p4.getId(), p4);
  17.         map.put(p5.getId(), p5);
  18.         MyTreeMap<Integer,Persona> map2 = new MyTreeMap(map);
  19.         System.out.println("* tamaño mapa 1: " + map.size());
  20.         System.out.println(map);
  21.         System.out.println("* tamaño mapa 2: " + map2.size());
  22.         System.out.println(map2);
  23.     }

Cuando inserto 2, pasa esto:

Cita:
* tamaño mapa 1: 2
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2: 2
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
Cuando son 3:

Cita:
* tamaño mapa 1: 3
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2: 3
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
Hasta 4 funciona bien:

Cita:
* tamaño mapa 1: 4
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2: 4
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
De 5 en adelante es el problema y el rotateLeft es el que me está complicando:

Código Java: 
Ver original
  1. private void rotateLeft(Entry<K,V> p) {
  2.         if(p != null){
  3.             Entry<K,V> r = p.right;
  4.             p.right = r.left; // esta es la línea del problema
  5.             if (r.left != null)
  6.                 r.left.parent = p;
  7.             r.parent = p.parent;
  8.             if (p.parent == null) {
  9.                 root = (Entry)r;
  10.             } else if (p == p.parent.left) {
  11.                 p.parent.left = r;
  12.             } else {
  13.                 p.parent.right = r;
  14.             }
  15.             r.left = p;
  16.             p.parent = r;
  17.         }        
  18.     }

¿cómo lo soluciono?

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
Última edición por detective_jd; 14/06/2018 a las 20:26
  #6 (permalink)  
Antiguo 15/06/2018, 04:43
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
El problema que tienes es que estás creando un segundo Map con una referencia al contenido del primer Map.

Si ejecutas algún método que modifique el contenido del primer map, automáticamente se modificará también para el segundo map.

Un método toString() no debería en ningún caso reordenar los contenidos, sino mostrar su contenido tal cual está.

es mejor que separes cualquier método para reorganizar un map de los métodos de visualización.

Luego tendrás que revisar qué quieres hacer con esos métodos rotate, y si realmente hacen lo que deben, ya que no deberían eliminar contenido sino que en todo caso debería modificarse su posición.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #7 (permalink)  
Antiguo 15/06/2018, 20:29
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Hola FuzzyLog gracias por responder y si querías ver algo mucho más troll, es que probé sin toString y me hace esto:

Cita:
* tamaño mapa 1: 5
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
* tamaño mapa 2: 4
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
O sea el 3 está bien escondido jaja, cuando tu código te hace ver cómo idiota jaja,

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #8 (permalink)  
Antiguo 18/06/2018, 05:47
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
Por defecto al tratar de imprimir un objeto te llama al toString sin necesidad de que tú lo especifiques.

La diferencia que podría tener es que lo q muestra es el valor que queda después de finalizar la ejecución.

Pero lo cierto es que sí ejecuta el toString.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #9 (permalink)  
Antiguo 18/06/2018, 21:50
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Hola FuzzyLog gracias por responder, resolví el problema del elemento que se borraba, resulta que era el put el que no funcionaba bien y logré cambiarlo:

Código Java: 
Ver original
  1. public V put(K key, V value) {
  2.         if(key != null){
  3.             Entry<K,V> e = new Entry(key, value);
  4.             Entry<K,V> parent = null;
  5.             Entry<K,V> t = root;        
  6.             int cmp = 0;
  7.             while (t != null) {
  8.                 parent = t;
  9.                 Comparable<? super K> k = (Comparable<? super K>) key;
  10.                 cmp = (comparator != null) ? comparator.compare(key,t.key) : k.compareTo(t.key);
  11.                 if(cmp < 0){
  12.                     t = t.left;
  13.                 } else if(cmp > 0) {
  14.                     t = t.right;
  15.                 } else {
  16.                     t.value = value;
  17.                     return value;
  18.                 } 
  19.             }
  20.             e.parent = parent;
  21.             if(t == null){
  22.                 root = e;
  23.             } else if (cmp < 0) {
  24.                 parent.left = e;
  25.             } else {
  26.                 parent.right = e;
  27.             }
  28.             rbInsertFixup(e);
  29.             size++;
  30.         }
  31.         return null;
  32.     }

sólo que ahora me muestra así:
Cita:
* tamaño mapa 1: 5
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
* tamaño mapa 2: 5
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
en el map1 me lo ordena de forma decreciente y el 2 creciente, cuando los 2 tendrían que estar creciente.
Apenas hice estos otros cambios:

Código Java: 
Ver original
  1. private void rbInsertFixup(Entry<K,V> x) {
  2.         x.color = RED;
  3.         while (x.parent != null && x.parent.color == RED) {
  4.             if (x.parent == x.parent.parent.left) {
  5.                 Entry<K,V> y = x.parent.parent.right;
  6.                 if (y != null && y.color == RED) {
  7.                     x.parent.color = BLACK;
  8.                     y.color = BLACK;
  9.                     x.parent.parent.color = RED;
  10.                     x = x.parent.parent;
  11.                 } else {
  12.                     if (x == x.parent.right) {
  13.                         x = x.parent;
  14.                         rotateLeft(x);
  15.                     } else {
  16.                         x.parent.color = BLACK;
  17.                         x.parent.parent.color = RED;
  18.                         rotateRight(x.parent.parent);
  19.                     }
  20.                 }
  21.             } else {
  22.                 Entry<K,V> y = x.parent.parent.left; 
  23.                 if (y != null && y.color == RED) {
  24.                     x.parent.color = BLACK;
  25.                     y.color = BLACK;
  26.                     x.parent.parent.color = RED;
  27.                     x = x.parent.parent;
  28.                 } else {
  29.                     if (x == x.parent.left) {
  30.                         x = x.parent;
  31.                         rotateRight(x);
  32.                     } else {
  33.                         x.parent.color = BLACK;
  34.                         x.parent.parent.color = RED;
  35.                         rotateLeft(x.parent.parent);
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.         root.color = BLACK;
  41.     }
  42.     /**
  43.      * Do a right rotation around this node.
  44.     */
  45.     private void rotateRight(Entry<K,V> p) {
  46.         Entry<K,V> x = p.left;
  47.         p.left = x.right;
  48.         if (x.right != null)
  49.             x.right.parent = p;
  50.         x.parent = p.parent;
  51.         x.right = p;
  52.         p.right = x;
  53.         if (p.parent == null) {
  54.             root = (Entry)x;
  55.         } else if (p == p.parent.right){ 
  56.             p.parent.right = x;
  57.         } else {
  58.             x.parent.left = x;
  59.         }        
  60.     }
  61.     /**
  62.      * Do a left rotation around this node.
  63.     */
  64.     private void rotateLeft(Entry<K,V> p) {        
  65.         Entry<K,V> y = p.right;
  66.         p.right = y.left;
  67.         if (y.left != null)
  68.             y.left.parent = p;
  69.         y.parent = p.parent;
  70.         if (p.parent == null) {
  71.             root = (Entry)y;
  72.         } else if (p == p.parent.left) {
  73.             p.parent.left = y;
  74.         } else {
  75.             p.parent.right = y;
  76.         }
  77.         y.left = p;
  78.         p.parent = y; 
  79.     }

Espero sus respuestas y saludos.

PD: El toString ya no está más, desapareció.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #10 (permalink)  
Antiguo 19/06/2018, 20:38
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Cuando tu satisfacción se vuelve una decepción, resulta que el código de ayer estaba mal si lo pongo así quedo cómo estaba:

Código Java: 
Ver original
  1. @Override
  2.     public V put(K key, V value) {
  3.         if(key != null){
  4.             Entry<K,V> z = new Entry(key, value);
  5.             Entry<K,V> y = null;
  6.             Entry<K,V> x = root;        
  7.             int cmp = 0;
  8.             if(comparator != null){
  9.                 while (x != null) {
  10.                     y = x;
  11.                     cmp = comparator.compare(key,x.key);
  12.                     if(cmp < 0){
  13.                         x = x.left;
  14.                     } else if(cmp > 0) {
  15.                         x = x.right;
  16.                     } else {
  17.                         x.value = value;
  18.                         return value;
  19.                     } 
  20.                 }
  21.             } else {
  22.                 while (x != null) {
  23.                     y = x;
  24.                     Comparable<? super K> k = (Comparable<? super K>) key;
  25.                     cmp = k.compareTo(x.key);
  26.                     if(cmp < 0){
  27.                         x = x.left;
  28.                     } else if(cmp > 0) {
  29.                         x = x.right;
  30.                     } else {
  31.                         x.value = value;
  32.                         return value;
  33.                     } 
  34.                 }
  35.             }            
  36.             z.parent = y;
  37.             if(y == null){ // si pongo x en el ifme muestra 5 elementos sino me muestra 4
  38.                 root = z;
  39.             } else if (cmp < 0) {
  40.                 y.left = z;
  41.             } else {
  42.                 y.right = z;
  43.             }
  44.             z.color = RED;
  45.             rbInsertFixup(z);
  46.             size++;
  47.         }
  48.         return null;
  49.     }

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #11 (permalink)  
Antiguo 22/06/2018, 20:25
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Buenas noticias logré hacer andar el código pudiendo poner datos de un map a otro, tenía que arreglar el put, fixUp y el successor:

Código Java: 
Ver original
  1. @Override
  2.     public V put(K key, V value) {
  3.         if(key != null){
  4.             Entry<K,V> t = root;
  5.             if(t == null){
  6.                 root = new Entry(key,value,null);
  7.                 size = 1;
  8.             } else {
  9.                 Entry<K,V> parent = null;                    
  10.                 int cmp = 0;
  11.                 while (t != null) {
  12.                     parent = t;
  13.                     cmp = checkCompare(t,key);
  14.                     if(cmp < 0){
  15.                         t = t.left;
  16.                     } else if(cmp > 0) {
  17.                         t = t.right;
  18.                     } else {
  19.                         return t.value = value;
  20.                     } 
  21.                 }
  22.                 Entry<K,V> e = new Entry<>(key, value, parent);
  23.                 if (cmp < 0) {
  24.                     parent.left = e;
  25.                 } else {
  26.                     parent.right = e;
  27.                 }
  28.                 e.color = RED;
  29.                 fixUp(e);
  30.                 size++;
  31.             }                            
  32.         }
  33.         return null;
  34.     }
  35.     private int checkCompare(Entry<K,V>x, K key){
  36.         if(comparator != null){
  37.             return comparator.compare(key,x.key);
  38.         } else {
  39.             Comparable<? super K> k = (Comparable<? super K>) key;
  40.             return k.compareTo(x.key);
  41.         }
  42.     }
  43.     private void fixUp(Entry<K,V> x) {
  44.         while (x != null && x != root && x.parent.color == RED) {
  45.             if (x.parent == x.parent.parent.left) {
  46.                 Entry<K,V> y = x.parent.parent.right;
  47.                 if (y != null && y.color == RED) {
  48.                     x.parent.color = BLACK;
  49.                     y.color = BLACK;
  50.                     x.parent.parent.color = RED;
  51.                     x = x.parent.parent;
  52.                 } else {
  53.                     if (x == x.parent.right) {
  54.                         x = x.parent;
  55.                         rotateLeft(x);
  56.                     } else {
  57.                         x.parent.color = BLACK;
  58.                         x.parent.parent.color = RED;
  59.                         rotateRight(x.parent.parent);
  60.                     }
  61.                 }
  62.             } else {
  63.                 Entry<K,V> y = x.parent.parent.left; 
  64.                 if (y != null && y.color == RED) {
  65.                     x.parent.color = BLACK;
  66.                     y.color = BLACK;
  67.                     x.parent.parent.color = RED;
  68.                     x = x.parent.parent;
  69.                 } else {
  70.                     if (x == x.parent.left) {
  71.                         x = x.parent;
  72.                         rotateRight(x);
  73.                     } else {
  74.                         x.parent.color = BLACK;
  75.                         x.parent.parent.color = RED;
  76.                         rotateLeft(x.parent.parent);
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.         root.color = BLACK;
  82.     }
  83.     /**
  84.      * Do a right rotation around this node.
  85.     */
  86.     private void rotateRight(Entry<K,V> p) {
  87.         Entry<K,V> x = p.left;
  88.         p.left = x.right;
  89.         if (x.right != null)
  90.             x.right.parent = p;
  91.         x.parent = p.parent;
  92.         x.right = p;
  93.         p.right = x;
  94.         if (p.parent == null) {
  95.             root = (Entry)x;
  96.         } else if (p == p.parent.right){ 
  97.             p.parent.right = x;
  98.         } else {
  99.             x.parent.left = x;
  100.         }        
  101.     }
  102.     /**
  103.      * Do a left rotation around this node.
  104.     */
  105.     private void rotateLeft(Entry<K,V> p) {        
  106.         Entry<K,V> y = p.right;
  107.         p.right = y.left;
  108.         if (y.left != null)
  109.             y.left.parent = p;
  110.         y.parent = p.parent;
  111.         if (p.parent == null) {
  112.             root = (Entry)y;
  113.         } else if (p == p.parent.left) {
  114.             p.parent.left = y;
  115.         } else {
  116.             p.parent.right = y;
  117.         }
  118.         y.left = p;
  119.         p.parent = y; 
  120.     }
  121.     //copié el successor de Oracle, claro está
  122.     private Entry<K,V> successor(Entry<K,V> t) {      
  123.         if (t == null)
  124.             return null;
  125.         else if (t.right != null) {
  126.             Entry<K,V> p = t.right;
  127.             while (p.left != null)
  128.                 p = p.left;
  129.             return p;
  130.         } else {
  131.             Entry<K,V> p = t.parent;
  132.             Entry<K,V> ch = t;
  133.             while (p != null && ch == p.right) {
  134.                 ch = p;
  135.                 p = p.parent;
  136.             }
  137.             return p;
  138.         }
  139.     }

Y los test de inserción simple, inserción con clases, y defiendo el órden por las claves de forma creciente andan, pero cuando quiero que me los inserte ordenados por las claves de forma decreciente no andan bien, me hace esto:

Cita:
---- prueba 4 ----
tamaño: 10

[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
................
El código es prueba es este:

Código Java: 
Ver original
  1. private static void insertWithClassOrderDesc(){
  2.         Persona.resetId();
  3.         MyTreeMap<Integer,Persona> map = new MyTreeMap(new OrdenarDesc());
  4.         Persona p1 = new Persona(Persona.getMaxId(), "Juan", 56);
  5.         Persona.maxIdUp();
  6.         Persona p2 = new Persona(Persona.getMaxId(), "Alberto", 73);
  7.         Persona.maxIdUp();
  8.         Persona p3 = new Persona(Persona.getMaxId(), "Julia", 62);
  9.         Persona.maxIdUp();
  10.         Persona p4 = new Persona(Persona.getMaxId(), "Luis", 71);
  11.         Persona.maxIdUp();
  12.         Persona p5 = new Persona(Persona.getMaxId(), "Maria", 18);
  13.         Persona.maxIdUp();
  14.         Persona p6 = new Persona(Persona.getMaxId(), "Pedro", 16);
  15.         Persona.maxIdUp();
  16.         Persona p7 = new Persona(Persona.getMaxId(), "Deborah", 26);
  17.         Persona.maxIdUp();
  18.         Persona p8 = new Persona(Persona.getMaxId(), "Nelson", 37);
  19.         Persona.maxIdUp();
  20.         Persona p9 = new Persona(Persona.getMaxId(), "Tommy", 22);
  21.         Persona.maxIdUp();
  22.         Persona p10 = new Persona(Persona.getMaxId(), "Manuela", 15);
  23.         Persona.maxIdUp();
  24.         map.put(p1.getId(), p1);
  25.         map.put(p2.getId(), p2);
  26.         map.put(p3.getId(), p3);
  27.         map.put(p4.getId(), p4);
  28.         map.put(p5.getId(), p5);
  29.         map.put(p6.getId(), p6);
  30.         map.put(p7.getId(), p7);
  31.         map.put(p8.getId(), p8);
  32.         map.put(p9.getId(), p9);
  33.         map.put(p10.getId(), p10);
  34.         map.put(10, new Persona(10, "Micaela", 21));
  35.         map.put(6, new Persona(6, "Sergio", 25));
  36.         map.put(null, new Persona(11, "Sefafin", 7));
  37.         System.out.println("---- prueba 4 ----");
  38.         System.out.println("tamaño: " + map.size() + "\n");
  39.         map.entrySet().forEach((e)->{
  40.             System.out.println(e);
  41.         });
  42.         //System.out.println(map);
  43.     }

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #12 (permalink)  
Antiguo 23/06/2018, 21:35
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Problema resuelto, resulta que era esta línea 93 del rotateRight que era lo que me fallaba, la borré y me anduvo lo más bien quedándome así:

Código Java: 
Ver original
  1. private void rotateRight(Entry<K,V> p) {
  2.         Entry<K,V> x = p.left;
  3.         p.left = x.right;
  4.         if (x.right != null)
  5.             x.right.parent = p;
  6.         x.parent = p.parent;
  7.         x.right = p;
  8.         if (p.parent == null) {
  9.             root = (Entry)x;
  10.         } else if (p == p.parent.right){ 
  11.             p.parent.right = x;
  12.         } else {
  13.             x.parent.left = x;
  14.         }        
  15.     }

Pasé a hacer las pruebas de lo que pasa cuando agregas un treemap a otro pero desde pones de uno ordenado de forma decreciente a uno
creciente, hace esto:

Cita:
---- prueba 3 ----
* tamaño mapa 1: 5
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]

* tamaño mapa 2: 10
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[6 -> Persona{6, Nombre: Sergio, Edad: 25}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
El mapa 2 no tiene el 1,2,3 y 4, esta es la prueba que hago:

Código Java: 
Ver original
  1. private static void insertAllWithClassOrderAsc(){
  2.         Persona.resetId();
  3.         //MyTreeMap<Integer,Persona> map1 = new MyTreeMap();
  4.         MyTreeMap<Integer,Persona> map1 = new MyTreeMap(new OrdenarDesc());
  5.         MyTreeMap<Integer,Persona> map2 = new MyTreeMap(new OrdenarAsc());
  6.         Persona p1 = new Persona(Persona.getMaxId(), "Juan", 56);
  7.         Persona.maxIdUp();
  8.         Persona p2 = new Persona(Persona.getMaxId(), "Alberto", 73);
  9.         Persona.maxIdUp();
  10.         Persona p3 = new Persona(Persona.getMaxId(), "Julia", 62);
  11.         Persona.maxIdUp();
  12.         Persona p4 = new Persona(Persona.getMaxId(), "Luis", 71);
  13.         Persona.maxIdUp();
  14.         Persona p5 = new Persona(Persona.getMaxId(), "Maria", 18);
  15.         Persona.maxIdUp();
  16.         Persona p6 = new Persona(Persona.getMaxId(), "Pedro", 16);
  17.         Persona.maxIdUp();
  18.         Persona p7 = new Persona(Persona.getMaxId(), "Deborah", 26);
  19.         Persona.maxIdUp();
  20.         Persona p8 = new Persona(Persona.getMaxId(), "Nelson", 37);
  21.         Persona.maxIdUp();
  22.         Persona p9 = new Persona(Persona.getMaxId(), "Tommy", 22);
  23.         Persona.maxIdUp();
  24.         Persona p10 = new Persona(Persona.getMaxId(), "Manuela", 15);
  25.         Persona.maxIdUp();
  26.         map1.put(p1.getId(), p1);
  27.         map1.put(p2.getId(), p2);
  28.         map1.put(p3.getId(), p3);
  29.         map1.put(p4.getId(), p4);
  30.         map1.put(p5.getId(), p5);
  31.         passToMap(map1, map2);
  32.         map2.put(p6.getId(), p6);
  33.         map2.put(p7.getId(), p7);
  34.         map2.put(p8.getId(), p8);
  35.         map2.put(p9.getId(), p9);
  36.         map2.put(p10.getId(), p10);
  37.         map2.put(10, new Persona(10, "Micaela", 21));
  38.         map2.put(6, new Persona(6, "Sergio", 25));
  39.         map2.put(null, new Persona(11, "Sefafin", 7));
  40.         System.out.println("---- prueba 3 ----");
  41.         System.out.println("* tamaño mapa 1: " + map1.size());
  42.         /*map.entrySet().forEach((e) -> {
  43.             System.out.println(e);
  44.         });*/
  45.         System.out.println(map1);
  46.         System.out.println("* tamaño mapa 2: " + map2.size());
  47.         /*map2.entrySet().forEach((e) -> {
  48.             System.out.println(e);
  49.         });*/
  50.         System.out.println(map2);
  51.         
  52.     }
  53.     private static void passToMap(MyTreeMap<Integer,Persona> map1,MyTreeMap<Integer,Persona> map2){
  54.         map1.entrySet().forEach((e) -> {
  55.             map2.put(e.getKey(), e.getValue());
  56.         });
  57.     }

Estas son las clases de ordenación:

Código Java: 
Ver original
  1. package treemapsimple;
  2. import java.util.Comparator;
  3. public class OrdenarDesc implements Comparator<Integer>
  4. {
  5.     @Override
  6.     public int compare(Integer o1, Integer o2) {
  7.         return o2 - o1;
  8.     }
  9. }

Código Java: 
Ver original
  1. package treemapsimple;
  2. import java.util.Comparator;
  3. public class OrdenarAsc implements Comparator<Integer>
  4. {
  5.     @Override
  6.     public int compare(Integer o1, Integer o2) {
  7.         return o1 - o2;
  8.     }    
  9. }

¿Cuál será el problema?

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #13 (permalink)  
Antiguo 24/06/2018, 09:12
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
Al mover de un mapa a otro estás pasando un valor en vez del objeto en sí

private static void passToMap(MyTreeMap<Integer,Persona> map1,MyTreeMap<Integer,Persona> map2){
map1.entrySet().forEach((e) -> {
map2.put(e.getKey(), e.getValue());
});
}

mira si con esto te va bien

private static void passToMap(MyTreeMap<Integer,Persona> map1,MyTreeMap<Integer,Persona> map2){
map1.entrySet().forEach((e) -> {
map2.put(e.getKey(), e);
});
}
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #14 (permalink)  
Antiguo 24/06/2018, 20:42
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Hola FuzzyLog probé lo que me dijiste pero no funcionó dando error de que no es admitido, sólo que de lo que me dijiste cambié un poco el test y encontre algo interesante, resulta que antes de agregar los elementos 6,7,8,9,10 conserva el orden de forma decreciente sólo que cuando agrego los mencionados acontece lo dicho en mi mensaje anterior.
Este es el test cambiado:

Código Java: 
Ver original
  1. private static void insertAllWithClassOrderAsc(){
  2.         Persona.resetId();
  3.         //MyTreeMap<Integer,Persona> map1 = new MyTreeMap();
  4.         MyTreeMap<Integer,Persona> map1 = new MyTreeMap(new OrdenarDesc());
  5.         MyTreeMap<Integer,Persona> map2 = new MyTreeMap(new OrdenarAsc());
  6.         Persona p1 = new Persona(Persona.getMaxId(), "Juan", 56);
  7.         Persona.maxIdUp();
  8.         Persona p2 = new Persona(Persona.getMaxId(), "Alberto", 73);
  9.         Persona.maxIdUp();
  10.         Persona p3 = new Persona(Persona.getMaxId(), "Julia", 62);
  11.         Persona.maxIdUp();
  12.         Persona p4 = new Persona(Persona.getMaxId(), "Luis", 71);
  13.         Persona.maxIdUp();
  14.         Persona p5 = new Persona(Persona.getMaxId(), "Maria", 18);
  15.         Persona.maxIdUp();
  16.         Persona p6 = new Persona(Persona.getMaxId(), "Pedro", 16);
  17.         Persona.maxIdUp();
  18.         Persona p7 = new Persona(Persona.getMaxId(), "Deborah", 26);
  19.         Persona.maxIdUp();
  20.         Persona p8 = new Persona(Persona.getMaxId(), "Nelson", 37);
  21.         Persona.maxIdUp();
  22.         Persona p9 = new Persona(Persona.getMaxId(), "Tommy", 22);
  23.         Persona.maxIdUp();
  24.         Persona p10 = new Persona(Persona.getMaxId(), "Manuela", 15);
  25.         Persona.maxIdUp();
  26.         map1.put(p1.getId(), p1);
  27.         map1.put(p2.getId(), p2);
  28.         map1.put(p3.getId(), p3);
  29.         map1.put(p4.getId(), p4);
  30.         map1.put(p5.getId(), p5);
  31.         passToMap(map1, map2);        
  32.         System.out.println("---- prueba 3 ----");
  33.         System.out.println("* tamaño mapa 1: " + map1.size());
  34.         /*map.entrySet().forEach((e) -> {
  35.             System.out.println(e);
  36.         });*/
  37.         System.out.println(map1);
  38.         System.out.println("* tamaño mapa 2 antes del extra: " + map2.size());
  39.         /*map2.entrySet().forEach((e) -> {
  40.             System.out.println(e);
  41.         });*/
  42.         System.out.println(map2);
  43.         /*-------- extra --------*/
  44.         map2.put(p6.getId(), p6);
  45.         map2.put(p7.getId(), p7);
  46.         map2.put(p8.getId(), p8);
  47.         map2.put(p9.getId(), p9);
  48.         map2.put(p10.getId(), p10);
  49.         map2.put(10, new Persona(10, "Micaela", 21));
  50.         map2.put(6, new Persona(6, "Sergio", 25));
  51.         map2.put(null, new Persona(11, "Sefafin", 7));
  52.         System.out.println("* tamaño mapa 2 después del extra: " + map2.size());
  53.         /*map2.entrySet().forEach((e) -> {
  54.             System.out.println(e);
  55.         });*/
  56.         System.out.println(map2);
  57.         
  58.     }

Y esto es lo que sale en la consola:

Cita:
run:
---- prueba 3 ----
* tamaño mapa 1: 5
[1 -> Persona{1, Nombre: Juan, Edad: 56}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]

* tamaño mapa 2 antes del extra: 5
[5 -> Persona{5, Nombre: Maria, Edad: 18}]
[4 -> Persona{4, Nombre: Luis, Edad: 71}]
[3 -> Persona{3, Nombre: Julia, Edad: 62}]
[2 -> Persona{2, Nombre: Alberto, Edad: 73}]
[1 -> Persona{1, Nombre: Juan, Edad: 56}]

* tamaño mapa 2 después del extra: 10
[10 -> Persona{10, Nombre: Micaela, Edad: 21}]
[9 -> Persona{9, Nombre: Tommy, Edad: 22}]
[8 -> Persona{8, Nombre: Nelson, Edad: 37}]
[7 -> Persona{7, Nombre: Deborah, Edad: 26}]
[6 -> Persona{6, Nombre: Sergio, Edad: 25}]
[5 -> Persona{5, Nombre: Maria, Edad: 18}]

BUILD SUCCESSFUL (total time: 0 seconds)
Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #15 (permalink)  
Antiguo 29/06/2018, 20:30
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Hola a todos, problema resuelto resulta que le faltaba una línea al final de rotateRight:

Código Java: 
Ver original
  1. private void rotateRight(Entry<K,V> p) {
  2.         Entry<K,V> x = p.left;
  3.         p.left = x.right;
  4.         if (x.right != null)
  5.             x.right.parent = p;
  6.         x.parent = p.parent;        
  7.         if (p.parent == null) {
  8.             root = (Entry)x;
  9.         } else if (p == p.parent.right){ 
  10.             p.parent.right = x;
  11.         } else {
  12.             x.parent.left = x;
  13.         }
  14.         x.right = p;
  15.         p.parent = x; //faltaba esta línea
  16.     }

Ya hice todas las pruebas y es oficial el put ya esta funciona bien, iré viendo las demás funcionalidades si alguna me falla iré pegando el grito.

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #16 (permalink)  
Antiguo 07/07/2018, 21:59
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Buenas a todos, aquí estoy de vuelta resulta que ahora el eliminar no funciona, me da este error:

Cita:
Exception in thread "main" java.lang.NullPointerException
at treemapsimple.MyTreeMap.fixDown(MyTreeMap.java:258 )
at treemapsimple.MyTreeMap.deleteEntry(MyTreeMap.java :212)
at treemapsimple.MyTreeMap.remove(MyTreeMap.java:182)
at treemapsimple.Cuerpo.checkDelete1(Cuerpo.java:35)
at treemapsimple.Cuerpo.main(Cuerpo.java:43)
/home/detectivejd/.cache/netbeans/8.2/executor-snippets/run.xml:53: Java returned: 1
BUILD FAILED (total time: 0 seconds)
Acá está el código:

Código Java: 
Ver original
  1. @Override
  2.     public V remove(Object key) {
  3.         Entry<K,V> p = getEntry(key);
  4.         if (p == null) {
  5.             return null;
  6.         } else {
  7.             V oldValue = p.value;
  8.             deleteEntry(p);              
  9.             return oldValue;
  10.         }
  11.     }
  12.     private void deleteEntry(Entry<K,V> p) {
  13.         size--;
  14.         if (p.left != null && p.right != null) {
  15.             Entry<K,V> s = successor(p);
  16.             p.key = s.key;
  17.             p.value = s.value;
  18.             p = s;
  19.         } 
  20.         Entry<K,V> rep = (p.left != null ? p.left : p.right);
  21.         if (rep != null) {
  22.             rep.parent = p.parent;
  23.             if (p.parent == null) {
  24.                 root = rep;
  25.             } else if (p == p.parent.left) {
  26.                 p.parent.left  = rep;
  27.             } else {
  28.                 p.parent.right = rep; 
  29.             }
  30.             p.left = p.right = p.parent = null;
  31.             if (p.color == BLACK) {
  32.                 fixDown(rep); 
  33.             }
  34.         } else if (p.parent == null) { // return if we are the only node.
  35.             root = null;
  36.         } else { //  No children. Use self as phantom replacement and unlink.
  37.             if (p.color == BLACK) {
  38.                 fixDown(p); 
  39.             }
  40.             if (p.parent != null) {
  41.                 if (p == p.parent.left) {
  42.                     p.parent.left = null;
  43.                 } else if (p == p.parent.right) {
  44.                     p.parent.right = null; 
  45.                 }
  46.                 p.parent = null;
  47.             }
  48.         }        
  49.     }
  50.     private void fixDown(Entry<K,V>x){
  51.         while(x != root && x.color == BLACK) {
  52.             if(x == x.parent.left) {
  53.                 Entry<K,V> sib = x.parent.right;
  54.                 if(sib.color == RED) {
  55.                     sib.color = BLACK;
  56.                     x.parent.color = RED;
  57.                     rotateLeft(x.parent);
  58.                     sib = x.parent.right;
  59.                 }
  60.                 if(sib.left.color == BLACK && sib.right.color == BLACK) { //acá se detiene
  61.                     sib.color = RED;
  62.                     x = x.parent;
  63.                 } else {
  64.                     if(sib.right.color == BLACK) {
  65.                         sib.left.color = BLACK;
  66.                         sib.color = RED;
  67.                         rotateRight(sib);
  68.                         sib = x.parent.right;
  69.                     }
  70.                     sib.color = x.parent.color;
  71.                     x.parent.color = BLACK;
  72.                     sib.right.color = BLACK;
  73.                     rotateLeft(x.parent);
  74.                     x = root;
  75.                 }
  76.             } else {
  77.                 Entry<K,V> sib = x.parent.left;
  78.                 if(sib.color == RED) {
  79.                     sib.color = BLACK;
  80.                     x.parent.color = RED;
  81.                     rotateRight(x.parent);
  82.                     sib = x.parent.left;
  83.                 }
  84.                 if(sib.right.color == BLACK && sib.left.color == BLACK) { // acá se detiene
  85.                     sib.color = RED;
  86.                     x = x.parent;
  87.                 } else {
  88.                     if(sib.left.color == BLACK) {
  89.                         sib.right.color = BLACK;
  90.                         sib.color = RED;
  91.                         rotateLeft(sib);
  92.                         sib = x.parent.left;
  93.                     }
  94.                     sib.color = x.parent.color;
  95.                     x.parent.color = BLACK;
  96.                     sib.left.color = BLACK;
  97.                     rotateRight(x.parent);
  98.                     x = root;
  99.                 }
  100.             }
  101.         }
  102.         x.color = BLACK;
  103.     }

Mirando en otros sitios el fix del eliminar es muy parecido al que tengo, y no sé dónde está el problema, depurando se me detiene en la línea de los if del lado izquierdo como derecho.

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #17 (permalink)  
Antiguo 09/07/2018, 02:52
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
Un nullpointer es que algún objeto es null en el momento de la ejecución y estás intentando acceder a una propiedad o método del mismo y por eso falla. Averigua qué objeto es null y a partir de ahí mira si te falta por añadir algo.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #18 (permalink)  
Antiguo 10/07/2018, 20:51
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
FuzzyLog gracias por responder, resulta que me faltaban estos:

Código Java: 
Ver original
  1. /*
  2.        sólo con este ya se arreglaba mi problema, porque cuando quería obtener el color de una entrada cual fuera
  3.        me pateaba porque era nulo, ya con esto es indiferente
  4.     */
  5.     private boolean colorOf(Entry<K,V> p) {
  6.         return (p == null ? BLACK : p.color);
  7.     }
  8.     //el resto está por prolijidad
  9.     private Entry<K,V> parentOf(Entry<K,V> p) {
  10.         return (p == null ? null: p.parent);
  11.     }
  12.     private void setColor(Entry<K,V> p, boolean c) {
  13.         if (p != null)
  14.             p.color = c;
  15.     }
  16.     private Entry<K,V> leftOf(Entry<K,V> p) {
  17.         return (p == null) ? null: p.left;
  18.     }
  19.     private Entry<K,V> rightOf(Entry<K,V> p) {
  20.         return (p == null) ? null: p.right;
  21.     }

Con implementar eso todo mi problema se solucionó, subí el código para github por si alguien le interesa:

TreeMapCasero

Entre ayer y hoy pensé que hasta ahora tengo lon que necesito para poder avanzar con lo que quiero hacer pero podría intentar simular todo su comportamiento para ver cómo queda, lo mío será aparte de esto, sólo porque me interesó ver cómo quedará.
Necesitaré que me digan que testeos puedo hacer para verificar el funcionamiento de este árbol casero además de agregar lo que tenga que agregar al implementar SortedMap y posteriormente NavigableMap.

espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #19 (permalink)  
Antiguo 18/07/2018, 21:24
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Buenas a todos, hace días empecé a implementar la 2da parte del TreeMap casero implementando SortedMap, he estado teniendo problemas con la función tailMap, en concreto con el iterator de la clase interna para dicho fin el error es éste:

Cita:
incompatible types: Entry<K#1,V#1> cannot be converted to Entry<K#2,V#2>
where K#1,V#1,K#2,V#2 are type-variables:
K#1 extends Object declared in class MyTreeMap.NavigableSubMap
V#1 extends Object declared in class MyTreeMap.NavigableSubMap
K#2 extends Object declared in class MyTreeMap
V#2 extends Object declared in class MyTreeMa...
La parte del código es ésta:

Código Java: 
Ver original
  1. class NavigableSubMap<K,V> extends AbstractMap<K,V> implements SortedMap<K,V>{
  2.         final MyTreeMap<K,V> m;
  3.         final K lo, hi;
  4.         final boolean fromStart, toEnd;
  5.         final boolean loInclusive, hiInclusive;
  6.         NavigableSubMap(MyTreeMap<K, V> m,
  7.                 boolean fromStart, K lo, boolean loInclusive, 
  8.                 boolean toEnd, K hi, boolean hiInclusive) {
  9.             if (!fromStart && !toEnd) {
  10.                 if (m.compare(lo, hi) > 0)
  11.                     throw new IllegalArgumentException("fromKey > toKey");
  12.             } else {
  13.                 if (!fromStart) // type check
  14.                     m.compare(lo, lo);
  15.                 if (!toEnd)
  16.                     m.compare(hi, hi);
  17.             }
  18.             this.m = m;
  19.             this.lo = lo;
  20.             this.hi = hi;
  21.             this.fromStart = fromStart;
  22.             this.toEnd = toEnd;
  23.             this.loInclusive = loInclusive;
  24.             this.hiInclusive = hiInclusive;
  25.         }        
  26.         final boolean tooLow(Object key) {
  27.             if (!fromStart) {
  28.                 int c = m.compare(key, lo);
  29.                 if (c < 0 || (c == 0 && !loInclusive))
  30.                     return true;
  31.             }
  32.             return false;
  33.         }
  34.         final boolean tooHigh(Object key) {
  35.             if (!toEnd) {
  36.                 int c = m.compare(key, hi);
  37.                 if (c > 0 || (c == 0 && !hiInclusive))
  38.                     return true;
  39.             }
  40.             return false;
  41.         }
  42.         final MyTreeMap.Entry<K,V> absLowest() {
  43.             MyTreeMap.Entry<K,V> e;
  44.             if(fromStart){
  45.                 e = m.getFirstEntry();
  46.             } else if(loInclusive){
  47.                 e = m.getCeilingEntry(lo);
  48.             } else {
  49.                 e = m.getHigherEntry(lo);
  50.             }
  51.             return (e == null || tooHigh(e.getKey())) ? null : e;
  52.         }
  53.         final Entry<K,V> absHighFence() {
  54.             if(toEnd){
  55.                 return null;
  56.             } else if(hiInclusive){
  57.                 return m.getHigherEntry(hi);
  58.             } else {
  59.                 return m.getCeilingEntry(hi);
  60.             }
  61.         }
  62.         @Override
  63.         public Set<Entry<K, V>> entrySet() {
  64.             return new EntrySetView();
  65.         }
  66.         @Override
  67.         public Comparator<? super K> comparator() {
  68.             return m.comparator;
  69.         }
  70.         @Override
  71.         public SortedMap<K, V> subMap(K fromKey, K toKey) {
  72.             return m.subMap(fromKey, toKey);
  73.         }
  74.         @Override
  75.         public SortedMap<K, V> headMap(K toKey) {
  76.             return m.headMap(toKey);
  77.         }
  78.         @Override
  79.         public SortedMap<K, V> tailMap(K fromKey) {
  80.             return m.tailMap(fromKey);
  81.         }
  82.         @Override
  83.         public K firstKey() {
  84.             return m.firstKey();
  85.         }
  86.         @Override
  87.         public K lastKey() {
  88.             return m.lastKey();
  89.         }
  90.         @Override
  91.         public String toString(){
  92.             StringBuilder sb = new StringBuilder();
  93.             sb.append('{');
  94.             for (Entry<K,V> e : entrySet()) {
  95.                 sb.append(e.getKey() == this ? "(this Map)" : e.getKey());
  96.                 sb.append('=');
  97.                 sb.append(e.getValue() == this ? "(this Map)" : e.getValue());
  98.                 sb.append(',').append(' ');
  99.             }
  100.             return sb.append('}').toString();
  101.         }
  102.         class EntrySetView extends AbstractSet<Entry<K,V>> {
  103.             @Override
  104.             public Iterator<Entry<K, V>> iterator() {
  105.                 //me subraya el error sólo en absLowest(),
  106.                 return new SubMapEntryIterator(absLowest(), null);
  107.             }
  108.             @Override
  109.             public int size() {
  110.                 if(fromStart && toEnd){
  111.                     return m.size;
  112.                 } else {
  113.                     return size; 
  114.                 }
  115.             }        
  116.         }
  117.     }
  118.     /*------------------------------------------------------------*/    
  119.     abstract class SubMapIterator<T> implements Iterator<T> {
  120.         Entry<K,V> last;
  121.         Entry<K,V> next;
  122.         final Object fenceKey;
  123.         SubMapIterator(Entry<K,V> first, Entry<K,V> fence) {
  124.             last = null;
  125.             next = first;
  126.             fenceKey = fence == null ? new Object() : fence.key;
  127.         }
  128.         @Override
  129.         public boolean hasNext() {
  130.             return next != null && next.key != fenceKey;
  131.         }
  132.         public Entry<K,V> nextEntry() {
  133.             Entry<K,V> e = next;
  134.             next = successor(e);
  135.             last = e;
  136.             return e;
  137.         }        
  138.     }
  139.     class SubMapEntryIterator extends SubMapIterator<Entry<K,V>> {
  140.         public SubMapEntryIterator(Entry<K, V> first, Entry<K, V> fence) {
  141.             super(first, fence);
  142.         }        
  143.         @Override
  144.         public Entry<K, V> next() {
  145.             return nextEntry();
  146.         }        
  147.     }

Y no me doy cuenta de dónde está el problema.

Espero sus respuestas y Saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #20 (permalink)  
Antiguo 19/07/2018, 01:30
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
Échale un ojo a este post

https://coderanch.com/t/328104/java/...mpatible-types
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #21 (permalink)  
Antiguo 21/07/2018, 21:53
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
FuzzyLog gracias por responder, verás estuve haciendo unos cambios al código para comprobar el error en el 1er parámetro:

Código Java: 
Ver original
  1. @Override
  2.             public Iterator<Entry<K, V>> iterator() {
  3.                 Entry<K,V> e;
  4.                 if(fromStart){
  5.                     e = m.getFirstEntry();
  6.                 } else if(loInclusive){
  7.                     e = m.getCeilingEntry(lo);
  8.                 } else {
  9.                     e = m.getHigherEntry(lo);
  10.                 }
  11.                 if(e == null || tooHigh(e.getKey())){
  12.                     e = null;
  13.                 }
  14.                 //return new SubMapEntryIterator(absLowest(), null);
  15.                 // en la variable e me marca el error
  16.                 return new SubMapEntryIterator(e, null);
  17.             }

y me cambió el error a esto:

Cita:
incompatible types: java.util.Map.Entry<K#1,V#1> cannot be converted to treemapsimple.MyTreeMap.Entry<K#2,V#2>
where K#1,V#1,K#2,V#2 are type-variables:
K#1 extends Object declared in class MyTreeMap.NavigableSubMap
V#1 extends Object declared in class MyTreeMap.NavigableSubM...
No se me ocurre nada, espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #22 (permalink)  
Antiguo 22/07/2018, 04:26
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
A lo mejor problema viene de que el override del método Set<Map.Entry<K,V>> no está tan fino como debiera, pero está complicado encontrarlo porque tienes mucho código pululando por ahí.

Igual si consigues replicar el mismo problema con un código más sencillo lo entiendes mejor y encuentras la solución.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #23 (permalink)  
Antiguo 22/07/2018, 21:11
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Hey FuzzyLog gracias por responder, subí el código a github, me volvió a cambiar el error del código por unos leves cambios que le hice, acá pongo el link:

Código Subido

Después de un rato buscando la vuelta y no la encuentro, espero que me digan dónde está el error, el drama está en las clases internas NavigableSubMap, EntrySetView y las funciones absLowest() y absHighFence() para que el iterator funcione.

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #24 (permalink)  
Antiguo 23/07/2018, 03:54
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
Puedes indicar el nuevo error?
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #25 (permalink)  
Antiguo 23/07/2018, 17:24
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 733
Antigüedad: 16 años, 5 meses
Puntos: 61
Respuesta: Balanceos con Árboles Hash
Esta manera de describir problemas (link a github) y ahi descubran donde esta el error, esta malutilizando el foro, en mi opinion. Seria mas util si publicas una duda puntual, recortando el codigo si fuera necesario, para mostrar el problema que tienes.

Tal como posteas, no va a ser muy util para el resto y una de las ventajas de resolver tus problemas en un foro es que otros puedan buscar y encontrar solucion a problemas similares.

Sugiero hacer un post por problema, no un gran post con muchos problemas.
__________________
Visita mi perfil en LinkedIn
  #26 (permalink)  
Antiguo 23/07/2018, 20:09
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Bien gracias por responder, así es cómo tengo las cosas:
En el proyecto que tengo en NetBeans tengo 2 clases, la de MyTreeMap.java que está en el repositorio y una de prueba llamada Cuerpo.java.

Código Java: 
Ver original
  1. package treemapsimple;
  2. public class Cuerpo {
  3.     public static void main(String[] args) {
  4.         MyTreeMap<Integer,String>map = new MyTreeMap();
  5.         map.put(1, "Juan");
  6.         map.put(2, "Alberto");
  7.         map.put(3, "Julia");
  8.         map.put(4, "Luis");
  9.         map.put(5, "Maria");
  10.         map.put(6, "Pedro");
  11.         map.put(7, "Deborah");
  12.         map.put(8, "Nelson");
  13.         map.put(9, "Tommy");
  14.         map.put(10, "Manuela");
  15.         map.put(10, "Micaela");
  16.         map.put(6, "Sergio");
  17.         map.put(null, "Serafin");
  18.         System.out.println("primera clave: " + map.firstKey());
  19.         System.out.println("última clave: " + map.lastKey());
  20.         System.out.println("cola del mapa: " + map.tailMap(6).toString());
  21.     }    
  22. }

El error me figura en la clase MyTreeMap.java en la línea 652 subrayandome la función absLowest() y al acercar el mouse me aparece esto:

Cita:
incompatible types: Entry<K#1,V#1> cannot be converted to Entry<K#2,V#2>
where K#1,V#1,K#2,V#2 are type-variables:
K#1 extends Object declared in class MyTreeMap.NavigableSubMap
V#1 extends Object declared in class MyTreeMap.NavigableSubMap
K#2 extends Object declared in class MyTreeMap
V#2 extends Object declared in class MyTreeM...
Todo es un problema por el entrySet con los tipos de Entry, que con ayuda de FuzzyLog se reveló como las clases internas y funciones pertinentes llegar a dónde está ahora el código, pero no descubro cómo resolver este error que me da.

CalgaryCorpus me alegra que te haya interesado este post, creeme que no logro descubrir el error y eso que depuré el código y probé cambio por cambio que se me ocurriera y no funcionó, pero puedes quedarte que luego de que termine con lo de los submaps pondré en otro post diferente ya que lo tengo 2 cosas por preguntar , una que tiene que ver lo del árbol hash en la 3ra etapa que es implementando NavigableMap ya que hasta ahora esta implementado con SortedMap y para hacer andar sus funciones de forma decepcionante tienes que crear una clase interna para que en base a los parámetros que le pases en el constructor es lo que determina el funcionamiento de las funciones headMap, subMap, tailMap aunque parezca mentira, y lo otro por preguntar que tiene que ver árbol binario pero es sobre algo diferente.

En base a todo esto, espero que no queden dudas y con respecto al problema que tengo, espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #27 (permalink)  
Antiguo 24/07/2018, 03:53
Avatar de Fuzzylog  
Fecha de Ingreso: agosto-2008
Ubicación: En internet
Mensajes: 2.511
Antigüedad: 16 años, 2 meses
Puntos: 188
Respuesta: Balanceos con Árboles Hash
Revisa bien como tienes definidas las entries

private MyTreeMap.Entry<K,V> getFirstEntry() {
MyTreeMap.Entry<K,V> p = root;
if (p != null){
while(leftOf(p) != null){
p = leftOf(p);
}
}
return p;
}
private Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null){
while(rightOf(p) != null){
p = rightOf(p);
}
}
return p;
}

por ejemplo ahí hay algo que no cuadra, en un método es Entry<K,V> y en el otro MyTreeMap.Entry<K,V>

Primero revisa que hay coherencia en todos los casos (no solo el del ejempo).

Luego mira si tienes errores.
__________________
if (fuzzy && smooth) {
fuzzylog = "c00l";
return true;
}
  #28 (permalink)  
Antiguo 24/07/2018, 08:39
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 733
Antigüedad: 16 años, 5 meses
Puntos: 61
Respuesta: Balanceos con Árboles Hash
Modificar Entry por MyTreeMap.Entry no va a resolver el problema de compilacion.

Sugiero que escribas aqui el comienzo (la definicion) de las clases que estas usando, la firma del metodo que estas invocando, y la invocacion que genera el problema de compilacion, solo con eso se resuelve el problema.
__________________
Visita mi perfil en LinkedIn
  #29 (permalink)  
Antiguo 25/07/2018, 20:11
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Gracias por responder FuzzyLog y CalgaryCorpus pues los 2 tenían razón. Así cómo lo tenía nunca iba a funcionar, así que lo que hice fue poner a EntrySetView, SubMapIterator y SubMapEntryIterator como clases internas a NavigableMap para que me andara los generics y funcionó.
Lo siguiente que tuve que hacer para que el nextEntry de SubMapIterator funcionara fue hacer a la función successor como estática provocando como consecuencia que las funciones leftOf, rightOf, colorOf, setColor y parentOf también sean estáticas sólo que a éstas tuve que ponerle el comodin para que me tomara bien los generics (parece ser propio del JDK8):

Código Java: 
Ver original
  1. private static <K,V> boolean colorOf(Entry<K,V> p) {
  2.         return (p == null ? BLACK : p.color);
  3.     }
  4.     private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
  5.         return (p == null ? null: p.parent);
  6.     }
  7.     private static <K,V> void setColor(Entry<K,V> p, boolean c) {
  8.         if (p != null)
  9.             p.color = c;
  10.     }
  11.     private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
  12.         return (p == null) ? null: p.left;
  13.     }
  14.     private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
  15.         return (p == null) ? null: p.right;
  16.     }

Por úlitmo tuve que ver la congruencia pertinente para que me andarán bien todo de los submaps con el tailMap. Eso lo pueden ver en el código.

Código del TreeMap casero

Ahora seguiré probando e implementando lo que quedan de los submaps, en caso que ocurra algo, daré el grito.

Espero sus respuestas y Saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias
  #30 (permalink)  
Antiguo 29/08/2018, 20:36
Avatar de detective_jd  
Fecha de Ingreso: abril-2011
Ubicación: Salto
Mensajes: 437
Antigüedad: 13 años, 7 meses
Puntos: 6
Respuesta: Balanceos con Árboles Hash
Buenas a todos, he tenido mis cosas que hacer por eso no he escrito aquí, en fin he llegado hasta el punto de empezar a implementar las funciones de NavigableMap lo que he adaptado de nuevo es esto:

Código Java: 
Ver original
  1. NavigableSubMap(MyTreeMap<K, V> xm,
  2.                 boolean fromStart, K lo, boolean loInclusive, 
  3.                 boolean toEnd, K hi, boolean hiInclusive) {
  4.             if (!fromStart && !toEnd) {
  5.                 if(lo == null && hi == null) {
  6.                     xm.clear();
  7.                 } else if(lo != null && hi == null) {
  8.                     xm.compare(lo, lo);
  9.                 } else if(lo == null && hi != null){
  10.                     xm.compare(hi, hi);
  11.                 } else {    
  12.                     if (xm.compare(lo, hi) > 0)
  13.                         throw new IllegalArgumentException("fromKey > toKey");
  14.                 }
  15.             } else {
  16.                 if (!fromStart) // type check
  17.                     if(lo != null){
  18.                         xm.compare(lo, lo);
  19.                     } else {
  20.                         xm.clear();
  21.                     }
  22.                 if (!toEnd)
  23.                     if(hi != null){
  24.                         xm.compare(hi, hi);
  25.                     } else {
  26.                         xm.clear();
  27.                     }
  28.             }
  29.             this.m = xm;
  30.             this.lo = lo;
  31.             this.hi = hi;
  32.             this.fromStart = fromStart;
  33.             this.toEnd = toEnd;
  34.             this.loInclusive = loInclusive;
  35.             this.hiInclusive = hiInclusive;
  36.         }

Al contructor lo validé en caso de que no te salga una excepción en el subMap cuando no le pones parámetros te devolverá una estructura vacía, en caso que pongas sólo el inicio en el final ya esta definido por defecto y viceversa si podes el final te da el inicio definido por defecto.
En headMap y tailMap si no pones ningún parámetro, te devolverá una estructura vacía.

Ahora diré mis dudas, resulta que las funciones lowerKey, floorKey, lastKey y firstKey ¿en que aportan si tienes las entry de cada una? si me dijeras que es para delegar en TreeSet lo entiendo, pero es cómo su get.key.

Por otro lado no entiendo cuál es el sentido de estos iterator: descendingKeySet(), navigableKeySet() y descendingMap().

Los pollFirstEntry y pollLastEntry obtienen su respectivo elemento pero eliminándolo de la estructura ¿que utilidad tiene?

Las funciones getLowerEntry, getFloorEntry, getLastEntry y getFirstEntry funcionan de forma similar pero ¿existe una forma de simplificar estas funciones?

Aquí está el código subido:

Código casero

Espero sus respuestas y saludos.
__________________
Si te interesa, visita mi perfil de Linkedin. Gracias

Etiquetas: hash
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta


« Tema Anterior | Próximo Tema »


La zona horaria es GMT -6. Ahora son las 12:33.