BoundingBoxGeoHashIterator (Version 1.3.0) hasNext() never returns false with some specific coordinates

[liptga]

Please see the following test class:

import ch.hsr.geohash.BoundingBox;
import ch.hsr.geohash.GeoHash;
import ch.hsr.geohash.util.BoundingBoxGeoHashIterator;
import ch.hsr.geohash.util.TwoGeoHashBoundingBox;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

import static org.hamcrest.CoreMatchers.hasItem;
import static org.hamcrest.CoreMatchers.not;
import static org.junit.Assert.assertThat;

/**
 * Created by liptak on 2016.10.21..
 */
public class GeoHashBug {
    @Test
    public void endlessIterator() {
        BoundingBox box = new BoundingBox(72.28907f, 88.62655f, -50.976562f, 170.50781f);
        BoundingBoxGeoHashIterator iterator = new BoundingBoxGeoHashIterator(
                TwoGeoHashBoundingBox.withCharacterPrecision(box, 2)
        );
        Set<GeoHash> hashes = new HashSet<>();
        while( iterator.hasNext() ) {
            GeoHash hash = iterator.next();
            assertThat("Hash has been already produced by the iterator once: " + hash, hashes, not(hasItem(hash)));
            hashes.add(hash);
        }
    }
}

I would expect, that each hash comes only once, and the iterator exits. Output:

