﻿ Programming for Physicists: Exercise 8
Exercise 7: Structures - Pointers

 !! Electronic student evaluation of the courses !! All students are asked to login on the ABSALON web pages for all the courses they follow in this block and fill out the evaluation form.You must do this within the period 9th to 26th October.So why don't you do it right now?!

Introduction:

In the earlier exercises you have been dealing with programs that use basic variables in the calculations. These types of variables are useful for most of the numerical problems you may encounter. But, there are situations in which it is favorable to use more complex variables containing more information, while still providing the same simple way of communication between different parts of a program. Such variables are know as structures. Structures are objects defined in terms of normal variables and pointers. This combination of information allows for some very useful user defined variables that can be used in many situations. For instance, the star catalog you were working with in the IO exercise could be kept in one such structure containing all the information for each star. In this exercise you will have the chance to play with structures, see the basic concepts they provide and how to use them in a specific situation.

Getting the required files:

> cd ~/Dat_F
> tar -zxvf fortran7.tgz
> rm fortran7.tgz

This creates a new directory "Exercise_7" that contains the files needed for this exercise.

Structures:

To become more acquainted with structures and their usefulness, you are to change a simple program written using array notation into a version using structures. The idea behind the problem is simple; assume you are given three vectors that represent the direction and length of the three sides in a parallel-pipidum -- a skew box. You want to calculate the volume of this box. This is done by some simple arithmetic;

Vol = abs( a dot (b cross c)),  (1)

where a, b and c represents the three vectors outlining the three directions of the edges seen from one of the corners of the box. Given these vectors, the task is to perform the simple calculation given in eq(1). In the file, volume.f90, this has been done using array notation. Take this program as a reference, and change it to use structures instead of arrays, while still giving the correct result. There are two main steps in this, showing different aspects of the usages of types.

For the first case, you simply have to exchange the array notation to structures with the following characteristics:
• Call the new file volume_type_1.f90
• Define two types.
• One representing three points (x, y and z).
• A second defining the three vectors (a, b and c), each consisting of three points.
• Change the expression of the calculation of Vol to utilize the new main structure.
• Check that this calculation gives the same result as before for a series of test cases.
• Keep everything in one main program.

 I have a working program volume_type_1.f90 Credits: 2/-1

Using types directly, the expression calculating Vol, eq(1), becomes very dense and a little difficult to read. To make the expression simpler, Fortran provides a method to define various operations with structures. In this version of the same calculation, you again start from volume.f90 or volume_type_1.f90 and rewrite it to using types, functions and interface blocks to define simple arithmetic for the two operations needed (cross and dot). The simplest is to split the code into two routines. One hosting, basically the same as in volume.f90 and a second file that contains the definitions of the special cross and dot operations, that works directly on the structures.
• Call the new files volume_type_2.f90 and math_fun.f90.
• math_fun.f90 is a module that contains the definitions of a cross and a dot operation using types.
• volume_type_2.f90 is the main program that uses the math functions.
• To use the function on types, dedicated interface blocks have to be included defining the ".***." names used to indicate the type arithmetic.
• The functions should be done passing the vectors (a,b or c) defined in the types into the routine.
• You may either include the required lines into the Makefile, or simply compile and link the program by hand (only need two lines)
• Test that the same results are reached with this version.

 I have a working program volume_type_2.f90 Credits: 2/-1

 I have a working program math_fun.f90 Credits: 2/-1

Pointers:

Before we proceed with the larger exercises an example in using pointers have to be conducted. As said earlier, a pointer is simply a direct reference to an address in memory space. The advantage of using pointers is that they can be used to provide "organized random" access to memory space. As such they are used in indirect addressing of memory space. You will work more with this in the last exercise. Now you are going to make a small program, that shows there, in terms of calculations, are no differences between the usage of arrays or pointers. The new program has to be able to do the following:
• Create a file called pointers.f90
• Define three 1D arrays (x, a, b) of a given dimension (say 10) .
• Allow the arrays to be addressed by pointers (using target in their definition).
• Define two pointers (p1, p2) with one dimension, but no specification of their size.
• Assign the first array "x" to the values between 0 and Pi:
x=(/(i, i=0,n-1)/)*3.14159/(n-1.)
• Assign sin(x) to the "a" array.
• Assign the first pointer (p1) to the "x" array (=>).
• Assign the second pointer (p2) to the first pointer (p1).
• Reassign the first pointer (p1) to the second array (a).
• Assign "b" to cos(p2).
• Print the values of the arrays and pointers in a loop
 Which functions do the pointers p1, p2 print sin, x x, x x, sin sin, sin Credits: 2/-1

 Which numerical range does b print 0 - pi 0 - 1 -1 - 1 -1 - 0 Credits: 2/-1

Did you understand why you got the values you got? If not, go back and look at the program once more to understand it!

Now that you understand it, lets extent the program a little more.

