Коллекция, которая не содержит a, где a⊆b и b находятся в коллекции - PullRequest
Новая
       2

Коллекция, которая не содержит a, где a⊆b и b находятся в коллекции

3 голосов
/ 10 марта 2012

Мне нужна коллекция, которая игнорирует элементы, включенные в другие: 

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

У меня действительно есть решение 

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
}

Но мне интересно, есть ли уже коллекция, которая включает в себя этоконцепция, потому что то, что я пытаюсь сделать, звучит немного как набор с некой функцией сокращения, что-то вроде следующего воображаемого набора, который принимает функцию worse ((a, b) => a subset b в нашем конкретном случае): 

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

Где для любых элементов (a, b), если worse(a, b) вернул true, a будет отброшено

Чтобы прояснить разницу с Set, Set будет частным случаемPickySet: 

PickySet(){_ == _}

1 Ответ

1 голос
/ 11 марта 2012

Я не думаю, что вы найдете удобную готовую реализацию этой коллекции, но вы можете сделать вашу более общую, используя scala.math.PartialOrdering и тот факт, что наборычастично упорядочено отношением подмножеств.

Сначала для определения Picky.По сути, вам нужен контейнер, содержащий только максимальные элементы , где элементы не упорядочены относительно друг друга, а все более мелкие элементы удалены. 

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
  }
}

Далее длячастичное упорядочение наборов, которое определяется только в том случае, если один из наборов является подмножеством другого (возможно, тривиально): 

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

Следующее эквивалентное определение tryCompare может быть немного быстрее: 

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
}

Теперь мы получаем желаемые результаты: 

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

Обратите внимание, что мы могли бы очень легко определить альтернативный частичный порядок, который дал бы Picky простой старый набор семантики (то есть, только равныйвсе упорядочено по отношению друг к другу, и они всегда равны).

...