ch8-Classes.asciidoc

1) We’re working on a gaming site, and need to track popular consoles like the Xbox Two and Playstation Five (I’m planning for the future here).

a) Create a console class that can track the make, model, debut date, wifi type, physical media formats supported, and maximum video resolution. Override the default toString method to print a reasonably-sized description of the instance (< 120 chars).

• The debut date (or launch date) should be an instance of java.util.Date

• Keep the wifi type (b/g, b/g/n, etc) field optional, in case some consoles don’t have wifi.

• The physical media formats should be a list. Is a String the best bet here, or an Int that matches a constant value?

• The maximum video resolution should be in a format that would make it possible to sort consoles in order of greatest number of pixels.

b) Test our your new console class by writing a new class that creates 4 instances of this console class. All of the instances should have reasonably accurate values.

c) Now its time for games. Create a game class that includes the name, maker, and a list of consoles it supports, plus an "isSupported" method that returns true if a given console is supported.

d) Test out this game class by generating a list of games, each containing one or more instances of consoles. Can you convert this list to a lookup table of consoles to a list of supported games? How about a function that prints a list of the games, sorted first by maker and then by game name?

Answer

Instead of answering this in four separate parts, I’ll just give my complete solution for the exercise. It would be difficult to replace the package name and import statement across all the code blocks just to see it included once with the final class.

If you’re working from an IDE, copy and paste the contents into a "GameConsole.scala" file and compile. As it only uses a JDK class, it should be compatible with any running IDE project.

package ch8

import java.util.Date


abstract class MediaFormat
class DvdMediaFormat extends MediaFormat
class BluRayMediaFormat extends MediaFormat
class USBMediaFormat extends MediaFormat
class CartridgeMediaFormat extends MediaFormat

abstract class VideoResolution(pixels: Int)
class HD extends VideoResolution(1280 * 720)
class FHD extends VideoResolution(1920 * 1080)
class QHD extends VideoResolution(2560 * 1440)
class UHD4K extends VideoResolution(3840 * 2160)


/**
 * A console that can play games built for it with one or more video resolutions.
 */
class GameConsole(val make: String, val model: String, val debut: Date, val wifiType: Option[String],
                  val mediaFormats: List[MediaFormat], val maxVideoResolution: VideoResolution) {

  override def toString = s"GameConsole($make, $model), max video resolution = ${maxVideoResolution.getClass.getName}"
}



class GameConsoleLibrary {

  def strToDate(s: String): Date = java.text.DateFormat.getInstance.parse(s)

  val chanduOne = new GameConsole("Chandu", "One", strToDate("2/12/2007 0:00 AM"), Some("a/b"),
      List(new CartridgeMediaFormat), new HD)

  val aquaTopia = new GameConsole("Aqua", "Topia", strToDate("5/2/2012 0:00 AM"), Some("a/b/g"),
      List(new DvdMediaFormat), new HD)

  val oonaSeven = new GameConsole("Oona", "Seven", strToDate("3/3/2014 0:00 AM"), Some("b/g/n"),
      List(new BluRayMediaFormat, new DvdMediaFormat), new FHD)

  val leoChallenge = new GameConsole("Leonardo", "Challenge", strToDate("12/12/2014 0:00 AM"), Some("g/n"),
      List(new USBMediaFormat), new UHD4K)

}


/**
 * A game developed for one or more game consoles
 */
class Game(val name: String, val maker: String, val consoles: List[GameConsole]) {
  def isSupported(console: GameConsole) = consoles contains console
  override def toString = s"Game($name, by $maker)"
}

class GameShop {

  val consoles = new GameConsoleLibrary()

  val games = List(
    new Game("Elevator Action", "Taito", List(consoles.chanduOne)),
    new Game("Mappy", "Namco", List(consoles.chanduOne, consoles.aquaTopia)),
    new Game("StreetFigher", "Capcom", List(consoles.oonaSeven, consoles.leoChallenge))
  )

