0

I am trying to take union of two trees using the union method. For the purposes of checking the code I added the print statements inside the method. But the print of acc shows that it is not changing with the recrsion. I do not understand why is this happening. Can someone please explain.

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
        {
          acc.foreach(x=> println(x))
          println("####################")
          set.foreach(x=>println(x))
          println("####################")
          unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))
          return acc
        }
      }
      unionRec(this,that)
    }

    def takeLeft: TweetSet =
    {
      return left
    }

    def takeRight: TweetSet =
    {
      return right
    }
    def rootTweet: Tweet =
    {
      return elem
    }
  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
  }
  def isEmpty: Boolean = false
  def foreach(f: Tweet => Unit): Unit = {
    f(elem)
    left.foreach(f)
    right.foreach(f)
  }
}
class Empty extends TweetSet {
 def isEmpty: Boolean = true
}
sarthak
  • 774
  • 1
  • 11
  • 27

1 Answers1

2

You are doing the exact same mistake as you did in your last question (Adding an element to a tree in scala). You are throwing away the result of your unionRec-call. Remember that TweetSet is immutable, so acc will never change!

These two lines:

unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))
return acc

Has to be changed to this:

return unionRec(set.takeRight,unionRec(set.takeLeft,acc.incl(set.rootTweet)))
Community
  • 1
  • 1
marstran
  • 26,413
  • 5
  • 61
  • 67
  • I did that initially, it also gave the same result, but for each iteration I am passing an `acc` which includes 1 extra element. But when I print the `acc` as shown in the method, in all the iterations I see the value of acc unchanged. This should not happen – sarthak Nov 25 '16 at 19:58
  • I just ran your code with the change, and it worked. – marstran Nov 25 '16 at 21:02
  • Did you try to just print the result of the `union`-function instead of printing `acc` again and again? – marstran Nov 25 '16 at 21:23
  • I guess your problem must be somewhere else than the code you posted then, because that's the only mistake I can see in this code (and that mistake causes exactly the result you get). – marstran Nov 25 '16 at 21:34