|
1 " |
|
2 COPYRIGHT (c) 1989-93 by Claus Gittinger |
|
3 All Rights Reserved |
|
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 " |
|
12 |
|
13 SequenceableCollection subclass:#LinkedList |
|
14 instanceVariableNames:'firstLink lastLink nodeClass numberOfNodes' |
|
15 classVariableNames:'' |
|
16 poolDictionaries:'' |
|
17 category:'Collections-Sequenceable' |
|
18 ! |
|
19 |
|
20 LinkedList comment:' |
|
21 |
|
22 COPYRIGHT (c) 1989-93 by Claus Gittinger |
|
23 All Rights Reserved |
|
24 |
|
25 this class implements an anchor to a list of Links. |
|
26 The data itself is held in the Link elements (see Link and subclasses). |
|
27 |
|
28 %W% %E% |
|
29 '! |
|
30 |
|
31 !LinkedList class methodsFor:'instance creation'! |
|
32 |
|
33 new |
|
34 "create and return a new LinkedList" |
|
35 |
|
36 ^ super new initialize |
|
37 ! ! |
|
38 |
|
39 !LinkedList methodsFor:'ininialization'! |
|
40 |
|
41 initialize |
|
42 numberOfNodes := 0 |
|
43 ! ! |
|
44 |
|
45 !LinkedList methodsFor:'copying'! |
|
46 |
|
47 deepCopy |
|
48 |newList| |
|
49 newList := self shallowCopy. |
|
50 newList setFirstNode:(firstLink deepCopy). |
|
51 newList setLastNode:(firstLink last). |
|
52 ^ newList |
|
53 ! ! |
|
54 |
|
55 !LinkedList methodsFor:'accessing'! |
|
56 |
|
57 setFirstNode:aNode |
|
58 "set the first node to be the argument, aNode" |
|
59 |
|
60 firstLink := aNode |
|
61 ! |
|
62 |
|
63 setLastNode:aNode |
|
64 "set the last node to be the argument, aNode" |
|
65 |
|
66 lastLink := aNode |
|
67 ! |
|
68 |
|
69 first |
|
70 "return the first node in the list" |
|
71 |
|
72 ^ firstLink |
|
73 ! |
|
74 |
|
75 last |
|
76 "return last node in the list" |
|
77 |
|
78 ^ lastLink |
|
79 ! |
|
80 |
|
81 size |
|
82 "return the size of the LinkedList i.e. the number of nodes" |
|
83 |
|
84 ^ numberOfNodes |
|
85 ! ! |
|
86 |
|
87 !LinkedList methodsFor:'testing'! |
|
88 |
|
89 includes:anObject |
|
90 "return true, if some nodes contents is anObject" |
|
91 |
|
92 |theNode| |
|
93 |
|
94 theNode := firstLink. |
|
95 [theNode notNil] whileTrue:[ |
|
96 (anObject = theNode) ifTrue:[^ true]. |
|
97 theNode := theNode nextLink |
|
98 ]. |
|
99 ^ false |
|
100 ! ! |
|
101 |
|
102 !LinkedList methodsFor:'adding/removing elements'! |
|
103 |
|
104 addFirst:aLink |
|
105 "adds aLink to the beginning of the sequence. Returns aLink" |
|
106 |
|
107 firstLink isNil ifTrue:[ |
|
108 firstLink := aLink. |
|
109 lastLink := aLink |
|
110 ] ifFalse: [ |
|
111 aLink nextLink:firstLink. |
|
112 firstLink := aLink |
|
113 ]. |
|
114 numberOfNodes := numberOfNodes + 1. |
|
115 ^ aLink |
|
116 ! |
|
117 |
|
118 add:aLink |
|
119 "adds aLink to the end of the sequence. Returns aLink" |
|
120 |
|
121 aLink nextLink:nil. |
|
122 lastLink isNil ifTrue:[ |
|
123 firstLink := aLink |
|
124 ] ifFalse: [ |
|
125 lastLink nextLink:aLink |
|
126 ]. |
|
127 lastLink := aLink. |
|
128 numberOfNodes := numberOfNodes + 1. |
|
129 ^ aLink |
|
130 ! |
|
131 |
|
132 add:linkToAdd after:aLink |
|
133 "adds linkToAdd after another link, aLink. If aLink is nil, |
|
134 linkToAdd is inserted at the beginning. Returns linkToAdd." |
|
135 |
|
136 |this| |
|
137 |
|
138 aLink isNil ifTrue:[ ^ self addFirst:linkToAdd ]. |
|
139 |
|
140 this := firstLink. |
|
141 [this notNil and:[this ~~ aLink]] whileTrue:[ |
|
142 this := this nextLink |
|
143 ]. |
|
144 this isNil ifTrue:[ ^ self addLast:linkToAdd ]. |
|
145 linkToAdd nextLink:(this nextLink). |
|
146 this nextLink:linkToAdd. |
|
147 ^ linkToAdd |
|
148 ! |
|
149 |
|
150 removeFirst |
|
151 "remove and return the first node from the sequence" |
|
152 |
|
153 |link| |
|
154 |
|
155 firstLink isNil ifTrue:[ |
|
156 self errorIsEmpty |
|
157 ] ifFalse:[ |
|
158 link := firstLink. |
|
159 (firstLink == lastLink) ifTrue:[ |
|
160 firstLink := nil. |
|
161 lastLink := nil |
|
162 ] ifFalse:[ |
|
163 firstLink := firstLink nextLink |
|
164 ]. |
|
165 numberOfNodes := numberOfNodes - 1 |
|
166 ]. |
|
167 ^ link |
|
168 ! |
|
169 |
|
170 remove:aLink ifAbsent:exceptionBlock |
|
171 "remove the argument, aLink from the sequence; if absent, |
|
172 evaluate the excpetionBlock" |
|
173 |
|
174 |prevNode nextNode thisNode| |
|
175 |
|
176 thisNode := firstLink. |
|
177 [thisNode notNil] whileTrue:[ |
|
178 nextNode := thisNode nextLink. |
|
179 (thisNode == aLink) ifTrue:[ |
|
180 prevNode isNil ifTrue:[ |
|
181 firstLink := thisNode nextLink |
|
182 ] ifFalse:[ |
|
183 prevNode nextLink:(thisNode nextLink) |
|
184 ]. |
|
185 (lastLink == thisNode) ifTrue:[ |
|
186 thisNode nextLink isNil ifTrue:[ |
|
187 lastLink := prevNode |
|
188 ] ifFalse:[ |
|
189 lastLink := thisNode nextLink |
|
190 ] |
|
191 ]. |
|
192 numberOfNodes := numberOfNodes - 1. |
|
193 ^ self |
|
194 ]. |
|
195 prevNode := thisNode. |
|
196 thisNode := nextNode |
|
197 ]. |
|
198 ^ exceptionBlock value |
|
199 ! ! |
|
200 |
|
201 !LinkedList methodsFor:'enumerating'! |
|
202 |
|
203 do:aBlock |
|
204 "evaluate the argument, aBlock with 1 arg for every element in the list" |
|
205 |
|
206 |thisNode| |
|
207 |
|
208 thisNode := firstLink. |
|
209 [thisNode notNil] whileTrue:[ |
|
210 aBlock value:thisNode. |
|
211 thisNode := thisNode nextLink |
|
212 ] |
|
213 ! |
|
214 |
|
215 reverseDo:aBlock fromNode:aNode |
|
216 "helper for reverseDo:" |
|
217 |
|
218 aNode notNil ifTrue:[ |
|
219 aNode nextLink notNil ifTrue:[ |
|
220 self reverseDo:aBlock fromNode:(aNode nextLink) |
|
221 ]. |
|
222 aBlock value:aNode |
|
223 ] |
|
224 ! |
|
225 |
|
226 reverseDo:aBlock |
|
227 "evaluate the argument, aBlock with 1 arg for every element in the list |
|
228 in the reverse order" |
|
229 |
|
230 self reverseDo:aBlock fromNode:firstLink |
|
231 ! ! |