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