CODEWITHSUNDEEP
scalascala-collections
qtwo
qtwo

Reputation: 507

Collection that contains no a where a⊆b and b is in the collection

I need a collection that disregards elements that are included in others:

Picky(Set(1, 2)) + Set(1) should equal(Picky(Set(1, 2)))

Picky(Set(1)) + Set(1, 2) should equal(Picky(Set(1, 2)))

Picky(Set(1, 3)) + Set(1, 2) should equal(Picky(Set(1, 3), Set(1, 2)))

Picky(Set(1, 2), (Set(1))) should equal(Picky(Set(1, 2)))

I actually have a solution

case class Picky[T] private(sets: Set[Set[T]]) {
  def +(s: Set[T]): Picky[T] = Picky(Picky.internalAddition(this.sets, s))
}

object Picky {
  def apply[T](sets: Set[T]*): Picky[T] = 
    Picky((Set[Set[T]]() /: sets)(internalAddition(_, _)))

  private def internalAddition[T](c: Set[Set[T]], s: Set[T]): Set[Set[T]] =
    if (c.exists(s subsetOf _)) c else c.filterNot(_ subsetOf s) + s
}

But I wonder whether there's already a collection that includes this concept, because what I'm trying to do sounds a bit like a set with a kind of reduction function, something like the following imaginary collection that accepts a worse function ((a, b) => a subset b in our specific case):

PickySet(){(a, b) => a subset b}

Where for any to elements (a, b) if worse(a, b) returned true, a would be discarded

To clarify the difference with Set, a Set would be a special case of PickySet:

PickySet(){_ == _}

Upvotes: 3

Views: 169

Answers (1)

Travis Brown
Travis Brown

Reputation: 139058

I don't think you're going to find a convenient ready-made implementation of this collection, but you can make yours a little more general by using scala.math.PartialOrdering and the fact that sets are partially ordered by the subset relation.

First for the definition of Picky. In effect what you want is a container holding only maximal elements, where no elements are ordered with respect to each other, and all smaller elements have been deleted.

class Picky[A: PartialOrdering] private(val xs: Seq[A]) {
  def +(y: A): Picky[A] = new Picky(Picky.add(xs, y))
  override def toString = "Picky(%s)".format(xs.mkString(", "))
}

object Picky {
  def apply[A: PartialOrdering](xs: A*): Picky[A] =
    new Picky(xs.foldLeft(Seq.empty[A])(add))

  private def add[A](xs: Seq[A], y: A)(implicit ord: PartialOrdering[A]) = {
    val notSmaller = xs.filterNot(ord.lteq(_, y))
    if (notSmaller.exists(ord.lteq(y, _))) notSmaller else notSmaller :+ y
  }
}

Next for the partial ordering for sets, which is only defined if one of the sets is a subset of the other (possibly trivially):

implicit def subsetOrdering[A] = new PartialOrdering[Set[A]] {
   def tryCompare(x: Set[A], y: Set[A]) =
     if (x == y) Some(0)
     else if (x subsetOf y) Some(-1)
     else if (y subsetOf x) Some(1)
     else None

   def lteq(x: Set[A], y: Set[A]) =
     this.tryCompare(x, y).map(_ <= 0).getOrElse(false)
}

The following equivalent definition of tryCompare could conceivably be a little faster:

def tryCompare(x: Set[A], y: Set[A]) = {
  val s = (x & y).size
  if (s == x.size || s == y.size) Some(x.size - y.size) else None
}

Now we get the desired results:

scala> Picky(Set(1, 2)) + Set(1)
res0: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2))

scala> Picky(Set(1)) + Set(1, 2)
res1: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2))

scala> Picky(Set(1, 3)) + Set(1, 2)
res2: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 3), Set(1, 2))

scala> Picky(Set(1, 2), (Set(1)))
res3: Picky[scala.collection.immutable.Set[Int]] = Picky(Set(1, 2))

Note that we could very easily define an alternative partial ordering that would give Picky plain old set semantics (i.e., only equal things are ordered with respect to each other, and they're always equal).

Upvotes: 1

Related Questions