Tree Sort Example
This is an example that uses all the features of the build system. The generic code to be placed
into the library is embedded in an HTML document between the code delimiters:
PLACE HTML HERE
<!--FORTRAN90--><xmp>
PLACE FORTRAN CODE HERE
<xmp><!--FORTRAN90-->
PLACE MORE HTML HERE
In addition, the simple <xmp> and </xmp> lines are used to include ufpp(1) input that
in this case is used to create test files, test programs, and test scripts.
So the documentation (or links to documentation), the source code and test cases are all in one file.
You can browse the files as documents. The module is built just by adding the filename to the LIBOBJ
file. Add the file again into the UFPP section of LIBOBJ and after all the routines are built the file
is processed to run the test case. Instead of just a simple echo command, the status of the test usually
goes into a database (I find SQLite3 files ideal for building and updating such tables of data).
So, here is a file that shows that the auto builder can be combined with ufpp(1) without much trouble.
Specifically, the example file is a tree-sort module that sorts a tree of integers as they are added to the table,
along with a test program, test input file, and commands to run the test:
$OUTPUT _testit.ff
!===================================================================================================================================
PROGRAM TREE_SORT
$DOCUMENT COMMENT
Copyright (c) 1990 by Walter S. Brainerd, Charles H. Goldberg,
and Jeanne C. Adams. This program may be copied and used without
restriction as long as this notice is retained.
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.
$DOCUMENT END
!===================================================================================================================================
USE M_TREESORT, ONLY : NODE, INSERT, PRINT_TREE
IMPLICIT NONE
TYPE(NODE), POINTER :: T ! A tree
INTEGER :: NUMBER
INTEGER :: IOS
NULLIFY(T) ! Start with empty tree
INFINITE: DO
READ (*,*,IOSTAT=IOS) NUMBER
IF(IOS.NE.0)EXIT INFINITE
CALL INSERT(T,NUMBER) ! Put next number in tree
ENDDO INFINITE
CALL PRINT_TREE(T) ! Print nodes of tree in infix order
END PROGRAM TREE_SORT
!===================================================================================================================================
$OUTPUT
The module used by the test program is not processed by ufpp(1), it is extracted and built
and placed in the libraries by the standard makefiles by placing the filename in the LIBOBJ
file.
module m_treesort ! @(#) simple tree sort of integers as they are added to the sort
TYPE NODE
INTEGER :: VALUE
TYPE (NODE), POINTER :: LEFT, RIGHT
END TYPE NODE
contains
RECURSIVE SUBROUTINE INSERT (T, NUMBER)
IMPLICIT NONE
TYPE (NODE), POINTER :: T ! A tree
INTEGER, INTENT (IN) :: NUMBER
! If (sub)tree is empty, put number at root
IF (.NOT. ASSOCIATED (T)) THEN
ALLOCATE (T)
T % VALUE = NUMBER
NULLIFY (T % LEFT)
NULLIFY (T % RIGHT)
! Otherwise, insert into correct subtree
ELSE IF (NUMBER < T % VALUE) THEN
CALL INSERT (T % LEFT, NUMBER)
ELSE
CALL INSERT (T % RIGHT, NUMBER)
END IF
END SUBROUTINE INSERT
RECURSIVE SUBROUTINE PRINT_TREE (T)
! Print tree in infix order
IMPLICIT NONE
TYPE (NODE), POINTER :: T ! A tree
IF (ASSOCIATED (T)) THEN
CALL PRINT_TREE (T % LEFT)
PRINT *, T % VALUE
CALL PRINT_TREE (T % RIGHT)
END IF
END SUBROUTINE PRINT_TREE
end module m_treesort
The remainder is input for the ufpp(1) program that
creates a simple input file for the example program
and runs it and tests the output; assuming you are
on a GNU/Linux, Cygwin, or Unix variant platform.
$! Test input file for example program
$OUTPUT _in1
1792
8577
3423
0
200
0
0
8941
0
8558
0
0
-3086
517
3617
205
10378
114373
43641
-4478
7501
27
21
34589
2923
1726
8692
40709
25038
4432
1751
3243
888
6290
-28663
1014
1969
$!==================================================================================================================================
$OUTPUT
$! commands for running a simple test
$! create test executable _testit
$SYSTEM ccall _testit.ff
$! run test
$SYSTEM _testit < _in1 > _in1.out
$! create expected output from test inputfile using the sort(1) command
$SYSTEM sort -k 1n < _in1 > _in1.template
$! compare program output with expected program output
$SYSTEM diff -y -w --ignore-blank-lines --ignore-space-change _in1.template _in1.out && (echo treesort passed)||(echo error: treesort failed)
$SYSTEM rm _in1 _in1.out _in1.template _testit.ff `which _testit`
$!==================================================================================================================================
John S. Urban