Dynamic Data Structures

Lack of dynamic data structures is another shortcoming of Fortran 77 that has been overcome in Fortran 90. Linked lists, trees, graphs, and other dynamic data structures that are allocated at runtime can be constructed using some of Fortran 90's new capabilities. The following program indicates the basic features of Fortran 90's pointers.

program TryPointers
   integer, pointer :: p, q
   integer, target :: n
   integer m

   n = 5

   p => n
   q => p

   allocate( p )
   p = 4

   m = p + q + n

   print *, "m = ", m
end program TryPointers

The program above illustrates many key concepts in the design of Fortran 90 pointers.

• The pointer attribute is used to identify variables that serve as descriptors for other data objects only. In the program above, p and q are ``pointers to integers''.
• The variable n is declared with the target attribute. This indicates that n may serve as a target to an integer pointer such as p or q. A target is an object that may be referenced via a pointer. The target of a pointer is very restrictive--only variables with the target or pointer attributes may be referenced via a pointer.
• The statement p => n is called a pointer assignment statement, and is used to associate the target, n, with the pointer, p. This is possible because n has been declared with the target attribute. In effect, p is an alias for n and may be used just as n is used (p can be thought of as ``pointing to'' n).
• The following statement, q => p, is different. In the previous pointer assignment statement, a pointer is associated with a non-pointer variable, n. However, this pointer assignment statement contains variables that are pointers on both the left and right hand sides. In this case, q is associated with the target of p, namely n, rather than p itself.
• The allocate statement is used to dynamically allocate space for a target and associate the pointer with the target. Thus, allocate( p ) reserves space for an integer target that is associated with p. At this time, the contents of the target are not defined. The previous target of p, n, is unaffected. Similarly, because q is not associated with p, the target of q is unaffected.
• The statement p = 4 defines the target of p to contain the integer 4 and illustrates an important characteristic of Fortran 90's pointers--there is no dereference operator. Instead, the pointers are resolved to their targets before the assignment is made. This occurs in any expression involving pointers with the exception of the pointer assignment statement described above.
• As mentioned above, pointers are resolved to their targets in any expression not involving pointer assignment. Consequently, the statement m = p + q + n uses the values of the targets of p and q and the value of n to evaluate the expression. Because the values of the targets of p and q are 4 and 5, respectively, and n is 5, their sum, 14, is assigned to the the integer m.

A more complete example of a dynamic data structure is given below which manipulates a linked list of real numbers. Elements are allocated as needed and deallocated after use.

program LinkedList
   type node
      real data
      type( node ), pointer :: next
   end type node
 
   type( node ), pointer :: list, current, previous
   integer, parameter :: N = 10

   nullify( list )   ! Initialize list to point to no target.

   ! Add the 1st element as a special case.
   if ( N > 0 ) then
      allocate( list )
      nullify( list%next )
      call random_number( list%data )
   end if

   current => list

   ! Add N random numbers to the list.
   do i = 2, N
      allocate( current%next )
      nullify( current%next%next )
      call random_number( current%next%data )
      current => current%next
   end do

   ! Output the list, deallocating them after use.

   print *, 'List elements are:'

   current => list
   do while ( associated( current ) )
      print *, current%data
      previous => current
      current => current%next
      deallocate( previous )
   end do

end program LinkedList

Exercise 2.14 A linked list can be used to model an integer of arbitrary length. The following program implements unsigned extended integer arithmetic using this integer model, where the head of the linked list points to the least significant digit in the extended integer. For example, the extended integer 987654321 is represented as the list 1 2 3 4 5 6 7 8 9 where the last pointer in the integer is nullified to mark the end of the list.

