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