Avatar of Wows

Wows's solution

to Custom Set in the Scala Track

Published at Mar 24 2019 · 0 comments
Instructions
Test suite
Solution

Create a custom set type.

Sometimes it is necessary to define a custom data structure of some type, like a set. In this exercise you will define your own set. How it works internally doesn't matter, as long as it behaves like a set of unique elements.

The Scala exercises assume an SBT project scheme. The exercise solution source should be placed within the exercise directory/src/main/scala. The exercise unit tests can be found within the exercise directory/src/test/scala.

To run the tests simply run the command sbt test in the exercise directory.

For more detailed info about the Scala track see the help page.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

CustomSetTest.scala

import org.scalatest.{FunSuite, Matchers}

/** @version 1.3.0 */
class CustomSetTest extends FunSuite with Matchers {

  // Empty test cases - Returns true if the set contains no elements
  test("sets with no elements are empty") {
    val set = CustomSet.fromList(List())
    CustomSet.empty(set) should be(true)
  }

  test("sets with elements are not empty") {
    pending
    val set = CustomSet.fromList(List(1))
    CustomSet.empty(set) should be(false)
  }

  // Contains test cases - Sets can report if they contain an element
  test("nothing is contained in an empty set") {
    pending
    val set = CustomSet.fromList(List())
    CustomSet.member(set, 1) should be(false)
  }

  test("when the element is in the set") {
    pending
    val set = CustomSet.fromList(List(1, 2, 3))
    CustomSet.member(set, 1) should be(true)
  }

  test("when the element is not in the set") {
    pending
    val set = CustomSet.fromList(List(1, 2, 3))
    CustomSet.member(set, 4) should be(false)
  }

  // Subset test cases - A set is a subset if all of its elements are contained in the other set
  test("empty set is a subset of another empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List())
    CustomSet.isSubsetOf(set1, set2) should be(true)
  }

  test("empty set is a subset of non-empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List(1))
    CustomSet.isSubsetOf(set1, set2) should be(true)
  }

  test("non-empty set is not a subset of empty set") {
    pending
    val set1 = CustomSet.fromList(List(1))
    val set2 = CustomSet.fromList(List())
    CustomSet.isSubsetOf(set1, set2) should be(false)
  }