  val consoleToGames: Map[GameConsole, List[Game]] = {
    val consoleToGames1: List[(GameConsole, Game)] = games flatMap (g => g.consoles.map(c => c -> g))
    val consoleToGames2: Map[GameConsole, List[(GameConsole, Game)]] = consoleToGames1 groupBy (_._1)
    val consoleToGames3: Map[GameConsole, List[Game]] = consoleToGames2 mapValues(_ map (_._2))
    consoleToGames3
  }

  def reportGames(): Unit = {
    games sortBy (g => s"${g.maker}_${g.name}") foreach { game =>
      val consoleInfo = game.consoles.map(c => s"${c.make} ${c.model}").mkString(", ")
      println(s"${game.name} by ${game.maker} for $consoleInfo")
    }
  }

}

2) Let’s create a linked list, object-oriented-style.

a) Create a container class that has an instance of itself plus an instance of a parameterized type. The constructor should take a variable number of the instances (e.g., strings or ints or any other parameterized type), which can be implemented with vararg parameters . Implement a "foreach" method that users can call to iterate over the list, invoking their function for every element.

• How will you determine the end of the list?

• C-style lists often use a null value to denote the end of the list, is that the best approach here?

• Do you have a good use for the apply() method here?

b) I’m sure your linked list works great, but let’s try refactoring it with a more interesting approach. Make your container class abstract with two subclasses: one representing a node with a valid item and one representing a node without a valid item, signifying the last item in the list.

• Will you ever need more than one instance of the second subclass?

• Are there any helper methods that should be private?

• How about abstract methods that the subclasses will need to implement?

• If you implemented the apply() method, should each subclass have its own implementation?

c) Add the standard head, tail, filter, size and map collection methods for your linked list. Can you implement any of these using lazy values? Which of these should be implemented in the parent class from exercise 5 versus being implemented in its subclasses?

Note this should say "exercise b", not "exercise 5".

d) Implement the head, tail, filter, size and map collection methods using recursion instead of iteration. Can you ensure these all use tail recursion to prevent stack overflow errors for massive collections?

Answer

a) Here’s my linked list, using an option to wrap the single value (ie, the "head") and another option to wrap the reference to the next item in the list. The final element in the list will be a valid instance that has neither a head nor a reference to the next item.

/**
 * Listy is a linked list of items that have the parameterized type A
 * @param items one or more items that will make up the list
 */
class Listy[A](items: A*) {

  val item: Option[A] = items.headOption

  val next: Option[Listy[A]] = {
    if (item.isDefined) Some(new Listy(items.tail: _*)) else None
  }

  def foreach(f: A => Unit): Unit = {
    for {i <- item; n <- next} {
      f(i)
      n.foreach(f)
    }
  }

  def apply(index: Int): Option[A] = {
    if (index < 1) item else next flatMap (_.apply(index - 1))
  }
}

You can verify if this works by pasting this code block into the REPL, after first setting the raw-paste mode with :paste -raw. Raw paste mode makes it possible to enter a full class definition.

scala> :paste -raw
// Entering paste mode (ctrl-D to finish)

/**
 * Listy is a linked list of items that have the parameterized type A
 * @param items one or more items that will make up the list
 */
class Listy[A](items: A*) {
...

// Exiting paste mode, now interpreting.


scala> val l = new Listy(1, 2, 3, 4)
l: Listy[Int] = Listy@2260c7bf

scala> l.item
res0: Option[Int] = Some(1)

scala> l foreach println
1
2
3
4

b) The previous implementation used the Option type to denote the empty element at the end of the list. Using one type for regular list elements and another type to denote the end of a list removes the needed to use options and simplifies our operations. Having the two list element types extend from a shared abstract class decouples their implementation from the list interface.

