Class: PriorityQueue

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

Inheritance:

   Object
   |
   +--Collection
      |
      +--PriorityQueue

Package:

stx:libbasic2

Category:

Collections-Ordered

Version:

rev: 1.8 date: 2023/03/13 03:32:23

user: cg

file: PriorityQueue.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Description:

a priority queue is a collection which keeps its elements in order.
The internal organization is a heap; 
eg. elements are not kept sorted internally.

If a maximumu size is given:
    keeping only the maxSize largest values at any time.
    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 next smallest element.

A different comparator may be given, to sort the elements in reverse,
or to use a different comparison method.

copyright
COPYRIGHT (c) 2018 by eXept Software AG
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

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.

 newWithUnlimitedSize

retun a new PriorityQueue, which holds any number of elements

 newWithUnlimitedSizeWithComparator: comparatorBlock

retun a new PriorityQueue, which holds any number of 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

Usage example(s):

|pq| pq := PriorityQueue new:5. pq add:1. pq add:10. pq add:5. pq add:9. pq add:17. pq add:-1. pq add:29. pq

 isEmpty

(comment from inherited method)
return true, if the receiver is empty

 size

 do: aBlock

evaluate the argument, aBlock for each element in the queue
(in the order of priority)

 comparator: aBlock

 initializeFor: maxSizeArg

 initializeFor: maxSizeArg comparator: aBlock

 contents

return the current contents sorted

 downHeap

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

 getContents

return the current contents.
Attention: it is not sorted, but a heap structure

 upHeap

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

 removeAll

remove all elements from the receiver. Returns the receiver

 removeFirst

removes and returns the smallest element from the priority queue.
The interpretation of 'smallest' is defined by the compare block

Usage example(s):

|pq| pq := PriorityQueue new:5. #(30 80 10 50 60 20 70 40) do:[:e | pq add:e]. self assert:(pq contents = #(40 50 60 70 80)). self assert:(pq size == 5). self assert:(pq removeFirst = 40). self assert:(pq size == 4). self assert:(pq removeFirst = 50). self assert:(pq size == 3). self assert:(pq removeFirst = 60). self assert:(pq size == 2). self assert:(pq removeFirst = 70). self assert:(pq size == 1). self assert:(pq removeFirst = 80). self assert:(pq size == 0). self assert:(pq isEmpty).

 max

(comment from inherited method)
return the maximum value in the receiver collection,
using #< to compare elements.
Raises an error, if the receiver is empty.

 min

(comment from inherited method)
return the minimum value in the receiver collection,
using < to compare elements.
Raises an error if the receiver is empty.

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 getContents copy sort = #(40 50 60 70 80)).
      self assert:(pq contents = #(40 50 60 70 80)).
  ].

  |pq coll|
  pq := PriorityQueue newWithUnlimitedSizeWithComparator:[:a :b | a < b].
  coll := OrderedCollection new.
  1000 timesRepeat:[ 
      |n|
      pq add:(n := Random nextIntegerBetween:1 and:100000).
      coll add:n.
  ].
  coll sort.
  Transcript show:'smallest: '; showCR:(coll first:10).
  Transcript show:'largest: '; showCR:(coll last:10).

  Transcript showCR:'prio largest:'.
  10 timesRepeat:[ Transcript showCR:pq removeFirst ].
  Transcript show:'remaining: '; showCR: pq size.
  pq size - 10 timesRepeat:[pq removeFirst].
  Transcript showCR:'prio smallest:'.
  10 timesRepeat:[ Transcript showCR:pq removeFirst ].