Pointers to arrays and arrays of pointers

I am being brave today and swimming further from the shore of POINTERland. Specifically, I am trying to write code that uses an octree data structure. Maybe the fact that I couldn't easily find any octree FORTRAN source code out there should have warned me off, but still.

The thing that is causing me serious brainache is the need for an array of pointers. I've done enough homework to know that I'm not allowed to have one in FORTRAN 9x, not as such (why is that, incidentally?), but that I can 'achieve the effect' by sleight of code. I've also looked at some examples of how to do this, and I can even, for brief eureka moments, understand them. Sort of. However, they all involve an ALLOCATABLE array of a simple derived data type, for example (for .. read :, it prevents infection of code by the smiley virus):

type foo integer, pointer :: x (..) end type foo

type (foo), allocatable :: y (..)

So that gives a one-dimensional array of one-dimensional arrays, and gets around the prohibition of ALLOCATABLE components of derived types, but still requires the use of ALLOCATABLE 'at the top level', as it were.

It seems to me that the essential nature of these examples is not an array of pointers, but an array of arrays. It just happens that to get such a thing in FORTRAN 9x *requires *an array of pointers.

My problem is that I want to do something like this:

type foo ... type (foo), pointer :: next (n) end typ foo

except that gives me, within the derived type, a pointer to an array of type foo, rather than an array of pointers to type foo. And if I try and work from the examples, they don't help, because I don't want a one-dimensional array of one-dimensional arrays, I just want a one-dimensional array of pointers, but inside a derived type, and that seems to require the use of ALLOCATABLE, which I'm not allowed to have.

Am I hard up against a linguistic boundary of FORTRAN 9x here, or is there an ingenious way to work around the prohibition on ALLOCATABLE components of derived types AND the prohibition on arrays of pointers?

I realise I *could *do this:

type foo ... type (foo), pointer :: next1 type (foo), pointer :: next2 ... type (foo), pointer :: nextn end typ foo

but this would definitely be a last resort.

I hope this makes sense. I think I need to go and have a lie down in a dark room.

Replying to my own post just to say, if anyone else is puzzling over this, on my or their behalf, please puzzle no more for I have found the answer.

As always, Metcalf knows all. The answer is actually to be found in Metcalf & Reid, and I had even seen it and not recognised it for what it was. I had to find and read this little gem:

http://cdsweb.cern.ch/record/277012/files/cn-95-001.pdf

before the penny dropped.

The trick, which sets up the FORTRAN analogue (I hesitate to say equivalent) of pointer to pointer, is the data type equivalent of putting a wrapper around a function or subroutine. Like this:

type foo_pointer
  type (foo), pointer :: next
end type foo_pointer

type foo
.
.
  type (foo_pointer) :: bar (:)
.
.
end type foo

Beautiful. Or as Blackadder put it, more cunning than a fox who has just been made professor of Cunning at Cunning University. I struggle to keep my head around it; I am in awe of someone who could originate it.

Most programming languages allow pointers to type T to be used as components in defining type B before type T has been defined. In fact, pointers to type T can be used in the definition of type T itself.

For your amusement, here is a short program to construct the classical binary tree and to print the node values (words of text in this example) in lexical order. The key is the 'self-referential structure' in the derived type tnode.

program BinTree

! Insert a list of 5-character words into a binary tree, starting from scratch
! Print the words in alphabetical order
!
implicit none

type tnode
  type (tnode), pointer :: left=>null(),right=>null()
  character(len=5),pointer :: name=>null()
  integer :: count=1
end type tnode

type(tnode),pointer :: T
integer, parameter :: N = 7
character(5), dimension(N) :: names=(/'cat  ','mouse','lion ','bat  ', &
                                      'tiger','bat  ','goat '/)
integer :: i

  allocate(T)
  do i=1,N
     call add(T,names(i))
  end do

  call prnt(T)
  
contains

   recursive subroutine add(root,word)
   implicit none
   type(tnode), intent(in out) :: root
   character(len=*),intent(in),target :: word

   type(tnode), pointer :: p
    
   if(.not.associated(root%name))then          !empty leaf node found
      root%name => word
      return
   endif
   if(llt(word,root%name))then
      if(.not.associated(root%left))then       !fork new left  branch
         allocate(p)
         root%left=>p
         p%name => word
         return
      endif
      call add(root%left,word)
      return
   elseif(lgt(word,root%name))then
      if(.not.associated(root%right))then       !fork new right branch
         allocate(p)
         root%right=>p
         p%name => word
         return
      endif
      call add(root%right,word)
      return
   endif
   root%count=root%count+1                      ! match found; update count
   return
   end subroutine add

   recursive subroutine prnt(root)
   implicit none
   type(tnode) :: root

   if(associated(root%left))call prnt(root%left)
   write(*,'(1x,A5,1x,I2)')root%name,root%count
   if(associated(root%right))call prnt(root%right)

   return
   end subroutine prnt
   
end program BinTree

Amused.

And abused.

The text looks not easily readable. Scary if this is Fortran future.

But could be it's just my opinion. What people think, may be it is the best way to write for example the chess-like programs? Can anyone write an example of simple X's & O's game written this way which requires numerous branching trees created and compare to older programming style?