Unfortunately it also means that we lose our multi-item constructor, as abstract classes aren’t instantiable. To provide the same functionality, I added a helper class that can create the lists and hide the implementation details from the caller.

/**
 * ListyHelper can create a linked list of items that have the parameterized type A
 */
class ListyHelper {
  def create[A](items: A*) = {
    var result: Listy[A] = new EmptyList[A]
    for (item <- items.reverse) {
      result = new NonEmptyList[A](item, result)
    }
    result
  }
}

abstract class Listy[A] {
  def foreach(f: A => Unit): Unit
  def apply(index: Int): Option[A]

  def headOption: Option[A] = apply(0)
}

class NonEmptyList[A](val item: A, val next: Listy[A]) extends Listy[A] {

  override def foreach(f: A => Unit): Unit = {
    f(item)
    next.foreach(f)
  }

  override def apply(index: Int): Option[A] = {
    if (index < 1) Some(item) else next.apply(index - 1)
  }
}

class EmptyList[A] extends Listy[A] {
  override def foreach(f: A => Unit): Unit = {}
  override def apply(index: Int): Option[A] = None
}

The Listy.headOption method seemed useful to callers, and was implementable in the abstract class by reusing the apply method. This is an example of how a good foundation of foreach and apply functions can be used as the basis for other helpful functions.

c) Most of these new methods can be implemented using the foreach function added in the previous exercise, and so can be handled by the abstract base class. A notable exception is tail which requires access to the underlying linked list, which is only available in the NonEmptyList subclass. Fortunately this is easily implementable by renaming the field "next" to "tail". The EmptyList.tail implementation returns a null value to indicate there isn’t any more list to return, but you may prefer to throw an exception here instead to make the error more noticeable.

/**
 * ListyHelper can create a linked list of items that have the parameterized type A
 */
class ListyHelper {
  def create[A](items: A*) = {
    var result: Listy[A] = new EmptyList[A]
    for (item <- items.reverse) {
      result = new NonEmptyList[A](item, result)
    }
    result
  }
}

abstract class Listy[A] {
  def foreach(f: A => Unit): Unit
  def apply(index: Int): Option[A]

  def headOption: Option[A] = apply(0)

  lazy val head: A = headOption.get

  def tail: Listy[A]

  def filter(f: A => Boolean): Listy[A] = {
    var result: Listy[A] = new EmptyList[A]
    foreach { i =>
      if ( f(i) ) {
        result = new NonEmptyList[A](i, result)
      }
    }
    result.reverse
  }

  lazy val size: Int = {
    var count = 0
    foreach { _ => count += 1 }
    count
  }

  def map[B](f: A => B): Listy[B] = {
    var result: Listy[B] = new EmptyList[B]
    foreach { i =>
      result = new NonEmptyList[B](f(i), result)
    }
    result.reverse
  }

  lazy val reverse: Listy[A] = {
    var result: Listy[A] = new EmptyList[A]
    foreach { i => result = new NonEmptyList[A](i, result) }
    result
  }
}

class NonEmptyList[A](val item: A, val tail: Listy[A]) extends Listy[A] {

  override def foreach(f: A => Unit): Unit = {
    f(item)
    tail.foreach(f)
  }

  override def apply(index: Int): Option[A] = {
    if (index < 1) Some(item) else tail.apply(index - 1)
  }
}

class EmptyList[A] extends Listy[A] {
  override def foreach(f: A => Unit): Unit = {}
  override def apply(index: Int): Option[A] = None
  override def tail: Listy[A] = null
}

d) Here’s the final version of our own linked list, with many of the functions rewritten to be tail-recursive. I’ve added a traditional "cons" operator ("::") to simplify list building.

Recursion (and tail-recursion) may not be the right solution for this list, or for other problems. Designing and implementing recursive functions is a great exercise, however, for learning to work with immutable data. It’s also a good exercise for learning to separate the interface of these functions from the recursive implementation.

