1 "{ Package: 'stx:libbasic2' }"

     2 

     3 "{ NameSpace: Smalltalk }"

     4 

     5 Collection subclass:#PriorityQueue

     6 	instanceVariableNames:'size maxSize heap comparator'

     7 	classVariableNames:''

     8 	poolDictionaries:''

     9 	category:'Collections-Ordered'

    10 !

    11 

    12 !PriorityQueue class methodsFor:'documentation'!

    13 

    14 documentation

    15 "

    16     a priority queue is a collection with a given maximum size

    17     which only keeps the maxSize largest values.

    18     Only up to maxSize elements are stored at any time.

    19     The internal organization is a heap; eg. elements are not kept

    20     sorted internally.

    21 

    22     When elements are added, a check is made, if the new element should

    23     be kept or not.

    24 

    25     Finally, when all elements have been added,

    26     get the elements in sorted order by repeated calls to removeFirst,

    27     which will remove and return the smallest element.

    28 "

    29 !

    30 

    31 examples

    32 "

    33     find the 10 largest files in the stx source tree

    34                                                             [exBegin]

    35     |pq dir|

    36 

    37     pq := PriorityQueue new:10 comparator:[:a :b | a fileSize > b fileSize].

    38     dir := '../../' asFilename.

    39     dir directoryContentsAsFilenamesDo:[:eachLib |

    40         (eachLib baseName startsWith:'lib') ifTrue:[

    41             eachLib filesWithSuffix:'st' do:[:fn |

    42                 pq add:fn

    43             ].

    44         ].

    45     ].

    46     [ pq notEmpty ] whileTrue:[

    47         |next|

    48 

    49         next := pq removeFirst.

    50         Transcript show:next fileSize; space; showCR:next pathName

    51     ].

    52                                                             [exEnd]

    53 

    54     generate 1 million random numbers and show the 10 largest

    55                                                             [exBegin]

    56     |pq|

    57 

    58     pq := PriorityQueue new:10.

    59     1000000 timesRepeat:[

    60         pq add:(Random nextInteger).

    61     ].

    62     [ pq notEmpty ] whileTrue:[

    63         Transcript showCR:pq removeFirst.

    64     ].

    65                                                             [exEnd]

    66 

    67     a little test

    68                                                             [exBegin]

    69     |pq|

    70 

    71     #(10 20 30 40 50 60 70 80) permutationsDo:[:p |

    72         pq := PriorityQueue new:5.

    73         pq addAll:p.

    74         self assert:(pq contents copy sort = #(40 50 60 70 80)).

    75     ].

    76                                                             [exEnd]

    77 "

    78 ! !

    79 

    80 !PriorityQueue class methodsFor:'instance creation'!

    81 

    82 new:maxSize

    83     "retun a new PriorityQueue, which holds at most maxNode elements,

    84      the largest one's added"

    85 

    86     ^ self new initializeFor:maxSize

    87 !

    88 

    89 new:maxSize comparator:aBlock

    90     "retun a new PriorityQueue, which holds at most maxNode elements,

    91      the largest one's added"

    92 

    93     ^ self new initializeFor:maxSize comparator:aBlock

    94 ! !

    95 

    96 !PriorityQueue methodsFor:'adding'!

    97 

    98 add:anElement

    99     "if the argument is larger than the currently smallest element,

   100      then add it and remove the smallest.

   101      Otherwise do nothing"

   102 

   103     size < maxSize ifTrue:[

   104         size := size + 1.

   105         heap at:size put:anElement.

   106         self upHeap.

   107     ] ifFalse:[

   108         (comparator value:anElement value:(heap at:1)) ifTrue:[

   109             heap at:1 put:anElement.

   110             self downHeap.

   111         ].

   112     ]

   113 

   114     "

   115      |pq|

   116 

   117      pq := PriorityQueue new:5.

   118      pq add:1.

   119      pq add:10.

   120      pq add:5.

   121      pq add:9.

   122      pq add:17.

   123      pq add:-1.

   124      pq add:29.

   125      pq

   126     "

   127 !

   128 

   129 isEmpty

   130     ^ size == 0

   131 !

   132 

   133 size

   134     ^ size

   135 ! !

   136 

   137 !PriorityQueue methodsFor:'enumerating'!

   138 

   139 do:aBlock

   140     heap from:1 to:size do:aBlock

   141 ! !

   142 

   143 !PriorityQueue methodsFor:'initialization'!

   144 

   145 comparator:aBlock

   146     comparator := aBlock

   147 !

   148 

   149 initializeFor:maxSizeArg

   150     self assert:(maxSizeArg > 0).

   151 

   152     heap := Array new:maxSizeArg.

   153     maxSize := maxSizeArg.

   154     size := 0.

   155     comparator := [:a :b | a > b].

   156 !

   157 

   158 initializeFor:maxSizeArg comparator:aBlock

   159     self initializeFor:maxSizeArg.

   160     comparator := aBlock

   161 ! !

   162 

   163 !PriorityQueue methodsFor:'private'!

   164 

   165 contents

   166     "return the current contents.   

   167      It is not sorted by size, but a heap structure"

   168 

   169     ^ heap

   170 !

   171 

   172 downHeap

   173     "an element was added at the bottom of the heap;

   174      shift it to its place"

   175 

   176     |i j k node|

   177 

   178     i := 1.

   179     node := heap at:i.

   180     j := i * 2.

   181     k := j + 1.

   182     ((k <= size) and:[ comparator value:(heap at:j) value:(heap at:k)]) ifTrue:[

   183         j := k

   184     ].

   185 

   186     [ (j <= size) and:[ comparator value:node value:(heap at:j) ]] whileTrue:[

   187         heap at:i put:(heap at:j).

   188         i := j.

   189         j := j * 2.

   190         k := j + 1.

   191         ((k <= size) and:[ comparator value:(heap at:j) value:(heap at:k)]) ifTrue:[

   192             j := k

   193         ].

   194     ].

   195     heap at:i put:node

   196 !

   197 

   198 upHeap

   199     "an element was added to the top of the heap;

   200      shift it to its place"

   201 

   202     |i j node|

   203 

   204     i := size.

   205     node := heap at:i.

   206     j := i // 2.

   207     [ (j > 0) and:[ comparator value:(heap at:j) value:node ]] whileTrue:[

   208         heap at:i put:(heap at:j).

   209         i := j.

   210         j := j // 2

   211     ].

   212     heap at:i put:node

   213 ! !

   214 

   215 !PriorityQueue methodsFor:'removing'!

   216 

   217 removeAll

   218     size := 0

   219 !

   220 

   221 removeFirst

   222     "removes and returns the smallest element from the priority queue"

   223 

   224     |rslt|

   225 

   226     size == 0 ifTrue:[ self emptyCollectionError ].

   227 

   228     rslt := heap at:1.

   229     heap at:1 put:(heap at:size).

   230     size := size - 1.

   231     self downHeap.

   232     ^ rslt

   233 ! !

   234 

   235 !PriorityQueue class methodsFor:'documentation'!

   236 

   237 version

   238     ^ '$Header$'

   239 !

   240 

   241 version_CVS

   242     ^ '$Header$'

   243 ! !

   244