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