(* Lists.mod provides an unordered list manipulation package.

Copyright (C) 2001-2023 Free Software Foundation, Inc.
Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>.

This file is part of GNU Modula-2.

GNU Modula-2 is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GNU Modula-2 is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Modula-2; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  *)

IMPLEMENTATION MODULE Lists ;


FROM Storage IMPORT ALLOCATE, DEALLOCATE ;

CONST
   MaxNoOfElements = 5 ;

TYPE
   List = POINTER TO list ;
   list = RECORD
             NoOfElements: CARDINAL ;
             Elements    : ARRAY [1..MaxNoOfElements] OF WORD ;
             Next        : List ;
          END ;

(*
   InitList - creates a new list, l.
*)

PROCEDURE InitList (VAR l: List) ;
BEGIN
   NEW (l) ;
   WITH l^ DO
      NoOfElements := 0 ;
      Next := NIL
   END
END InitList ;


(*
   KillList - deletes the complete list, l.
*)

PROCEDURE KillList (VAR l: List) ;
BEGIN
   IF l#NIL
   THEN
      IF l^.Next#NIL
      THEN
         KillList(l^.Next)
      END ;
      DISPOSE(l)
   END
END KillList ;


(*
   PutItemIntoList - places a WORD, c, into list, l.
*)

PROCEDURE PutItemIntoList (l: List; c: WORD) ;
BEGIN
   WITH l^ DO
      IF NoOfElements<MaxNoOfElements
      THEN
         INC(NoOfElements) ;
         Elements[NoOfElements] := c
      ELSIF Next#NIL
      THEN
         PutItemIntoList(Next, c)
      ELSE
         InitList(Next) ;
         PutItemIntoList(Next, c)
      END
   END
END PutItemIntoList ;


(*
   GetItemFromList - retrieves the nth WORD from list, l.
                     (recursive solution).
*)
(*
PROCEDURE GetItemFromList (l: List; n: CARDINAL) : WORD ;
BEGIN
   IF n>NoOfItemsInList(l)
   THEN
      RETURN( 0 )
   ELSE
      WITH l^ DO
         IF n<=NoOfElements
         THEN
            RETURN( Elements[n] )
         ELSE
            RETURN( GetItemFromList( Next, n-NoOfElements ) )
         END
      END
   END
END GetItemFromList ;
*)

(* iterative solution *)
PROCEDURE GetItemFromList (l: List; n: CARDINAL) : WORD ;
BEGIN
   WHILE l#NIL DO
      WITH l^ DO
         IF n<=NoOfElements
         THEN
            RETURN( Elements[n] )
         ELSE
            DEC(n, NoOfElements)
         END
      END ;
      l := l^.Next
   END ;
   RETURN( 0 )
END GetItemFromList ;


(*
   GetIndexOfList - returns the index for WORD, c, in list, l.
                    If more than one WORD, c, exists the index
                    for the first is returned.
*)

PROCEDURE GetIndexOfList (l: List; c: WORD) : CARDINAL ;
VAR
   i: CARDINAL ;
BEGIN
   IF l=NIL
   THEN
      RETURN( 0 )
   ELSE
      WITH l^ DO
         i := 1 ;
         WHILE i<=NoOfElements DO
            IF Elements[i]=c
            THEN
               RETURN( i )
            ELSE
               INC(i)
            END
         END ;
         RETURN( NoOfElements+GetIndexOfList(Next, c) )
      END
   END
END GetIndexOfList ;


(*
   NoOfItemsInList - returns the number of items in list, l.
*)
(*
PROCEDURE NoOfItemsInList (l: List) : CARDINAL ;
BEGIN
   IF l=NIL
   THEN
      RETURN( 0 )
   ELSE
      WITH l^ DO
         RETURN( NoOfElements+NoOfItemsInList(Next) )
      END
   END
END NoOfItemsInList ;
*)


(*
   NoOfItemsInList - returns the number of items in list, l.
                     (iterative algorithm of the above).
*)

PROCEDURE NoOfItemsInList (l: List) : CARDINAL ;
VAR
   t: CARDINAL ;
BEGIN
   IF l=NIL
   THEN
      RETURN( 0 )
   ELSE
      t := 0 ;
      REPEAT
         WITH l^ DO
            INC(t, NoOfElements)
         END ;
         l := l^.Next
      UNTIL l=NIL;
      RETURN( t )
   END
END NoOfItemsInList ;


(*
   IncludeItemIntoList - adds a WORD, c, into a list providing
                         the value does not already exist.
*)

PROCEDURE IncludeItemIntoList (l: List; c: WORD) ;
BEGIN
   IF NOT IsItemInList(l, c)
   THEN
      PutItemIntoList(l, c)
   END
END IncludeItemIntoList ;


(*
   RemoveItem - remove an element at index, i, from the list data type.
*)

PROCEDURE RemoveItem (p, l: List; i: CARDINAL) ;
BEGIN
   WITH l^ DO
      DEC(NoOfElements) ;
      WHILE i<=NoOfElements DO
         Elements[i] := Elements[i+1] ;
         INC(i)
      END ;
      IF (NoOfElements=0) AND (p#NIL)
      THEN
         p^.Next := l^.Next ;
         DISPOSE(l)
      END
   END
END RemoveItem ;


(*
   RemoveItemFromList - removes a WORD, c, from a list.
                        It assumes that this value only appears once.
*)

PROCEDURE RemoveItemFromList (l: List; c: WORD) ;
VAR
   p    : List ;
   i    : CARDINAL ;
   Found: BOOLEAN ;
BEGIN
   IF l#NIL
   THEN
      Found := FALSE ;
      p := NIL ;
      REPEAT
         WITH l^ DO
            i := 1 ;
            WHILE (i<=NoOfElements) AND (Elements[i]#c) DO
               INC(i)
            END ;
         END ;
         IF (i<=l^.NoOfElements) AND (l^.Elements[i]=c)
         THEN
            Found := TRUE
         ELSE
            p := l ;
            l := l^.Next
         END
      UNTIL (l=NIL) OR Found ;
      IF Found
      THEN
         RemoveItem(p, l, i)
      END
   END
END RemoveItemFromList ;


(*
   IsItemInList - returns true if a WORD, c, was found in list, l.
*)

PROCEDURE IsItemInList (l: List; c: WORD) : BOOLEAN ;
VAR
   i: CARDINAL ;
BEGIN
   REPEAT
      WITH l^ DO
         i := 1 ;
         WHILE (i<=NoOfElements) DO
            IF Elements[i]=c
            THEN
               RETURN( TRUE )
            ELSE
               INC(i)
            END
         END
      END ;
      l := l^.Next
   UNTIL l=NIL ;
   RETURN( FALSE )
END IsItemInList ;


(*
   ForeachItemInListDo - calls procedure, P, foreach item in list, l.
*)

PROCEDURE ForeachItemInListDo (l: List; P: PerformOperation) ;
VAR
   i, n: CARDINAL ;
BEGIN
   n := NoOfItemsInList(l) ;
   i := 1 ;
   WHILE i<=n DO
      P(GetItemFromList(l, i)) ;
      INC(i)
   END
END ForeachItemInListDo ;


(*
   DuplicateList - returns a duplicate list derived from, l.
*)

PROCEDURE DuplicateList (l: List) : List ;
VAR
   m   : List ;
   n, i: CARDINAL ;
BEGIN
   InitList(m) ;
   n := NoOfItemsInList(l) ;
   i := 1 ;
   WHILE i<=n DO
      PutItemIntoList(m, GetItemFromList(l, i)) ;
      INC(i)
   END ;
   RETURN( m )
END DuplicateList ;


END Lists.