Hey,
I am building a BSP tree using a recursive function, however, I seem to be stuck in getting out of the function. I'll paste my code and explain along the way:
CODE
module tree
type treenode
type (treenode), pointer :: left, right
integer :: n
real :: data
endtype
type (treenode), pointer :: root
real :: tree_xmin, tree_xmax
! Counters
integer :: nodes, work
contains
function create_node( ) result (node)
type (treenode), pointer :: node
integer :: ierr
allocate( node, stat=ierr )
if (ierr .ne. 0) then
print *, "Allocate Failed"
stop
endif
nullify( node%right )
nullify( node%left )
node%n = 0
end function create_node
This code was given to us. Just the definition for the treenone and a create_node function
CODE
integer function partition_data( xdata, xmiddle )
implicit none
real,INTENT(INOUT), dimension(:) :: xdata !Data Array
real,INTENT(IN) :: xmiddle
integer :: l = 1, i
integer :: r = 16
real :: temp
do
if (xdata(l) < xmiddle) then !Data Value less than middle
if (l == r) then
partition_data = l
return
end if
l = l + 1 !Increment Counter
else
do
if (xdata(r) >= xmiddle) then
if (l == r) then
partition_data = (l - 1)
return
end if
r = r -1
else
temp = xdata(l)
xdata(l) = xdata(r)
xdata(r) = temp
exit
end if
end do
end if
end do
end function partition_data
This code I wrote. Essentially, it takes in a set array (given) and partitions the array so that any values lower than the x middle value are put to the left and value greater are put to the right. Then the function returns the array index of the element to the left of the xmiddle value. I have tested this function by itself, and it works fine and gives the expected results.
CODE
recursive function make_node( xdata, xmin, xmax ) result (node)
implicit none
type (treenode), pointer :: node
real, intent(inout) :: xdata(:)
real, intent(inout) :: xmin, xmax
real :: xmiddle
integer :: p, i, arraySize
REAL, ALLOCATABLE, DIMENSION(:) :: newArray1, newArray2
node => create_node()
xmiddle = ((xmin + xmax) / 2)
arraySize = size(xdata)
print *, "The arraysize is ", arraysize
if (arraySize == 1 ) then
node%data = xdata(1)
node%n = 1
else
p = partition_data(xdata, xmiddle)
print *, "THe partition value is", p
print *, "THe xmiddle value is ", xmiddle
ALLOCATE(newArray1(p)) !Allocate memory for the LEFT array
do i = 1,p !Copy data from xdata to newarray1
newArray1(i) = xdata(i)
enddo
print *, newArray1(1:p)
node%left => make_node(newArray1, xmin, xmiddle)
! ALLOCATE(newArray2((p+1):arraySize)) !Allocate memory for the RIGHT array
! do i = (p+1),arraySize !COpy data from xdata to newarray2
! newArray2(i) = xdata(i)
! enddo
! node%right => make_node(newArray2, xmiddle, xmax)
end if
!
end function make_node
This part I also wrote myself. (There are some print statements and commented out code for debugging purposes) This recursive function is used to make the nodes. The problem I am having is that this function never seems to hit the case where arraysize is equal to one. The parition value always stays constant and the new array that is suppose to be sent in, does not get changed. Tracing it out on paper, the function seems like it should work.
CODE
subroutine build_tree( xdata, xmin, xmax )
implicit none
real, intent(inout) :: xdata(:)
real, intent(in) :: xmin, xmax
if (size(xdata) == 0) then
print *, "No data provided"
return
endif
tree_xmin = xmin
tree_xmax = xmax
root => make_node( xdata, tree_xmin, tree_xmax )
end subroutine build_tree
end module tree
This was the build_tree subroutine given to us.
CODE
program treetest
use tree
implicit none
integer, parameter :: ndata = 16
real, target :: xdata(ndata)
integer :: partition_value, i
real :: xpartition = 0.7
! call random_number( xdata )
xdata = (/ 0.00392, 0.0251, 0.453, 0.667, 0.963, 0.838, 0.335, 0.975, &
0.796, 0.833, 0.345, 0.871, 0.0899, 0.888, 0.701, 0.735 /)
nodes = 0
! call build_tree( xdata, 0.0, 1.0 )
print *,"Tree Built: nodes ",nodes
print *, xdata(1:16)
partition_value = partition_data(xdata, xpartition)
print *, "The partition value is ", partition_value
print *, "The partitioned array is "
do i=1,16
print *, xdata(i)
end do
end program treetest
This is the main driver program.
I apologize for the length of this post, however, any help at all would be appreciated. This is the only forum I can find offering Fortran help.
Thanks!
This post has been edited by bobby19: 25 Nov, 2007 - 01:27 PM
25 Nov, 2007 - 01:26 PM
| 