CODEWITHSUNDEEP
javascalarecursionstack-overflow
KAs
KAs

Reputation: 1868

stackoverflowerror when processing depth-first-iteration via scala

I intend to recursively iterate all grids within a circle zone, the code below will perform depth-first-search. But after 204 stacks, java.lang.StackOverflowError will be thrown.

def geohash_circle_around_point(lat: Double, lon: Double, radius: Double) = {

  def expand_neighbors_impl(ghCenter: GeoHash, ghCur: GeoHash, buffer: collection.mutable.Set[GeoHash]): Unit = {
    // MARK: DP: check whether it's iterated already or not
    if(buffer contains ghCur)  {
      return
    }
    buffer += ghCur

    for(ghAround <- get4GeoHashAround(ghCur))  {
      if(distanceBetweenGeohash(ghCenter, ghAround) <= radius)  {
        expand_neighbors_impl(ghCenter, ghAround, buffer)
      }
    }
  }

  def get4GeoHashAround(gh: GeoHash): Array[GeoHash] = {
    Array(gh.getNorthernNeighbour, gh.getSouthernNeighbour, gh.getWesternNeighbour, gh.getEasternNeighbour)
  }

  def distanceBetweenGeohash(gh1: GeoHash, gh2: GeoHash) = {
    haversine(gh1.getBoundingBoxCenterPoint.getLatitude, gh1.getBoundingBoxCenterPoint.getLongitude, gh2.getBoundingBoxCenterPoint.getLatitude, gh2.getBoundingBoxCenterPoint.getLongitude)
  }

  val ghCenter = GeoHash.withBitPrecision(lat, lon, 40)
  val s = collection.mutable.Set[GeoHash]()
  expand_neighbors_impl(ghCenter, ghCenter, s)
  s.map(_.getBoundingBox)
}

The stacktrace is as follows:

Exception in thread "main" java.lang.StackOverflowError
  at scala.collection.mutable.HashSet.index(HashSet.scala:40)
  at scala.collection.mutable.FlatHashTable$class.findElemImpl(FlatHashTable.scala:126)
  at scala.collection.mutable.FlatHashTable$class.containsElem(FlatHashTable.scala:121)
  at scala.collection.mutable.HashSet.containsElem(HashSet.scala:40)
  at scala.collection.mutable.HashSet.contains(HashSet.scala:57)
  at Test$.Test$$expand_neighbors_impl$1(Test.scala:32)
  at Test$$anonfun$Test$$expand_neighbors_impl$1$1.apply(Test.scala:39)
  at Test$$anonfun$Test$$expand_neighbors_impl$1$1.apply(Test.scala:37)
  at scala.collection.IndexedSeqOptimized$class.foreach(IndexedSeqOptimized.scala:33)
  at scala.collection.mutable.ArrayOps$ofRef.foreach(ArrayOps.scala:186)
  at Test$.Test$$expand_neighbors_impl$1(Test.scala:37)
  at Test$$anonfun$Test$$expand_neighbors_impl$1$1.apply(Test.scala:39)
  at Test$$anonfun$Test$$expand_neighbors_impl$1$1.apply(Test.scala:37)
  at scala.collection.IndexedSeqOptimized$class.foreach(IndexedSeqOptimized.scala:33)
  at scala.collection.mutable.ArrayOps$ofRef.foreach(ArrayOps.scala:186)
  at Test$.Test$$expand_neighbors_impl$1(Test.scala:37)
....

Could anyone give some suggestions? Thanks!

P.S.

Implementation for equals and hashCode for GeoHash:

public boolean equals(Object obj) {
    if(obj == this) {
        return true;
    } else {
        if(obj instanceof GeoHash) {
            GeoHash other = (GeoHash)obj;
            if(other.significantBits == this.significantBits && other.bits == this.bits) {
                return true;
            }
        }

        return false;
    }
}

public int hashCode() {
    byte f = 17;
    int f1 = 31 * f + (int)(this.bits ^ this.bits >>> 32);
    f1 = 31 * f1 + this.significantBits;
    return f1;
}

Upvotes: 1

Views: 245

Answers (1)

Cyrille Corpet
Cyrille Corpet

Reputation: 5305

Seems like you really need more than 200 calls at 40 precision...

You might want to consider rewriting your recursion to be tail-recursive, in order to be optimized by the compiler. Here's a way to do this:

@tailrec
def expand_neighbors_impl(ghCenter: GeoHash, toGoThrough: List[GeoHash], buffer: Set[GeoHash] = Set()): Set[GeoHash] = {
  toGoThrough.headOption match {
    case None => buffer
    case Some(ghCur) =>
      if (buffer contains ghCur) {
        expand_neighbors_impl(ghCenter, toGoThrough.tail, buffer)
      }
      else {
        val neighbors = get4GeoHashAround(ghCur).filter(distanceBetweenGeohash(ghCenter, _) <= radius)
        expand_neighbors_impl(ghCenter, neighbors ++: toGoThrough, buffer + ghCur)
      }
  }
}

def expand_neighbors_impl(ghCenter: GeoHash, ghCur: GeoHash): Set[GeoHash] =
  expand_neighbors_impl(ghCenter, List(ghCur))

Besides using tail-recursion, it avoids using a mutable Set, which might give some unexpected complication.

Upvotes: 1

Related Questions