# 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