MODULE C5P3;  (* Chapter 5  Problem 3 *)

  (* From the book "Modula-2  A Seafarer's Manual and Shipyard Guide" *)
  (* Page 162   adapted "Amiga M2Modula-2"   11 Mar 1988 *)

FROM InOut IMPORT WriteLn,
                  WriteString,
                  WriteCard,
                  ReadCard;
FROM Storage IMPORT ALLOCATE;
                                   
TYPE
  AgePntr = POINTER TO AgeNode;
  AgeNode =			(* list entry, age/next pointer *)
    RECORD
      CrewMemAge : CARDINAL;
      PrevAge : AgePntr;
      NextAge : AgePntr;
    END;
    
VAR
  YoungPntr,			(* list pointers: youngest age *)
  OldPntr,			(*                oldest age *)
  NewPntr,			(*                new age entry *)
  CurrPntr,			(*                current one for search *)
  PrevPntr : AgePntr;		(*                previous one for search *)
  
BEGIN
  YoungPntr := NIL;		(* initially set list null *)
  OldPntr := NIL;
  WriteLn;
  WriteString ("Enter crew ages: ");
  WriteLn;
  
  LOOP
    ALLOCATE (NewPntr, SIZE (NewPntr^));   (* allocate space for list entry *)
    WriteLn;
    ReadCard (NewPntr^.CrewMemAge);	(* accept age from keyboard *)
    IF (NewPntr^.CrewMemAge = 0) THEN	(* age = 0? *)
      EXIT;				(* yes - input done *)
    END;   (* IF *)			(* no - add age in list by
                                           ascending order *)
    PrevPntr := NIL;		(* set previous pointer to NIL *)
    CurrPntr := YoungPntr;	(* set current pointer to youngest *)
    
    (* find place in list where age belongs *)
    WHILE ((CurrPntr # NIL) AND
           (NewPntr^.CrewMemAge > CurrPntr^.CrewMemAge))
           DO
      PrevPntr := CurrPntr;
      CurrPntr := CurrPntr^.NextAge;
    END;   (* WHILE *)		(* quit searching if end of list or new
                                   age <= current age on list *)
                                   
    IF (CurrPntr # NIL) THEN	(* new age <= current age on list? *)
      NewPntr^.NextAge := CurrPntr;	(* yes - put new in front *)
      CurrPntr^.PrevAge := NewPntr;
    ELSE
      NewPntr^.NextAge := NIL;		(* no - put new at end *)
      OldPntr := NewPntr;
    END;   (* IF *)
    
    IF (PrevPntr # NIL) THEN	(* is new before youngest or is list null? *)
      PrevPntr^.NextAge := NewPntr;	(* no - point previous at new *)
      NewPntr^.PrevAge := PrevPntr;
    ELSE
      YoungPntr := NewPntr;		(* yes - point youngest at new *)
      NewPntr^.PrevAge := NIL;
    END;   (* IF *)
    
  END;   (* LOOP *)		(* get next age *)
  
  WriteLn;
  WriteString ("Sorted ages in ascending order:");
  
  CurrPntr := YoungPntr;		(* display ages in ascending order *)
  WHILE (CurrPntr # NIL) DO		(* end of list? *)
    WriteLn;				(* no *)
    WriteCard (CurrPntr^.CrewMemAge,0);
    CurrPntr := CurrPntr^.NextAge;	(* point to next one *)
  END;   (* WHILE *)
  WriteLn;

  WriteLn;
  WriteString ("Sorted ages in descending order:");
  
  CurrPntr := OldPntr;			(* display ages in descending order *)
  WHILE (CurrPntr # NIL) DO		(* end of list? *)
    WriteLn;				(* no *)
    WriteCard (CurrPntr^.CrewMemAge,0);
    CurrPntr := CurrPntr^.PrevAge;	(* point to next one *)
  END;   (* WHILE *)
  WriteLn; WriteLn;

END C5P3.