Exercise 6

In exercise 6, we will work with the following tasks.

Some of the exam problems may be best solved by using recursion. If this happens then it is usually the hardest task in the exam. The first three tasks below are about defining recursive functions. Anyone who wants to concentrate the other tasks may choose to directly jump to the tasks 4 and 5 below and then continue with the exam in January 2012. from the last time.

The greatest common divisor to two natural numbers m and n is the largest natural number d such that both m and n are divisible by d. Such greatest common divisor exists if m and n are not both zero.
Example: The greatest common divisor of 60 and 84 is 12, which the reader is invited to check himself/herself.
The task now is to define a static method:
```
public static int gcd(int m, int n)
```
which calculates the greatest common divisor of arguments m and n.
To compute the greatest common divisor, one can use Euclid's algorithm:
- If n is 0, the result is m.
- Otherwise, the greatest common divisor of m and n is equal to the greatest common divisor of n and m % n (where m % n is the remainder of dividing m by n).
For example we get that
gcd(84,60) is equal to the gcd(60,24)
gcd(60,24) is equal to the gcd(24,12)
gcd(24,12) is equal to the gcd(12,0)
gcd(12,0) is equal to 12
Define the method gcd and test it on some examples. Note that Euclid's algorithm naturally gives a recursive definition of the method.
The java.util.Arrays class has a method:
```
public static int binarySearch(int[] a,
                               int fromIndex,
                               int toindex,
                               int key)
```
which searches for an integer key in a part of the array a (from a[fromIndex] through a[toindex-1]). If the number is found it returns the position in which the number is found (i.e. the i for which a[i] == key). If the number key does not exist in this part of the array, the method returns -1 (the function in Arrays returns, in fact, another negative number in this case, but we ignore this).
The binarySearch assumes that the relevant part of a is sorted with the numbers in increasing order.
Define the binarySearch as a recursive function (in Lecture 8 gave us a different, non-recursive definition).
A hierarchical file system consists of files, and directories. A directory in turn contains files and other directories.
The objects in the class java.io.File represent the names of such files and directories. The class contains a constructor:
```
public File (String pathname)
```
and includes the following methods:
- public int length(), which returns the file's size (number of characters).
- public File[] listFiles(), which returns null if the current File object is a file and returns a list of the files and directories if it is a directory.
Write a program TotalFileSize such that
```
> java TotalFileSize dir
```
calculates and prints the sum of the sizes of all files in the directory dir and its subdirectories.
Example: The directory Labs contains directories lab1 and lab2. In lab1 there is Lab1.java which contains 1000 characters. In lab2 there are files Lab2.java (500 characters) Lab2.class(700 characters) as well as the subdirectory OldFiles, which in turn contains the file Lab2.java (400 characters). Running java TotalFileSize labs should then print 2600.
Hint: Define a recursive function that does the whole work.
(Intended to be easy.) Define a static method
```
public static void makePositive(int[] a)
```
which changes its argument so that all negative elements change sign, i.e. -3 becomes 3, -13 becomes 13, and so on. Write a test program that reads an array from the command line, use the method and prints the result, as in the example below:
```
> java Uppgift4 3 -5 13 8 -2
3 5 13 8 2
>
```
(Semi-Hard.) In this exercise we will make use of the class Point from Task 1, Exercise 4:
```
public class Point {

     private int x, y;

     public Point (int x, int y) {
         this.x = x;
         this.y = y;
     }

     public int getX () {return x;}
     public int gety () {return y;}
}
```
Define a class Rectangle, whose objects are rectangles in a plane.
To construct a rectangle, you must specify two points, the upper left corner and the lower right corner. The class should therefore have a constructor:
```
public Rectangle (Point upperLeft, Point lowerRight)
```
The constructor should check that the point that is in the upper left corner is actually located to the left of and above the lower right corner; otherwise it should throw IllegalArgumentException. We assume that, as in the Java window systems, y coordinates grows down (unlike from what it is usual in math).
The class should have four methods:
```
public Point getUpperLeft()
public Point getLowerRight()
public int area()
public boolean contains(Rectangle r)
```
The area returns the area of the rectangle and the method contains should be such that r1.contains(r2) determines whether rectangle r1 contains the rectangle r2 in the geometric meaning.

Optional

Write a program that asks a user for a file name and prints the number of lines in that file. Make sure that you handle the FileNotFoundException and that you close the file properly.
Write a program that concatenates the contents of several files into one file. For example:
```
java CatFiles chapter1.txt chapter2.txt chapter3.txt book.txt
```
makes a long file book.txt, that contains the contents of the files chapter1.txt, chapter2.txt and chapter3.txt. The output file is always the last file specified on the command line.