eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'PriorityQueue':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: PriorityQueue


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:

instance creation
o  new: maxSize
retun a new PriorityQueue, which holds at most maxNode elements,
the largest one's added

o  new: maxSize comparator: aBlock
retun a new PriorityQueue, which holds at most maxNode elements,
the largest one's added

o  newWithCapacity: size
return a new empty Collection with capacity for n elements.


Instance protocol:

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

o  isEmpty

o  size

enumerating
o  do: aBlock

initialization
o  comparator: aBlock

o  initializeFor: maxSizeArg

o  initializeFor: maxSizeArg comparator: aBlock

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

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

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

removing
o  removeAll

o  removeFirst
removes and returns the smallest element from the priority queue


Examples:


find the 10 largest files in the stx source tree
  |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
  ].
generate 1 million random numbers and show the 10 largest
  |pq|

  pq := PriorityQueue new:10.
  1000000 timesRepeat:[
      pq add:(Random nextInteger).
  ].
  [ pq notEmpty ] whileTrue:[
      Transcript showCR:pq removeFirst.
  ].
a little test
  |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)).
  ].


ST/X 7.1.0.0; WebServer 1.663 at exept.de:8081; Sun, 22 Jul 2018 16:43:28 GMT