author | Claus Gittinger <cg@exept.de> |
Sat, 02 May 2020 21:40:13 +0200 | |
changeset 5476 | 7355a4b11cb6 |
parent 5431 | bf9f5c42a067 |
permissions | -rw-r--r-- |
4976 | 1 |
"{ Encoding: utf8 }" |
2 |
||
5 | 3 |
" |
4 |
COPYRIGHT (c) 1993 by Claus Gittinger |
|
47 | 5 |
All Rights Reserved |
5 | 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 |
" |
|
903 | 14 |
"{ Package: 'stx:libbasic2' }" |
15 |
||
4035 | 16 |
"{ NameSpace: Smalltalk }" |
17 |
||
30 | 18 |
Collection subclass:#Queue |
254 | 19 |
instanceVariableNames:'contentsArray readPosition writePosition tally' |
20 |
classVariableNames:'' |
|
21 |
poolDictionaries:'' |
|
22 |
category:'Collections-Ordered' |
|
5 | 23 |
! |
24 |
||
582 | 25 |
!Queue class methodsFor:'documentation'! |
30 | 26 |
|
27 |
copyright |
|
28 |
" |
|
29 |
COPYRIGHT (c) 1993 by Claus Gittinger |
|
47 | 30 |
All Rights Reserved |
5 | 31 |
|
30 | 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 |
||
41 |
documentation |
|
42 |
" |
|
4064 | 43 |
Queues provide a simple implementation of a collection, |
1245 | 44 |
where elements are added at one end and removed at the other. |
3448 | 45 |
|
4064 | 46 |
Access protocol is somewhat like a stream's protocol, |
47 |
i.e. access is by #nextPut: and #next. |
|
48 |
||
74 | 49 |
The queue is created with a size argument, defining how many elements |
50 |
are to be stored. It will report an error if the queue ever becomes full |
|
4064 | 51 |
and another element is to be added. |
52 |
Likewise, it will report an error if it is empty and an element is to be removed. |
|
74 | 53 |
|
4151 | 54 |
It is NOT safe when two processes access the same queue-instance simultaneously, |
74 | 55 |
since accesses to the internals are not protected against process-switches. |
4064 | 56 |
See SharedQueue for a class which IS safe w.r.t. processes and which blocks |
74 | 57 |
on write when full or on read when empty. |
254 | 58 |
|
587 | 59 |
[Implementation note:] |
3448 | 60 |
All of queue's functionality is also provided by the OrderedCollection (OC) |
587 | 61 |
class; OC could easily simulate a queue (using #addLast: / #removeFirst). |
4035 | 62 |
The reason for providing Queue is not any speed advantage |
63 |
(actually, OC seems to be even a tiny bit faster). |
|
587 | 64 |
The point is that an implementation of SharedQueue as a subclass of OC |
65 |
would require that many OC methods had to be blocked and/or redefined in |
|
66 |
such a subclass, to care for simultaneous access. |
|
4035 | 67 |
Since queue implements a much more lightweight protocol, |
4064 | 68 |
the sharedQueue implementation is much cleaner when based on this more |
587 | 69 |
lightweight Queue class. |
4035 | 70 |
|
254 | 71 |
[author:] |
72 |
Claus Gittinger |
|
30 | 73 |
" |
587 | 74 |
! |
75 |
||
76 |
examples |
|
77 |
" |
|
78 |
adding at one end, removing at the other ... |
|
79 |
[exBegin] |
|
80 |
|q element | |
|
81 |
||
82 |
q := Queue new:10. |
|
4035 | 83 |
1 to:5 do:[:i | |
587 | 84 |
Transcript showCR:('adding ' , i printString). |
85 |
q nextPut:i |
|
86 |
]. |
|
87 |
||
88 |
[q notEmpty] whileTrue:[ |
|
89 |
element := q next. |
|
90 |
Transcript showCR:('removed ' , element printString). |
|
91 |
]. |
|
92 |
[exEnd] |
|
93 |
||
94 |
||
95 |
||
96 |
timing; Queue vs. OrderedCollection |
|
97 |
[exBegin] |
|
98 |
|q oc tQueue tOC | |
|
99 |
||
100 |
q := Queue new:100. |
|
101 |
tQueue := Time millisecondsToRun:[ |
|
102 |
1000 timesRepeat:[ |
|
4035 | 103 |
1 to:100 do:[:i | |
587 | 104 |
q nextPut:i |
105 |
]. |
|
106 |
[q isEmpty] whileFalse:[ |
|
107 |
q next |
|
108 |
]. |
|
109 |
] |
|
110 |
]. |
|
111 |
||
112 |
oc := OrderedCollection new:100. |
|
113 |
tOC := Time millisecondsToRun:[ |
|
114 |
1000 timesRepeat:[ |
|
4035 | 115 |
1 to:100 do:[:i | |
587 | 116 |
oc addLast:i |
117 |
]. |
|
118 |
[oc isEmpty] whileFalse:[ |
|
119 |
oc removeFirst |
|
120 |
]. |
|
121 |
] |
|
122 |
]. |
|
123 |
Transcript showCR:('queue time: ' , tQueue printString , ' ms'). |
|
124 |
Transcript showCR:('oc time : ' , tOC printString , ' ms'). |
|
125 |
[exEnd] |
|
126 |
||
127 |
||
128 |
" |
|
30 | 129 |
! ! |
5 | 130 |
|
582 | 131 |
!Queue class methodsFor:'instance creation'! |
5 | 132 |
|
122 | 133 |
new |
134 |
"return a new queue with space for some elements" |
|
135 |
||
136 |
^ self new:50 |
|
137 |
! |
|
138 |
||
5 | 139 |
new:size |
140 |
"return a new queue with space for size elements" |
|
141 |
||
142 |
^ super new init:size |
|
143 |
||
144 |
" |
|
145 |
|q| |
|
146 |
||
147 |
q := Queue new. |
|
39 | 148 |
(1 to:5) do:[:i | q nextPut:i]. |
149 |
Transcript show:(q next); space. |
|
150 |
Transcript show:(q next); space. |
|
151 |
Transcript show:(q next); space. |
|
152 |
Transcript show:(q next); space. |
|
153 |
q nextPutAll:(6 to:10). |
|
154 |
Transcript show:(q next); space. |
|
155 |
Transcript show:(q next); space. |
|
156 |
Transcript show:(q next); space. |
|
157 |
Transcript show:(q next); space. |
|
158 |
Transcript show:(q next); space. |
|
159 |
Transcript show:(q next); space. |
|
160 |
Transcript show:(q next); space. |
|
161 |
Transcript show:(q next); space. |
|
162 |
Transcript show:(q next); space. |
|
350 | 163 |
Transcript showCR:(q next). |
5 | 164 |
" |
165 |
! ! |
|
166 |
||
2361 | 167 |
!Queue class methodsFor:'defaults'! |
168 |
||
169 |
defaultSize |
|
170 |
^ 50 |
|
171 |
! ! |
|
172 |
||
5 | 173 |
!Queue methodsFor:'accessing'! |
174 |
||
2163 | 175 |
at:index |
176 |
"return an element from the queue - indexing starts at 1 with the element |
|
177 |
which would next be fetched" |
|
178 |
||
179 |
(index between:1 and:tally) ifFalse:[ self subscriptBoundsError:index ]. |
|
180 |
^ contentsArray at:((readPosition+index-1-1) \\ contentsArray size)+1. |
|
181 |
||
182 |
" |
|
183 |
|q| |
|
184 |
||
185 |
q := Queue new:10. |
|
186 |
(1 to:5) do:[:i | q add:i]. |
|
187 |
(6 to:100) do:[:i | q removeFirst. q add:i ]. |
|
2164 | 188 |
self assert:(q at:1) = 96. |
189 |
self assert:(q at:2) = 97. |
|
190 |
self assert:(q at:3) = 98. |
|
191 |
self assert:(q at:4) = 99. |
|
192 |
self assert:(q at:5) = 100. |
|
193 |
self should:[ q at:6 ] raise:Error. |
|
2163 | 194 |
" |
195 |
! |
|
196 |
||
4345 | 197 |
remove:anElement ifAbsent:exceptionalValue |
198 |
"remove and return a particular element from the queue; |
|
199 |
Return the value from exceptionalValue if the element is not in the queue" |
|
200 |
||
201 |
|rPos "{ Class: SmallInteger }" |
|
202 |
wPos "{ Class: SmallInteger }" |
|
203 |
countRemoved |
|
204 |
el sz| |
|
205 |
||
206 |
||
207 |
(tally == 0) ifTrue:[ |
|
208 |
^ exceptionalValue value |
|
209 |
]. |
|
210 |
sz := contentsArray size. |
|
211 |
||
212 |
rPos := wPos := readPosition. |
|
213 |
||
214 |
countRemoved := 0. |
|
215 |
||
216 |
1 to:tally do:[:index| |
|
217 |
el := contentsArray at:rPos. |
|
218 |
el = anElement ifTrue:[ |
|
219 |
countRemoved := countRemoved + 1. |
|
220 |
contentsArray at:wPos put:nil. |
|
221 |
] ifFalse:[ |
|
222 |
rPos ~~ wPos ifTrue:[ |
|
223 |
contentsArray at:wPos put:el. |
|
224 |
]. |
|
225 |
wPos == sz ifTrue:[ |
|
226 |
wPos := 1. |
|
227 |
] ifFalse:[ |
|
228 |
wPos := wPos + 1. |
|
229 |
]. |
|
230 |
]. |
|
231 |
rPos == sz ifTrue:[ |
|
232 |
rPos := 1. |
|
233 |
] ifFalse:[ |
|
234 |
rPos := rPos + 1. |
|
235 |
]. |
|
236 |
]. |
|
237 |
countRemoved == 0 ifTrue:[ |
|
238 |
^ exceptionalValue value |
|
239 |
]. |
|
240 |
||
241 |
tally = countRemoved ifTrue:[ |
|
242 |
wPos := readPosition. |
|
243 |
]. |
|
244 |
writePosition := wPos. |
|
245 |
tally := tally - countRemoved. |
|
246 |
^ el |
|
247 |
||
248 |
" |
|
249 |
|q| |
|
250 |
||
251 |
q := Queue new:10. |
|
252 |
q nextPut:1; nextPut:2; nextPutAll:(3 to:10). |
|
253 |
q next. |
|
254 |
q nextPut:11. |
|
255 |
q next. |
|
256 |
q nextPut:12. |
|
257 |
q next. |
|
258 |
q remove:5. |
|
259 |
q |
|
260 |
||
261 |
|q| |
|
262 |
||
263 |
q := Queue new:10. |
|
264 |
q nextPut:1; nextPut:2; nextPutAll:(3 to:8). |
|
265 |
self assert:(q next == 1). |
|
266 |
self assert:(q next == 2). |
|
267 |
q removeIdentical:5. |
|
268 |
self assert:(q next == 3). |
|
269 |
self assert:(q next == 4). |
|
270 |
self assert:(q next == 6). |
|
271 |
self assert:(q next == 7). |
|
272 |
self assert:(q next == 8). |
|
273 |
self assert:(q isEmpty). |
|
274 |
q |
|
275 |
||
276 |
|q| |
|
277 |
||
278 |
q := Queue new:10. |
|
279 |
q nextPut:1; nextPut:2. |
|
280 |
self assert:(q next == 1). |
|
281 |
q remove:2. |
|
282 |
self assert:(q isEmpty). |
|
283 |
q nextPut:3. |
|
284 |
self assert:(q isEmpty not). |
|
285 |
self assert:(q next == 3). |
|
286 |
self assert:(q isEmpty). |
|
287 |
||
288 |
|q| |
|
289 |
||
290 |
q := Queue new:10. |
|
291 |
q nextPut:1; nextPut:2; nextPut:3. |
|
292 |
self assert:(q next == 1). |
|
293 |
q remove:3. |
|
294 |
self assert:(q isEmpty not). |
|
295 |
q nextPut:4. |
|
296 |
q removeI:4. |
|
297 |
q nextPut:5. |
|
298 |
self assert:(q isEmpty not). |
|
299 |
self assert:(q next == 2). |
|
300 |
self assert:(q next == 5). |
|
301 |
self assert:(q isEmpty). |
|
302 |
" |
|
303 |
||
304 |
"Created: / 22-02-2017 / 14:49:26 / stefan" |
|
305 |
! |
|
306 |
||
647 | 307 |
removeAll |
742 | 308 |
"remove all elements in the queue; return the receiver" |
647 | 309 |
|
310 |
tally := 0. |
|
311 |
readPosition := writePosition := 1. |
|
312 |
contentsArray atAllPut:nil "/ to help the garbage collector |
|
313 |
! |
|
314 |
||
1494 | 315 |
removeIdentical:anElement ifAbsent:exceptionalValue |
4064 | 316 |
"remove and return a particular element from the queue; |
317 |
Return the value from exceptionalValue if the element is not in the queue" |
|
318 |
||
1494 | 319 |
|rPos "{ Class: SmallInteger }" |
320 |
wPos "{ Class: SmallInteger }" |
|
321 |
countRemoved |
|
322 |
el sz| |
|
323 |
||
4035 | 324 |
|
1497 | 325 |
(tally == 0) ifTrue:[ |
326 |
^ exceptionalValue value |
|
327 |
]. |
|
1494 | 328 |
sz := contentsArray size. |
329 |
||
330 |
rPos := wPos := readPosition. |
|
331 |
||
332 |
countRemoved := 0. |
|
1497 | 333 |
|
334 |
1 to:tally do:[:index| |
|
1494 | 335 |
el := contentsArray at:rPos. |
336 |
el == anElement ifTrue:[ |
|
337 |
countRemoved := countRemoved + 1. |
|
1497 | 338 |
contentsArray at:wPos put:nil. |
1494 | 339 |
] ifFalse:[ |
340 |
rPos ~~ wPos ifTrue:[ |
|
341 |
contentsArray at:wPos put:el. |
|
342 |
]. |
|
343 |
wPos == sz ifTrue:[ |
|
344 |
wPos := 1. |
|
345 |
] ifFalse:[ |
|
346 |
wPos := wPos + 1. |
|
347 |
]. |
|
4035 | 348 |
]. |
1494 | 349 |
rPos == sz ifTrue:[ |
350 |
rPos := 1. |
|
351 |
] ifFalse:[ |
|
352 |
rPos := rPos + 1. |
|
353 |
]. |
|
354 |
]. |
|
355 |
countRemoved == 0 ifTrue:[ |
|
356 |
^ exceptionalValue value |
|
357 |
]. |
|
358 |
||
1497 | 359 |
tally = countRemoved ifTrue:[ |
360 |
wPos := readPosition. |
|
361 |
]. |
|
1494 | 362 |
writePosition := wPos. |
363 |
tally := tally - countRemoved. |
|
364 |
^ anElement |
|
365 |
||
366 |
" |
|
367 |
|q| |
|
368 |
||
369 |
q := Queue new:10. |
|
370 |
q nextPut:1; nextPut:2; nextPutAll:(3 to:10). |
|
371 |
q next. |
|
372 |
q nextPut:11. |
|
373 |
q next. |
|
374 |
q nextPut:12. |
|
375 |
q next. |
|
4035 | 376 |
q removeIdentical:5. |
1497 | 377 |
q |
378 |
||
379 |
|q| |
|
380 |
||
381 |
q := Queue new:10. |
|
382 |
q nextPut:1; nextPut:2; nextPutAll:(3 to:8). |
|
383 |
self assert:(q next == 1). |
|
384 |
self assert:(q next == 2). |
|
385 |
q removeIdentical:5. |
|
386 |
self assert:(q next == 3). |
|
387 |
self assert:(q next == 4). |
|
388 |
self assert:(q next == 6). |
|
389 |
self assert:(q next == 7). |
|
390 |
self assert:(q next == 8). |
|
391 |
self assert:(q isEmpty). |
|
4035 | 392 |
q |
1497 | 393 |
|
394 |
|q| |
|
395 |
||
396 |
q := Queue new:10. |
|
397 |
q nextPut:1; nextPut:2. |
|
398 |
self assert:(q next == 1). |
|
399 |
q removeIdentical:2. |
|
400 |
self assert:(q isEmpty). |
|
401 |
q nextPut:3. |
|
402 |
self assert:(q isEmpty not). |
|
403 |
self assert:(q next == 3). |
|
404 |
self assert:(q isEmpty). |
|
405 |
||
406 |
|q| |
|
407 |
||
408 |
q := Queue new:10. |
|
409 |
q nextPut:1; nextPut:2; nextPut:3. |
|
410 |
self assert:(q next == 1). |
|
411 |
q removeIdentical:3. |
|
412 |
self assert:(q isEmpty not). |
|
413 |
q nextPut:4. |
|
414 |
q removeIdentical:4. |
|
415 |
q nextPut:5. |
|
416 |
self assert:(q isEmpty not). |
|
417 |
self assert:(q next == 2). |
|
418 |
self assert:(q next == 5). |
|
419 |
self assert:(q isEmpty). |
|
420 |
||
1494 | 421 |
" |
422 |
! |
|
423 |
||
396 | 424 |
removeLast |
4064 | 425 |
"remove and return the last value in the queue; |
396 | 426 |
Return nil, if the queue is empty" |
427 |
||
428 |
|value pos "{ Class: SmallInteger }"| |
|
429 |
||
430 |
(tally == 0) ifTrue:[^ nil]. |
|
431 |
||
432 |
pos := writePosition. |
|
433 |
pos == 1 ifTrue:[ |
|
434 |
pos := contentsArray size |
|
435 |
] ifFalse:[ |
|
436 |
pos := pos - 1. |
|
437 |
]. |
|
438 |
||
439 |
value := contentsArray at:pos. |
|
647 | 440 |
contentsArray at:pos put:nil. "/ to help the garbage collector |
396 | 441 |
writePosition := pos. |
442 |
tally := tally - 1. |
|
443 |
^ value |
|
444 |
||
445 |
"Created: 22.6.1996 / 18:49:41 / cg" |
|
39 | 446 |
! ! |
447 |
||
903 | 448 |
!Queue methodsFor:'accessing-protocol compatibility'! |
686
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
449 |
|
1918
38fa135c92ef
Clean up code and document differences between #add: and #addLast:
Stefan Vogel <sv@exept.de>
parents:
1497
diff
changeset
|
450 |
add:someObject |
904 | 451 |
"same as #nextPut: - for protocol compatibility with other collections" |
686
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
452 |
|
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
453 |
self nextPut:someObject. |
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
454 |
^ someObject |
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
455 |
! |
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
456 |
|
4345 | 457 |
addFirst:someObject |
458 |
"same as #nextPutFirst: - for protocol compatibility with other collections" |
|
459 |
||
460 |
self nextPutFirst:someObject. |
|
461 |
^ someObject |
|
462 |
||
463 |
"Created: / 22-02-2017 / 15:12:58 / stefan" |
|
464 |
! |
|
465 |
||
686
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
466 |
removeFirst |
904 | 467 |
"same as #next - for protocol compatibility with other collections" |
686
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
468 |
|
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
469 |
^ self next |
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
470 |
|
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
471 |
"Created: / 27.8.1998 / 11:15:48 / cg" |
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
472 |
! ! |
d2daab8e8c8a
added #addLast: and #removeFirst for protocoll compatibility
Claus Gittinger <cg@exept.de>
parents:
647
diff
changeset
|
473 |
|
4067 | 474 |
!Queue methodsFor:'accessing-reading'! |
475 |
||
476 |
next |
|
477 |
"return the next value in the queue; |
|
478 |
Return nil, if the queue is empty. |
|
479 |
WARNING: this is an old behavior, which should be changed |
|
480 |
to raise an error if empty. |
|
481 |
It is left in here until all queue-users have been changed to |
|
482 |
call nextOrNil instead, to avoid breaking existing applications." |
|
483 |
||
484 |
^ self nextOrNil |
|
485 |
! |
|
486 |
||
487 |
nextOrNil |
|
488 |
"return the next value in the queue; |
|
489 |
Return nil, if the queue is empty" |
|
490 |
||
491 |
|value pos "{ Class: SmallInteger }"| |
|
492 |
||
493 |
(tally == 0) ifTrue:[^ nil]. |
|
494 |
||
495 |
pos := readPosition. |
|
496 |
||
497 |
value := contentsArray at:pos. |
|
498 |
contentsArray at:pos put:nil. "/ to help the garbage collector |
|
499 |
pos := pos + 1. |
|
500 |
pos > contentsArray size ifTrue:[pos := 1]. |
|
501 |
readPosition := pos. |
|
502 |
tally := tally - 1. |
|
503 |
^ value |
|
504 |
! |
|
505 |
||
506 |
peek |
|
507 |
"return the next value in the queue without removing it. |
|
508 |
If the queue is empty, return nil." |
|
509 |
||
510 |
(tally == 0) ifTrue:[^ nil]. |
|
511 |
^ contentsArray at:readPosition. |
|
512 |
! |
|
513 |
||
514 |
peekOrNil |
|
515 |
"return the next value in the queue without removing it. |
|
516 |
If the queue is empty, return nil." |
|
517 |
||
518 |
(tally == 0) ifTrue:[^ nil]. |
|
519 |
^ contentsArray at:readPosition. |
|
520 |
! ! |
|
521 |
||
522 |
!Queue methodsFor:'accessing-writing'! |
|
523 |
||
524 |
nextPut:anObject |
|
5187 | 525 |
"enter anObject into the queue - if the queue is full, report an error. |
526 |
Answer anObject" |
|
4067 | 527 |
|
528 |
|sz pos "{ Class: SmallInteger }" | |
|
529 |
||
530 |
sz := contentsArray size. |
|
531 |
pos := writePosition. |
|
532 |
||
533 |
(tally == sz) ifTrue:[ |
|
534 |
self error:'queue is full' mayProceed:true. |
|
5170 | 535 |
^ anObject |
4067 | 536 |
]. |
537 |
||
538 |
contentsArray at:pos put:anObject. |
|
539 |
pos := pos + 1. |
|
540 |
pos > sz ifTrue:[pos := 1]. |
|
541 |
writePosition := pos. |
|
542 |
tally := tally + 1. |
|
5170 | 543 |
^ anObject |
4347 | 544 |
|
545 |
"Modified: / 22-02-2017 / 16:33:22 / stefan" |
|
4067 | 546 |
! |
547 |
||
548 |
nextPutAll:aCollection |
|
5155 | 549 |
"enter all elements from aCollection into the queue. |
550 |
Answer the receiver" |
|
4067 | 551 |
|
552 |
aCollection do:[:element | self nextPut:element]. |
|
553 |
^ self |
|
554 |
! |
|
555 |
||
556 |
nextPutFirst:anObject |
|
557 |
|sz pos "{ Class: SmallInteger }" | |
|
558 |
||
559 |
tally == 0 ifTrue:[ |
|
560 |
self nextPut:anObject. |
|
561 |
^ self |
|
562 |
]. |
|
563 |
||
564 |
sz := contentsArray size. |
|
565 |
(tally == sz) ifTrue:[ |
|
566 |
self error:'queue is full' mayProceed:true. |
|
567 |
^ self |
|
568 |
]. |
|
569 |
pos := readPosition - 1. |
|
570 |
pos < 1 ifTrue:[pos := sz]. |
|
571 |
contentsArray at:pos put:anObject. |
|
572 |
readPosition := pos. |
|
573 |
||
574 |
tally := tally + 1 |
|
575 |
! ! |
|
576 |
||
50 | 577 |
!Queue methodsFor:'enumerating'! |
39 | 578 |
|
579 |
do:aBlock |
|
580 |
"evaluate the argument, aBlock for each element in the queue" |
|
581 |
||
582 | 582 |
|n "{ Class: SmallInteger }" |
4345 | 583 |
pos "{ Class: SmallInteger }" |
584 |
sz| |
|
39 | 585 |
|
586 |
pos := readPosition. |
|
4345 | 587 |
sz := contentsArray size. |
582 | 588 |
n := tally. |
4345 | 589 |
n timesRepeat:[ |
582 | 590 |
aBlock value:(contentsArray at:pos). |
591 |
pos := pos + 1. |
|
4345 | 592 |
pos > sz ifTrue:[ |
593 |
pos := 1. |
|
582 | 594 |
] |
39 | 595 |
] |
582 | 596 |
|
4345 | 597 |
"Modified: / 18-10-1997 / 16:24:01 / cg" |
598 |
"Modified (format): / 22-02-2017 / 14:59:38 / stefan" |
|
599 |
! |
|
600 |
||
601 |
reverseDo:aBlock |
|
602 |
"evaluate the argument, aBlock for each element in the queue" |
|
603 |
||
604 |
|n "{ Class: SmallInteger }" |
|
605 |
pos "{ Class: SmallInteger }" |
|
606 |
sz| |
|
607 |
||
608 |
pos := writePosition. |
|
609 |
sz := contentsArray size. |
|
610 |
n := tally. |
|
611 |
n timesRepeat:[ |
|
612 |
pos := pos - 1. |
|
613 |
pos <= 0 ifTrue:[ |
|
614 |
pos := sz. |
|
615 |
]. |
|
616 |
aBlock value:(contentsArray at:pos). |
|
617 |
]. |
|
618 |
||
619 |
" |
|
620 |
|q coll| |
|
621 |
||
622 |
coll := OrderedCollection new. |
|
623 |
q := Queue new:10. |
|
624 |
q nextPut:1; nextPut:2; nextPutAll:(3 to:8). |
|
625 |
q removeFirst; removeLast. |
|
626 |
q reverseDo:[:el| coll add:el]. |
|
627 |
coll. |
|
628 |
" |
|
629 |
||
630 |
"Created: / 22-02-2017 / 15:03:02 / stefan" |
|
5 | 631 |
! ! |
632 |
||
122 | 633 |
!Queue methodsFor:'initialization'! |
634 |
||
4064 | 635 |
capacity:newSize |
636 |
"change the capacity of the queue. |
|
4976 | 637 |
That is the number of slots it can hold |
638 |
before the writer gets an exception (here) |
|
639 |
or is suspended (in SharedQueue)." |
|
4064 | 640 |
|
641 |
|newContentsArray n1 n2| |
|
642 |
||
643 |
newSize < tally ifTrue:[ |
|
644 |
"/ cannot make me smaller, if I hold at least this number of elements. |
|
645 |
self error:'queue cannot be resized to this size while holding more elements' mayProceed:true. |
|
646 |
"/ if proceeded |
|
647 |
^ self |
|
648 |
]. |
|
649 |
newContentsArray := Array new:newSize. |
|
650 |
tally ~~ 0 ifTrue:[ |
|
651 |
n1 := contentsArray size - readPosition + 1. |
|
652 |
n1 > tally ifTrue:[ |
|
653 |
newContentsArray replaceFrom:1 to:tally with:contentsArray startingAt:readPosition. |
|
654 |
] ifFalse:[ |
|
655 |
newContentsArray replaceFrom:1 to:n1 with:contentsArray startingAt:readPosition. |
|
656 |
n2 := writePosition - 1. |
|
657 |
newContentsArray replaceFrom:n1+1 to:tally with:contentsArray startingAt:1. |
|
658 |
]. |
|
659 |
]. |
|
660 |
contentsArray := newContentsArray. |
|
661 |
readPosition := 1. |
|
662 |
writePosition := tally+1. |
|
663 |
||
664 |
" |
|
665 |
|q| |
|
666 |
1 to:10 do:[:fill | |
|
667 |
1 to:10 do:[:read | |
|
668 |
Transcript show:'fill: '; show:fill; show:' read: '; showCR:read. |
|
669 |
q := Queue new:10. |
|
670 |
fill timesRepeat:[ q nextPut: #foo ]. |
|
671 |
read timesRepeat:[ q next ]. |
|
672 |
q capacity:12. |
|
673 |
self assert:(q size == (fill-read)). |
|
674 |
self assert:((Array streamContents:[:s | q do:[:e |s nextPut:e]]) = (Array new:(fill-read) withAll:#foo)). |
|
675 |
]. |
|
676 |
]. |
|
677 |
" |
|
4976 | 678 |
|
679 |
"Modified (comment): / 04-06-2019 / 12:37:16 / Claus Gittinger" |
|
4064 | 680 |
! |
681 |
||
122 | 682 |
init:size |
683 |
"initialize the receiver for size entries" |
|
684 |
||
685 |
contentsArray := Array new:size. |
|
686 |
readPosition := writePosition := 1. |
|
687 |
tally := 0. |
|
688 |
! ! |
|
689 |
||
4345 | 690 |
!Queue methodsFor:'not implemented'! |
691 |
||
692 |
findFirst:anObject ifNone:aBlock |
|
693 |
^ self shouldNotImplement. |
|
694 |
||
695 |
"Created: / 22-02-2017 / 15:14:04 / stefan" |
|
696 |
! |
|
697 |
||
698 |
findLast:anObject ifNone:aBlock |
|
699 |
^ self shouldNotImplement. |
|
700 |
||
701 |
"Created: / 22-02-2017 / 15:14:11 / stefan" |
|
702 |
! |
|
703 |
||
704 |
grow:newSize |
|
705 |
^ self shouldNotImplement. |
|
706 |
||
707 |
"Created: / 22-02-2017 / 15:14:58 / stefan" |
|
708 |
! ! |
|
709 |
||
5 | 710 |
!Queue methodsFor:'queries'! |
711 |
||
4035 | 712 |
capacity |
4064 | 713 |
"return the number of elements the queue can hold. |
714 |
Trying to add more will: |
|
715 |
- raise an error in queue |
|
716 |
- block the writer in sharedQueue |
|
717 |
- lead to an automatic resize in UnlimitedSharedQueue" |
|
122 | 718 |
|
719 |
^ contentsArray size |
|
720 |
! |
|
721 |
||
4806 | 722 |
isEmpty |
723 |
"return true, if there are no elements in the queue" |
|
724 |
||
725 |
^ tally == 0 |
|
726 |
! |
|
727 |
||
728 |
isFull |
|
729 |
"return true, if the queue is full i.e. if writing is not |
|
730 |
possible" |
|
731 |
||
732 |
^ tally == contentsArray size |
|
733 |
! |
|
734 |
||
5431 | 735 |
notEmpty |
736 |
"return true, if there are elements in the queue" |
|
737 |
||
738 |
^ tally ~~ 0 |
|
739 |
||
740 |
"Created: / 23-01-2020 / 14:18:33 / stefan" |
|
741 |
! |
|
742 |
||
743 |
notEmptyOrNil |
|
744 |
"return true, if there are elements in the queue" |
|
745 |
||
746 |
^ tally ~~ 0 |
|
747 |
||
748 |
"Created: / 23-01-2020 / 14:18:47 / stefan" |
|
749 |
! |
|
750 |
||
904 | 751 |
size |
752 |
"return the number of elements in the queue" |
|
753 |
||
754 |
^ tally |
|
2148
5fe0c7beef0c
Define #species, so that #collect: and #select return OrderedCollection
Stefan Vogel <sv@exept.de>
parents:
1918
diff
changeset
|
755 |
! |
5fe0c7beef0c
Define #species, so that #collect: and #select return OrderedCollection
Stefan Vogel <sv@exept.de>
parents:
1918
diff
changeset
|
756 |
|
5fe0c7beef0c
Define #species, so that #collect: and #select return OrderedCollection
Stefan Vogel <sv@exept.de>
parents:
1918
diff
changeset
|
757 |
species |
5fe0c7beef0c
Define #species, so that #collect: and #select return OrderedCollection
Stefan Vogel <sv@exept.de>
parents:
1918
diff
changeset
|
758 |
"return the type of collection to be returned by collect, select etc." |
5fe0c7beef0c
Define #species, so that #collect: and #select return OrderedCollection
Stefan Vogel <sv@exept.de>
parents:
1918
diff
changeset
|
759 |
|
5fe0c7beef0c
Define #species, so that #collect: and #select return OrderedCollection
Stefan Vogel <sv@exept.de>
parents:
1918
diff
changeset
|
760 |
^ OrderedCollection |
904 | 761 |
! ! |
762 |
||
763 |
!Queue methodsFor:'testing'! |
|
764 |
||
3021 | 765 |
isFixedSize |
766 |
"return true if the receiver cannot grow" |
|
767 |
||
768 |
^ false |
|
122 | 769 |
! ! |
81 | 770 |
|
582 | 771 |
!Queue class methodsFor:'documentation'! |
131 | 772 |
|
773 |
version |
|
4035 | 774 |
^ '$Header$' |
2361 | 775 |
! |
776 |
||
777 |
version_CVS |
|
4035 | 778 |
^ '$Header$' |
131 | 779 |
! ! |
3021 | 780 |