Scala Programming Language
  1. Scala Programming Language
  2. SI-5085

Either documentation or implementation of PriorityQueue.iterator (and dependent functions) is incorrect

    Details

      Description

      The source code and documentation of scala.collections.mutable.PriorityQueue states that for .iterator and various dependent functions (notably .toList and .toString) elements are returned in priority order, which is not what the implementation actually does. Other methods, in particular the critical methods .dequeue() and .dequeueAll() behave correctly.

      To reproduce:

           @Test def test() {
              val pq = new scala.collections.mutable.PriorityQueue[Int]()
              pq ++= List( 9,1,8,2,7,3 )
              println( pq.iterator.mkString(",") ) // = "9,7,8,1,2,3"
           }
      

      Origin: came up via http://stackoverflow.com/questions/7792189/scala-what-is-the-most-appropriate-data-structure-for-sorted-subsets/7792837#7792837

        Activity

        Hide
        Aleksandar Prokopec added a comment - - edited

        The documentation is not up-to-date. Priority queue iterators don't respect any order.

        Show
        Aleksandar Prokopec added a comment - - edited The documentation is not up-to-date. Priority queue iterators don't respect any order.

          People

          • Assignee:
            Aleksandar Prokopec
            Reporter:
            Gregor Scheidt
          • Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development