]>
Commit | Line | Data |
---|---|---|
1eee94d3 GM |
1 | (* Lists.mod provides an unordered list manipulation package. |
2 | ||
83ffe9cd | 3 | Copyright (C) 2001-2023 Free Software Foundation, Inc. |
1eee94d3 GM |
4 | Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>. |
5 | ||
6 | This file is part of GNU Modula-2. | |
7 | ||
8 | GNU Modula-2 is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GNU Modula-2 is distributed in the hope that it will be useful, but | |
14 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
16 | General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GNU Modula-2; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. *) | |
21 | ||
22 | IMPLEMENTATION MODULE Lists ; | |
23 | ||
24 | ||
25 | FROM Storage IMPORT ALLOCATE, DEALLOCATE ; | |
26 | ||
27 | CONST | |
28 | MaxNoOfElements = 5 ; | |
29 | ||
30 | TYPE | |
31 | List = POINTER TO list ; | |
32 | list = RECORD | |
33 | NoOfElements: CARDINAL ; | |
34 | Elements : ARRAY [1..MaxNoOfElements] OF WORD ; | |
35 | Next : List ; | |
36 | END ; | |
37 | ||
38 | (* | |
39 | InitList - creates a new list, l. | |
40 | *) | |
41 | ||
42 | PROCEDURE InitList (VAR l: List) ; | |
43 | BEGIN | |
44 | NEW (l) ; | |
45 | WITH l^ DO | |
46 | NoOfElements := 0 ; | |
47 | Next := NIL | |
48 | END | |
49 | END InitList ; | |
50 | ||
51 | ||
52 | (* | |
53 | KillList - deletes the complete list, l. | |
54 | *) | |
55 | ||
56 | PROCEDURE KillList (VAR l: List) ; | |
57 | BEGIN | |
58 | IF l#NIL | |
59 | THEN | |
60 | IF l^.Next#NIL | |
61 | THEN | |
62 | KillList(l^.Next) | |
63 | END ; | |
64 | DISPOSE(l) | |
65 | END | |
66 | END KillList ; | |
67 | ||
68 | ||
69 | (* | |
70 | PutItemIntoList - places a WORD, c, into list, l. | |
71 | *) | |
72 | ||
73 | PROCEDURE PutItemIntoList (l: List; c: WORD) ; | |
74 | BEGIN | |
75 | WITH l^ DO | |
76 | IF NoOfElements<MaxNoOfElements | |
77 | THEN | |
78 | INC(NoOfElements) ; | |
79 | Elements[NoOfElements] := c | |
80 | ELSIF Next#NIL | |
81 | THEN | |
82 | PutItemIntoList(Next, c) | |
83 | ELSE | |
84 | InitList(Next) ; | |
85 | PutItemIntoList(Next, c) | |
86 | END | |
87 | END | |
88 | END PutItemIntoList ; | |
89 | ||
90 | ||
91 | (* | |
92 | GetItemFromList - retrieves the nth WORD from list, l. | |
93 | (recursive solution). | |
94 | *) | |
95 | (* | |
96 | PROCEDURE GetItemFromList (l: List; n: CARDINAL) : WORD ; | |
97 | BEGIN | |
98 | IF n>NoOfItemsInList(l) | |
99 | THEN | |
100 | RETURN( 0 ) | |
101 | ELSE | |
102 | WITH l^ DO | |
103 | IF n<=NoOfElements | |
104 | THEN | |
105 | RETURN( Elements[n] ) | |
106 | ELSE | |
107 | RETURN( GetItemFromList( Next, n-NoOfElements ) ) | |
108 | END | |
109 | END | |
110 | END | |
111 | END GetItemFromList ; | |
112 | *) | |
113 | ||
114 | (* iterative solution *) | |
115 | PROCEDURE GetItemFromList (l: List; n: CARDINAL) : WORD ; | |
116 | BEGIN | |
117 | WHILE l#NIL DO | |
118 | WITH l^ DO | |
119 | IF n<=NoOfElements | |
120 | THEN | |
121 | RETURN( Elements[n] ) | |
122 | ELSE | |
123 | DEC(n, NoOfElements) | |
124 | END | |
125 | END ; | |
126 | l := l^.Next | |
127 | END ; | |
128 | RETURN( 0 ) | |
129 | END GetItemFromList ; | |
130 | ||
131 | ||
132 | (* | |
133 | GetIndexOfList - returns the index for WORD, c, in list, l. | |
134 | If more than one WORD, c, exists the index | |
135 | for the first is returned. | |
136 | *) | |
137 | ||
138 | PROCEDURE GetIndexOfList (l: List; c: WORD) : CARDINAL ; | |
139 | VAR | |
140 | i: CARDINAL ; | |
141 | BEGIN | |
142 | IF l=NIL | |
143 | THEN | |
144 | RETURN( 0 ) | |
145 | ELSE | |
146 | WITH l^ DO | |
147 | i := 1 ; | |
148 | WHILE i<=NoOfElements DO | |
149 | IF Elements[i]=c | |
150 | THEN | |
151 | RETURN( i ) | |
152 | ELSE | |
153 | INC(i) | |
154 | END | |
155 | END ; | |
156 | RETURN( NoOfElements+GetIndexOfList(Next, c) ) | |
157 | END | |
158 | END | |
159 | END GetIndexOfList ; | |
160 | ||
161 | ||
162 | (* | |
163 | NoOfItemsInList - returns the number of items in list, l. | |
164 | *) | |
165 | (* | |
166 | PROCEDURE NoOfItemsInList (l: List) : CARDINAL ; | |
167 | BEGIN | |
168 | IF l=NIL | |
169 | THEN | |
170 | RETURN( 0 ) | |
171 | ELSE | |
172 | WITH l^ DO | |
173 | RETURN( NoOfElements+NoOfItemsInList(Next) ) | |
174 | END | |
175 | END | |
176 | END NoOfItemsInList ; | |
177 | *) | |
178 | ||
179 | ||
180 | (* | |
181 | NoOfItemsInList - returns the number of items in list, l. | |
182 | (iterative algorithm of the above). | |
183 | *) | |
184 | ||
185 | PROCEDURE NoOfItemsInList (l: List) : CARDINAL ; | |
186 | VAR | |
187 | t: CARDINAL ; | |
188 | BEGIN | |
189 | IF l=NIL | |
190 | THEN | |
191 | RETURN( 0 ) | |
192 | ELSE | |
193 | t := 0 ; | |
194 | REPEAT | |
195 | WITH l^ DO | |
196 | INC(t, NoOfElements) | |
197 | END ; | |
198 | l := l^.Next | |
199 | UNTIL l=NIL; | |
200 | RETURN( t ) | |
201 | END | |
202 | END NoOfItemsInList ; | |
203 | ||
204 | ||
205 | (* | |
206 | IncludeItemIntoList - adds a WORD, c, into a list providing | |
207 | the value does not already exist. | |
208 | *) | |
209 | ||
210 | PROCEDURE IncludeItemIntoList (l: List; c: WORD) ; | |
211 | BEGIN | |
212 | IF NOT IsItemInList(l, c) | |
213 | THEN | |
214 | PutItemIntoList(l, c) | |
215 | END | |
216 | END IncludeItemIntoList ; | |
217 | ||
218 | ||
219 | (* | |
220 | RemoveItem - remove an element at index, i, from the list data type. | |
221 | *) | |
222 | ||
223 | PROCEDURE RemoveItem (p, l: List; i: CARDINAL) ; | |
224 | BEGIN | |
225 | WITH l^ DO | |
226 | DEC(NoOfElements) ; | |
227 | WHILE i<=NoOfElements DO | |
228 | Elements[i] := Elements[i+1] ; | |
229 | INC(i) | |
230 | END ; | |
231 | IF (NoOfElements=0) AND (p#NIL) | |
232 | THEN | |
233 | p^.Next := l^.Next ; | |
234 | DISPOSE(l) | |
235 | END | |
236 | END | |
237 | END RemoveItem ; | |
238 | ||
239 | ||
240 | (* | |
241 | RemoveItemFromList - removes a WORD, c, from a list. | |
242 | It assumes that this value only appears once. | |
243 | *) | |
244 | ||
245 | PROCEDURE RemoveItemFromList (l: List; c: WORD) ; | |
246 | VAR | |
247 | p : List ; | |
248 | i : CARDINAL ; | |
249 | Found: BOOLEAN ; | |
250 | BEGIN | |
251 | IF l#NIL | |
252 | THEN | |
253 | Found := FALSE ; | |
254 | p := NIL ; | |
255 | REPEAT | |
256 | WITH l^ DO | |
257 | i := 1 ; | |
258 | WHILE (i<=NoOfElements) AND (Elements[i]#c) DO | |
259 | INC(i) | |
260 | END ; | |
261 | END ; | |
262 | IF (i<=l^.NoOfElements) AND (l^.Elements[i]=c) | |
263 | THEN | |
264 | Found := TRUE | |
265 | ELSE | |
266 | p := l ; | |
267 | l := l^.Next | |
268 | END | |
269 | UNTIL (l=NIL) OR Found ; | |
270 | IF Found | |
271 | THEN | |
272 | RemoveItem(p, l, i) | |
273 | END | |
274 | END | |
275 | END RemoveItemFromList ; | |
276 | ||
277 | ||
278 | (* | |
279 | IsItemInList - returns true if a WORD, c, was found in list, l. | |
280 | *) | |
281 | ||
282 | PROCEDURE IsItemInList (l: List; c: WORD) : BOOLEAN ; | |
283 | VAR | |
284 | i: CARDINAL ; | |
285 | BEGIN | |
286 | REPEAT | |
287 | WITH l^ DO | |
288 | i := 1 ; | |
289 | WHILE (i<=NoOfElements) DO | |
290 | IF Elements[i]=c | |
291 | THEN | |
292 | RETURN( TRUE ) | |
293 | ELSE | |
294 | INC(i) | |
295 | END | |
296 | END | |
297 | END ; | |
298 | l := l^.Next | |
299 | UNTIL l=NIL ; | |
300 | RETURN( FALSE ) | |
301 | END IsItemInList ; | |
302 | ||
303 | ||
304 | (* | |
305 | ForeachItemInListDo - calls procedure, P, foreach item in list, l. | |
306 | *) | |
307 | ||
308 | PROCEDURE ForeachItemInListDo (l: List; P: PerformOperation) ; | |
309 | VAR | |
310 | i, n: CARDINAL ; | |
311 | BEGIN | |
312 | n := NoOfItemsInList(l) ; | |
313 | i := 1 ; | |
314 | WHILE i<=n DO | |
315 | P(GetItemFromList(l, i)) ; | |
316 | INC(i) | |
317 | END | |
318 | END ForeachItemInListDo ; | |
319 | ||
320 | ||
321 | (* | |
322 | DuplicateList - returns a duplicate list derived from, l. | |
323 | *) | |
324 | ||
325 | PROCEDURE DuplicateList (l: List) : List ; | |
326 | VAR | |
327 | m : List ; | |
328 | n, i: CARDINAL ; | |
329 | BEGIN | |
330 | InitList(m) ; | |
331 | n := NoOfItemsInList(l) ; | |
332 | i := 1 ; | |
333 | WHILE i<=n DO | |
334 | PutItemIntoList(m, GetItemFromList(l, i)) ; | |
335 | INC(i) | |
336 | END ; | |
337 | RETURN( m ) | |
338 | END DuplicateList ; | |
339 | ||
340 | ||
341 | END Lists. |