For example, the "filter" function below takes a single parameter, the filter function. Its recursive implementation, however, needs a complete input and output list to operate.

import scala.annotation.tailrec


/**
 * ListyHelper can create a linked list of items that have the parameterized type A
 */
class ListyHelper {
  def create[A](items: A*) = {
    var result: Listy[A] = new EmptyList[A]
    for (item <- items.reverse) {
      result = new NonEmptyList[A](item, result)
    }
    result
  }
}

abstract class Listy[A] {
  def foreach(f: A => Unit): Unit
  def apply(index: Int): Option[A]

  def headOption: Option[A] = apply(0)

  lazy val head: A = headOption.get

  def tail: Listy[A]

  def ::(a: A): Listy[A] = new NonEmptyList[A](a, this)

  def filter(f: A => Boolean): Listy[A] = {

    @tailrec
    def filterLists(src: Listy[A], dest: Listy[A], f: A => Boolean): Listy[A] = {
      src.headOption match {
        case Some(i) if f(i) => filterLists(src.tail, i :: dest, f)
        case Some(i) => filterLists(src.tail, dest, f)
        case None => dest
      }
    }

    val result: Listy[A] = filterLists(this, new EmptyList[A], f)
    result.reverse
  }


  lazy val size: Int = {

    @tailrec
    def count(src: Listy[A], total: Int): Int = {
      src.headOption match {
        case Some(i) => count(src.tail, total + 1)
        case None => total
      }
    }

    count(this, 0)
  }

  def map[B](f: A => B): Listy[B] = {

    @tailrec
    def mapLists[B](src: Listy[A], dest: Listy[B], f: A => B): Listy[B] = {
      src.headOption match {
        case Some(i) => mapLists(src.tail, f(i) :: dest, f)
        case None => dest
      }
    }

    val result: Listy[B] = mapLists(this, new EmptyList[B], f)
    result.reverse
  }

  lazy val reverse: Listy[A] = {

    @tailrec
    def reverseLists(src: Listy[A], dest: Listy[A]): Listy[A] = {
      src.headOption match {
        case Some(i) => reverseLists(src.tail, i :: dest)
        case None => dest
      }
    }

    reverseLists(this, new EmptyList[A])
  }
}

class NonEmptyList[A](val item: A, val tail: Listy[A]) extends Listy[A] {

  override def foreach(f: A => Unit): Unit = {
    f(item)
    tail.foreach(f)
  }

  override def apply(index: Int): Option[A] = {
    if (index < 1) Some(item) else tail.apply(index - 1)
  }
}

class EmptyList[A] extends Listy[A] {
  override def foreach(f: A => Unit): Unit = {}
  override def apply(index: Int): Option[A] = None
  override def tail: Listy[A] = null
}

3) For a change of pace, let’s create a directory listing class. The constructor fields should be the full path to the directory and a predicate function that takes a String (the file name) and returns true if the file should be included. The method "list" should then list the files in the directory.

To implement this, create an instance of java.io.File and use its listFiles(filter: FilenameFilter) to list files that match the given filter. You’ll find javadocs for this method and for the java.io.FilenameFilter class, but you will need to figure out how this would be called from Scala. You should pass in the FilenameFilter argument as an anonymous class.

• Is there any part of this class that would work well as a lazy value?

• Would it make sense to store the anonmyous subclass of java.io.FilenameFilter as a lazy val?

• How about the filtered directory listing?

Answer

Sometimes it’s good to have a simpler exercise mixed in with the others. This exercise will get you familiar with working with Java API’s, especially the ones that take interface implementations as parameters.

I’ve marked the file and filter as lazy values, as they are really only required if the "list" function is called. In regular practice I probably would have not added the lazy designation, as the two values are not resource-intensive.

import java.io.{FilenameFilter, File}


class DirLister(path: String, f: String => Boolean) {

  lazy val file: File = new File(path)

