Repository: opencubicchunks/cubicchunks
Issue: Cube/Column inconsistency... again

This issue is back, again. Another instance of issue similar to #103, now failing a much earlier sanity check.

Crash report: 
[crash-2017-07-13_17.44.43-server.txt](https://github.com/OpenCubicChunks/CubicChunks/files/1149037/crash-2017-07-13_17.44.43-server.txt)


Changed files:
src/main/java/cubicchunks/world/cube/Cube.java, src/test/java/cubicchunks/TestXYZMap.java, src/main/java/cubicchunks/util/XYZMap.java, src/main/java/cubicchunks/world/column/CubeMap.java

diff --git a/src/main/java/cubicchunks/util/XYZMap.java b/src/main/java/cubicchunks/util/XYZMap.java
index c02de1cc..bd4cc5db 100644
--- a/src/main/java/cubicchunks/util/XYZMap.java
+++ b/src/main/java/cubicchunks/util/XYZMap.java
@@ -25,17 +25,14 @@ package cubicchunks.util;
 
 import mcp.MethodsReturnNonnullByDefault;
 
-import java.util.ArrayList;
 import java.util.Iterator;
-import java.util.List;
 
 import javax.annotation.Nonnull;
 import javax.annotation.Nullable;
 import javax.annotation.ParametersAreNonnullByDefault;
 
 /**
- * Hash table implementation for objects in a 3-dimensional cartesian coordinate
- * system.
+ * Hash table implementation for objects in a 3-dimensional cartesian coordinate system.
  *
  * @param <T> class of the objects to be contained in this map
  *
@@ -50,25 +47,24 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
      */
     private static final int HASH_SEED = 1183822147;
 
+
     /**
      * backing array containing all elements of this map
      */
     @Nonnull private XYZAddressable[] buckets;
-    @Nonnull private int[] pointers;
+
     /**
      * the current number of elements in this map
      */
-    private int size = 0;
+    private int size;
 
     /**
-     * the maximum permissible load of the backing array, after reaching it the
-     * array will be resized
+     * the maximum permissible load of the backing array, after reaching it the array will be resized
      */
     private float loadFactor;
 
     /**
-     * the load threshold of the backing array, after reaching it the array will
-     * be resized
+     * the load threshold of the backing array, after reaching it the array will be resized
      */
     private int loadThreshold;
 
@@ -77,9 +73,10 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
      */
     private int mask;
 
+
     /**
-     * Creates a new XYZMap with the given load factor and initial capacity. The
-     * map will automatically grow if the specified load is surpassed.
+     * Creates a new XYZMap with the given load factor and initial capacity. The map will automatically grow if
+     * the specified load is surpassed.
      *
      * @param loadFactor the load factor
      * @param capacity the initial capacity
@@ -97,11 +94,11 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
             tCapacity <<= 1;
         }
         this.buckets = new XYZAddressable[tCapacity];
-        this.pointers = new int[tCapacity];
 
         this.refreshFields();
     }
 
+
     /**
      * Returns the number of elements in this map
      *
@@ -111,6 +108,7 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
         return this.size;
     }
 
+
     /**
      * Computes a 32b hash based on the given coordinates.
      *
@@ -132,65 +130,69 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
     }
 
     /**
-     * Computes the desired pointer index for the given coordinates, based on
-     * the map's current capacity.
+     * Computes the desired bucket's index for the given coordinates, based on the map's current capacity.
      *
      * @param x the x-coordinate
      * @param y the y-coordinate
      * @param z the z-coordinate
      *
-     * @return the desired pointer index for the given coordinates
+     * @return the desired bucket's index for the given coordinates
      */
-    private int getPointerIndex(int x, int y, int z) {
+    private int getIndex(int x, int y, int z) {
         return hash(x, y, z) & this.mask;
     }
 
     /**
-     * Computes the next index to the right of the given index, wrapping around
-     * if necessary.
+     * Computes the next index to the right of the given index, wrapping around if necessary.
      *
      * @param index the previous index
      *
      * @return the next index
      */
-    private int getNextPointerIndex(int pointerIndex) {
-        return ++pointerIndex & this.mask;
+    private int getNextIndex(int index) {
+        return (index + 1) & this.mask;
     }
 
+
     /**
-     * Associates the given value with its xyz-coordinates. If the map
-     * previously contained a mapping for these coordinates, the old value is
-     * replaced.
+     * Associates the given value with its xyz-coordinates. If the map previously contained a mapping for these
+     * coordinates, the old value is replaced.
      *
      * @param value value to be associated with its coordinates
      *
-     * @return the previous value associated with the given value's coordinates
-     *         or null if no such value exists
+     * @return the previous value associated with the given value's coordinates or null if no such value exists
      */
-    @Nullable
-    @SuppressWarnings("unchecked")
+    @Nullable @SuppressWarnings("unchecked")
     public T put(T value) {
+
         int x = value.getX();
         int y = value.getY();
         int z = value.getZ();
-        int pointerIndex = this.getPointerIndex(x, y, z);
-        int index = pointers[pointerIndex];
+        int index = getIndex(x, y, z);
 
-        while (index != 0) {
-            XYZAddressable bucket = this.buckets[index];
+        // find the closest empty space or the element to be replaced
+        XYZAddressable bucket = this.buckets[index];
+        while (bucket != null) {
+
+            // If there exists an element at the given element's position, overwrite it.
             if (bucket.getX() == x && bucket.getY() == y && bucket.getZ() == z) {
                 this.buckets[index] = value;
                 return (T) bucket;
             }
-            pointerIndex = this.getNextPointerIndex(pointerIndex);
-            index = pointers[pointerIndex];
+
+            index = getNextIndex(index);
+            bucket = this.buckets[index];
         }
-        this.buckets[++size] = value;
-        pointers[pointerIndex] = size;
+
+        // Insert the element into the empty bucket.
+        this.buckets[index] = value;
 
         // If the load threshold has been reached, increase the map's size.
-        if (this.size > this.loadThreshold)
+        ++this.size;
+        if (this.size > this.loadThreshold) {
             grow();
+        }
+
         return null;
     }
 
@@ -201,28 +203,26 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
      * @param y the y-coordinate
      * @param z the z-coordinate
      *
-     * @return the entry associated with the specified coordinates or null if no
-     *         such entry exists
+     * @return the entry associated with the specified coordinates or null if no such entry exists
      */
-    @Nullable
-    @SuppressWarnings("unchecked")
+    @Nullable @SuppressWarnings("unchecked")
     public T remove(int x, int y, int z) {
 
-        int pointerIndex = this.getPointerIndex(x, y, z);
-        int index = pointers[pointerIndex];
+        int index = getIndex(x, y, z);
 
-        // Search for the element. Only the buckets from the element's supposed
-        // index up to the next free slot must
+        // Search for the element. Only the buckets from the element's supposed index up to the next free slot must
         // be checked.
-        while (index != 0) {
-            XYZAddressable bucket = this.buckets[index];
+        XYZAddressable bucket = this.buckets[index];
+        while (bucket != null) {
+
             // If the correct bucket was found, remove it.
             if (bucket.getX() == x && bucket.getY() == y && bucket.getZ() == z) {
-                this.collapseBucket(pointerIndex, index);
+                this.collapseBucket(index);
                 return (T) bucket;
             }
-            pointerIndex = this.getNextPointerIndex(pointerIndex);
-            index = pointers[pointerIndex];
+
+            index = getNextIndex(index);
+            bucket = this.buckets[index];
         }
 
         // nothing was removed
@@ -230,45 +230,41 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
     }
 
     /**
-     * Removes and returns the given value from this map. More specifically,
-     * removes the entry whose xyz-coordinates equal the given value's
-     * coordinates.
+     * Removes and returns the given value from this map. More specifically, removes the entry whose xyz-coordinates
+     * equal the given value's coordinates.
      *
      * @param value the value to be removed
      *
-     * @return the entry associated with the given value's coordinates or null
-     *         if no such entry exists
+     * @return the entry associated with the given value's coordinates or null if no such entry exists
      */
-    @Nullable
-    public T remove(T value) {
+    @Nullable public T remove(T value) {
         return this.remove(value.getX(), value.getY(), value.getZ());
     }
 
     /**
-     * Returns the value associated with the given coordinates or null if no
-     * such value exists.
+     * Returns the value associated with the given coordinates or null if no such value exists.
      *
      * @param x the x-coordinate
      * @param y the y-coordinate
      * @param z the z-coordinate
      *
-     * @return the entry associated with the specified coordinates or null if no
-     *         such value exists
+     * @return the entry associated with the specified coordinates or null if no such value exists
      */
-    @Nullable
-    @SuppressWarnings("unchecked")
+    @Nullable @SuppressWarnings("unchecked")
     public T get(int x, int y, int z) {
-        int pointerIndex = this.getPointerIndex(x, y, z);
-        int index = pointers[pointerIndex];
 
-        while (index != 0) {
-            XYZAddressable bucket = this.buckets[index];
+        int index = getIndex(x, y, z);
+
+        XYZAddressable bucket = this.buckets[index];
+        while (bucket != null) {
+
             // If the correct bucket was found, return it.
             if (bucket.getX() == x && bucket.getY() == y && bucket.getZ() == z) {
                 return (T) bucket;
             }
-            pointerIndex = this.getNextPointerIndex(pointerIndex);
-            index = pointers[pointerIndex];
+
+            index = getNextIndex(index);
+            bucket = this.buckets[index];
         }
 
         // nothing was found
@@ -276,28 +272,28 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
     }
 
     /**
-     * Returns true if there exists an entry associated with the given
-     * xyz-coordinates in this map.
+     * Returns true if there exists an entry associated with the given xyz-coordinates in this map.
      *
      * @param x the x-coordinate
      * @param y the z-coordinate
      * @param z the y-coordinate
      *
-     * @return true if there exists an entry associated with the given
-     *         coordinates in this map
+     * @return true if there exists an entry associated with the given coordinates in this map
      */
     public boolean contains(int x, int y, int z) {
-        int pointerIndex = this.getPointerIndex(x, y, z);
-        int index = pointers[pointerIndex];
 
-        while (index != 0) {
-            XYZAddressable bucket = this.buckets[index];
-            // If the correct bucket was found, return it.
+        int index = getIndex(x, y, z);
+
+        XYZAddressable bucket = this.buckets[index];
+        while (bucket != null) {
+
+            // If the correct bucket was found, return true.
             if (bucket.getX() == x && bucket.getY() == y && bucket.getZ() == z) {
                 return true;
             }
-            pointerIndex = this.getNextPointerIndex(pointerIndex);
-            index = pointers[pointerIndex];
+
+            index = getNextIndex(index);
+            bucket = this.buckets[index];
         }
 
         // nothing was found
@@ -305,9 +301,8 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
     }
 
     /**
-     * Returns true if the given value is contained within this map. More
-     * specifically, returns true if there exists an entry in this map whose
-     * xyz-coordinates equal the given value's coordinates.
+     * Returns true if the given value is contained within this map. More specifically, returns true if there exists
+     * an entry in this map whose xyz-coordinates equal the given value's coordinates.
      *
      * @param value the value
      *
@@ -318,120 +313,132 @@ public class XYZMap<T extends XYZAddressable> implements Iterable<T> {
     }
 
     /**
-     * Doubles the size of the backing array and redistributes all contained
-     * values accordingly.
+     * Doubles the size of the backing array and redistributes all contained values accordingly.
      */
     private void grow() {
-        int newLength = this.buckets.length * 2;
-        this.mask = newLength - 1;
-        XYZAddressable[] newBuckets = new XYZAddressable[newLength];
-        int[] newPointers = new int[newLength];
-        for (int i = 1; i <= size; i++) {
-            XYZAddressable bucket = buckets[i];
-            newBuckets[i] = bucket;
-            int pointerIndex = this.getPointerIndex(bucket.getX(), bucket.getY(), bucket.getZ());
-            while (newPointers[pointerIndex] != 0)
-                pointerIndex = this.getNextPointerIndex(pointerIndex);
-            newPointers[pointerIndex] = i;
+
+        XYZAddressable[] oldBuckets = this.buckets;
+
+        // double the size!
+        this.buckets = new XYZAddressable[this.buckets.length * 2];
+        this.refreshFields();
+
+        // Move the old entries to the new array.
+        for (XYZAddressable oldBucket : oldBuckets) {
+
+            // Skip empty buckets.
+            if (oldBucket == null) {
+                continue;
+            }
+
+            // Get the desired index of the old bucket and insert it into the first available slot.
+            int index = getIndex(oldBucket.getX(), oldBucket.getY(), oldBucket.getZ());
+            XYZAddressable bucket = this.buckets[index];
+            while (bucket != null) {
+                bucket = this.buckets[index = getNextIndex(index)];
+            }
+            this.buckets[index] = oldBucket;
         }
-        buckets = newBuckets;
-        pointers = newPointers;
-        loadThreshold = (int) (newLength * this.loadFactor) - 1;
     }
 
     /**
-     * Removes the value contained at the given index by shifting suitable
-     * values on its right to the left.
-     * 
-     * @param index
+     * Removes the value contained at the given index by shifting suitable values on its right to the left.
      *
-     * @param holePointerIndex the index of the ponter to be collapsed
-     * @param holeIndex an index of the bucket to be collapsed
+     * @param hole the index of the bucket to be collapsed
      */
-    private void collapseBucket(final int holePointerIndex, final int holeIndex) {
-        final int lastElement = size;
-        final int oldLastPointerIndex = getElementPointerIndex(lastElement);
+    private void collapseBucket(int hole) {
 
-        List<XYZAddressable> nextPointersBuckets = new ArrayList<XYZAddressable>(10);
-        List<Integer> nextBucketIndexes = new ArrayList<Integer>(10);
+        // This method must not be called on empty buckets.
+        assert this.buckets[hole] != null;
+        --this.size;
 
-        this.pointers[oldLastPointerIndex] = holeIndex;
-        this.pointers[holePointerIndex] = 0;
+        int currentIndex = hole;
+        while (true) {
+            currentIndex = getNextIndex(currentIndex);
 
-        int pointerIndex = this.getNextPointerIndex(holePointerIndex);
-        int index = pointers[pointerIndex];
-        while (index != 0) {
-            XYZAddressable bucket = this.buckets[index];
-            nextPointersBuckets.add(bucket);
-            nextBucketIndexes.add(index);
-            pointers[pointerIndex] = 0;
-            pointerIndex = this.getNextPointerIndex(pointerIndex);
-            index = pointers[pointerIndex];
-        }
-
-        this.buckets[holeIndex] = this.buckets[lastElement];
-        size--;
-
-        for (int i = 0; i < nextPointersBuckets.size(); i++) {
-            XYZAddressable bucket = nextPointersBuckets.get(i);
-            int x = bucket.getX();
-            int y = bucket.getY();
-            int z = bucket.getZ();
-            int newBucketPointerIndex = this.getPointerIndex(x, y, z);
-            int newIndex = pointers[newBucketPointerIndex];
-            while (newIndex != 0) {
-                newBucketPointerIndex = this.getNextPointerIndex(newBucketPointerIndex);
-                newIndex = pointers[newBucketPointerIndex];
+            // If there exists no element at the given index, there is nothing to fill the hole with.
+            XYZAddressable bucket = this.buckets[currentIndex];
+            if (bucket == null) {
+                this.buckets[hole] = null;
+                return;
             }
-            pointers[newBucketPointerIndex] = nextBucketIndexes.get(i);
-        }
 
-    }
+            // If the hole lies to the left of the currentIndex and to the right of the targetIndex, move the current
+            // element. These if conditions are necessary due to the bucket array wrapping around.
+            int targetIndex = getIndex(bucket.getX(), bucket.getY(), bucket.getZ());
+
+            // normal
+            if (hole < currentIndex) {
+                if (targetIndex <= hole || currentIndex < targetIndex) {
+                    this.buckets[hole] = bucket;
+                    hole = currentIndex;
+                }
+            }
 
-    private int getElementPointerIndex(int index) {
-        XYZAddressable lastElement = this.buckets[index];
-        int pointerIndex = this.getPointerIndex(lastElement.getX(), lastElement.getY(), lastElement.getZ());
-        while (pointers[pointerIndex] != index) {
-            pointerIndex = this.getNextPointerIndex(pointerIndex);
+            // wrap around!
+            else {
+                if (hole >= targetIndex && targetIndex > currentIndex) {
+                    this.buckets[hole] = bucket;
+                    hole = currentIndex;
+                }
+            }
         }
-        return pointerIndex;
     }
 
     /**
-     * Updates the load threshold and the index mask based on the backing
-     * array's current size.
+     * Updates the load threshold and the index mask based on the backing array's current size.
      */
     private void refreshFields() {
         // we need that 1 extra space, make shore it will be there
-        this.loadThreshold = (int) (this.buckets.length * this.loadFactor) - 1;
+        this.loadThreshold = Math.min(this.buckets.length - 1, (int) (this.buckets.length * this.loadFactor));
         this.mask = this.buckets.length - 1;
     }
 
-    // Interface: Iterable<T>
-    // ------------------------------------------------------------------------------------------
+
+    // Interface: Iterable<T> ------------------------------------------------------------------------------------------
 
     public Iterator<T> iterator() {
         return new Iterator<T>() {
-
-            int at = 1;
+            int at = -1;
+            int next = -1;
 
             @Override
             public boolean hasNext() {
-                return at <= size;
+                if (next > at) {
+                    return true;
+                }
+                for (next++; next < buckets.length; next++) {
+                    if (buckets[next] != null) {
+                        return true;
+                    }
+                }
+                return false;
             }
 
-            @Nullable
-            @Override
+            @Nullable @Override
             @SuppressWarnings("unchecked")
             public T next() {
-                return (T) buckets[at++];
+                if (next > at) {
+                    at = next;
+                    return (T) buckets[at];
+                }
+                for (next++; next < buckets.length; next++) {
+                    if (buckets[next] != null) {
+                        at = next;
+                        return (T) buckets[at];
+                    }
+                }
+                return null;
             }
 
+            //TODO: WARNING: risk of iterating over the same item more than once if this is used
+            //               do to items wrapping back around form the front of the buckets array
             @Override
             public void remove() {
-                int pointerIndex = getElementPointerIndex(--at);
-                collapseBucket(pointerIndex, at);
+                collapseBucket(at);
+                next = at = at - 1; // There could be a new item in the removed bucket
             }
         };
     }
+
 }
diff --git a/src/main/java/cubicchunks/world/column/CubeMap.java b/src/main/java/cubicchunks/world/column/CubeMap.java
index 95c2c03e..59d89660 100644
--- a/src/main/java/cubicchunks/world/column/CubeMap.java
+++ b/src/main/java/cubicchunks/world/column/CubeMap.java
@@ -69,9 +69,7 @@ public class CubeMap implements Iterable<Cube> {
     public void put(Cube cube) {
         int searchIndex = binarySearch(cube.getY());
         if (this.contains(cube.getY(), searchIndex)) {
-            Cube existing = cubes.get(searchIndex);
-            throw new IllegalArgumentException("Cube at " + cube.getY() + " already exists! "+
-                    "Existing "+existing+"  Attempt to add "+cube);
+            throw new IllegalArgumentException("Cube at " + cube.getY() + " already exists!");
         }
         cubes.add(searchIndex, cube);
     }
diff --git a/src/main/java/cubicchunks/world/cube/Cube.java b/src/main/java/cubicchunks/world/cube/Cube.java
index 4ca76636..847a52af 100644
--- a/src/main/java/cubicchunks/world/cube/Cube.java
+++ b/src/main/java/cubicchunks/world/cube/Cube.java
@@ -732,9 +732,4 @@ public class Cube implements XYZAddressable {
     public boolean isCubeLoaded() {
         return this.isCubeLoaded;
     }
-    
-    @Override
-    public String toString(){
-        return "cube"+"{"+getX()+";"+getY()+";"+getZ()+"}";
-    }
 }
diff --git a/src/test/java/cubicchunks/TestXYZMap.java b/src/test/java/cubicchunks/TestXYZMap.java
index d675d2e7..54cb4b91 100644
--- a/src/test/java/cubicchunks/TestXYZMap.java
+++ b/src/test/java/cubicchunks/TestXYZMap.java
@@ -26,7 +26,6 @@ package cubicchunks;
 import static org.hamcrest.Matchers.empty;
 import static org.hamcrest.Matchers.hasItem;
 import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertThat;
 import static org.junit.Assert.assertTrue;
@@ -34,13 +33,12 @@ import static org.junit.Assert.assertTrue;
 import cubicchunks.util.XYZAddressable;
 import cubicchunks.util.XYZMap;
 import mcp.MethodsReturnNonnullByDefault;
-
 import org.junit.Test;
 
 import java.util.HashSet;
-import java.util.Iterator;
 import java.util.Random;
 import java.util.Set;
+
 import javax.annotation.Nullable;
 import javax.annotation.ParametersAreNonnullByDefault;
 
@@ -120,7 +118,7 @@ public class TestXYZMap {
             map.put(values[i]);
 
             for (int j = 0; j <= i; ++j) {
-                assertTrue(map.contains(values[j].getX(), values[j].getY(), values[j].getZ()));
+                assertTrue(map.contains(values[i].getX(), values[i].getY(), values[i].getZ()));
             }
         }
     }
@@ -140,19 +138,6 @@ public class TestXYZMap {
             }
         }
     }
-    
-    @Test
-    public void testRemove() {
-        XYZMap<XYZAddressable> map = new XYZMap<>(0.75f, 10);
-        //set seed so that tests are predictable
-        Random rand = new Random(42);
-        int maxPuts = 500;
-        Addressable[] values = new Addressable[maxPuts];
-        testPutRandom(map, rand, maxPuts, values);
-        map.remove(values[maxPuts/2]);
-        assertTrue(!map.contains(values[maxPuts/2]));
-    }
-
 
     @Test
     public void testIterator() {
@@ -163,27 +148,15 @@ public class TestXYZMap {
         for (int i = 0; i < maxPut; i++) {
             Addressable newElement = new Addressable(rand.nextInt(), rand.nextInt(), rand.nextInt(), String.valueOf(i));
             map.put(newElement);
-            assertTrue(map.contains(newElement));
             allElements.add(newElement);
         }
         for (XYZAddressable element : map) {
-            assertTrue(map.contains(element));
             assertThat(allElements, hasItem(element));
             allElements.remove(element);
         }
         assertThat(allElements, empty());
-        Iterator<XYZAddressable> it = map.iterator();
-        while(it.hasNext()){
-            XYZAddressable xyza = it.next();
-            assertNotNull(xyza);
-            assertTrue(map.contains(xyza));
-            int sizeBefore = map.getSize();
-            it.remove();
-            assertTrue(!map.contains(xyza));
-            assertEquals(map.getSize(),sizeBefore-1);
-        }
     }
-    
+
     /**
      * Simple implementation of Addressable for testing, equal only if id of them is equal
      */