sarthak sarthak - 10 days ago 9
Scala Question

Stackoverflow error in scala code

In this code I am trying to take union of two trees as follows:

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {

def union(that: TweetSet): TweetSet =
{
def unionRec(set:TweetSet,acc:TweetSet): TweetSet =
{
if (set.isEmpty)
return acc
else
return unionRec(right,unionRec(left,acc.incl(elem)))
}
unionRec(this,that)
}

def isEmpty: Boolean = false

def incl(x: Tweet): TweetSet = {
if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right)
else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x))
else this
}

}

class Empty extends TweetSet {
def isEmpty: Boolean = true
}


But when I try to execute the union method, I am getting stackOverflow error:

java.lang.StackOverflowError
at scala.collection.immutable.StringLike$class.compare(StringLike.scala:74)
at scala.collection.immutable.StringOps.compare(StringOps.scala:30)
at scala.collection.immutable.StringOps.compare(StringOps.scala:30)
at scala.math.Ordered$class.$less(Ordered.scala:76)
at scala.collection.immutable.StringOps.$less(StringOps.scala:30)
at objsets.NonEmpty.incl(TweetSet.scala:235)
at objsets.NonEmpty.incl(TweetSet.scala:236)
at objsets.NonEmpty.incl(TweetSet.scala:235)
at objsets.NonEmpty.incl(TweetSet.scala:236)
at objsets.NonEmpty.incl(TweetSet.scala:235)
at objsets.NonEmpty.incl(TweetSet.scala:235)
at objsets.NonEmpty.incl(TweetSet.scala:236)
at objsets.NonEmpty.incl(TweetSet.scala:236)
at objsets.NonEmpty.incl(TweetSet.scala:235)


Why is this happening?

Answer

For the recursion to eventually terminate, you need to make sure the tree in the first argument of unionRec sooner or later is empty. Since you always call it with left and right, your recursion never terminates.

Comments