Interfaces and sorting -

Interfaces and sorting

Figure 556. Interfaces implemented by class String

Figure 557. The Comparable interface

interface Comparable<T> {
                ┌────┘  
                ▼
  int compareTo(T o);

}

Figure 558. class String and Comparable

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 559. Comparison examples

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 560. Ascending and descending names

‹›

Figure 561. API requirements

Antisymmetric: sgn(x.compareTo(y)) == -sgn(y.compareTo(x))
Transitive: x.compareTo(y) > 0 and y.compareTo(z) > 0 ⇒ x.compareTo(z) > 0.
x.compareTo(y)==0 ⇒ that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.
Recommendation: (x.compareTo(y)==0) == (x.equals(y))

Figure 562. Sorting strings alphabetically

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 560, “Ascending and descending names ”.
❸	The sorted array's content is being written to standard output.

exercise No. 184

Understanding `Arrays.sort()`

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.

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. 185

Sorting `Rectangle` instances by width

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.

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. 186

Sorting `Rectangle` instances by width and height

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

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 563. Situation dependent sorting criteria

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 564. Implementing flexible sorting

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 565. Comparator in action

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 566.

Case
                              insensitive sort

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

Figure 567.

Sort
                              descending by lambda expression

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. 187

Adding flexibility in sorting rectangles

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).

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

Prev	Up	Next
`interface` definitions and `abstract` Classes	Home	A nonsense generator

interface definitions and abstract Classes