Interfaces and sorting

Figure 548. Interfaces implemented by class String Slide presentation Create comment in forum

Figure 549. The Comparable interface Slide presentation Create comment in forum
interface Comparable<T> {
                ┌────┘  
                
  int compareTo​(T o);

}

Figure 550. class String and Comparable Slide presentation Create comment in forum
public class String implements Comparable <String >, ... {
  ...                           ┌────────────┘          
  @Override                     
  public int compareTo(final String  other) {
     ...
    return ...;
  }
}

Type parameter String to interface Comparable.

Matching type String to type parameter in .


Figure 551. Comparison examples Slide presentation Create comment in forum
System.out.println("Eve".compareTo("Paul"));      
System.out.println("Victor".compareTo("Andrew")); 
System.out.println("Hannah".compareTo("Hannah")); 
-11 
21  
0   

"Eve" is lexicographically smaller than "Paul".

"Victor" is lexicographically greater than "Andrew".

"Hannah" is (lexicographically) equal to "Hannah".


Figure 552. Ascending and descending names Slide presentation Create comment in forum

Figure 553. API requirements Slide presentation Create comment in forum
  1. Antisymmetric: sgn(x.compareTo(y)) == -sgn(y.compareTo(x))

  2. Transitive: x.compareTo(y) > 0 and y.compareTo(z) > 0x.compareTo(z) > 0.

  3. x.compareTo(y)==0 ⇒ that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

  4. Recommendation: (x.compareTo(y)==0) == (x.equals(y))


Figure 554. Sorting strings alphabetically Slide presentation Create comment in forum
final String[] names = { 
  "Laura", "Aaron", "Tim", "Peter", "Eve", "Bernie"
};

Arrays.sort(names); 

for (final String n: names) { 
  System.out.println(n);
}
Aaron
Bernie
Eve
Laura
Peter
Tim

An array of names in random lexicographical order.

Arrays.sort(Object[] a) will rearrange the array of names alphabetically in ascending order as being defined by String.compareTo(String anotherString), see left part of Figure 552, “Ascending and descending names ”.

The sorted array's content is being written to standard output.


exercise No. 168

Understanding Arrays.sort() Create comment in forum

Q:

Consider a simple Rectangle class:

public class Rectangle {

    public final int width, height;

    public Rectangle(final int width, final int height) {
        this.width = width;
        this.height = height;
    }
    @Override public String toString() {
        return width + " x " + height;
    }
}

We would like to be able sorting Rectangle instances by their respective width using Arrays.sort(Object[] a). Right now sorting does not work at all. Consider:

final Rectangle[] rectangles = new Rectangle[]{
  new Rectangle(2, 3),
  new Rectangle(4, 5),
  new Rectangle(4, 1)};

 Arrays.sort(rectangles);

This code compiles well. Execution however fails:

Exception in thread "main" java.lang.ClassCastException: de.hdm_stuttgart.mi.sd1.model.Rectangle
  cannot be cast to java.base/java.lang.Comparable
	at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
	at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
	at java.base/java.util.Arrays.sort(Arrays.java:1248)
	at de.hdm_stuttgart.mi.sd1.App.test1(App.java:28)
	at de.hdm_stuttgart.mi.sd1.App.main(App.java:19)

Why does this happen? Read Arrays.sort(Object[] a)'s documentation and try to understand the ComparableTimSort.java line 320 implementation causing the above ClassCastException. You don't have to understand what exactly the code does. Instead focus on types being involved.

A:

Our Rectangle[] array is being passed as Object[] in Arrays.sort(rectangles). Inside ComparableTimSort we have:

private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
  ... 
