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