module ExtendedIntegers

   ! A kind value representing a single digit only.
   integer, parameter :: Q = selected_int_kind( 1 )
   private Q

   type UnsignedExtendedInteger
      integer( Q ) digit
      type( UnsignedExtendedInteger ), pointer :: next
   end type UnsignedExtendedInteger

   type ExtendedInteger
      type( UnsignedExtendedInteger ), pointer :: number
   end type ExtendedInteger

   interface operator (+)
      module procedure addExtendedInteger
   end interface

   contains

   function addExtendedInteger( m, n )
      type( ExtendedInteger ) addExtendedInteger
      type( ExtendedInteger ), intent( in ) :: m, n

      type( ExtendedInteger ) sum
      type( UnsignedExtendedInteger ), pointer :: current1, current2
      type( UnsignedExtendedInteger ), pointer :: current, previous
      integer( Q ) carry
      integer digitSum

      ! Allocate space for the number component of sum.
      allocate( sum%number )
      nullify( sum%number%next )

      ! Add the first two digits of m and n as a special case.

      ! Associate current1 and current2 with the first digits of the numbers
      !  of m and n.
      current1 => m%number
      current2 => n%number

      digitSum = current1%digit + current2%digit 

      ! Check for carry
      if ( digitSum > 9 ) then
         digitSum = digitSum - 10
         carry = 1
      else
         carry = 0
      end if

      ! Assign the first digit into the sum.
      sum%number%digit = digitSum

      previous => sum%number
      current1 => current1%next
      current2 => current2%next

      ! Begin the general addition of m and n.  m and n should be
      !  have their ends marked with null pointers.
      do while ( associated( current1 ) .and. associated( current2 ) )
         digitSum = current1%digit + current2%digit + carry

         ! Check for carry
         if ( digitSum > 9 ) then
            digitSum = digitSum - 10
            carry = 1
         else
            carry = 0
         end if

         ! Assign current digit into sum.
         allocate( previous%next )
         nullify( previous%next%next )
         previous%next%digit = digitSum

         previous => previous%next
         current1 => current1%next
         current2 => current2%next
      end do

      ! current1, current2, or both have been exhausted.  Continue with current.
      if ( associated( current1 ) ) then
         current => current1
      else
         current => current2
      end if

      do while ( associated( current ) )
         digitSum = current%digit + carry

         ! Check for carry
         if ( digitSum > 9 ) then
            digitSum = digitSum - 10
            carry = 1
         else
            carry = 0
         end if

         ! Assign current digit into sum.
         allocate( previous%next )
         nullify( previous%next%next )
         previous%next%digit = digitSum

         previous => previous%next
         current => current%next
      end do

      ! Check for a carry that has propagated to the most significant
      !  place.
      if ( carry /= 0 ) then
         ! Assign carry digit into sum.
         allocate( previous%next )
         nullify( previous%next%next )
         previous%next%digit = carry
      end if

      ! Prepare to return sum.
      addExtendedInteger = sum
   end function addExtendedInteger

   subroutine readExtendedInteger( n )
      type( ExtendedInteger ), intent( out ) :: n

      type( UnsignedExtendedInteger ), pointer :: new
      character ch
      integer( Q ) value


      nullify( n%number )   ! No list initially.

      
      do while (.true.)
         read(*, fmt="(A)", advance="no", eor=100) ch

         ! Determine the numerical value of the character.
         select case ( ch )
            case( '0' )
               value = 0
            case( '1' )
               value = 1
            case( '2' )
               value = 2
            case( '3' )
               value = 3
            case( '4' )
               value = 4
            case( '5' )
               value = 5
            case( '6' )
               value = 6
            case( '7' )
               value = 7
            case( '8' )
               value = 8
            case( '9' )
               value = 9
            case default
               print * , 'Input error in reading extended integer'
               stop
         end select

         ! Allocate a new node for the digit
         allocate( new )
         new%digit = value

         if ( .not. associated( n%number ) ) then
            ! List not yet started.
            nullify( new%next )
         else
            ! List already started.
            new%next => n%number
         end if

         n%number => new
      enddo

   100 end subroutine readExtendedInteger

end module ExtendedIntegers

A subroutine to input unsigned extended integers is included in the module. Write a subroutine to output an extended integer based on the model of representation described above. Write a program to test your function and the ExtendedIntegers module.