Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!gatech!unmvax!brainerd
From: brainerd@unmvax.unm.edu (Walt Brainerd)
Newsgroups: comp.lang.fortran
Subject: Re: Pointer examples and 8x
Summary: The Fortran version
Message-ID: <158@unmvax.unm.edu>
Date: 17 Jun 89 17:40:37 GMT
References: <BILL.89Jun16132046@hcx2.ssd.harris.com>
Distribution: usa
Organization: University of New Mexico at Albuquerque
Lines: 146

In article <BILL.89Jun16132046@hcx2.ssd.harris.com>, bill@ssd.harris.com (Bill Leonard) writes:
> In article <6028@microsoft.UUCP> bobal@microsoft.UUCP (Bob Allison) writes:
> 
>    . . .  Bill Leonard, in
>    email to members of the committee complained that it was awfully difficult
>    to use this form of pointers to insert items in a linked list (at least,
> >  I think that was the example), a fairly common usage of pointers.  As I
> >  recall, someone came back with a solution which was deemed "elegant" and
> >  was implemented using recursion.  Ugh!  I just want to walk around
> >  lists and stuff.

> Okay, here are my examples.  I am wrote these in C ...  the point is
> that 8x pointers cannot point to other pointers,
> 
> NOTE: I know that you CAN implement these routines in 8x IF you make each
> pointer be a structure whose only field is the pointer.  This is fine, if
> your purpose is to obscure what the code is doing.

Well, I guess Bill didn't read the responses to his own queries
last time around, but maybe this will give others the opportunity to see
how it can be done in Fortran 8x.

I should be doing useful work instead of this, but I don't want to leave
the impression that all X3J3 members can't write programs in Fortran.
(although in this case, as opposed to C, I don't have a compiler to
test it on, so there is even more liklihood of some bugs).

First, note that there is no need for pointers pointing to pointers.
All pointers in the list processing examples (both Leonard's and mine)
point to structures.  Also, there are no structures whose only component
is a pointer.

To show the contrast between the C program Bill wrote, the "walk" around
version in Fortran 8x and the (Ugh!) elegant version using recursion
even more, let's not pick the particularaly simple example in Bill's
list insertion, but instead assume the list is to be maintained in
ascending order.  If, for example, we are to insert the number 17,
it must work if the list is empty, if all numbers are < 17, or if
all numbers are > 17.  In this example, you have to make an insertion
_before_ the node you find having a certain property. To do this,
I think even nonfreshman need two pointers (a trailing pointer is needed)
(but maybe someone else can do it with one)
and the empty list is either a special case (Bill just printed an error mesg)
or there must always be a dummy node in the list (I have arbitrarily chosen
the latter).  Here are the necessary declarations.

   TYPE NODE
      INTEGER :: VALUE
      TYPE (NODE), POINTER :: NEXT
   END TYPE NODE

   TYPE (NODE), POINTER :: LIST
   INTEGER :: NUMBER

Next is the code to initialize the list (to contain only a dummy node).

   ALLOCATE (LIST)
   LIST % VALUE = -HUGE (0)
   NULLIFY (LIST % NEXT)

Here is the program to insert NUMBER in order in the list
by "walking" thru the list.

   SUBROUTINE INSERT (PTR, NUMBER)

      TYPE (NODE), POINTER, INTENT (IN) :: PTR
      TYPE (NODE), POINTER :: TMP_PTR, TRAIL_PTR
      INTEGER, INTENT (IN) :: NUMBER

      ! "Walk" thru the list to
      ! determine where NUMBER goes
      TRAIL_PTR => PTR
      TMP_PTR => TRAIL_PTR % NEXT
      DO
         IF (.NOT. ASSOCIATED (TMP_PTR) EXIT
         IF (NUMBER <= TMP_PTR % VALUE) EXIT
         TRAIL_PTR = TMP_PTR
         TMP_PTR => TRAIL_PTR % NEXT
      END DO

      ! Insert into sublist
      ALLOCATE (TRAIL_PTR % NEXT)
      TRAIL_PTR % NEXT % VALUE = NUMBER
      TRAIL_PTR % NEXT % NEXT => TMP_PTR

   END SUBROUTINE INSERT

Others may be able to write a better version that does this,
because this is not my style.  Following is the (Ugh!) "elegant"
version.  This should be compared to the previous version, or to
one supplied by someone else, if they can provide a better one.
First is the code to initialize the list (no dummy node needed).

   NULLIFY (LIST)

Next, the subroutine.

   RECURSIVE SUBROUTINE INSERT (L, NUMBER)

      TYPE (NODE), POINTER :: L, TMP_L
      INTEGER, INTENT (IN) :: NUMBER

      ! If NUMBER goes here, insert it in new node
      IF (NUMBER <= L % VALUE) THEN
         ALLOCATE (TMP_L)
         TMP_L % VALUE = NUMBER
         TMP_L % NEXT => L % NEXT
      ! Otherwise, insert into sublist
      ELSE
         CALL INSERT (L % NEXT, NUMBER)
      END IF

   END SUBROUTINE INSERT

Challenge 1: Do this as well as possible and we'll let others vote
as to which version is better.

Challenge 2: Since Bob Allison likes to "walk around" structures, I would
like to see his version of the following (Ugh!) recursive subroutine
that prints a binary tree of integers in infix order (or any other order).
First the necessary declarations, then the subroutine.

   TYPE NODE
      INTEGER :: VALUE
      TYPE (NODE), POINTER :: LEFT, RIGHT
   END TYPE NODE

   RECURSIVE SUBROUTINE PRINT_TREE (T)
   ! Print tree in infix order

      TYPE (NODE), POINTER, INTENT (IN) :: T

      IF (ASSOCIATED (T)) THEN
         CALL PRINT_TREE (T % LEFT)
         PRINT *, T % VALUE
         CALL PRINT_TREE (T % RIGHT)
      END IF

   END SUBROUTINE PRINT_TREE

Jeanne Martin of LLNL, I believe, posted Fortran 8x versions of
Leonard's matrix example and it had none of the properties Bill claimed
it would have to have (I believe).  Maybe she would be willing to
post her example again.

Walt Brainerd   Unicomp, Inc.  brainerd@unmvax.unm.edu