5.7  Example: Sort the list of files by size

1. Data Analysis and Problem Analysis

The only data we need is the list of files, because each file know its size.

2. Purpose and Contract/Header:

  /////////////////////////////////////////////////////////////////
  // PURPOSE AND CONTRACT:
  // produce a list of all files in this list, sorted by size
  ALoF sort() { ... }

We develop the methods in the two classes concurrently, starting with examples.

3. Examples:

  File f1 = new File("MyTrip", 1000);
  File f2 = new File("hmwk1", 200);
  File f3 = new File("hmwk3", 350);
  ALoF mtlof = new MtLoF();
  ALoF lof1  = new ConsLoF(f1, mtlof);
  ALoF lof2  = new ConsLoF(f2, lof1);
  ALoF lof3  = new ConsLoF(f3, lof2);
  ...
  mtlof.sort()  -- expected: mtlof
  lof1.sort()   -- expected: lof1
  lof2.sort()   -- expected: new ConsLoF(f2, new ConsLoF(f1 mtlof))
  lof3.sort()   -- expected: 
                   new ConsLoF(f2, new ConsLoF(f3, new ConsLoF(f1 mtlof)))

4. Template:

There is a separate template for each of the two subclasses.

  /* TEMPLATE for the MtLoF class:
   ALoF sort() { ... }
  
  */

 /* TEMPLATE for the ConsLoF class:
  ALoF sort() {
    ... this.fst ...
        ... this.fst.name ...
        ... this.fst.size ...
    ... this.rst.sort() ...
  } 
  */

We observe, that, according to the contract, this.rst.sort() produces sorted rest of the list. Therefore, to complete the sort, all that is needed is to insert the this.fst item into the sorted rest of the list. Thus, we define a helper method:

2. Purpose and Contract/Header for the method insert:

  /* PURPOSE AND CONTRACT:
  // insert the given file into this sorted list
  ALoF insert(File f) { ... }

and add it to the template for the sort method, so the template now is:

  /* TEMPLATE for the ConsLoF class:
  ALoF sort() {
    ... this.fst ...
        ... this.fst.name ...
        ... this.fst.size ...
    ... this.rst.sort() ...
    ... this.rst.insert(... a_file ...) ...
  } 
  */

5. Program:

Again, we have two different methods, one for each class.

  // PROGRAM for the class MtLoF: 
  ALoF sort(){return this; }

  // PROGRAM for the class ConsLoF: 
  ALoF sort(){
    return (this.rst.sort()).insert(this.fst); 
  }

We cannot run the tests until we implement and test the helper method insert(File f).

3. Examples for the method insert:

  mtlof.insert(f1)  -- expected: lof1
  lof1.insert(f2)   -- expected: lof2
  lof2.insert(f3)   -- expected:  
     new ConsLoF(f2, new ConsLoF(f3, new ConsLoF(f1, mtlof)))
  lof2.insert(new File("hmwk5", 1200))  -- expected: 
     new ConsLoF(f2, new ConsLoF(f1, new ConsLoF(new File("hmwk5", 1200), mtlof)))

4. Template for the method insert:

There is a separate template for each of the two subclasses.

  /* TEMPLATE for the MtLoF class:
   ALoF insert(File f) { ... }
  
  */

 /* TEMPLATE for the ConsLoF class:
  ALoF insert(File f) {
     ... this.fst ...
        ... this.fst.name ...
        ... this.fst.size ...
    ... this.rst.sort() ...
    ... this.rst.insert(f) ...
        ... f.name ...
        ... f.size ...

    ... if (f.size < this.fst.size) ...
        else ...
  } 
  */

5. Program:

Again, we have two different methods, one for each class.

  // PROGRAM for the class MtLoF: 
  ALoF insert(File f) { return new ConsLoF(f, this); }

  // PROGRAM for the class ConsLoF: 
  ALoF insert(File f) { 
    if (f.size < this.fst.size)
      return new ConsLoF(f, this);
    else
      return new ConsLoF(this.fst, this.rst.insert(f));
  }

6. Tests:

We first test the examples given for the insert method, then the examples developed for the sort method. We need to use the Test Case tool to compare the resulting lists.