4523
|
1 |
"{ Encoding: utf8 }"
|
|
2 |
|
5371
|
3 |
"
|
|
4 |
COPYRIGHT (c) 2018 by eXept Software AG
|
|
5 |
All Rights Reserved
|
|
6 |
|
|
7 |
This software is furnished under a license and may be used
|
|
8 |
only in accordance with the terms of that license and with the
|
|
9 |
inclusion of the above copyright notice. This software may not
|
|
10 |
be provided or otherwise made available to, or used by, any
|
|
11 |
other person. No title to or ownership of the software is
|
|
12 |
hereby transferred.
|
|
13 |
"
|
3600
|
14 |
"{ Package: 'stx:libbasic2' }"
|
|
15 |
|
|
16 |
"{ NameSpace: Smalltalk }"
|
|
17 |
|
|
18 |
Collection subclass:#PriorityQueue
|
|
19 |
instanceVariableNames:'size maxSize heap comparator'
|
|
20 |
classVariableNames:''
|
|
21 |
poolDictionaries:''
|
|
22 |
category:'Collections-Ordered'
|
|
23 |
!
|
|
24 |
|
|
25 |
!PriorityQueue class methodsFor:'documentation'!
|
|
26 |
|
5371
|
27 |
copyright
|
|
28 |
"
|
|
29 |
COPYRIGHT (c) 2018 by eXept Software AG
|
|
30 |
All Rights Reserved
|
|
31 |
|
|
32 |
This software is furnished under a license and may be used
|
|
33 |
only in accordance with the terms of that license and with the
|
|
34 |
inclusion of the above copyright notice. This software may not
|
|
35 |
be provided or otherwise made available to, or used by, any
|
|
36 |
other person. No title to or ownership of the software is
|
|
37 |
hereby transferred.
|
|
38 |
"
|
|
39 |
!
|
|
40 |
|
3600
|
41 |
documentation
|
|
42 |
"
|
|
43 |
a priority queue is a collection with a given maximum size
|
|
44 |
which only keeps the maxSize largest values.
|
|
45 |
Only up to maxSize elements are stored at any time.
|
4149
|
46 |
The internal organization is a heap;
|
|
47 |
eg. elements are not kept sorted internally.
|
3600
|
48 |
|
4149
|
49 |
When elements are added, a check is made,
|
|
50 |
if the new element should be kept or not.
|
3600
|
51 |
|
|
52 |
Finally, when all elements have been added,
|
|
53 |
get the elements in sorted order by repeated calls to removeFirst,
|
|
54 |
which will remove and return the smallest element.
|
4149
|
55 |
|
|
56 |
[author:]
|
|
57 |
Claus Gittinger
|
3600
|
58 |
"
|
|
59 |
!
|
|
60 |
|
|
61 |
examples
|
|
62 |
"
|
4149
|
63 |
find the 10 largest files in the stx source tree
|
3600
|
64 |
[exBegin]
|
|
65 |
|pq dir|
|
|
66 |
|
|
67 |
pq := PriorityQueue new:10 comparator:[:a :b | a fileSize > b fileSize].
|
|
68 |
dir := '../../' asFilename.
|
|
69 |
dir directoryContentsAsFilenamesDo:[:eachLib |
|
|
70 |
(eachLib baseName startsWith:'lib') ifTrue:[
|
|
71 |
eachLib filesWithSuffix:'st' do:[:fn |
|
|
72 |
pq add:fn
|
|
73 |
].
|
|
74 |
].
|
|
75 |
].
|
|
76 |
[ pq notEmpty ] whileTrue:[
|
|
77 |
|next|
|
|
78 |
|
|
79 |
next := pq removeFirst.
|
|
80 |
Transcript show:next fileSize; space; showCR:next pathName
|
|
81 |
].
|
|
82 |
[exEnd]
|
|
83 |
|
4149
|
84 |
generate 1 million random numbers and show the 10 largest
|
3600
|
85 |
[exBegin]
|
|
86 |
|pq|
|
|
87 |
|
|
88 |
pq := PriorityQueue new:10.
|
|
89 |
1000000 timesRepeat:[
|
|
90 |
pq add:(Random nextInteger).
|
|
91 |
].
|
|
92 |
[ pq notEmpty ] whileTrue:[
|
|
93 |
Transcript showCR:pq removeFirst.
|
|
94 |
].
|
|
95 |
[exEnd]
|
|
96 |
|
4149
|
97 |
a little test
|
3600
|
98 |
[exBegin]
|
|
99 |
|pq|
|
|
100 |
|
|
101 |
#(10 20 30 40 50 60 70 80) permutationsDo:[:p |
|
|
102 |
pq := PriorityQueue new:5.
|
|
103 |
pq addAll:p.
|
|
104 |
self assert:(pq contents copy sort = #(40 50 60 70 80)).
|
|
105 |
].
|
|
106 |
[exEnd]
|
|
107 |
"
|
|
108 |
! !
|
|
109 |
|
|
110 |
!PriorityQueue class methodsFor:'instance creation'!
|
|
111 |
|
|
112 |
new:maxSize
|
|
113 |
"retun a new PriorityQueue, which holds at most maxNode elements,
|
|
114 |
the largest one's added"
|
|
115 |
|
|
116 |
^ self new initializeFor:maxSize
|
|
117 |
!
|
|
118 |
|
|
119 |
new:maxSize comparator:aBlock
|
|
120 |
"retun a new PriorityQueue, which holds at most maxNode elements,
|
|
121 |
the largest one's added"
|
|
122 |
|
|
123 |
^ self new initializeFor:maxSize comparator:aBlock
|
4523
|
124 |
!
|
|
125 |
|
|
126 |
newWithCapacity:size
|
|
127 |
"return a new empty Collection with capacity for n elements."
|
|
128 |
|
|
129 |
^ self new:size
|
|
130 |
|
|
131 |
"Created: / 10-10-2017 / 17:52:55 / stefan"
|
3600
|
132 |
! !
|
|
133 |
|
|
134 |
!PriorityQueue methodsFor:'adding'!
|
|
135 |
|
|
136 |
add:anElement
|
|
137 |
"if the argument is larger than the currently smallest element,
|
|
138 |
then add it and remove the smallest.
|
|
139 |
Otherwise do nothing"
|
|
140 |
|
|
141 |
size < maxSize ifTrue:[
|
|
142 |
size := size + 1.
|
|
143 |
heap at:size put:anElement.
|
|
144 |
self upHeap.
|
|
145 |
] ifFalse:[
|
|
146 |
(comparator value:anElement value:(heap at:1)) ifTrue:[
|
|
147 |
heap at:1 put:anElement.
|
|
148 |
self downHeap.
|
|
149 |
].
|
|
150 |
]
|
|
151 |
|
|
152 |
"
|
|
153 |
|pq|
|
|
154 |
|
|
155 |
pq := PriorityQueue new:5.
|
|
156 |
pq add:1.
|
|
157 |
pq add:10.
|
|
158 |
pq add:5.
|
|
159 |
pq add:9.
|
|
160 |
pq add:17.
|
|
161 |
pq add:-1.
|
|
162 |
pq add:29.
|
|
163 |
pq
|
|
164 |
"
|
|
165 |
!
|
|
166 |
|
|
167 |
isEmpty
|
|
168 |
^ size == 0
|
|
169 |
!
|
|
170 |
|
|
171 |
size
|
|
172 |
^ size
|
|
173 |
! !
|
|
174 |
|
|
175 |
!PriorityQueue methodsFor:'enumerating'!
|
|
176 |
|
|
177 |
do:aBlock
|
|
178 |
heap from:1 to:size do:aBlock
|
|
179 |
! !
|
|
180 |
|
|
181 |
!PriorityQueue methodsFor:'initialization'!
|
|
182 |
|
|
183 |
comparator:aBlock
|
|
184 |
comparator := aBlock
|
|
185 |
!
|
|
186 |
|
|
187 |
initializeFor:maxSizeArg
|
|
188 |
self assert:(maxSizeArg > 0).
|
|
189 |
|
|
190 |
heap := Array new:maxSizeArg.
|
|
191 |
maxSize := maxSizeArg.
|
|
192 |
size := 0.
|
|
193 |
comparator := [:a :b | a > b].
|
|
194 |
!
|
|
195 |
|
|
196 |
initializeFor:maxSizeArg comparator:aBlock
|
|
197 |
self initializeFor:maxSizeArg.
|
|
198 |
comparator := aBlock
|
|
199 |
! !
|
|
200 |
|
|
201 |
!PriorityQueue methodsFor:'private'!
|
|
202 |
|
|
203 |
contents
|
|
204 |
"return the current contents.
|
|
205 |
It is not sorted by size, but a heap structure"
|
|
206 |
|
|
207 |
^ heap
|
|
208 |
!
|
|
209 |
|
|
210 |
downHeap
|
|
211 |
"an element was added at the bottom of the heap;
|
|
212 |
shift it to its place"
|
|
213 |
|
|
214 |
|i j k node|
|
|
215 |
|
|
216 |
i := 1.
|
|
217 |
node := heap at:i.
|
|
218 |
j := i * 2.
|
|
219 |
k := j + 1.
|
|
220 |
((k <= size) and:[ comparator value:(heap at:j) value:(heap at:k)]) ifTrue:[
|
|
221 |
j := k
|
|
222 |
].
|
|
223 |
|
|
224 |
[ (j <= size) and:[ comparator value:node value:(heap at:j) ]] whileTrue:[
|
|
225 |
heap at:i put:(heap at:j).
|
|
226 |
i := j.
|
|
227 |
j := j * 2.
|
|
228 |
k := j + 1.
|
|
229 |
((k <= size) and:[ comparator value:(heap at:j) value:(heap at:k)]) ifTrue:[
|
|
230 |
j := k
|
|
231 |
].
|
|
232 |
].
|
|
233 |
heap at:i put:node
|
|
234 |
!
|
|
235 |
|
|
236 |
upHeap
|
|
237 |
"an element was added to the top of the heap;
|
|
238 |
shift it to its place"
|
|
239 |
|
|
240 |
|i j node|
|
|
241 |
|
|
242 |
i := size.
|
|
243 |
node := heap at:i.
|
|
244 |
j := i // 2.
|
|
245 |
[ (j > 0) and:[ comparator value:(heap at:j) value:node ]] whileTrue:[
|
|
246 |
heap at:i put:(heap at:j).
|
|
247 |
i := j.
|
|
248 |
j := j // 2
|
|
249 |
].
|
|
250 |
heap at:i put:node
|
|
251 |
! !
|
|
252 |
|
|
253 |
!PriorityQueue methodsFor:'removing'!
|
|
254 |
|
|
255 |
removeAll
|
|
256 |
size := 0
|
|
257 |
!
|
|
258 |
|
|
259 |
removeFirst
|
|
260 |
"removes and returns the smallest element from the priority queue"
|
|
261 |
|
|
262 |
|rslt|
|
|
263 |
|
|
264 |
size == 0 ifTrue:[ self emptyCollectionError ].
|
|
265 |
|
|
266 |
rslt := heap at:1.
|
|
267 |
heap at:1 put:(heap at:size).
|
|
268 |
size := size - 1.
|
|
269 |
self downHeap.
|
|
270 |
^ rslt
|
|
271 |
! !
|
|
272 |
|
|
273 |
!PriorityQueue class methodsFor:'documentation'!
|
|
274 |
|
|
275 |
version
|
|
276 |
^ '$Header$'
|
|
277 |
!
|
|
278 |
|
|
279 |
version_CVS
|
|
280 |
^ '$Header$'
|
|
281 |
! !
|
|
282 |
|