java.lang.AssertionError: Hash has been already produced by the iterator once: 111011010000000000000000000000000000000000000000000000000000000 -> (73.125,-56.25) -> (67.5,-45.0) -> fu Expected: not a collection containing <111011010000000000000000000000000000000000000000000000000000000 -> (73.125,-56.25) -> (67.5,-45.0) -> fu> but: was <[1101110111000000000000000000000000000000000000000000000000000000 -> (90.0,56.25) -> (84.375,67.5) -> vr, 111111011000000000000000000000000000000000000000000000000000000 -> (78.75,-11.25) -> (73.125,0.0) -> gv, 111111001000000000000000000000000000000000000000000000000000000 -> (78.75,-22.5) -> (73.125,-11.25) -> gt, 111110111000000000000000000000000000000000000000000000000000000 -> (90.0,-33.75) -> (84.375,-22.5) -> gr, 111011011000000000000000000000000000000000000000000000000000000 -> (78.75,-56.25) -> (73.125,-45.0) -> fv, 111111111000000000000000000000000000000000000000000000000000000 -> (90.0,-11.25) -> (84.375,0.0) -> gz, 111111101000000000000000000000000000000000000000000000000000000 -> (90.0,-22.5) -> (84.375,-11.25) -> gx, 111011111000000000000000000000000000000000000000000000000000000 -> (90.0,-56.25) -> (84.375,-45.0) -> fz, 1111110001000000000000000000000000000000000000000000000000000000 -> (78.75,135.0) -> (73.125,146.25) -> zj, 1111010001000000000000000000000000000000000000000000000000000000 -> (78.75,90.0) -> (73.125,101.25) -> yj, 1111010011000000000000000000000000000000000000000000000000000000 -> (78.75,101.25) -> (73.125,112.5) -> ym, 1111110101000000000000000000000000000000000000000000000000000000 -> (90.0,135.0) -> (84.375,146.25) -> zp, 1111110011000000000000000000000000000000000000000000000000000000 -> (78.75,146.25) -> (73.125,157.5) -> zm, 1101110001000000000000000000000000000000000000000000000000000000 -> (78.75,45.0) -> (73.125,56.25) -> vj, 1101010001000000000000000000000000000000000000000000000000000000 -> (78.75,0.0) -> (73.125,11.25) -> uj, 1111110111000000000000000000000000000000000000000000000000000000 -> (90.0,146.25) -> (84.375,157.5) -> zr, 1111010101000000000000000000000000000000000000000000000000000000 -> (90.0,90.0) -> (84.375,101.25) -> yp, 1101110011000000000000000000000000000000000000000000000000000000 -> (78.75,56.25) -> (73.125,67.5) -> vm, 1101010011000000000000000000000000000000000000000000000000000000 -> (78.75,11.25) -> (73.125,22.5) -> um, 1111111001000000000000000000000000000000000000000000000000000000 -> (78.75,157.5) -> (73.125,168.75) -> zt, 1111010111000000000000000000000000000000000000000000000000000000 -> (90.0,101.25) -> (84.375,112.5) -> yr, 1101110101000000000000000000000000000000000000000000000000000000 -> (90.0,45.0) -> (84.375,56.25) -> vp, 1101010101000000000000000000000000000000000000000000000000000000 -> (90.0,0.0) -> (84.375,11.25) -> up, 1111111011000000000000000000000000000000000000000000000000000000 -> (78.75,168.75) -> (73.125,180.0) -> zv, 1111011001000000000000000000000000000000000000000000000000000000 -> (78.75,112.5) -> (73.125,123.75) -> yt, 1101010111000000000000000000000000000000000000000000000000000000 -> (90.0,11.25) -> (84.375,22.5) -> ur, 1111111101000000000000000000000000000000000000000000000000000000 -> (90.0,157.5) -> (84.375,168.75) -> zx, 1111011011000000000000000000000000000000000000000000000000000000 -> (78.75,123.75) -> (73.125,135.0) -> yv, 1101111001000000000000000000000000000000000000000000000000000000 -> (78.75,67.5) -> (73.125,78.75) -> vt, 1101011001000000000000000000000000000000000000000000000000000000 -> (78.75,22.5) -> (73.125,33.75) -> ut, 1111111111000000000000000000000000000000000000000000000000000000 -> (90.0,168.75) -> (84.375,180.0) -> zz, 1111011101000000000000000000000000000000000000000000000000000000 -> (90.0,112.5) -> (84.375,123.75) -> yx, 1101111011000000000000000000000000000000000000000000000000000000 -> (78.75,78.75) -> (73.125,90.0) -> vv, 1101011011000000000000000000000000000000000000000000000000000000 -> (78.75,33.75) -> (73.125,45.0) -> uv, 1111011111000000000000000000000000000000000000000000000000000000 -> (90.0,123.75) -> (84.375,135.0) -> yz, 1101111101000000000000000000000000000000000000000000000000000000 -> (90.0,67.5) -> (84.375,78.75) -> vx, 111110001000000000000000000000000000000000000000000000000000000 -> (78.75,-45.0) -> (73.125,-33.75) -> gj, 1101011101000000000000000000000000000000000000000000000000000000 -> (90.0,22.5) -> (84.375,33.75) -> ux, 1101111111000000000000000000000000000000000000000000000000000000 -> (90.0,78.75) -> (84.375,90.0) -> vz, 111110011000000000000000000000000000000000000000000000000000000 -> (78.75,-33.75) -> (73.125,-22.5) -> gm, 1101011111000000000000000000000000000000000000000000000000000000 -> (90.0,33.75) -> (84.375,45.0) -> uz, 111110101000000000000000000000000000000000000000000000000000000 -> (90.0,-45.0) -> (84.375,-33.75) -> gp, 1101010110000000000000000000000000000000000000000000000000000000 -> (84.375,11.25) -> (78.75,22.5) -> uq, 111110110000000000000000000000000000000000000000000000000000000 -> (84.375,-33.75) -> (78.75,-22.5) -> gq, 111110010000000000000000000000000000000000000000000000000000000 -> (73.125,-33.75) -> (67.5,-22.5) -> gk, 111011010000000000000000000000000000000000000000000000000000000 -> (90.0,-56.25) -> (67.5,180.0) -> fu, 111111100000000000000000000000000000000000000000000000000000000 -> (84.375,-22.5) -> (78.75,-11.25) -> gw, 111111010000000000000000000000000000000000000000000000000000000 -> (73.125,-11.25) -> (67.5,0.0) -> gu, 111111000000000000000000000000000000000000000000000000000000000 -> (73.125,-22.5) -> (67.5,-11.25) -> gs, 111011110000000000000000000000000000000000000000000000000000000 -> (84.375,-56.25) -> (78.75,-45.0) -> fy, 111111110000000000000000000000000000000000000000000000000000000 -> (84.375,-11.25) -> (78.75,0.0) -> gy, 1101110000000000000000000000000000000000000000000000000000000000 -> (73.125,45.0) -> (67.5,56.25) -> vh, 1111110100000000000000000000000000000000000000000000000000000000 -> (84.375,135.0) -> (78.75,146.25) -> zn, 1111010100000000000000000000000000000000000000000000000000000000 -> (84.375,90.0) -> (78.75,101.25) -> yn, 1111010000000000000000000000000000000000000000000000000000000000 -> (73.125,90.0) -> (67.5,101.25) -> yh, 1111110010000000000000000000000000000000000000000000000000000000 -> (73.125,146.25) -> (67.5,157.5) -> zk, 1111110000000000000000000000000000000000000000000000000000000000 -> (73.125,135.0) -> (67.5,146.25) -> zh, 1111010010000000000000000000000000000000000000000000000000000000 -> (73.125,101.25) -> (67.5,112.5) -> yk, 1101010000000000000000000000000000000000000000000000000000000000 -> (73.125,0.0) -> (67.5,11.25) -> uh, 1101110010000000000000000000000000000000000000000000000000000000 -> (73.125,56.25) -> (67.5,67.5) -> vk, 1111110110000000000000000000000000000000000000000000000000000000 -> (84.375,146.25) -> (78.75,157.5) -> zq, 1111010110000000000000000000000000000000000000000000000000000000 -> (84.375,101.25) -> (78.75,112.5) -> yq, 1101010010000000000000000000000000000000000000000000000000000000 -> (73.125,11.25) -> (67.5,22.5) -> uk, 1101110100000000000000000000000000000000000000000000000000000000 -> (84.375,45.0) -> (78.75,56.25) -> vn, 1111111000000000000000000000000000000000000000000000000000000000 -> (73.125,157.5) -> (67.5,168.75) -> zs, 1111011000000000000000000000000000000000000000000000000000000000 -> (73.125,112.5) -> (67.5,123.75) -> ys, 1101010100000000000000000000000000000000000000000000000000000000 -> (84.375,0.0) -> (78.75,11.25) -> un, 1101110110000000000000000000000000000000000000000000000000000000 -> (84.375,56.25) -> (78.75,67.5) -> vq, 1111111010000000000000000000000000000000000000000000000000000000 -> (73.125,168.75) -> (67.5,180.0) -> zu, 1111011010000000000000000000000000000000000000000000000000000000 -> (73.125,123.75) -> (67.5,135.0) -> yu, 1101111000000000000000000000000000000000000000000000000000000000 -> (73.125,67.5) -> (67.5,78.75) -> vs, 1111111100000000000000000000000000000000000000000000000000000000 -> (84.375,157.5) -> (78.75,168.75) -> zw, 1111011100000000000000000000000000000000000000000000000000000000 -> (84.375,112.5) -> (78.75,123.75) -> yw, 1101011000000000000000000000000000000000000000000000000000000000 -> (73.125,22.5) -> (67.5,33.75) -> us, 1101111010000000000000000000000000000000000000000000000000000000 -> (73.125,78.75) -> (67.5,90.0) -> vu, 1111111110000000000000000000000000000000000000000000000000000000 -> (84.375,168.75) -> (78.75,180.0) -> zy, 1111011110000000000000000000000000000000000000000000000000000000 -> (84.375,123.75) -> (78.75,135.0) -> yy, 1101011010000000000000000000000000000000000000000000000000000000 -> (73.125,33.75) -> (67.5,45.0) -> uu, 1101111100000000000000000000000000000000000000000000000000000000 -> (84.375,67.5) -> (78.75,78.75) -> vw, 111110000000000000000000000000000000000000000000000000000000000 -> (73.125,-45.0) -> (67.5,-33.75) -> gh, 1101011100000000000000000000000000000000000000000000000000000000 -> (84.375,22.5) -> (78.75,33.75) -> uw, 1101111110000000000000000000000000000000000000000000000000000000 -> (84.375,78.75) -> (78.75,90.0) -> vy, 1101011110000000000000000000000000000000000000000000000000000000 -> (84.375,33.75) -> (78.75,45.0) -> uy, 111110100000000000000000000000000000000000000000000000000000000 -> (84.375,-45.0) -> (78.75,-33.75) -> gn]>

at org.hamcrest.MatcherAssert.assertThat(MatcherAssert.java:20) at org.junit.Assert.assertThat(Assert.java:956) at xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx.GeoHashBug.endlessIterator(GeoHashBug.java:29) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:498) at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50) at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12) at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47) at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17) at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325) at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78) at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57) at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290) at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71) at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288) at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58) at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268) at org.junit.runners.ParentRunner.run(ParentRunner.java:363) at org.junit.runner.JUnitCore.run(JUnitCore.java:137) at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:117) at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:42) at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:262) at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:84) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:498) at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

Process finished with exit code 255

[kungfoo]

Hmm, that code I merged from a contributor, but honestly I find it quite hard right now to figure out what it does and why it does it in a certain way. I'll look into it.

[liptga]

I also tried to debug it, but I did not know the code, and a workaround if I stop by the first "already known" element worked well. So I just used my workaround. But definitely it would be interesting to understand why this happens.

[kungfoo]

I could internalize the Set of already produced hashes into the iterator and then stop producing new values as soon as it loops, but I'd rather understand why it loops. :)

[liptga]

Yeah, I know. I had to go to the next bug in our software, so there was no time anymore for that. But it was funny, since we collected the hashes in a collection and then we have got GC limit overhead OOM in production :)