gcc/m2/mc/alists.mod

   1 (* alists.mod address lists module.
   2
   3 Copyright (C) 2015-2024 Free Software Foundation, Inc.
   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.