Walt Brainerd <[log in to unmask]> wrote:
...
>The first half of this sentence is a matter of opinion, of course,
>but could you please show us a program that does a tree sort using
>reallocatable arrays (one that is approximately as readable as the
>F program in http://www.imagine1.com/imagine1/ex_tree_sort.html).
>
>>>>
> I no longer consider recursive data structures as
>sufficient reason to spoil the language with pointers (especially since
>all could be emulated efficiently with reallocatable arrays).
I suspect you intended this to be a challenging exercise. But, with the
exception that REALLOCATE is not yet in the language, the transformation
is almost mechanical in its simplicity. Instead of the system's heap, you
allocate your tree on a reallocatable array. Dereferences of your pointers
become indexes into that array. Assignments or other definitions of your
pointers become integer assignments to the indices. I leave the amount
by which the array is allocated and/or incremented undefined here in order
to emphasize that it could be a decision made on a case-by-case basis.
In any case, the fact that you call the system's memory manager only once
every amount() times you allocate a new node on the tree means that
this version is probably even faster than the one using pointers.
Note that, in general, you would also have to implement a MY_DEALLOCATE
routine and maintain a free lins within the array. This is a complication not needed
in this example.
This was written quickly and without a test, but it should at least get the point
across (transformed directly from imagine1, plus the addition of MY_ALLOCATE
routine):
module tree_sort_module
public :: insert, print_tree, my_allocate
type, public :: node
integer :: value
integer :: left, right ! these are "pointers" into
! an array of type NODE
end type node
integer, public :: number
integer :: inuse !number of elements in ARRAY in use
type(node), allocatable :: ARRAY(:) ! in F you probably
! use the DIMENSION
! attribute :-(
contains
recursive subroutine insert (t)
integer :: t ! A tree
integer :: number
! If (sub)tree is empty, put number at root
if (t == 0) then
call my_allocate (t)
ARRAY(t) % value = number
ARRAY(t) % left = 0
ARRAY(t) % right = 0
! Otherwise, insert into correct subtree
else if (number < ARRAY(t) % value) then
call insert (ARRAY(t) % left)
else
call insert (ARRAY(t) % right)
end if
end subroutine insert
recursive subroutine print_tree (t)
! Print tree in infix order
integer :: t ! A tree
if (t /= 0) then
call print_tree (ARRAY(t) % left)
print *, ARRAY(t) % value
call print_tree (ARRAY(t) % right)
end if
end subroutine print_tree
subroutine my_allocate(t)
! assign a space for a new element
! (REALLOCATE ARRAY if necessary)
integer :: t ! A tree
integer :: ierr
if (.not. allocated(ARRAY)) then
ALLOCATE (ARRAY(amount(), stat = ierr)
if (ierr /= 0) exit
t = 1
inuse = 1
else if (inuse >= size(ARRAY)) then
REALLOCATE (ARRAY(inuse+amount()), stat = ierr)
! if reallocate existed !!!
if (ierr /= 0) exit
inuse = inuse + 1
t = inuse
else
inuse = inuse + 1
t = inuse
endif
end subroutine my_allocate
end module tree_sort_module
program tree_sort
! Sorts a file of integers by building a
! tree, sorted in infix order.
! This sort has expected behavior n log n,
! but worst case (input is sorted) n ** 2.
use tree_sort_module
integer :: t = 0 ! A tree (initially empty)
integer :: ios
do
read (unit=*, fmt=*, iostat = ios) number
if (ios < 0) then
exit
end if
call insert (t) ! Put next number in tree
! NUMBER is public in the module and is an
! implicit argument to INSERT
end do
! Print nodes of tree in infix order
call print_tree (t)
end program tree_sort
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
