Changeset 2423 in josm for trunk/src/org/openstreetmap/josm

Timestamp:

2009-11-09T23:58:58+01:00 (15 years ago)

Author:

hansendc

Message:

This fixes #3796.

The issue was that we somehow ended up with a branch node
that had no valid children. We assumed in the iterator
that any node with no content must have children, but
that was wrong.

File:

• trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (modified) (6 diffs)

trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java

@@ -17 +17 @@
 {
     public static boolean debug = false;
-    static boolean consistency_testing = false;
+    static boolean consistency_testing = true;
 
     static void abort(String s)
@@ -247 +247 @@
                 this.content = null;
             }
+            if (this.canRemove())
+                this.remove_from_parent();
             return ret;
         }
@@ -365 +367 @@
                 }
                 if (level >= NR_LEVELS-1) {
-                    out("can not split, but too deep: " + level + " size: " + content.size());
+                    if (debug)
+                        out("can not split, but too deep: " + level + " size: " + content.size());
                     return;
                 }
@@ -484 +487 @@
             return true;
         }
+        QBLevel nextSibling()
+        {
+            QBLevel next = this;
+            QBLevel sibling = next.next_sibling();
+            // Walk back up the tree to find the
+            // next sibling node.  It may be either
+            // a leaf or branch.
+            while (sibling == null) {
+                if (debug) {
+                    out("no siblings at level["+next.level+"], moving to parent");
+                    }
+                next = next.parent;
+                if (next == null) {
+                    break;
+                    }
+                sibling = next.next_sibling();
+            }
+            next = sibling;
+            return next;
+        }
         QBLevel nextContentNode()
         {
             QBLevel next = this;
-            if (this.isLeaf()) {
-                QBLevel sibling = next.next_sibling();
-                // Walk back up the tree to find the
-                // next sibling node.  It may be either
-                // a leaf or branch.
-                while (sibling == null) {
-                    if (debug) {
-                        out("no siblings at level["+next.level+"], moving to parent");
-                    }
-                    next = next.parent;
-                    if (next == null) {
-                        break;
-                    }
-                    sibling = next.next_sibling();
-                }
-                next = sibling;
-            }
+            if (this.isLeaf())
+                next = this.nextSibling();
             if (next == null)
                 return null;
-            // all branches are guaranteed to have
-            // at least one leaf.  It may not have
-            // any contents, but there *will* be a
-            // leaf.  So, walk back down the tree
+            // Walk back down the tree
             // and find the first leaf
-            while (!next.isLeaf()) {
-                if (next.hasContent() && next != this) {
+            while (next != null && !next.isLeaf()) {
+                if (next.hasContent() && next != this)
                     break;
-                }
-                if (debug) {
+                if (debug)
                     out("["+next.level+"] next node ("+next+") is a branch (content: "+next.hasContent()+"), moving down...");
-                }
+                boolean progress = false;
                 for (QBLevel child : next.children) {
-                    if (child == null) {
+                    if (child == null)
                         continue;
-                    }
                     next = child;
+                    progress = true;
                     break;
                 }
-            }
+                if (!progress) {
+                    // this should out it as not being a branch
+                    next.children = null;
+                    break;
+                }
+            }
+            // This means that there are no leaves or branches
+            // with content as children.  We must continue to
+            // search siblings.
+            if (next == this)
+                return nextSibling().nextContentNode();
             return next;
         }
@@ -784 +798 @@
             return QuadTiling.tile2LatLon(this.quad);
         }
+        void remove_from_parent()
+        {
+            if (parent == null)
+                return;
+
+            int nr_siblings = 0;
+            for (int i = 0; i < parent.children.length; i++) {
+                QBLevel sibling = parent.children[i];
+                if (sibling != null)
+                    nr_siblings++;
+                if (sibling != this)
+                    continue;
+                if (this.content != null ||
+                    this.children != null)
+                    abort("attempt to remove non-empty child");
+                parent.children[i] = null;
+                nr_siblings--;
+            }
+            if (parent.canRemove())
+                parent.remove_from_parent();
+        }
+        boolean canRemove()
+        {
+            if (content != null && content.size() > 0)
+                return false;
+            if (children != null) {
+                for (QBLevel child : children) {
+                    if (child != null)
+                        return false;
+                }
+            }
+            return true;
+        }
     }
 
@@ -1073 +1120 @@
             //    an element
             content_index--;
-            peek(); //TODO Is the call to peek() necessary?
-            current_node.content.remove(content_index);
+            T object = peek(); //TODO Is the call to peek() necessary?
+            current_node.remove_content(object);
         }
     }