Блог

Я использую эту реализацию ограниченной очереди приоритетов,https://gist.github.com/ryanlecompte/5746241, и это работает отлично. Однако я хочу, чтобы эта очередь не содержала ни одного элемента с одинаковым порядком ‘ord’. Как я могу этого добиться?

Я попытался обновить функцию maybeReplaceLowest, указав функцию lteq вместо lt.

 private def maybeReplaceLowest(a: A) {
    if (ord.lteq(a, head)) {
      dequeue()
      super. =(a)
    }
  }
  

Но я думаю, что это не сработает, потому что элемент, который имеет тот же порядок, что и новый элемент, может не находиться во главе. Каким может быть быстрое решение этой проблемы?

Большое спасибо.

Scala PriorityQueue реализован с использованием Array . Что очень неэффективно для операции поиска, которую вам нужно выполнять для каждой вставки (чтобы проверить, существует ли элемент уже в очереди.

Для TreeSet идеально подходит для поиска и упорядоченного хранения. Но поскольку это закрытый класс (scala-2.12.8), я создал составной класс

 import scala.collection.mutable

class PrioritySet[A](val maxSize:Int)(implicit ordering:Ordering[A]) {
    var set = mutable.TreeSet[A]()(ordering)

    private def removeAdditional(): this.type = {
        val additionalElements = set.size - maxSize
        if( additionalElements > 0) { set = set.drop(additionalElements) }
        this
    }

    def  (elem: A): this.type = {
        set  = elem
        removeAdditional()
    }

    def   =(elem: A, elements: A*) : this.type = {
        set  = elem   = elements 
        removeAdditional()
    }

    override def toString = this.getClass.getName   set.mkString("(", ", ", ")")
}
  

Это может быть использовано как

 >>> val set = new PrioritySet[Int](4)
>>> set   =(1000,3,42,2,5, 1,2,4, 100)
>>> println(set)
PrioritySet(5, 42, 100, 1000)