A collection that does not contain a, where a⊆b and b are in the collection
I need a collection that ignores 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'm wondering if there is already a collection that includes this concept, because what I'm trying to do is a bit like a set with a shrink function, something like the following imaginary collection that takes a function worse
( (a, b) => a subset b
in our particular case):
PickySet(){(a, b) => a subset b}
Where for any element (a, b), if worse(a, b)
returned true
, a
will be discarded
To clarify the difference with Set, Set will be a special case of PickySet:
PickySet(){_ == _}
source to share
I don't think you will find a convenient out-of-the-box implementation of this collection, but you can make yours a little more general by taking advantage of scala.math.PartialOrdering
the fact that the sets are partially ordered in relation to a subset.
First for the definition Picky
. In fact, you want the container to contain only the maximum elements , where none of the elements are ordered relative to each other, and all the smaller elements are removed.
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
}
}
Further, for a partial ordering for sets, which is only defined if one of the sets is a subset of the other (possibly trivial):
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 tryCompare
could be slightly 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
}
We will now 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 easily define an alternative partial ordering that would give the Picky
usual old set semantics (i.e. only equal things are ordered relative to each other and they are always equal).
source to share