  test("set is a subset of set with exact same elements") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3))
    val set2 = CustomSet.fromList(List(1, 2, 3))
    CustomSet.isSubsetOf(set1, set2) should be(true)
  }

  test("set is a subset of larger set with same elements") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3))
    val set2 = CustomSet.fromList(List(4, 1, 2, 3))
    CustomSet.isSubsetOf(set1, set2) should be(true)
  }

  test("set is not a subset of set that does not contain its elements") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3))
    val set2 = CustomSet.fromList(List(4, 1, 3))
    CustomSet.isSubsetOf(set1, set2) should be(false)
  }

  // Disjoint test cases - Sets are disjoint if they share no elements
  test("the empty set is disjoint with itself") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List())
    CustomSet.isDisjointFrom(set1, set2) should be(true)
  }

  test("empty set is disjoint with non-empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List(1))
    CustomSet.isDisjointFrom(set1, set2) should be(true)
  }

  test("non-empty set is disjoint with empty set") {
    pending
    val set1 = CustomSet.fromList(List(1))
    val set2 = CustomSet.fromList(List())
    CustomSet.isDisjointFrom(set1, set2) should be(true)
  }

  test("sets are not disjoint if they share an element") {
    pending
    val set1 = CustomSet.fromList(List(1, 2))
    val set2 = CustomSet.fromList(List(2, 3))
    CustomSet.isDisjointFrom(set1, set2) should be(false)
  }

  test("sets are disjoint if they share no elements") {
    pending
    val set1 = CustomSet.fromList(List(1, 2))
    val set2 = CustomSet.fromList(List(3, 4))
    CustomSet.isDisjointFrom(set1, set2) should be(true)
  }

  // Equal test cases - Sets with the same elements are equal
  test("empty sets are equal") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List())
    CustomSet.isEqual(set1, set2) should be(true)
  }

  test("empty set is not equal to non-empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List(1, 2, 3))
    CustomSet.isEqual(set1, set2) should be(false)
  }

  test("non-empty set is not equal to empty set") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3))
    val set2 = CustomSet.fromList(List())
    CustomSet.isEqual(set1, set2) should be(false)
  }

  test("sets with the same elements are equal") {
    pending
    val set1 = CustomSet.fromList(List(1, 2))
    val set2 = CustomSet.fromList(List(2, 1))
    CustomSet.isEqual(set1, set2) should be(true)
  }

  test("sets with different elements are not equal") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3))
    val set2 = CustomSet.fromList(List(1, 2, 4))
    CustomSet.isEqual(set1, set2) should be(false)
  }

  test("set is not equal to larger set with same elements") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3))
    val set2 = CustomSet.fromList(List(1, 2, 3, 4))
    CustomSet.isEqual(set1, set2) should be(false)
  }

  // Add test cases - Unique elements can be added to a set
  test("add to empty set") {
    pending
    val set = CustomSet.fromList(List())
    val expected = CustomSet.fromList(List(3))
    CustomSet.isEqual(CustomSet.insert(set, 3), expected) should be(true)
  }

  test("add to non-empty set") {
    pending
    val set = CustomSet.fromList(List(1, 2, 4))
    val expected = CustomSet.fromList(List(1, 2, 3, 4))
    CustomSet.isEqual(CustomSet.insert(set, 3), expected) should be(true)
  }

  test("adding an existing element does not change the set") {
    pending
    val set = CustomSet.fromList(List(1, 2, 3))
    val expected = CustomSet.fromList(List(1, 2, 3))
    CustomSet.isEqual(CustomSet.insert(set, 3), expected) should be(true)
  }

  // Intersection test cases - Intersection returns a set of all shared elements
  test("intersection of two empty sets is an empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List())
    val expected = CustomSet.fromList(List())
    CustomSet.isEqual(CustomSet.intersection(set1, set2), expected) should be(
      true)
  }

  test("intersection of an empty set and non-empty set is an empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List(3, 2, 5))
    val expected = CustomSet.fromList(List())
    CustomSet.isEqual(CustomSet.intersection(set1, set2), expected) should be(
      true)
  }

  test("intersection of a non-empty set and an empty set is an empty set") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3, 4))
    val set2 = CustomSet.fromList(List())
    val expected = CustomSet.fromList(List())
    CustomSet.isEqual(CustomSet.intersection(set1, set2), expected) should be(
      true)
  }

  test("intersection of two sets with no shared elements is an empty set") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3))
    val set2 = CustomSet.fromList(List(4, 5, 6))
    val expected = CustomSet.fromList(List())
    CustomSet.isEqual(CustomSet.intersection(set1, set2), expected) should be(
      true)
  }

  test(
    "intersection of two sets with shared elements is a set of the shared elements") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3, 4))
    val set2 = CustomSet.fromList(List(3, 2, 5))
    val expected = CustomSet.fromList(List(2, 3))
    CustomSet.isEqual(CustomSet.intersection(set1, set2), expected) should be(
      true)
  }

  // Difference test cases - Difference (or Complement) of a set is a set of all elements that are only in the first set
  test("difference of two empty sets is an empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List())
    val expected = CustomSet.fromList(List())
    CustomSet.isEqual(CustomSet.difference(set1, set2), expected) should be(
      true)
  }

  test("difference of empty set and non-empty set is an empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List(3, 2, 5))
    val expected = CustomSet.fromList(List())
    CustomSet.isEqual(CustomSet.difference(set1, set2), expected) should be(
      true)
  }

  test("difference of a non-empty set and an empty set is the non-empty set") {
    pending
    val set1 = CustomSet.fromList(List(1, 2, 3, 4))
    val set2 = CustomSet.fromList(List())
    val expected = CustomSet.fromList(List(1, 2, 3, 4))
    CustomSet.isEqual(CustomSet.difference(set1, set2), expected) should be(
      true)
  }

  test(
    "difference of two non-empty sets is a set of elements that are only in the first set") {
    pending
    val set1 = CustomSet.fromList(List(3, 2, 1))
    val set2 = CustomSet.fromList(List(2, 4))
    val expected = CustomSet.fromList(List(1, 3))
    CustomSet.isEqual(CustomSet.difference(set1, set2), expected) should be(
      true)
  }

  // Union test cases - Union returns a set of all elements in either set
  test("union of empty sets is an empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List())
    val expected = CustomSet.fromList(List())
    CustomSet.isEqual(CustomSet.union(set1, set2), expected) should be(true)
  }

  test("union of an empty set and non-empty set is the non-empty set") {
    pending
    val set1 = CustomSet.fromList(List())
    val set2 = CustomSet.fromList(List(2))
    val expected = CustomSet.fromList(List(2))
    CustomSet.isEqual(CustomSet.union(set1, set2), expected) should be(true)
  }

  test("union of a non-empty set and empty set is the non-empty set") {
    pending
    val set1 = CustomSet.fromList(List(1, 3))
    val set2 = CustomSet.fromList(List())
    val expected = CustomSet.fromList(List(1, 3))
    CustomSet.isEqual(CustomSet.union(set1, set2), expected) should be(true)
  }

  test("union of non-empty sets contains all unique elements") {
    pending
    val set1 = CustomSet.fromList(List(1, 3))
    val set2 = CustomSet.fromList(List(2, 3))
    val expected = CustomSet.fromList(List(3, 2, 1))
    CustomSet.isEqual(CustomSet.union(set1, set2), expected) should be(true)
  }
}
case class CustomSet[+A](as: Map[Int, List[A]])

