Data-Structures/SimpleLinkedList/SingleLinkedList.mod

IMPLEMENTATION MODULE SingleLinkedList;

FROM SYSTEM IMPORT ADDRESS;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;

TYPE 
  ElementPtr = POINTER TO Element;
  Element    = RECORD
                 pos : CARDINAL;
                 next : ElementPtr;
                 item : ADDRESS;
              END;  
  List      = POINTER TO ListRec;            
  ListRec   = RECORD
                firstElement    : ElementPtr;
                lastElement     : ElementPtr;
                currentElement  :  ElementPtr;
                homogene        : BOOLEAN; (* allows or not homogene items                            *)
                CheckType       : PROC;   (* procedure to check if the elements are of the same type *)
              END; 

(*
PROCEDURE SearchItem ( item : ; compare : PROC ) : BOOLEAN;

  BEGIN
    ;
  END Seach;

PROCEDURE Traverse (l : List; toDo : PROC);

  BEGIN
    ;
  END Traverse;
*)
PROCEDURE Empty (VAR l : List): BOOLEAN ;

  BEGIN
    IF l^.firstElement = NIL THEN
      RETURN TRUE
    ELSE 
     RETURN FALSE 
    END      
  END Empty;
(*
PROCEDURE RemoveItem (): BOOLEAN;

  BEGIN
    ;
  END Remove;

PROCEDURE AddItem (): BOOLEAN;

  BEGIN
    ;
  END Add;

*)
PROCEDURE SetPos(l : List; pos : CARDINAL ) : BOOLEAN ;

BEGIN
  IF pos <= l^.lastElement^.pos THEN
    l^.currentElement^.pos := pos;
    RETURN TRUE 
  ELSE 
    RETURN FALSE   
  END;
END SetPos;

PROCEDURE GetPosCurrentElement (l : List) : CARDINAL ;

  BEGIN
    RETURN l^.currentElement^.pos
  END GetPosCurrentElement;

PROCEDURE GetPosLastElement (l : List) : CARDINAL ;

  BEGIN
    RETURN l^.lastElement^.pos
  END GetPosLastElement;

PROCEDURE AddElement (VAR l : List; pos : CARDINAL) : BOOLEAN ;

VAR 
  localElementPtr : ElementPtr;
  localElementPtr1 : ElementPtr;
  localElementPtr2 : ElementPtr;
  
BEGIN
  IF l # NIL THEN
    IF pos > l^.lastElement^.pos THEN
      RETURN FALSE
    END;
    localElementPtr := l^.firstElement;
    WHILE  l^.localElementPtr^.pos # pos DO
      localElementPtr := localElementPtr^.next;
    END;
    localElementPtr1 := localElementPtr^.next; 
     NEW(localElementPtr2);
     localElementPtr2^.next := localElementPtr1;
     localElementPtr^.next:= localElementPtr;
     WHILE localElementPtr1 # NIL DO
       localElementPtr1^.pos := localElementPtr1^.pos + 1
     END;
  ELSE 
    RETURN  TRUE
  END; 
END AddElement;

PROCEDURE AddElementLast  (VAR l : List );

VAR 
  localElementPtr : ElementPtr;
  
  BEGIN
     IF l # NIL THEN
      (*creating NEW element first, THEN add it TO the list *)
      NEW(localElementPtr);
      localElementPtr^.next := NIL;
      localElementPtr^.item := NIL;
      IF l^.firstElement = NIL THEN
        l^.firstElement := localElementPtr;
        localElementPtr^.pos := 0;
      ELSE 
        localElementPtr^.pos := l^.lastElement^.pos + 1;  
      END; 
      l^.currentElement := localElementPtr;
      l^.lastElement := localElementPtr;
    END 
   
  END AddElementLast ;
  
PROCEDURE FindElement (l : List ; pos : CARDINAL ; VAR p : ElementPtr) : BOOLEAN ;

VAR
  localElementPtr : ElementPtr;
  localElementPtrNext : ElementPtr;
  localPos : CARDINAL;
  
  BEGIN
    (* test if pos is not outside intervalle *)
    IF pos > l^.lastElement^.pos THEN 
      RETURN FALSE 
    END;
    
    localElementPtr := l^.firstElement;
    
    (* test if pos is the first element *)
    IF pos = 0 THEN
      p := localElementPtr;
      RETURN TRUE 
    END;  

    (* other cases : we go the list along*) 
    WHILE localElementPtr # NIL DO
      localElementPtr := localElementPtr^.next;
      IF localElementPtr^.pos = pos THEN 
        p := localElementPtr;
        RETURN TRUE 
      END;
    END;
    RETURN FALSE 
  END FindElement;  
  
  
PROCEDURE RemoveElement (VAR l : List; pos : CARDINAL ) : BOOLEAN ;

VAR
  localElementPtr1 : ElementPtr;
  localElementPtr2 : ElementPtr;
  
  BEGIN
    IF l # NIL THEN 
      IF pos > l^.lastElement^.pos THEN
        RETURN FALSE 
      ELSIF pos = l^.firstElement THEN 
      
      
      ELSIF  pos = l^.lastElement THEN
        
        
      ELSE 
      (* case where the element is in-betwwen *)
      
      END;
    ELSE   
      RETURN FALSE   
    END;
  END RemoveElement;
    

PROCEDURE DoEmptyList (VAR l : List);

BEGIN

END DoEmptyList;

PROCEDURE DeleteAllItems (VAR l : List);

BEGIN

END DeleteAllItems;

PROCEDURE Free ( VAR l : List);

BEGIN 
  DeleteAllItems(l);
  DoEmptyList(l);
  l^.firstElement := NIL;
  l^.lastElement := NIL;
  l^.currentElement := NIL;
  l^.homogene := TRUE ;
  l^.CheckType := NIL;
  DISPOSE (l);               (* destroying the List structure record *)
  l := NIL;
END Free;

PROCEDURE Init ( VAR l : List; mode : BOOLEAN ; p : PROC );

  BEGIN
    NEW (l);                 (* creating the List structure record *)
    l^.firstElement := NIL;
    l^.lastElement := l^.firstElement;
    l^.currentElement := l^.firstElement;
    l^.homogene := mode;
    l^.CheckType := p;
  END Init;

BEGIN
  (* Initialization of the SingleLinkedList structure *)
  
END SingleLinkedList.