Class: PriorityQueue

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • adding
  • enumerating
  • initialization
  • private
  • removing
• Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--PriorityQueue

Package:

stx:libbasic2

Category:

Collections-Ordered

Version:

rev: 1.3 date: 2017/10/10 16:06:53

user: stefan

file: PriorityQueue.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Author:

Claus Gittinger

Description:

a priority queue is a collection with a given maximum size
which only keeps the maxSize largest values.
Only up to maxSize elements are stored at any time.
The internal organization is a heap; 
eg. elements are not kept sorted internally.

When elements are added, a check is made, 
if the new element should be kept or not.

Finally, when all elements have been added,
get the elements in sorted order by repeated calls to removeFirst,
which will remove and return the smallest element.

Class protocol:

 new: maxSize

retun a new PriorityQueue, which holds at most maxNode elements,
the largest one's added

 new: maxSize comparator: aBlock

retun a new PriorityQueue, which holds at most maxNode elements,
the largest one's added

 newWithCapacity: size

return a new empty Collection with capacity for n elements.

Instance protocol:

 add: anElement

if the argument is larger than the currently smallest element,
then add it and remove the smallest.
Otherwise do nothing

 isEmpty

 size

 do: aBlock

 comparator: aBlock

 initializeFor: maxSizeArg

 initializeFor: maxSizeArg comparator: aBlock

 contents

return the current contents.
It is not sorted by size, but a heap structure

 downHeap

an element was added at the bottom of the heap;
shift it to its place

 upHeap

an element was added to the top of the heap;
shift it to its place

 removeAll

 removeFirst

removes and returns the smallest element from the priority queue

Examples:

  |pq dir|

  pq := PriorityQueue new:10 comparator:[:a :b | a fileSize > b fileSize].
  dir := '../../' asFilename.
  dir directoryContentsAsFilenamesDo:[:eachLib |
      (eachLib baseName startsWith:'lib') ifTrue:[
          eachLib filesWithSuffix:'st' do:[:fn |
              pq add:fn
          ].
      ].
  ].
  [ pq notEmpty ] whileTrue:[
      |next|

      next := pq removeFirst.
      Transcript show:next fileSize; space; showCR:next pathName
  ].

  |pq|

  pq := PriorityQueue new:10.
  1000000 timesRepeat:[
      pq add:(Random nextInteger).
  ].
  [ pq notEmpty ] whileTrue:[
      Transcript showCR:pq removeFirst.
  ].

  |pq|

  #(10 20 30 40 50 60 70 80) permutationsDo:[:p |
      pq := PriorityQueue new:5.
      pq addAll:p.
      self assert:(pq contents copy sort = #(40 50 60 70 80)).
  ].