• Define four temporary real variables (t1, .. t3)
• Assign the second pointer (p2) to the first pointer (p1)
• Assign t1 to p1(1) and t2 to p2(1)
• Reassign p1 to b
• Assign t3 to p1(1)
• Print the temporary variables
• Assign a(5) to p1(4)
• Assign b(5) to p2(4)
 Which values does t1,t2 and t3 have (one decimal accuracy)? 0, 0, 0 0, 0, 1 0, 1, 0 1, 0, 0 0, 1, 1 1, 0, 1 1, 1, 0 1, 1, 1 Credits: 2/-1

 Which values does a(5), b(5) have (two decimals accuracy)? 0.50, 0.87 0.87, 0.50 0.50, 0.50 0.87, 0.87 Credits: 2/-1

Notice that in the correct implementation, you have only assigned values to the two arrays, but the assigning of memory addresses to the pointers have made them point at the same value. Did you notice, that even if one pointer is assigned through another pointer, then it's value is not changed as the intermediate pointer is reassigned to another memory address?

 I have a working program pointers.f90 Credits: 2/-1

Assume you are given an array of random numbers and you need them sorted, smallest to largest, before you can use them. Using Numerical Recipes, there are a number of methods that can do this for you. These were developed before the introduction of Fortran 90 and therefor could not use dynamical memory allocation, structures and pointers. Here you are going to address this problem by making a simple tree structure - this is one of many possible implementations (see for instance Figure 7.7 in Metcalf & Reid for an example where a dataset is sorted by interchanging pointers as new values are added to the list). The idea we are going to address here is to define a structure that host the value of the number and reference to two other branches representing the possibility for pointing at a larger and a smaller value relative to the one in the given structure. As new values are added to the list more structures are allocated and added to the tree structure at an appropriate position relative to the new value and the structure of the old list. This process is repeated until all values are placed at their appropriate position in the tree. Notice that the structure of the tree depend on the order in which the numbers are given to the routine forming the tree. The tree is then read back in an ordered fashion and the numbers are returned in an increasing order. The figure below gives a representation of such a tree, where value represents the data, smaller and larger are two pointers hosting the addresses of the underlying structures, indicated by the line connecting two boxes. To get the values back going from smallest to largest, you trace the structure to the bottom of the smaller path, assign the value, then go down the local larger path to the smallest value and repeat the process. In the end all values are read in a sorted manner. The red numbers in the figure represent the order in which the values must be assigned to get the correct sorted list. To implement this the following steps have to be take:
• Look at the Makefile. It assumes that there are a main_list.f90 and a list.f90 program. The first is provided - only a few holes you need to fill out - and a skeleton for the second is given.
• Look through the three files to see how the structure of the program is laid out.
• Random numbers are (again) provided using the build in function random_number.
• Define a type in list.f90 that includes three entries: one real (value) and two pointers (smaller and larger), as indicated in the figure above.
• Initialize the first structure using the first value in the array.
• Then build up the tree structure by adding new numbers to the list:
• Check relative numerical value against the value in the structure.
• Smaller -- Larger.
• Check the relevant pointer smaller/larger.
• If the pointer exist, then call the routine again, this time with the address of smaller/larger and repeat the steps above.
• Notice that we are recursively calling the same routine until there is a free space to open a new structure and place the given value.
• If the pointer is empty:
• Allocate a new structure.
• Add the value to this structure.
• Assign its address to the smaller/larger pointer in the parent structure.
• Return back to the main routine.
• This tree structure does not allow for multiple identical values.
• Could easily be included by adding an integer variable counting the number of repeated values.
• Also requires a small change to the reading routine.
This is the type of program where it may be difficult to predict how the flow structure behaves. It may therefore be useful to use the debugger from last exercise to track the evolution of the program while it runs.

The routine for reading the tree structure is included, with a single small error. Check this part of the routine to make sure you know how it works. Especially make sure you understand the way that it steps through the routine to actually place the values in the correct order. Run the program to check that it sorts the data correctly.

Using pointers and allocate this way, is a typical approach in which one can create a program that can grow in size without limits, especially if the full sort algorithm is repeated many times. The problem is often that one does not clean up properly when dismissing the tree structure. It is not enough to release the root pointer, as it only releases the amount of data included in this part of the code, leaving the lower level structures still hanging there, but without a change to access them. Therefore address this type of programs with some care! Making sure that you do the correct cleaning all the time.

When it is working, make the small change such that it can read the data file data.bin, which contains one block of data containing 1000 random numbers. Read these data into the program and sort them.

If you downloaded the fortran7.tgz file before the 14 October at 11pm, you have to download it again and extract an updated version of the data.bin file again:
\$ tar -zxvf fortran7.tgz Exercise_7/data.bin

 What is the 99th and 899th number in this sorted list? 0.1013568, 0.9060328 9.9985912E-02, 0.9046561 0.1020229, 0.9081894 0.1035907, 0.9063501 0.1034469, 0.9112576 Credits: 2/-1

 I have a working version of list.f90 Credits: 2/-1

\$Id: index.php,v 1.8 2009/10/14 21:21:18 kg Exp \$ kg@astro.ku.dk