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.

In the past we were dealing with arrays and used indexes to extract values from a specific position in the array. There is one limitation to this, namely that you can't build up structures that link to other similar objects. The concept of pointers become very important for expanding the functionality of this concept. A pointer is nothing else than an address to memory space. One can therefore make structures which contain pointers with no initial address. As more information is required to be added, new structures can be allocated and their memory address be added in the various slots. When the order of the list needs to be changed, then instead of having to move all subsequent physical values in index space, this can simply be handled by adding a new structure and reorder the memory addresses of the pointers. This way it is simple to buildup large structures containing various information in an ordered manner.


Getting the required files:

Download the tar file to your ~/Dat_F directory and unpack it:

> 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:

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.

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:
Which functions do the pointers p1, p2 print Credits: 2/-1

Which numerical range does b print 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.

Which values does t1,t2 and t3 have (one decimal accuracy)? Credits: 2/-1

Which values does a(5), b(5) have (two decimals accuracy)? 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


Linked lists:

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.


tree.png



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:
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? 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