week03 progfun solution

TweetSet.scala

package objsets

import common._
import TweetReader._

/**
 * A class to represent tweets.
 */
class Tweet(val user: String, val text: String, val retweets: Int) {
  override def toString: String =
    "User: " + user + "\n" +
    "Text: " + text + " [" + retweets + "]"
}

abstract class TweetSet {

  /**
   * This method takes a predicate and returns a subset of all the elements
   * in the original set for which the predicate is true.
   *
   * Question: Can we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def filter(p: Tweet => Boolean): TweetSet = {
    filterAcc(p, new Empty)
  }

  /**
   * This is a helper method for `filter` that propagetes the accumulated tweets.
   */
  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet

  /**
   * Returns a new `TweetSet` that is the union of `TweetSet`s `this` and `that`.
   *
   * Question: Should we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def union(that: TweetSet): TweetSet = ???

  /**
   * Returns the tweet from this set which has the greatest retweet count.
   *
   * Calling `mostRetweeted` on an empty set should throw an exception of
   * type `java.util.NoSuchElementException`.
   *
   * Question: Should we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
  def mostRetweeted: Tweet = ???

  /**
   * Returns a list containing all tweets of this set, sorted by retweet count
   * in descending order. In other words, the head of the resulting list should
   * have the highest retweet count.
   *
   * Hint: the method `remove` on TweetSet will be very useful.
   * Question: Should we implment this method here, or should it remain abstract
   * and be implemented in the subclasses?
   */
//  def descendingByRetweet: TweetList = ???


  def descendingByRetweet: TweetList = {

    def orderedTweets(tweetSet: TweetSet, tweetList: TweetList): TweetList = {
      val bigger = tweetSet.mostRetweeted
      println(bigger)
      if(bigger == null) tweetList
      else orderedTweets(tweetSet.remove(bigger), new Cons(bigger, tweetList))
    }

    def reverse(tweetList: TweetList): TweetList = {
      def toList(lst: List[Tweet], tweetList: TweetList): List[Tweet] =
        if (tweetList.isEmpty) lst else toList(tweetList.head :: lst, tweetList.tail)

      def toTweetList(lst: List[Tweet], tweetList: TweetList): TweetList =
        if (lst.isEmpty) tweetList else toTweetList(lst.tail, new Cons(lst.head, tweetList))

      toTweetList(toList(List[Tweet](), tweetList).reverse, Nil)
    }

    reverse(orderedTweets(this, Nil))
  }


  /**
   * The following methods are already implemented
   */

  /**
   * Returns a new `TweetSet` which contains all elements of this set, and the
   * the new element `tweet` in case it does not already exist in this set.
   *
   * If `this.contains(tweet)`, the current set is returned.
   */
  def incl(tweet: Tweet): TweetSet

  /**
   * Returns a new `TweetSet` which excludes `tweet`.
   */
  def remove(tweet: Tweet): TweetSet

  /**
   * Tests if `tweet` exists in this `TweetSet`.
   */
  def contains(tweet: Tweet): Boolean

  /**
   * This method takes a function and applies it to every element in the set.
   */
  def foreach(f: Tweet => Unit): Unit
}

class Empty extends TweetSet {

  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = acc

  override def union(that: TweetSet): TweetSet = that

  override def mostRetweeted: Tweet = null

  /**
   * The following methods are already implemented
   */

  def contains(tweet: Tweet): Boolean = false

  def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty)

  def remove(tweet: Tweet): TweetSet = this

  def foreach(f: Tweet => Unit): Unit = ()
}

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

  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = {
    def maybeInclude(p: Tweet => Boolean, acc: TweetSet): TweetSet =
      if (p(elem)) acc.incl(elem) else acc

    maybeInclude(
      p,
      left.filterAcc(p,
        right.filterAcc(p, acc))
    )
  }

  override def union(that: TweetSet): TweetSet = {
    left.union(right.union(that.incl(elem)))
  }

  override def mostRetweeted: Tweet = {
    val leftMax = left.mostRetweeted
    val rightMax = right.mostRetweeted

    def retweets(tweet: Tweet): Int = if (tweet == null) -1 else tweet.retweets

    if(elem.retweets > retweets(leftMax ) && elem.retweets > retweets(rightMax)) this.elem
    else if(retweets(leftMax) > retweets(rightMax)) leftMax
    else rightMax
  }

  /**
   * The following methods are already implemented
   */

  def contains(x: Tweet): Boolean =
    if (x.text < elem.text) left.contains(x)
    else if (elem.text < x.text) right.contains(x)
    else true

  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 remove(tw: Tweet): TweetSet =
    if (tw.text < elem.text) new NonEmpty(elem, left.remove(tw), right)
    else if (elem.text < tw.text) new NonEmpty(elem, left, right.remove(tw))
    else left.union(right)

  def foreach(f: Tweet => Unit): Unit = {
    f(elem)
    left.foreach(f)
    right.foreach(f)
  }
}

trait TweetList {
  def head: Tweet
  def tail: TweetList
  def isEmpty: Boolean
  def foreach(f: Tweet => Unit): Unit =
    if (!isEmpty) {
      f(head)
      tail.foreach(f)
    }
}

object Nil extends TweetList {
  def head = throw new java.util.NoSuchElementException("head of EmptyList")
  def tail = throw new java.util.NoSuchElementException("tail of EmptyList")
  def isEmpty = true
}

class Cons(val head: Tweet, val tail: TweetList) extends TweetList {
  def isEmpty = false
}


object GoogleVsApple {
  val google = List("android", "Android", "galaxy", "Galaxy", "nexus", "Nexus")
  val apple = List("ios", "iOS", "iphone", "iPhone", "ipad", "iPad")

  def containsAny(words: List[String], text: String): Boolean = {
    words.filter((word: String) => text.contains(word)).length != 0
  }

  lazy val googleTweets: TweetSet = TweetReader.allTweets.filter((t: Tweet) => containsAny(google, t.text))
  lazy val appleTweets: TweetSet = TweetReader.allTweets.filter((t: Tweet) => containsAny(apple, t.text))

  /**
   * A list of all tweets mentioning a keyword from either apple or google,
   * sorted by the number of retweets.
   */
  lazy val trending: TweetList = googleTweets.union(appleTweets).descendingByRetweet
}

object Main extends App {
  // Print the trending tweets
  GoogleVsApple.trending foreach println
}