# 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] =

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`

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

``````PickySet(){_ == _}
```

```
+3

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] =

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).

+1

source

All Articles