if (((Comparable) a[...]).compareTo(...) < 0) { 

This is an attempt casting an Object to Comparable. Since our Rectangle class does not yet implement the Comparable interface this cast is bound to fail.

exercise No. 169

Sorting Rectangle instances by width Create comment in forum

Q:

Correct Understanding Arrays.sort() by implementing the Comparable interface in Rectangle. More precisely use the underlying type parameter Comparable<Rectangle>. Thus is an anticipation of upcoming Java generics.

A:

We implement the interface consisting only of one method compareTo(T o) with T representing the type in question:

public class Rectangle implements Comparable<Rectangle> {
...
  @Override
  public String toString() {
    return width + " x " + height;
  }
  @Override
  public int compareTo(final Rectangle other) {
    return  width - other.width;
  }
}

This solves the ClassCastException runtime problem and sorts Rectangle instances by width:

final Rectangle[] rectangles = new Rectangle[]{
  new Rectangle(2, 3),
  new Rectangle(4, 5),
  new Rectangle(4, 1)};

Arrays.sort(rectangles);

for (final Rectangle n : rectangles) {
  System.out.println(n);
}
2 x 3
4 x 5
4 x 1

exercise No. 170

Sorting Rectangle instances by width and height Create comment in forum

Q:

Our current sorting implementation may be considered incomplete. We may have multiple Rectangle instances of common width but differing in height as in the current example:

final Rectangle[] rectangles = new Rectangle[]{
  new Rectangle(2, 3),
  new Rectangle(4, 5),
  new Rectangle(4, 1)};
2 x 3
4 x 5
4 x 1

Two Rectangle instances share a common width of 4 but differ in height. The original sequence is being retained showing the rectangle having larger height 5 first.

We want rectangles of common width to be sorted by height in ascending order as well. Modify your compareTo() implementation accordingly to produce:

final Rectangle[] rectangles = new Rectangle[]{
  new Rectangle(2, 3),
  new Rectangle(4, 5),
  new Rectangle(4, 1)};
2 x 3
4 x 1
4 x 5

A:

We extend our compareTo(T o) implementation accounting in case of common width values:

@Override
 public int compareTo(final Rectangle other) {
  if (width == other.width) {
    return height - other.height;
  } else {
    return width - other.width;
  }
}
Figure 555. Situation dependent sorting criteria Slide presentation Create comment in forum
Unsorted Case sensitive Case insensitive Descending
UK
quick
hello
sign
ATM
ATM
UK
hello
quick
sign
ATM
hello
quick
sign
UK
sign
quick
hello
UK
ATM

Figure 556. Implementing flexible sorting Slide presentation Create comment in forum

Solution: Provide your own Comparator!

import java.util.Comparator;

public class SortCaseInsensitive implements Comparator<String> {
                              ┏━━━━━━━━━━━━━━┳━━━━━━━━━━━┛
  @Override                   ▼              ▼
  public int compare(final String a, final String b) {
    return a.toLowerCase().compareTo(b.toLowerCase());
  }
}

Figure 557. Comparator in action Slide presentation Create comment in forum
System.out.println("hello".compareTo("UK")); 

System.out.println(new SortCaseInsensitive(). 
   compare("hello", "UK"));
19 
-13 

Standard String comparison.

Custom Comparator evaluating "hello".compareTo("uk") behind the scenes.


Figure 558. Case insensitive sort Slide presentation Create comment in forum
final String[] names = {
"UK", "quick", "hello", "sign", "ATM"
};

Arrays.sort(names, new SortCaseInsensitive());

for (final String n: names) { 
  System.out.println(n);
}
ATM
hello
quick
sign
UK

final String[] names = {
"UK", "quick", "hello", "sign", "ATM"
};
Arrays.sort(names, (a, b) -> b.compareTo(a)); 

for (final String n: names) { 
  System.out.println(n);
}
sign
quick
hello
UK
ATM

This lambda expression is equivalent to the following custom comparator:

public class SortDescending implements Comparator<String> {
    @Override
    public int compare(final String a, final String b) {
        return b.compareTo(a); // Equivalent to 
    }
}

exercise No. 171

Adding flexibility in sorting rectangles Create comment in forum

Q:

We want to change the ordering of rectangles in a flexible manner. Consider the following examples:

  • A list of rectangles may be ordered either by width, area or perimeter.

  • The ordering may be ascending or descending

Define an additional ordering prescription: Rectangle instances shall be sortable by area in descending order in addition to the already defined ordering by width and height. Instances sharing common area shall be sorted first by width and second by height in descending order as well.

Tip

The sort(T[] a, Comparator<? super T> c) method is your friend. It allows for passing a comparator instance as in the sort students by rollno example. Thus define an appropriate SortByArea class implementing Comparator<Rectangle> and pass an instance of this class to sort(T[] a, Comparator<? super T> c).

A:

For convenience we add a getArea() method to our Rectangle class:

public class Rectangle implements Comparable<Rectangle> {
   ...
  public int getArea() {
    return width * height;
  }
}

The intended sorting requires a corresponding class implementing the Comparator (Not Comparable!) interface:

public class SortByArea implements Comparator<Rectangle> {
  @Override
  public int compare(Rectangle r1, Rectangle r2) {
    if (r1.width * r1.height == r2.width * r2.height) {
      if (r1.width == r2.width) {
        return r2.height - r1.height; 
      } else {
        return r2.width - r1.width; 
      }
    } else {
      return r2.width * r2.height - r1.width * r1.height; 
    }
  }
}

Two rectangles having common area and width values.

Two rectangles having common area values but different width.

Two rectangles having different area values.

We may now use both ordering prescriptions next to each other:

final Rectangle[] rectangles = new Rectangle[]{
  new Rectangle(2, 3),
  new Rectangle(3, 2),
  new Rectangle(4, 5),
  new Rectangle(4, 1)};

System.out.println("Ascending by width and height:");
Arrays.sort(rectangles);
for (final Rectangle r : rectangles) {
  System.out.println(r);
}

System.out.println("\nDescending by area, width and height:");
Arrays.sort(rectangles, new SortByArea());
for (final Rectangle r : rectangles) {
  System.out.println(r + ", area = " + r.getArea());
}
Ascending by width and height:
2 x 3
3 x 2
4 x 1
4 x 5

Descending by area, width and height:
4 x 5, area = 20
3 x 2, area = 6
2 x 3, area = 6
4 x 1, area = 4

Notice the two rectangles having a common area value of 6 being sorted by descending width value.

Side note: Upcoming lambda expressions in Software development 2 allow for defining sorting methods directly without requiring classes. We provide two simple examples:

final Rectangle[] rectangles = new Rectangle[]{
  new Rectangle(2, 3),
  new Rectangle(3, 2),
  new Rectangle(4, 5),
  new Rectangle(4, 1)};

System.out.println("Descending by width:");
Arrays.sort(rectangles, (x, y) -> y.width - x.width);
for (final Rectangle r : rectangles) {
  System.out.println(r);
}

System.out.println("\nAscending by area:");
Arrays.sort(rectangles, (x, y) -> x.getArea() - y.getArea());
for (final Rectangle r : rectangles) {
  System.out.println(r + ", area = " + r.getArea());
}
Descending by width:
4 x 5
4 x 1
3 x 2
2 x 3

Ascending by area:
4 x 1, area = 4
3 x 2, area = 6
2 x 3, area = 6
4 x 5, area = 20