object CustomSet {

  private def add[A](l1: List[A], l2: List[A]): List[A] =
    l1.foldLeft(l2)((as, a) => if (as.contains(a)) as else a :: as)

  private def remove[A](l1: List[A], l2: List[A]): List[A] =
    l1.foldLeft(List[A]())((as, a) => if (l2.contains(a)) as else a :: as)

  private def addElements[A](m: Map[Int, List[A]], source: Map[Int, List[A]]): Map[Int, List[A]] =
    m.map { case (k, v) => (k, add(v, source.getOrElse(k, List()))) }

  def union[A](set1: CustomSet[A], set2: CustomSet[A]): CustomSet[A] = CustomSet(
    set1.as ++ addElements(set2.as, set1.as)
  )

  def difference[A](set1: CustomSet[A], set2: CustomSet[A]): CustomSet[A] = CustomSet(
    set1.as.map { case (k, v) => set2.as.get(k) match {
      case None => (k, v)
      case Some(as) => (k, remove(v, as))
    }
    }.filter { case (_, l) => l.nonEmpty })

  def intersection[A](set1: CustomSet[A], set2: CustomSet[A]): CustomSet[A] = CustomSet(
    set1.as.map { case (k, v) => set2.as.get(k) match {
      case None => (k, List[A]())
      case Some(l) => (k, v.intersect(l))
    }
    }.filter { case (_, l) => l.nonEmpty })

  def insert[A](set: CustomSet[A], a: A): CustomSet[A] = if (member(set, a)) set else
    CustomSet(set.as.+((a.##, a :: set.as.getOrElse(a.##, List())))) //not nice

  def isEqual[A](set1: CustomSet[A], set2: CustomSet[A]): Boolean = set1.as == set2.as

  def isDisjointFrom[A](set1: CustomSet[A], set2: CustomSet[A]): Boolean =
    if (set1.as.isEmpty || set2.as.isEmpty) true else
      set1.as.forall { case (k, v) => !set2.as.get(k).contains(v) } &&
        set2.as.forall { case (k, v) => !set1.as.get(k).contains(v) }

  def isSubsetOf[A](set1: CustomSet[A], set2: CustomSet[A]): Boolean =
    if (set1.as.isEmpty) true
    else if (set2.as.isEmpty) false
    else set1.as.forall { case (k, v) => set2.as.get(k).contains(v) }

  def member[A](set: CustomSet[A], a: A): Boolean =
    set.as.keys.exists(_ == a.##) && set.as.getOrElse(a.##, List()).contains(a)

  def empty[A](set: CustomSet[A]): Boolean = set.as.isEmpty

  def fromList[A](list: List[A]): CustomSet[A] = CustomSet(list.groupBy(_.##))

}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?