1 " |
1 " |
2 COPYRIGHT (c) 1989 by Claus Gittinger |
2 COPYRIGHT (c) 1989 by Claus Gittinger |
3 All Rights Reserved |
3 All Rights Reserved |
4 |
4 |
5 This software is furnished under a license and may be used |
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 |
6 only in accordance with the terms of that license and with the |
7 inclusion of the above copyright notice. This software may not |
7 inclusion of the above copyright notice. This software may not |
8 be provided or otherwise made available to, or used by, any |
8 be provided or otherwise made available to, or used by, any |
9 other person. No title to or ownership of the software is |
9 other person. No title to or ownership of the software is |
10 hereby transferred. |
10 hereby transferred. |
11 " |
11 " |
12 |
12 |
13 SequenceableCollection subclass:#LinkedList |
13 SequenceableCollection subclass:#LinkedList |
14 instanceVariableNames:'firstLink lastLink nodeClass numberOfNodes' |
14 instanceVariableNames:'firstLink lastLink numberOfNodes' |
15 classVariableNames:'' |
15 classVariableNames:'' |
16 poolDictionaries:'' |
16 poolDictionaries:'' |
17 category:'Collections-Sequenceable' |
17 category:'Collections-Sequenceable' |
18 ! |
18 ! |
19 |
19 |
20 LinkedList comment:' |
20 LinkedList comment:' |
21 COPYRIGHT (c) 1989 by Claus Gittinger |
21 COPYRIGHT (c) 1989 by Claus Gittinger |
22 All Rights Reserved |
22 All Rights Reserved |
23 |
23 |
24 $Header: /cvs/stx/stx/libbasic/LinkedList.st,v 1.8 1994-08-05 00:58:53 claus Exp $ |
24 $Header: /cvs/stx/stx/libbasic/LinkedList.st,v 1.9 1994-10-10 00:26:30 claus Exp $ |
25 '! |
25 '! |
26 |
26 |
27 !LinkedList class methodsFor:'documentation'! |
27 !LinkedList class methodsFor:'documentation'! |
28 |
28 |
29 copyright |
29 copyright |
30 " |
30 " |
31 COPYRIGHT (c) 1989 by Claus Gittinger |
31 COPYRIGHT (c) 1989 by Claus Gittinger |
32 All Rights Reserved |
32 All Rights Reserved |
33 |
33 |
34 This software is furnished under a license and may be used |
34 This software is furnished under a license and may be used |
35 only in accordance with the terms of that license and with the |
35 only in accordance with the terms of that license and with the |
36 inclusion of the above copyright notice. This software may not |
36 inclusion of the above copyright notice. This software may not |
37 be provided or otherwise made available to, or used by, any |
37 be provided or otherwise made available to, or used by, any |
68 numberOfNodes := 0 |
68 numberOfNodes := 0 |
69 ! ! |
69 ! ! |
70 |
70 |
71 !LinkedList methodsFor:'copying'! |
71 !LinkedList methodsFor:'copying'! |
72 |
72 |
73 deepCopy |
73 XXXdeepCopy |
74 "a kludge, to be removed when deepCopy handles recursive structures" |
74 "a kludge, to be removed when deepCopy handles recursive structures" |
75 |
75 |
76 |newList| |
76 |newList| |
|
77 |
77 newList := self shallowCopy. |
78 newList := self shallowCopy. |
78 newList setFirstNode:(firstLink deepCopy). |
79 newList setFirstNode:(firstLink deepCopy) lastNode:(firstLink last). |
79 newList setLastNode:(firstLink last). |
|
80 ^ newList |
80 ^ newList |
|
81 |
|
82 " |
|
83 |l| |
|
84 l := LinkedList new. |
|
85 l add:(ValueLink new value:1). |
|
86 l add:(ValueLink new value:2). |
|
87 l add:(ValueLink new value:3). |
|
88 l inspect. |
|
89 l deepCopy inspect |
|
90 " |
|
91 ! ! |
|
92 |
|
93 !LinkedList methodsFor:'private accessing'! |
|
94 |
|
95 XXsetFirstNode:first lastNode:last |
|
96 "set the first node to be the argument, aNode" |
|
97 |
|
98 firstLink := first. |
|
99 lastLink := last |
81 ! ! |
100 ! ! |
82 |
101 |
83 !LinkedList methodsFor:'accessing'! |
102 !LinkedList methodsFor:'accessing'! |
84 |
|
85 setFirstNode:aNode |
|
86 "set the first node to be the argument, aNode" |
|
87 |
|
88 firstLink := aNode |
|
89 ! |
|
90 |
|
91 setLastNode:aNode |
|
92 "set the last node to be the argument, aNode" |
|
93 |
|
94 lastLink := aNode |
|
95 ! |
|
96 |
103 |
97 first |
104 first |
98 "return the first node in the list" |
105 "return the first node in the list" |
99 |
106 |
|
107 firstLink isNil ifTrue:[self emptyCollectionError]. |
100 ^ firstLink |
108 ^ firstLink |
101 ! |
109 ! |
102 |
110 |
103 last |
111 last |
104 "return last node in the list" |
112 "return last node in the list" |
105 |
113 |
|
114 lastLink isNil ifTrue:[self emptyCollectionError]. |
106 ^ lastLink |
115 ^ lastLink |
|
116 ! |
|
117 |
|
118 at:index |
|
119 "return the n'th element - use of this method should be avoided, |
|
120 since it is slow to walk through the list - think about using |
|
121 another collection if you need index access. |
|
122 Notice, that many methods in SeqColl are based on at:-access." |
|
123 |
|
124 |theLink |
|
125 runIndex "{Class: SmallInteger}"| |
|
126 |
|
127 theLink := firstLink. |
|
128 runIndex := 1. |
|
129 [theLink isNil or:[runIndex == index]] whileFalse:[ |
|
130 theLink := theLink nextLink. |
|
131 runIndex := runIndex + 1. |
|
132 ]. |
|
133 theLink isNil ifTrue:[ |
|
134 ^ self subscriptBoundsError:index |
|
135 ]. |
|
136 ^ theLink |
107 ! ! |
137 ! ! |
108 |
138 |
109 !LinkedList methodsFor:'queries'! |
139 !LinkedList methodsFor:'queries'! |
110 |
|
111 |
140 |
112 size |
141 size |
113 "return the size of the LinkedList i.e. the number of nodes" |
142 "return the size of the LinkedList i.e. the number of nodes" |
114 |
143 |
115 ^ numberOfNodes |
144 ^ numberOfNodes |
128 |
157 |
129 |theNode| |
158 |theNode| |
130 |
159 |
131 theNode := firstLink. |
160 theNode := firstLink. |
132 [theNode notNil] whileTrue:[ |
161 [theNode notNil] whileTrue:[ |
133 (anObject = theNode) ifTrue:[^ true]. |
162 (anObject = theNode) ifTrue:[^ true]. |
134 theNode := theNode nextLink |
163 theNode := theNode nextLink |
135 ]. |
164 ]. |
136 ^ false |
165 ^ false |
137 ! ! |
166 ! ! |
138 |
167 |
139 !LinkedList methodsFor:'adding/removing elements'! |
168 !LinkedList methodsFor:'adding/removing elements'! |
140 |
169 |
141 addFirst:aLink |
170 addFirst:aLink |
142 "adds aLink to the beginning of the sequence. Returns aLink" |
171 "adds aLink to the beginning of the sequence. Returns aLink" |
143 |
172 |
144 firstLink isNil ifTrue:[ |
173 firstLink isNil ifTrue:[ |
145 firstLink := aLink. |
174 firstLink := aLink. |
146 lastLink := aLink |
175 lastLink := aLink |
147 ] ifFalse: [ |
176 ] ifFalse: [ |
148 aLink nextLink:firstLink. |
177 aLink nextLink:firstLink. |
149 firstLink := aLink |
178 firstLink := aLink |
150 ]. |
179 ]. |
151 numberOfNodes := numberOfNodes + 1. |
180 numberOfNodes := numberOfNodes + 1. |
152 ^ aLink |
181 ^ aLink |
153 ! |
182 ! |
154 |
183 |
155 add:aLink |
184 add:aLink |
156 "adds aLink to the end of the sequence. Returns aLink" |
185 "adds aLink to the end of the sequence. Returns aLink" |
157 |
186 |
158 aLink nextLink:nil. |
187 aLink nextLink:nil. |
159 lastLink isNil ifTrue:[ |
188 lastLink isNil ifTrue:[ |
160 firstLink := aLink |
189 firstLink := aLink |
161 ] ifFalse: [ |
190 ] ifFalse: [ |
162 lastLink nextLink:aLink |
191 lastLink nextLink:aLink |
163 ]. |
192 ]. |
164 lastLink := aLink. |
193 lastLink := aLink. |
165 numberOfNodes := numberOfNodes + 1. |
194 numberOfNodes := numberOfNodes + 1. |
166 ^ aLink |
195 ^ aLink |
167 ! |
196 ! |
170 "adds linkToAdd after another link, aLink. If aLink is nil, |
199 "adds linkToAdd after another link, aLink. If aLink is nil, |
171 linkToAdd is inserted at the beginning. Returns linkToAdd." |
200 linkToAdd is inserted at the beginning. Returns linkToAdd." |
172 |
201 |
173 |this| |
202 |this| |
174 |
203 |
175 aLink isNil ifTrue:[ ^ self addFirst:linkToAdd ]. |
204 aLink isNil ifTrue:[^ self addFirst:linkToAdd ]. |
176 |
205 |
177 this := firstLink. |
206 this := firstLink. |
178 [this notNil and:[this ~~ aLink]] whileTrue:[ |
207 [this notNil and:[this ~~ aLink]] whileTrue:[ |
179 this := this nextLink |
208 this := this nextLink |
180 ]. |
209 ]. |
181 this isNil ifTrue:[ ^ self add:linkToAdd ]. |
210 this isNil ifTrue:[^ self add:linkToAdd ]. |
182 linkToAdd nextLink:(this nextLink). |
211 linkToAdd nextLink:(this nextLink). |
183 this nextLink:linkToAdd. |
212 this nextLink:linkToAdd. |
184 ^ linkToAdd |
213 ^ linkToAdd |
185 ! |
214 ! |
186 |
215 |
188 "remove and return the first node from the sequence" |
217 "remove and return the first node from the sequence" |
189 |
218 |
190 |link| |
219 |link| |
191 |
220 |
192 firstLink isNil ifTrue:[ |
221 firstLink isNil ifTrue:[ |
193 self errorIsEmpty |
222 self errorIsEmpty |
194 ] ifFalse:[ |
223 ] ifFalse:[ |
195 link := firstLink. |
224 link := firstLink. |
196 (firstLink == lastLink) ifTrue:[ |
225 (firstLink == lastLink) ifTrue:[ |
197 firstLink := nil. |
226 firstLink := nil. |
198 lastLink := nil |
227 lastLink := nil |
199 ] ifFalse:[ |
228 ] ifFalse:[ |
200 firstLink := firstLink nextLink |
229 firstLink := firstLink nextLink |
201 ]. |
230 ]. |
202 link nextLink:nil. |
231 link nextLink:nil. |
203 numberOfNodes := numberOfNodes - 1 |
232 numberOfNodes := numberOfNodes - 1 |
204 ]. |
233 ]. |
205 ^ link |
234 ^ link |
206 ! |
235 ! |
207 |
236 |
208 remove:aLink ifAbsent:exceptionBlock |
237 remove:aLink ifAbsent:exceptionBlock |
211 |
240 |
212 |prevNode nextNode thisNode| |
241 |prevNode nextNode thisNode| |
213 |
242 |
214 thisNode := firstLink. |
243 thisNode := firstLink. |
215 [thisNode notNil] whileTrue:[ |
244 [thisNode notNil] whileTrue:[ |
216 nextNode := thisNode nextLink. |
245 nextNode := thisNode nextLink. |
217 (thisNode == aLink) ifTrue:[ |
246 (thisNode == aLink) ifTrue:[ |
218 prevNode isNil ifTrue:[ |
247 prevNode isNil ifTrue:[ |
219 firstLink := thisNode nextLink |
248 firstLink := thisNode nextLink |
220 ] ifFalse:[ |
249 ] ifFalse:[ |
221 prevNode nextLink:(thisNode nextLink) |
250 prevNode nextLink:(thisNode nextLink) |
222 ]. |
251 ]. |
223 (lastLink == thisNode) ifTrue:[ |
252 (lastLink == thisNode) ifTrue:[ |
224 thisNode nextLink isNil ifTrue:[ |
253 thisNode nextLink isNil ifTrue:[ |
225 lastLink := prevNode |
254 lastLink := prevNode |
226 ] ifFalse:[ |
255 ] ifFalse:[ |
227 lastLink := thisNode nextLink |
256 lastLink := thisNode nextLink |
228 ] |
257 ] |
229 ]. |
258 ]. |
230 numberOfNodes := numberOfNodes - 1. |
259 numberOfNodes := numberOfNodes - 1. |
231 thisNode nextLink:nil. |
260 thisNode nextLink:nil. |
232 ^ self |
261 ^ self |
233 ]. |
262 ]. |
234 prevNode := thisNode. |
263 prevNode := thisNode. |
235 thisNode := nextNode |
264 thisNode := nextNode |
236 ]. |
265 ]. |
237 ^ exceptionBlock value |
266 ^ exceptionBlock value |
238 ! ! |
267 ! ! |
239 |
268 |
240 !LinkedList methodsFor:'enumerating'! |
269 !LinkedList methodsFor:'enumerating'! |
244 |
273 |
245 |thisNode| |
274 |thisNode| |
246 |
275 |
247 thisNode := firstLink. |
276 thisNode := firstLink. |
248 [thisNode notNil] whileTrue:[ |
277 [thisNode notNil] whileTrue:[ |
249 aBlock value:thisNode. |
278 aBlock value:thisNode. |
250 thisNode := thisNode nextLink |
279 thisNode := thisNode nextLink |
251 ] |
280 ] |
252 ! |
281 ! |
253 |
282 |
254 reverseDo:aBlock fromNode:aNode |
283 reverseDo:aBlock fromNode:aNode |
255 "helper for reverseDo:" |
284 "helper for reverseDo: - this implementation is very expensive." |
256 |
285 |
257 aNode notNil ifTrue:[ |
286 aNode notNil ifTrue:[ |
258 aNode nextLink notNil ifTrue:[ |
287 aNode nextLink notNil ifTrue:[ |
259 self reverseDo:aBlock fromNode:(aNode nextLink) |
288 self reverseDo:aBlock fromNode:(aNode nextLink) |
260 ]. |
289 ]. |
261 aBlock value:aNode |
290 aBlock value:aNode |
262 ] |
291 ] |
263 ! |
292 ! |
264 |
293 |
265 reverseDo:aBlock |
294 reverseDo:aBlock |
266 "evaluate the argument, aBlock with 1 arg for every element in the list |
295 "evaluate the argument, aBlock with 1 arg for every element in the list |