Hi,
As a learning exercise, I have coded the Towers of Hanoi in Fortran by examining sample code from Wikipedia, "
fortran.com", and "Fortran Cafe".
The implemented solution uses an auxiliary stack and I have faced two problems. At first I had to duplicate the function "push" for operator overloading. At second, I couldn't figure out how to define a function named size. Both problems are marked with a "!how-to?" comment below.
Can you recommend a workaround and perhaps a gfortran PR (maybe 79440) if applicable that would allow me combine the two push functions in one?
Ev. Drikos
PS: I don't want to upgrade gfortran now!
----------------------------------------------------------------------
module util
type Vector
integer, allocatable :: array(:)
integer :: elements=0;
integer :: size=0;
CONTAINS
procedure add ;
end type Vector
type, extends(Vector) :: Stack
CONTAINS
procedure top ;
procedure pop ;
procedure push ;
end type Stack
INTERFACE OPERATOR (+)
PROCEDURE op_push
END INTERFACE OPERATOR (+)
INTERFACE OPERATOR (==)
PROCEDURE equals
END INTERFACE OPERATOR (==)
!Obviously, a casual constructor insn't the
!best approach in Fortran. But let's try it!
interface Stack
module procedure new_Stack
end interface Stack
contains
function new_Stack(i)
integer, intent(in) :: i
type(Stack) new_Stack
allocate(new_Stack%array(i))
new_Stack%size = i
do j=1,i
new_Stack%array(j)=0;
enddo
end function
subroutine add (self, element)
class(Vector), intent(inout) :: self
integer, intent(in) :: element
integer, allocatable :: tmp(:);
if ( self%elements >= self%size ) then
!realloc (if you know Fortran)
allocate(tmp(2*size(self%array)))
tmp(1:size(self%array)) = self%array
deallocate(self%array)
self%array=tmp
endif
self%elements=self%elements+1;
self%array( self%elements ) = element;
end subroutine add
integer function pop(self)
class(Stack), intent(inout) :: self
if ( self%elements > 0 ) then
pop=self%array(self%elements)
self%array(self%elements)=0; !for display purposes!
self%elements = self%elements - 1 ;
endif
end function pop
! Instead of a function size, finally the Vector has a variable size
! integer function size(self)
! class(Vector), intent(inout) :: self
!
! size= size(self%array) !how-to?
!
! end function size
integer function top(self)
class(Stack), intent(inout) :: self
if ( self%elements > 0 ) then
top=self%array(self%elements)
else
write (*,*) "examine the stack before you try to pop an element";
error stop -1;
endif
end function top
function push(self,e)
class(Stack), intent(inout) :: self
INTEGER, INTENT (IN) :: e
type(Stack) :: push
call self%add(e);
!push=self; !how-to?
!gfortran-4.8.5
!main.f90:118:0: internal compiler error: in fold_convert_loc, at fold-const.c:2044
end function push
FUNCTION op_push(s, element)
TYPE(Stack), INTENT(IN) :: s
INTEGER, INTENT(IN) :: element
TYPE(Stack) :: op_push
op_push=s;
call op_push%add(element);
END FUNCTION op_push
FUNCTION equals(v1, v2)
class(Vector), INTENT(IN) :: v1
class(Vector), INTENT(IN) :: v2
logical :: equals
if ( v1%elements /= v2%elements) then
equals=.false.;
return ;
end if
do i=1,v2%elements
if ( v1%array(i) /=v2%array(i)) then
equals=.false.;
return ;
end if
end do;
equals=.true.;
END FUNCTION equals
end module util
PROGRAM TowersOfHanoi
use util
integer :: i,stat;
character(32) :: arg
integer :: disk, disks = 4 ;
type( Stack) A, B, C ;
! Allow user to specify number of disks
if ( command_argument_count() > 0 ) then
CALL get_command_argument(1, arg)
read(arg,*,iostat=stat) disks;
if ( stat/=0 ) then
write (*,*) "Invalid number of disks."
disks=4;
end if
END if
A = Stack(disks) ;
B = Stack(disks) ;
C = Stack(disks) ;
! Push all Disks into Stack One, from larger to smaller
do disk=disks,1,-1
A = A + disk;
end do
call show;
call move(disks, A, C, B)
if ( A == B .and. A%elements == 0 .and. C%elements == disks ) then
write (*,*) "Stacks of Hanoi have been swapped in the right order!!"
endif
CONTAINS
RECURSIVE SUBROUTINE move(disks, source, target, auxiliary)
INTEGER, INTENT (IN) :: disks
type(Stack) source, target, auxiliary
if ( disks > 0 ) THEN
call move(disks - 1, source, auxiliary, target);
target=target + source%pop() ;
call show;
call move(disks - 1, auxiliary, target , source) ;
endif
END SUBROUTINE move
subroutine show()
write (*,*) "--";
write (*,*) "A=[", a%array , " ]";
write (*,*) "B=[", b%array , " ]";
write (*,*) "C=[", c%array , " ]";
write (*,*) "--";
END SUBROUTINE show
END PROGRAM TowersOfHanoi