On 08/28/2012 10:48 PM, James Van Buskirk wrote:
> "Wolfgang Kilian"<see...@domain.invalid> wrote in message
> news:k1i3ue$rld$1...@dont-email.me...
>
>> And IIRC, Fortran 2008 introduces recursive derived types with ALLOCATABLE
>> components, so pointers will no longer be required for allocating ordinary
>> lists/trees - hopefully.
>
> How in the world is that going to work? You have to insert into,
> delete from, and rebalance trees. Can you really do all the
> necessary shuffling with allocatables rather than pointers?
I thought that was the rationale for introducing type-recursive
allocatable components?
In any case, since I have uses for this anyway, I wrote a short module
that can build a list, print, and extract/insert list slices at
arbitrary position. That should cover all cases, right? (If you like,
you may turn the idea into a generic list handler.) I checked the
program as a pointer version, but it is trivial to eliminate all
pointers in favor of allocatables (see below). Lacking a F2008
compiler, I couldn't check the version with allocatables only.
The version with allocatables only has no way to involuntarily introduce
memory leaks or circles in the data structure.
In the example, list scanning is done by recursive procedures and takes
linear time. It is probably better to do this iteratively and/or use
shortcuts; this would require additional pointers on top of the
allocatable backbone. However, they just point to something, there is
never a (DE)ALLOCATE statement for a pointer, which is the main point of
the argument.
If the reasoning is correct, I would conjecture that pointers can be
eliminated naturally from all data structures that are representable as
a directed acyclical graph. For others, it's also possible, but one
needs additional pointers for back- and circular references, which spoil
the simplicity of the approach.
Here is some code:
----------------------------------------------------------------------
! Simple list-handling module
! using pointers
! To trade all pointers for allocatables:
! - remove the move_alloc subroutine, so the intrinsic is used instead
! - change pointer -> allocatable
! - change associated -> allocated
module list_alloc
implicit none
type :: entry_t
integer :: value = 0
type(entry_t), pointer :: next => null ()
! type(entry_t), allocatable :: next ! not allowed in F2003
end type entry_t
type :: list_t
type(entry_t), pointer :: first => null ()
! type(entry_t), allocatable :: first
end type list_t
contains
subroutine move_alloc (from, to)
type(entry_t), pointer, intent(inout) :: from, to
to => from
from => null ()
end subroutine move_alloc
subroutine append_entry (list, value)
type(list_t), intent(inout) :: list
integer, intent(in) :: value
call find_last_append (list%first)
contains
recursive subroutine find_last_append (entry)
type(entry_t), pointer, intent(inout) :: entry
if (associated (entry)) then
call find_last_append (entry%next)
else
allocate (entry)
entry%value = value
end if
end subroutine find_last_append
end subroutine append_entry
subroutine list_extract_slice (list, slice, beg, len)
type(list_t), intent(inout) :: list
type(list_t), intent(out) :: slice
integer, intent(in) :: beg, len
call split_at_beg (list%first, 1)
contains
recursive subroutine split_at_beg (list_entry, i)
type(entry_t), pointer, intent(inout) :: list_entry
integer, intent(in) :: i
if (associated (list_entry)) then
if (i == beg) then
call move_alloc (list_entry, slice%first)
call join_tail (slice%first, list_entry, 0)
else
call split_at_beg (list_entry%next, i + 1)
end if
end if
end subroutine split_at_beg
recursive subroutine join_tail (slice_entry, last_list_entry, i)
type(entry_t), pointer, intent(inout) :: slice_entry, last_list_entry
integer, intent(in) :: i
if (associated (slice_entry)) then
if (i == len) then
call move_alloc (slice_entry, last_list_entry)
else
call join_tail (slice_entry%next, last_list_entry, i + 1)
end if
end if
end subroutine join_tail
end subroutine list_extract_slice
subroutine list_insert_slice (list, slice, beg)
type(list_t), intent(inout) :: list
type(list_t), intent(inout) :: slice
integer, intent(in) :: beg
call split_at_beg (list%first, 1)
contains
recursive subroutine split_at_beg (list_entry, i)
type(entry_t), pointer, intent(inout) :: list_entry
integer, intent(in) :: i
type(entry_t), pointer :: tail_first
if (associated (list_entry)) then
if (i == beg) then
call move_alloc (list_entry, tail_first)
call move_alloc (slice%first, list_entry)
call join_tail (list_entry, tail_first)
else
call split_at_beg (list_entry%next, i + 1)
end if
end if
end subroutine split_at_beg
recursive subroutine join_tail (list_entry, tail_first)
type(entry_t), pointer, intent(inout) :: list_entry, tail_first
if (associated (list_entry)) then
call join_tail (list_entry%next, tail_first)
else
call move_alloc (tail_first, list_entry)
end if
end subroutine join_tail
end subroutine list_insert_slice
subroutine list_print (list)
type(list_t), intent(in) :: list
call print_entry_rec (list%first)
contains
recursive subroutine print_entry_rec (entry)
type(entry_t), pointer, intent(in) :: entry
if (associated (entry)) then
print *, entry%value
call print_entry_rec (entry%next)
end if
end subroutine print_entry_rec
end subroutine list_print
end module list_alloc
program main
use list_alloc
implicit none
type(list_t) :: list, slice
integer :: i
print *, "Fill list: 1 2 3 4 5 6 7 8 9 10"
do i = 1, 10
call append_entry (list, i)
end do
call list_print (list)
print *
print *, "Extract slice from beg=5, len=3"
call list_extract_slice (list, slice, 5, 3)
print *, "New list: 1 2 3 4 8 9 10"
call list_print (list)
print *
print *, "Slice: 5 6 7"
call list_print (slice)
print *
print *, "Insert slice at beg=3"
call list_insert_slice (list, slice, 3)
print *, "New list: 1 2 5 6 7 3 4 8 9 10"
call list_print (list)
end program main
----------------------------------------------------------------------