  lazy val filter = new FilenameFilter {
    override def accept(dir: File, name: String): Boolean = f(name)
  }

  def list: List[String] = file.list(filter).toList

}

4) The JVM library includes a working MIDI sound synthesizer. Here’s an example of playing a short set of notes:

scala> val synth = javax.sound.midi.MidiSystem.getSynthesizer
synth: javax.sound.midi.Synthesizer = com.sun.media.sound
  .SoftSynthesizer@283a8ad6

scala> synth.open()

scala> val channel = synth.getChannels.head
channel: javax.sound.midi.MidiChannel = com.sun.media.sound
  .SoftChannelProxy@606d6d2c

scala> channel.noteOn(50, 80); Thread.sleep(250); channel.noteOff(30)

scala> synth.close()

Create a simpler interface to this by writing a class that plays a series of notes. The class’s constructor should take the volume (set to 80 in the example) but always use the same duration (250 milliseconds in the example) . Its "play" method should take a list of the notes, for example Seq(30, 35, 40, 45, 50, 55, 60, 65, 70), and play them in the synthesizer.

• Assume the getSynthesizer method call is expensive. How can you prevent unnecessarily calling it in case the "play" method is never called?

• Make sure to hide fields that callers don’t need to know about

• Can you support a Range as input, eg play(30 to 70 by 5) ?

• Can you support multiple ranges, for example a series of notes that rise, fall, and then rise again?

• Assume we only ever need one instance, ever, with the volume set to 95) Can you use access controls to ensure that there will never be more than one instance of this class?

Answer

Note the example code has a minor error, as one ought to be turning off the same notes they turned on. The last function should instead read "channel.noteOff(50)".

Here’s my take on the music playing class.

• The getSynthesizer result is stored as a lazy value, so it is only created once (or never, if it is never played).

• The local fields are all marked private to ensure they are not read by other classes. While the "duration" field cannot be tampered with, the "synth" object is mutable and could be modified or ruined by external access.

• The "play" function takes a Seq, a base class of Range, so you can invoke it with List, Seq, Range, and other collections.

• Multiple ranges? Mais oui! new Calliope(80).play20 to 90 by 2) ++ (85 to 30 by -3 . In other words, multiple ranges are easily composed with the collection library.

• Using a local package, and package-level protection, it is possible to ensure that only a local class can ever access the calliope class, and that the volume will always be set to 95. However, it isn’t possible to ensure that there will be no more than one instance in the entire JVM. To do this you would need to use an Object, which we cover in the following chapter.

package clever.calliope {

  import javax.sound.midi.MidiChannel

  private[calliope] class Calliope(volume: Int) {

    private val duration = 250L
    private lazy val synth = javax.sound.midi.MidiSystem.getSynthesizer

    /**
     * Plays a series of MIDI notes at the specified volume for this calliope
     * @param notes a sequence of MIDI notes as integers
     */
    def play(notes: Seq[Int]): Unit = {
      playChannel { channel =>
        for (note <- notes) {
          channel.noteOn(note, volume)
          Thread.sleep(duration)
          channel.noteOn(note, 0)
        }
      }
    }

    /**
     * Provides a mechanism to play music in a channel without
     * worrying about opening and closing synths.
     */
    private def playChannel(f: MidiChannel => Unit): Unit = {
      synth.open()
      val channel: MidiChannel = synth.getChannels.head
      f(channel)
      synth.close()
    }
  }


  class CalliopePlaying {

    val calliope = new Calliope(95)

    def playScale(): Unit = {
      calliope.play(Seq(60, 62, 64, 65, 67, 69, 71, 72))
    }

    def playMary(): Unit = {
      val (c, d, e) = (60, 62, 64)
      val mary = Seq(0,e,d,c,d,e,e,e,0,d,d,d,0,e,e,e,0,e,d,c,d,e,e,e,e,d,d,e,d,c,0)
      calliope.play(mary)
    }
  }

}