author | Claus Gittinger <cg@exept.de> |
Thu, 03 Aug 2017 16:41:13 +0200 | |
changeset 22159 | c8f19ee3f888 |
parent 20636 | e3346053cd78 |
child 20727 | fb8c5591428b |
child 23711 | 2f0fb1e83275 |
permissions | -rw-r--r-- |
1 | 1 |
" |
5 | 2 |
COPYRIGHT (c) 1989 by Claus Gittinger |
159 | 3 |
All Rights Reserved |
1 | 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 |
" |
|
5519
925d9a1eda2c
fixed emptyCollection error signaling
Claus Gittinger <cg@exept.de>
parents:
5244
diff
changeset
|
12 |
"{ Package: 'stx:libbasic' }" |
925d9a1eda2c
fixed emptyCollection error signaling
Claus Gittinger <cg@exept.de>
parents:
5244
diff
changeset
|
13 |
|
17262 | 14 |
"{ NameSpace: Smalltalk }" |
15 |
||
1 | 16 |
SequenceableCollection subclass:#LinkedList |
1110 | 17 |
instanceVariableNames:'firstLink lastLink numberOfNodes' |
18 |
classVariableNames:'' |
|
19 |
poolDictionaries:'' |
|
1364 | 20 |
category:'Collections-Linked' |
1 | 21 |
! |
22 |
||
88 | 23 |
!LinkedList class methodsFor:'documentation'! |
24 |
||
25 |
copyright |
|
26 |
" |
|
27 |
COPYRIGHT (c) 1989 by Claus Gittinger |
|
159 | 28 |
All Rights Reserved |
1 | 29 |
|
88 | 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 |
! |
|
1 | 38 |
|
88 | 39 |
documentation |
40 |
" |
|
41 |
this class implements an anchor to a list of Links. |
|
10647 | 42 |
The data itself is held in the link elements. |
243 | 43 |
See (the abstract) Link, ValueLink and (possibly other) classes, |
44 |
which can be used as elements of a linkedList. |
|
45 |
||
360 | 46 |
LinkedList does not care for storage; all it does is handling |
47 |
chained link elements, which must respond to #nextLink/#nextLink:. |
|
17123 | 48 |
(i.e. any object which can do this, can be used as elements of a linked list). |
2146 | 49 |
An abstract superclass for linkElements is Link; a concrete class is |
50 |
ValueLink, which holds a reference to some object. |
|
51 |
||
52 |
[warning:] |
|
13727 | 53 |
Be careful when subclassing Link, since there is a big drawback, |
54 |
which may be overlooked by beginners: |
|
17123 | 55 |
a Link element can ONLY be in one LinkedList at a time |
13727 | 56 |
- adding the same element to another LinkedList |
17123 | 57 |
will remove it from the first as a side effect. |
13727 | 58 |
Therefore, NEVER simply add something to a linkedList (except for |
59 |
valueLinks) unless you know what you do. |
|
60 |
The ST-80 implementors probably wanted this behavior, to move |
|
61 |
processes from the waitingList to runLists and vice versa; |
|
62 |
however, literature seems to not point this out enough. |
|
360 | 63 |
|
243 | 64 |
Although LinkedList is a subclass of SequenceableCollection (and therefore |
65 |
supports indexed access via at:), you should be careful in using it or |
|
10647 | 66 |
other methods based upon at:. |
360 | 67 |
The reason is that #at: walks the linkedlist to find the indexed element |
10647 | 68 |
and is therefore slow. |
69 |
This means that some linear-in-time algorithms inherited from |
|
360 | 70 |
SequenceableCollection become square in runtime. |
243 | 71 |
In general, if you need access via a numeric index, you better use Array, |
72 |
OrderedCollection or similar. |
|
360 | 73 |
|
74 |
For the above reasons, the system does not make heavily use of LinkedLists; |
|
75 |
the only good application is where elements must be repeatedly be removed |
|
76 |
at the front and added at the end. |
|
17123 | 77 |
(the scheduler's process handling code does this to manage process lists.) |
1290 | 78 |
|
4063 | 79 |
[memory requirements:] |
13727 | 80 |
(OBJ-HEADER + (3 * ptr-size)) * size |
81 |
+ any additional instvars due to subclassing |
|
4063 | 82 |
|
1290 | 83 |
[author:] |
13727 | 84 |
Claus Gittinger (July 1993) |
2146 | 85 |
|
86 |
[see also:] |
|
13727 | 87 |
Link ValueLink Process |
360 | 88 |
" |
89 |
! |
|
90 |
||
10647 | 91 |
examples |
360 | 92 |
" |
19970 | 93 |
[exBegin] |
94 |
|l| |
|
95 |
||
96 |
l := LinkedList new. |
|
97 |
l addLast:'one'. |
|
98 |
l addLast:'two'. |
|
99 |
l addLast:'three'. |
|
100 |
l addLast:'four'. |
|
101 |
l inspect |
|
102 |
[exEnd] |
|
103 |
||
104 |
[exBegin] |
|
360 | 105 |
|l| |
106 |
||
107 |
l := LinkedList new. |
|
108 |
l addLast:(ValueLink new value:'one'). |
|
109 |
l addLast:(ValueLink new value:'two'). |
|
110 |
l addLast:(ValueLink new value:'three'). |
|
111 |
l addLast:(ValueLink new value:'four'). |
|
112 |
l inspect |
|
19970 | 113 |
[exEnd] |
360 | 114 |
|
19970 | 115 |
[exBegin] |
360 | 116 |
|l| |
117 |
||
118 |
l := LinkedList new. |
|
119 |
l addLast:(ValueLink new value:'one'). |
|
120 |
l addLast:(ValueLink new value:'two'). |
|
121 |
l addLast:(ValueLink new value:'three'). |
|
122 |
l addLast:(ValueLink new value:'four'). |
|
123 |
(l at:3) value inspect. 'slow operation for large lists'. |
|
19970 | 124 |
[exEnd] |
360 | 125 |
|
126 |
||
19970 | 127 |
[exBegin] |
360 | 128 |
|l link| |
129 |
||
130 |
l := LinkedList new. |
|
131 |
l addLast:(ValueLink new value:'one'). |
|
132 |
l addLast:(ValueLink new value:'two'). |
|
133 |
l addLast:(ValueLink new value:'three'). |
|
134 |
l addLast:(ValueLink new value:'four'). |
|
135 |
link := l removeFirst. |
|
136 |
l addLast:link. |
|
10647 | 137 |
l inspect. |
19970 | 138 |
[exEnd] |
88 | 139 |
" |
140 |
! ! |
|
1 | 141 |
|
142 |
!LinkedList class methodsFor:'instance creation'! |
|
143 |
||
144 |
new |
|
145 |
"create and return a new LinkedList" |
|
146 |
||
4300 | 147 |
^ self basicNew initialize |
1 | 148 |
! ! |
149 |
||
150 |
!LinkedList methodsFor:'accessing'! |
|
151 |
||
159 | 152 |
at:index |
19970 | 153 |
"return the n'th value - use of this method should be avoided, |
159 | 154 |
since it is slow to walk through the list - think about using |
9118 | 155 |
another collection if you need indexed access. |
17575 | 156 |
Notice: |
157 |
that many methods in SeqColl are based on at:-access, |
|
19970 | 158 |
so other inherited methods may be very slow (showing O^2 runtime). |
17575 | 159 |
It is a very bad idea to access LinkedList elements by index. |
160 |
many algorithms degenerate to poor performance if you do. |
|
161 |
This method is provided for protocol completeness, |
|
162 |
but please consider using another type of collection if you use it" |
|
159 | 163 |
|
9117 | 164 |
^ self at:index ifAbsent:[ self subscriptBoundsError:index] |
165 |
! |
|
166 |
||
19975 | 167 |
at:index ifAbsent:exceptionValue |
19970 | 168 |
"return the n'th value - use of this method should be avoided, |
9117 | 169 |
since it is slow to walk through the list - think about using |
9118 | 170 |
another collection if you need indexed access. |
17575 | 171 |
Notice: |
172 |
that many methods in SeqColl are based on at:-access, |
|
19970 | 173 |
so other inherited methods may be very slow (showing O^2 runtime). |
17575 | 174 |
It is a very bad idea to access LinkedList elements by index. |
175 |
many algorithms degenerate to poor performance if you do. |
|
176 |
This method is provided for protocol completeness, |
|
177 |
but please consider using another type of collection if you use it" |
|
9117 | 178 |
|
19975 | 179 |
|theLink| |
159 | 180 |
|
19975 | 181 |
theLink := self linkAt:index ifAbsent:[^ exceptionValue value]. |
19970 | 182 |
^ theLink value |
20231 | 183 |
|
184 |
" |
|
185 |
|l| |
|
186 |
||
187 |
l := LinkedList new. |
|
188 |
l add:'one'. |
|
189 |
l add:'two'. |
|
190 |
l add:'hello'. |
|
191 |
l at:3 ifAbsent:'missing'. |
|
192 |
l at:4 ifAbsent:'missing'. |
|
193 |
" |
|
606 | 194 |
! |
195 |
||
196 |
first |
|
19970 | 197 |
"return the first value in the list" |
606 | 198 |
|
19970 | 199 |
^ self firstLink value |
606 | 200 |
! |
201 |
||
10647 | 202 |
firstIfEmpty:exceptionalValue |
19970 | 203 |
"return the first value in the list or exceptionlValue, if empty" |
17262 | 204 |
|
205 |
firstLink isNil ifTrue:[^ exceptionalValue value]. |
|
19970 | 206 |
^ firstLink value |
17262 | 207 |
! |
208 |
||
209 |
firstLink |
|
210 |
"return the first node in the list" |
|
211 |
||
212 |
firstLink isNil ifTrue:[^ self emptyCollectionError]. |
|
213 |
^ firstLink |
|
214 |
! |
|
215 |
||
216 |
firstLinkIfEmpty:exceptionalValue |
|
217 |
"return the first node in the list or exceptionlValue, if empty" |
|
218 |
||
10647 | 219 |
firstLink isNil ifTrue:[^ exceptionalValue value]. |
220 |
^ firstLink |
|
221 |
! |
|
222 |
||
606 | 223 |
last |
19970 | 224 |
"return last value in the list" |
17262 | 225 |
|
17274 | 226 |
lastLink isNil ifTrue:[^ self emptyCollectionError]. |
227 |
^ lastLink value |
|
17262 | 228 |
! |
229 |
||
230 |
lastLink |
|
231 |
"return last node in the list" |
|
232 |
||
606 | 233 |
lastLink isNil ifTrue:[self emptyCollectionError]. |
234 |
^ lastLink |
|
17272 | 235 |
! |
236 |
||
19970 | 237 |
linkAt:index ifAbsent:exceptionBlock |
238 |
"return the n'th link - use of this method should be avoided, |
|
17272 | 239 |
since it is slow to walk through the list - think about using |
240 |
another collection if you need indexed access. |
|
17575 | 241 |
Notice: |
20231 | 242 |
that many methods in the superclass, SequenceableCollection are based on at:-access, |
19970 | 243 |
so other inherited methods may be very slow (showing O^2 runtime). |
17575 | 244 |
It is a very bad idea to access LinkedList elements by index. |
245 |
many algorithms degenerate to poor performance if you do. |
|
246 |
This method is provided for protocol completeness, |
|
247 |
but please consider using another type of collection if you use it" |
|
17272 | 248 |
|
249 |
|theLink |
|
20231 | 250 |
count "{Class: SmallInteger}"| |
251 |
||
252 |
count := index. |
|
253 |
(count < 1 or:[count > numberOfNodes]) ifTrue:[ |
|
254 |
^ exceptionBlock value. |
|
255 |
]. |
|
17272 | 256 |
|
257 |
theLink := firstLink. |
|
20231 | 258 |
count-1 timesRepeat:[ |
17272 | 259 |
theLink isNil ifTrue:[^ exceptionBlock value]. |
260 |
theLink := theLink nextLink. |
|
261 |
]. |
|
262 |
^ theLink |
|
606 | 263 |
! ! |
264 |
||
265 |
!LinkedList methodsFor:'adding & removing'! |
|
266 |
||
17262 | 267 |
add:aLinkOrAnyOtherObject |
606 | 268 |
"adds aLink to the end of the sequence. Returns aLink" |
269 |
||
17262 | 270 |
|newLink| |
271 |
||
272 |
newLink := aLinkOrAnyOtherObject asLink. |
|
273 |
||
274 |
newLink nextLink:nil. |
|
606 | 275 |
lastLink isNil ifTrue:[ |
17262 | 276 |
firstLink := newLink |
606 | 277 |
] ifFalse: [ |
17262 | 278 |
lastLink nextLink:newLink |
606 | 279 |
]. |
17262 | 280 |
lastLink := newLink. |
606 | 281 |
numberOfNodes := numberOfNodes + 1. |
17262 | 282 |
^ newLink |
606 | 283 |
! |
284 |
||
19970 | 285 |
add:aLinkOrAnyOtherObject after:aLinkOrValue |
286 |
"adds aLinkOrAnyOtherObject after another aLinkOrValue. |
|
287 |
If aLinkOrValue is nil, linkToAdd is inserted at the beginning. |
|
288 |
If aLinkOrValue is not in the list, linkToAdd is added at the end. |
|
289 |
Returns aLinkOrAnyOtherObject." |
|
606 | 290 |
|
19970 | 291 |
|this linkToAdd linkOrValue| |
606 | 292 |
|
19970 | 293 |
aLinkOrValue isNil ifTrue:[^ self addFirst:aLinkOrAnyOtherObject ]. |
17262 | 294 |
|
295 |
linkToAdd := aLinkOrAnyOtherObject asLink. |
|
19970 | 296 |
linkOrValue := aLinkOrValue value. |
297 |
||
606 | 298 |
this := firstLink. |
19970 | 299 |
[this notNil and:[this ~~ linkOrValue]] whileTrue:[ |
17262 | 300 |
this := this nextLink |
606 | 301 |
]. |
302 |
this isNil ifTrue:[^ self add:linkToAdd ]. |
|
303 |
linkToAdd nextLink:(this nextLink). |
|
304 |
this nextLink:linkToAdd. |
|
10647 | 305 |
numberOfNodes := numberOfNodes + 1. |
606 | 306 |
^ linkToAdd |
307 |
! |
|
308 |
||
17262 | 309 |
addFirst:aLinkOrAnyOtherObject |
606 | 310 |
"adds aLink to the beginning of the sequence. Returns aLink" |
311 |
||
17262 | 312 |
|linkToAdd| |
313 |
||
314 |
linkToAdd := aLinkOrAnyOtherObject asLink. |
|
315 |
||
606 | 316 |
firstLink isNil ifTrue:[ |
17262 | 317 |
lastLink := linkToAdd. |
606 | 318 |
]. |
17262 | 319 |
linkToAdd nextLink:firstLink. |
320 |
firstLink := linkToAdd. |
|
606 | 321 |
numberOfNodes := numberOfNodes + 1. |
17262 | 322 |
^ linkToAdd |
606 | 323 |
! |
324 |
||
19970 | 325 |
remove:aLinkOrValue ifAbsent:exceptionBlock |
326 |
"remove the argument, aLinkOrValue from the sequence and return it; |
|
327 |
if absent, evaluate the exceptionBlock." |
|
328 |
||
329 |
|prevNode nextNode thisNode linkOrValue| |
|
606 | 330 |
|
19970 | 331 |
linkOrValue := aLinkOrValue value. |
332 |
thisNode := firstLink. |
|
333 |
[thisNode notNil] whileTrue:[ |
|
334 |
nextNode := thisNode nextLink. |
|
335 |
(thisNode value = linkOrValue) ifTrue:[ |
|
336 |
prevNode isNil ifTrue:[ |
|
337 |
firstLink := nextNode |
|
338 |
] ifFalse:[ |
|
339 |
prevNode nextLink:nextNode |
|
340 |
]. |
|
341 |
nextNode isNil ifTrue:[ |
|
342 |
lastLink := prevNode |
|
343 |
]. |
|
344 |
numberOfNodes := numberOfNodes - 1. |
|
345 |
thisNode nextLink:nil. |
|
346 |
^ thisNode value |
|
347 |
]. |
|
348 |
prevNode := thisNode. |
|
349 |
thisNode := nextNode |
|
350 |
]. |
|
351 |
^ exceptionBlock value |
|
2349 | 352 |
|
19970 | 353 |
"Created: / 30-11-2010 / 13:38:25 / cg" |
606 | 354 |
! |
355 |
||
1110 | 356 |
removeAll |
1164 | 357 |
"remove all elements from the sequence. Returns the receiver." |
1110 | 358 |
|
359 |
firstLink := lastLink := nil. |
|
360 |
numberOfNodes := 0 |
|
361 |
||
362 |
"Created: 21.3.1996 / 15:24:38 / cg" |
|
1164 | 363 |
"Modified: 12.4.1996 / 13:34:53 / cg" |
1110 | 364 |
! |
365 |
||
606 | 366 |
removeFirst |
367 |
"remove and return the first node from the sequence" |
|
368 |
||
369 |
|link| |
|
370 |
||
371 |
firstLink isNil ifTrue:[ |
|
10647 | 372 |
^ self emptyCollectionError |
5519
925d9a1eda2c
fixed emptyCollection error signaling
Claus Gittinger <cg@exept.de>
parents:
5244
diff
changeset
|
373 |
]. |
925d9a1eda2c
fixed emptyCollection error signaling
Claus Gittinger <cg@exept.de>
parents:
5244
diff
changeset
|
374 |
link := firstLink. |
10647 | 375 |
firstLink := firstLink nextLink. |
376 |
firstLink isNil ifTrue:[ |
|
377 |
lastLink := nil |
|
606 | 378 |
]. |
5519
925d9a1eda2c
fixed emptyCollection error signaling
Claus Gittinger <cg@exept.de>
parents:
5244
diff
changeset
|
379 |
link nextLink:nil. |
925d9a1eda2c
fixed emptyCollection error signaling
Claus Gittinger <cg@exept.de>
parents:
5244
diff
changeset
|
380 |
numberOfNodes := numberOfNodes - 1. |
606 | 381 |
^ link |
13153
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
382 |
! |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
383 |
|
19970 | 384 |
removeIdentical:aLinkOrValue ifAbsent:exceptionBlock |
385 |
"remove the argument, aLinkOrValue from the sequence and return it; |
|
13163
e4845fce0ada
changed comment: #removeIdentical:ifAbsent:
Stefan Vogel <sv@exept.de>
parents:
13153
diff
changeset
|
386 |
if absent, evaluate the exceptionBlock." |
13153
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
387 |
|
19970 | 388 |
|prevNode nextNode thisNode linkOrValue| |
13153
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
389 |
|
19970 | 390 |
linkOrValue := aLinkOrValue value. |
13153
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
391 |
thisNode := firstLink. |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
392 |
[thisNode notNil] whileTrue:[ |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
393 |
nextNode := thisNode nextLink. |
19970 | 394 |
(thisNode value == linkOrValue) ifTrue:[ |
13153
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
395 |
prevNode isNil ifTrue:[ |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
396 |
firstLink := nextNode |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
397 |
] ifFalse:[ |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
398 |
prevNode nextLink:nextNode |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
399 |
]. |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
400 |
nextNode isNil ifTrue:[ |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
401 |
lastLink := prevNode |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
402 |
]. |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
403 |
numberOfNodes := numberOfNodes - 1. |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
404 |
thisNode nextLink:nil. |
19970 | 405 |
^ thisNode value |
13153
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
406 |
]. |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
407 |
prevNode := thisNode. |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
408 |
thisNode := nextNode |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
409 |
]. |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
410 |
^ exceptionBlock value |
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
411 |
|
572dc11e2e96
added: #removeIdentical:ifAbsent:
Claus Gittinger <cg@exept.de>
parents:
13150
diff
changeset
|
412 |
"Created: / 30-11-2010 / 13:38:25 / cg" |
17274 | 413 |
! |
414 |
||
415 |
removeLast |
|
416 |
"remove the last link element and return it; |
|
417 |
if empty, raise an exception." |
|
418 |
||
419 |
|nextNode thisNode| |
|
420 |
||
421 |
thisNode := firstLink. |
|
422 |
thisNode isNil ifTrue:[ |
|
423 |
^ self emptyCollectionError |
|
424 |
]. |
|
425 |
thisNode == lastLink ifTrue:[ |
|
426 |
firstLink := lastLink := nil. |
|
427 |
numberOfNodes := 0. |
|
428 |
^ thisNode |
|
429 |
]. |
|
430 |
||
431 |
[ |
|
432 |
nextNode := thisNode nextLink. |
|
433 |
nextNode == lastLink ifTrue:[ |
|
434 |
firstLink == lastLink ifTrue:[ |
|
435 |
firstLink := thisNode |
|
436 |
]. |
|
437 |
lastLink := thisNode. |
|
438 |
numberOfNodes := numberOfNodes - 1. |
|
439 |
thisNode nextLink:nil. |
|
440 |
^ nextNode. |
|
441 |
]. |
|
442 |
thisNode := nextNode |
|
443 |
] loop. |
|
606 | 444 |
! ! |
445 |
||
446 |
!LinkedList methodsFor:'enumerating'! |
|
447 |
||
448 |
do:aBlock |
|
19976 | 449 |
"evaluate the argument, aBlock with 1 arg for every value element in the list" |
17274 | 450 |
|
451 |
|thisNode| |
|
452 |
||
20231 | 453 |
"aBlock may add elements, so do not use 'numberOfNodes-1 timesRepeat:[]'" |
17274 | 454 |
thisNode := firstLink. |
455 |
[thisNode notNil] whileTrue:[ |
|
19976 | 456 |
aBlock value:thisNode value. |
17274 | 457 |
thisNode := thisNode nextLink |
458 |
] |
|
459 |
! |
|
460 |
||
461 |
linksDo:aBlock |
|
462 |
"evaluate the argument, aBlock with 1 arg for every link element in the list" |
|
606 | 463 |
|
464 |
|thisNode| |
|
465 |
||
20231 | 466 |
"aBlock may add elements, so do not use 'numberOfNodes-1 timesRepeat:[]'" |
606 | 467 |
thisNode := firstLink. |
468 |
[thisNode notNil] whileTrue:[ |
|
17274 | 469 |
aBlock value:thisNode. |
470 |
thisNode := thisNode nextLink |
|
606 | 471 |
] |
17406 | 472 |
! |
473 |
||
474 |
printElementsDo:aBlock |
|
475 |
"perform aBlock (1 arg) for all elements. |
|
476 |
Used in #printOn:." |
|
477 |
||
478 |
^ self linksDo:aBlock |
|
606 | 479 |
! ! |
480 |
||
5244 | 481 |
!LinkedList methodsFor:'initialization'! |
606 | 482 |
|
483 |
initialize |
|
484 |
numberOfNodes := 0 |
|
93 | 485 |
! ! |
486 |
||
487 |
!LinkedList methodsFor:'queries'! |
|
488 |
||
606 | 489 |
size |
490 |
"return the size of the LinkedList i.e. the number of nodes" |
|
491 |
||
492 |
^ numberOfNodes |
|
1 | 493 |
! ! |
494 |
||
17209 | 495 |
!LinkedList methodsFor:'searching-equality'! |
496 |
||
19970 | 497 |
indexOf:aLinkOrValue startingAt:start |
498 |
"search the collection for aLinkOrValue, starting the search at index start; |
|
499 |
if found, return the index otherwise return 0. |
|
500 |
Here, index is defined as the link-node's position in the list. |
|
17575 | 501 |
The comparison is done using = (i.e. equality test - not identity test). |
502 |
Warning: |
|
503 |
it is a very bad idea to access LinkedList elements by index. |
|
504 |
many algorithms degenerate to poor performance if you do. |
|
505 |
This method is provided for protocol completeness, |
|
506 |
but please consider using another type of collection if you use it. |
|
507 |
" |
|
17209 | 508 |
|
20231 | 509 |
|theNode count "{ Class: SmallInteger }" |
19970 | 510 |
linkOrValue| |
17209 | 511 |
|
20231 | 512 |
count := start. |
513 |
(count < 1 or:[count > numberOfNodes]) ifTrue:[ |
|
514 |
^ 0. |
|
515 |
]. |
|
516 |
||
517 |
theNode := firstLink. |
|
518 |
count-1 timesRepeat:[ |
|
519 |
theNode isNil ifTrue:[^ 0]. "reached the end" |
|
520 |
theNode := theNode nextLink. |
|
521 |
]. |
|
522 |
||
19970 | 523 |
linkOrValue := aLinkOrValue value. |
20231 | 524 |
|
525 |
[theNode notNil] whileTrue:[ |
|
526 |
(linkOrValue = theNode value) ifTrue:[^ count]. |
|
17575 | 527 |
theNode := theNode nextLink. |
20231 | 528 |
count := count + 1. |
17209 | 529 |
]. "reached the end" |
530 |
^ 0 |
|
531 |
||
532 |
" |
|
533 |
|l| |
|
534 |
||
535 |
l := LinkedList new. |
|
20231 | 536 |
l indexOf:'hello' startingAt:1 |
17209 | 537 |
" |
538 |
||
539 |
" |
|
540 |
|l v| |
|
541 |
||
542 |
l := LinkedList new. |
|
543 |
l add:(ValueLink new value:'one'). |
|
544 |
l add:(ValueLink new value:'two'). |
|
545 |
l add:(v := ValueLink new value:'hello'). |
|
20231 | 546 |
l indexOf:v startingAt:2. |
17209 | 547 |
" |
548 |
! ! |
|
549 |
||
550 |
!LinkedList methodsFor:'searching-identity'! |
|
1 | 551 |
|
19970 | 552 |
identityIndexOf:aLinkOrValue startingAt:start |
553 |
"search the collection for aLinkOrValue, starting the search at index start; |
|
554 |
if found, return the index otherwise return 0. |
|
555 |
Here, index is defined as the link-node's position in the list. |
|
556 |
The comparison is done using == (i.e. identity test - not equality test). |
|
557 |
Warning: |
|
558 |
it is a very bad idea to access LinkedList elements by index. |
|
17575 | 559 |
many algorithms degenerate to poor performance if you do. |
560 |
This method is provided for protocol completeness, |
|
19970 | 561 |
but please consider using another type of collection if you use it. |
562 |
" |
|
243 | 563 |
|
20231 | 564 |
|theNode count "{ Class: SmallInteger }" |
19970 | 565 |
linkOrValue| |
243 | 566 |
|
20231 | 567 |
count := start. |
568 |
(count < 1 or:[count > numberOfNodes]) ifTrue:[ |
|
569 |
^ 0. |
|
570 |
]. |
|
571 |
||
572 |
theNode := firstLink. |
|
573 |
count-1 timesRepeat:[ |
|
574 |
theNode isNil ifTrue:[^ 0]. "reached the end" |
|
575 |
theNode := theNode nextLink. |
|
576 |
]. |
|
577 |
||
19970 | 578 |
linkOrValue := aLinkOrValue value. |
20231 | 579 |
|
580 |
[theNode notNil] whileTrue:[ |
|
581 |
(linkOrValue == theNode value) ifTrue:[^ count]. |
|
13150
e20625aa25a7
comment changed: #identityIndexOf:startingAt:
Stefan Vogel <sv@exept.de>
parents:
10647
diff
changeset
|
582 |
theNode := theNode nextLink. |
20231 | 583 |
count := count + 1. |
243 | 584 |
]. "reached the end" |
585 |
^ 0 |
|
586 |
||
587 |
" |
|
588 |
|l| |
|
589 |
||
590 |
l := LinkedList new. |
|
20231 | 591 |
l identityIndexOf:'hello' startingAt:1 |
243 | 592 |
" |
593 |
||
594 |
" |
|
595 |
|l v| |
|
596 |
||
597 |
l := LinkedList new. |
|
598 |
l add:(ValueLink new value:'one'). |
|
599 |
l add:(ValueLink new value:'two'). |
|
600 |
l add:(v := ValueLink new value:'hello'). |
|
20231 | 601 |
l identityIndexOf:v startingAt:2. |
243 | 602 |
" |
1 | 603 |
! ! |
604 |
||
17210 | 605 |
!LinkedList methodsFor:'testing'! |
606 |
||
607 |
isEmpty |
|
608 |
"return true, if the collection is empty" |
|
609 |
||
610 |
^ firstLink isNil |
|
611 |
! |
|
612 |
||
613 |
isFixedSize |
|
614 |
"return true if the receiver cannot grow" |
|
615 |
||
616 |
^ false |
|
617 |
! |
|
618 |
||
619 |
notEmpty |
|
620 |
"return true, if the collection is not empty" |
|
621 |
||
622 |
^ firstLink notNil |
|
623 |
! ! |
|
624 |
||
629 | 625 |
!LinkedList class methodsFor:'documentation'! |
626 |
||
627 |
version |
|
19970 | 628 |
^ '$Header$' |
13150
e20625aa25a7
comment changed: #identityIndexOf:startingAt:
Stefan Vogel <sv@exept.de>
parents:
10647
diff
changeset
|
629 |
! |
e20625aa25a7
comment changed: #identityIndexOf:startingAt:
Stefan Vogel <sv@exept.de>
parents:
10647
diff
changeset
|
630 |
|
e20625aa25a7
comment changed: #identityIndexOf:startingAt:
Stefan Vogel <sv@exept.de>
parents:
10647
diff
changeset
|
631 |
version_CVS |
19970 | 632 |
^ '$Header$' |
629 | 633 |
! ! |
15428 | 634 |