1. Data Structures and Algorithms

Data structures store essential information in the application. They are organized via lists, sets, queues and associative maps. In Java, the interfaces and classes around data structures are called Collection-API. Since there are so many types to choose from, the purpose of this chapter is to bring order to the confusion and to illustrate the use of the corresponding collections through the exercises.

Prerequisites

  • be able to distinguish data structures lists, sets, associative memory

  • know data types List, ArrayList and LinkedList.

  • know data types Set, HashSet and `TreeSet

  • know Map, HashMap and TreeMap data types

  • know the difference between queue and deque

  • know how to create order with Comparator

  • know how to use and implement iterators

  • be able to use data structures in a thread-safe way

  • optional: Interest in the open source library Guava for further data structures

Data types used in this chapter:

1.1. The types of the Collection API

The list of used types is long this time. However, the design follows a basic principle, so it is not so complicated after all:

  • Interfaces describe the functionality of a data structure, "what is provided".

  • Classes use different strategies to implement the specification from the interfaces; they represent the "how it is implemented".

As developers, we need to know interfaces and implementations, and to review, let’s look again at the central types we’ll encounter more often in this chapter:

Collection Classes UML
Figure 1. UML diagram of selected data structures and type relationships

To note:

  • Iterable is the most general interface, representing what can be traversed; Iterable provides Iterator instances. Not only data structures are Iterable.

  • Collection is the top interface that really represents data structures. It specifies methods for adding elements to the collection or for deleting them.

  • Under Collection are the actual abstractions, whether it is a list, set or queue. Below are the implementations.

  • Some operations are not with the data types themselves, but are outsourced to a class Collections. Similar applies to arrays, where there is also a utility class Arrays.

We want to build a decision tree for the classes and interfaces java.util.Set, java.util.List, java.util.Map, java.util.HashSet, java.util.TreeSet, java.util.Hashtable, java.util.HashMap and java.util.TreeMap. The following considerations must be made in the selection process:

  • Access via key

  • duplicates allowed

  • fast access

  • sorted iteration

  • thread safe

If access is from a key to a value, this is generally an associative map, that is, an implementation of the Map interface. Implementations of Map are HashMap, TreeMap and the outdated class Hashtable. However, lists are also special associative stores, where the index is an integer starting at 0 and ascending. Lists work quite well whenever the key is a small integer and there are few spaces. Association of arbitrary integers on objects does not map well with a list.

Duplicates are allowed in lists, but not in sets and associative stores. There are indeed requirements that a set should note how often an element occurs, but this must be implemented itself with an associative memory that associates the element with a counter.

All data structures allow a fast access. The only question is what to ask for. A list cannot quickly answer the question of whether an element is present or not, because the list must be traversed from front to back to do so. With an associative store or set, this query is much faster because of the internal organization of the data. This test of existence can be answered even somewhat faster for data structures that use hashing internally than for data structures that keep elements sorted.

Lists can be sorted, and a traversal returns the elements in the sorted order. A TreeSet and a TreeMap are also sorted by a criteria. The data structures with the hashing method have no user-defined order of sorting.

Data structures can be divided into three groups: Data structures since Java 1.0, data structures since Java 1.2 and data structures since Java 5. In the first Java versions the data structures Vector, Hashtable, Dictionary and Stack were introduced. These data structures are all thread-safe, but they are no longer used today. In Java 1.2 the Collection API was introduced, all data structures are not thread safe. In Java 5 the new package java.util.concurrent has been introduced, all data structures in it are safe against concurrent changes.

1.1.1. Quiz: Search for StringBuilder ⭐

What is the output of the following program if it resided in a main(…​) method of a class?

Collection<String> islands1 = new ArrayList<>();
islands1.add( "Galápagos" );
islands1.add( "Revillagigedo" );
islands1.add( "Clipperton" );
System.out.println( islands1.contains( "Clipperton" ) );

Collection<StringBuilder> islands2 = new ArrayList<>();
islands2.add( new StringBuilder( "Galápagos" ) );
islands2.add( new StringBuilder( "Revillagigedo" ) );
islands2.add( new StringBuilder( "Clipperton" ) );
System.out.println( islands2.contains( new StringBuilder( "Clipperton" ) ) );

How can the output be explained? Does it perhaps deviate from the presumed behavior? Could it be due to an important requirement that String fulfills, but not StringBuilder?

1.2. Lists

For the exercises, let’s start with the simplest data structure, lists. Lists are sequences of information where the order is maintained when appending new elements, and elements can occur multiple times. Even null is allowed as an element.

1.2.1. Singing and cooking: Traverse lists and check properties ⭐

Captain CiaoCiao is putting together a new crew. Everyone in the crew has a name and a profession:

record CrewMember( String name, Profession profession ) {
  enum Profession { CAPTAIN, NAVIGATOR, CARPENTER, COOK, MUSICIAN, DOCTOR }
}

For each crew, Captain CiaoCiao makes sure that there are as many cooks as musicians.

Exercise:

  • Write a method areSameNumberOfCooksAndMusicians(List<CrewMember>) that returns true if there are the same number of cooks as musicians, false otherwise.

Example:

CrewMember captain   = new CrewMember( "CiaoCiao", CrewMember.Profession.CAPTAIN );
CrewMember cook1     = new CrewMember( "Remy", CrewMember.Profession.COOK );
CrewMember cook2     = new CrewMember( "The Witch Cook", CrewMember.Profession.COOK );
CrewMember musician1 = new CrewMember( "Mahna Mahna", CrewMember.Profession.MUSICIAN );
CrewMember musician2 = new CrewMember( "Rowlf", CrewMember.Profession.MUSICIAN );

List<CrewMember> crew1 = List.of( cook1, musician1 );
System.out.println( areSameNumberOfCooksAndMusicians( crew1 ) ); // true

List<CrewMember> crew2 = List.of( cook1, musician1, musician2, captain );
System.out.println( areSameNumberOfCooksAndMusicians( crew2 ) ); // false

List<CrewMember> crew3 = List.of( cook1, musician1, musician2, captain, cook2  );
System.out.println( areSameNumberOfCooksAndMusicians( crew3 ) ); // true

*Java 8 backport

The exercise uses a record for CrewMember. This can be easily expressed by a class with the object variables String name, Profession profession and a nested type Profession.

1.2.2. Filter comments from lists ⭐

Bonny Brain reads an old logbook of Captain Dipturus Dimwit, which repeatedly always contains four entries:

  1. Magnetic Compass Course [1].

  2. Speed of water current

  3. Weather

  4. Comments and general observations

Bonny Brain is looking for a specific entry in the comments, so from a list of strings the first, second and third entries are to be deleted that only the fourth entry with the comment remains.

Exercise:

  • Implement a method void reduceToComments(List<String> lines) that deletes each of the first, second and third entries in the passed list, keeping only the fourth.

Examples:

  • "A1", "A2", "A3", "A4", "B1", "B2", "B3", "B4", "C1", "C2", "C3", "C4""A4", "B4", "C4"

  • empty list → nothing happens

  • "A1" → exception Illegal size 1 of list, must be divisible by 4

1.2.3. Shorten lists, because there is no downturn ⭐

For Captain CiaoCiao, things should only ever go up; when he reads sequences of numbers, they should only ever go up.

Exercise:

  • Write a method trimNonGrowingNumbers(List<Double> numbers) that truncates the list when the next number is no longer greater than or equal to the previous one.

  • Remember: the passed list must be mutable, so that elements can be deleted.

Examples:

  • If the list contains the numbers 1, 2, 3, 4, 5, the list stays that way.

  • If the list contains the numbers 1, 2, 3, 2, 1, the sequence is shortened to 1, 2, 3.

1.2.4. Eating with friends: Compare elements, find commonalities ⭐

Bonny Brain is planning a party on the mainland, and in a large circle there should always be two guests sitting next to each other who have at least one thing in common. Guests are declared by the following type:

public record Guest(
    boolean likesToShoot,
    boolean likesToGamble,
    boolean likesBlackmail
) { }

Exercise:

  • Write a method int allGuestsHaveSimilarInterests(List<Guest> guests) that returns -1 if all guests have a neighbor that matches in at least one property. Otherwise, the result is >= 0 and the index on exactly the first guest that sits incorrectly, that is, has nothing in common with any of its neighbors.

  • Guest can be extended in any way

Java 8 Backport

Records are new in Java 16; in older Java versions implement Guest as a class:

public class Guest {
  public boolean likesToShoot;
  public boolean likesToGamble;
  public boolean likesBlackmail;
}

1.2.5. Check lists for same order of elements ⭐

Fat Donny Bone Spurs and Ally Al Lyons sneak into the Anonymous Buccaneers support group and are told to report to Captain CiaoCiao who is sitting to the right of whom in the conversation circle. Both try to remember. They do not necessarily start with the same person in their enumerations.

Task:

  • Write a method isSameCircle(List<String> names1, List<String> names2) that tests whether the names in the two lists immediately follow each other in the same order. Consider that the people are sitting in a circle, and the last person in the list "sits" next to the first person in the list.

Examples:

  • List 1: Alexandre, Charles, Anne, Henry. List 2: Alexandre, Charles, Anne, Henry` → agree

  • List 1: Anne, Henry, Alexandre, Charles, List 2: Alexandre, Charles, Anne, Henry → concur

  • List 1: Alexandre, Charles, Anne, Henry. List 2: Alexandre, Charles, Henry, Anne → do not agree

  • list 1: Anne, Henry, Alexandre, Charles, list 2: Alexandre, William, Anne, Henry → do not match

1.2.6. And now the weather: Find repeated elements ⭐

Napoleon Nose chats with Bonny Brain about the weather, "We’ve had so many rainy days for the last few months, it’s been bad for capering." Bonny Brain replies, "We haven’t had that many rainy days in a row!". Who is right?

Given a list of weather data:

Rain, sun, rain, rain, hail, snow, storm, sun, sun, rain, rain, sun.

In the list sun occurs three times in a row. That is what we want to know. Although rain occurs more often in the list overall, that is not relevant to the solution.

Task:

  • Create a new record WeatherOccurrence for weather information:

    record WeatherOccurrence( String weather, int occurrences, int startIndex ) { }
  • Implement a method WeatherOccurrence longestSequenceOfSameWeather(List<String> weather) that reveals,

    • what weather

    • how many times it appears in the list directly after each other and

    • where the longest list starts.

      If a weather occurs the same number of times in a row, the method is free to decide what it returns. Elements may be null.

*Java 8 Backport

Records exist since Java 16, in older versions we use a class: class WeatherOccurrence { String weather; int occurrences; int startIndex; }. It is then useful to write a toString() method.

1.2.7. Generate receipt output ⭐

A receipt contains entries and information such as quantity, product name, price, total.

Program a receipt in this task.

Task:

  • Create a new class Receipt for the receipt.

  • A receipt consists of items of type Item. Create the class Item as a nested type in Receipt.

  • Each Item has a name and a (gross) price stored in cents.

  • Receipt should override toString() and return a formatted receipt:

    • Output all products and the total.

    • Entries can appear more than once on the receipt and should be summarized. For example, there are not nuts, nuts in the list, but 2x nuts. The entries must have the same name and price for equivalence.

    • Use a Locale you like in NumberFormat.getCurrencyInstance(locale) to format the currency.

Example:

  • With the structure

    Receipt receipt = new Receipt();
    receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
    receipt.addItem( new Receipt.Item( "Lightsaber", 19999 ) );
    receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
    receipt.addItem( new Receipt.Item( "Log book", 1000 ) );
    receipt.addItem( new Receipt.Item( "Peanuts", 222 ) );
    System.out.println( receipt );

    is the output (the comma is used as a decimal separator):

    3x  Peanuts                 2,22 €    6,66 €
    1x  Lightsaber            199,99 €  199,99 €
    1x  Log book               10,00 €   10,00 €
    
    Sum: 216,65 €

1.2.8. Quiz: Arrays decorated ⭐

Arrays are common in the API, and a conversion to the more convenient List happens quite often.

What is the result if we write the following in a Java program?

Arrays.asList( "One", "Two" ).add( "Three" );

1.2.9. Quiz: Searched and not found ⭐

What is the output if we have the following in a Java program?

int[] numbers1 = { 1, 2, 3 };
System.out.println( Arrays.asList( numbers1 ).contains( 1 ) );
Integer[] numbers = { 1, 2, 3 };
System.out.println( Arrays.asList( numbers ).contains( 1 ) );
System.out.println( Arrays.asList( 1, 2, 3 ).contains( 1 ) );

1.2.10. Everything tastes better with cheese: Insert elements into lists ⭐

Captain CiaoCiao likes veggies, but when he does, he has to add lots of cheese.

Task:

  • Write a method insertCheeseAroundVegetable(List) that gets a list of recipe ingredients and whenever vegetables appear in the list, adds the ingredient "cheese" right before or after it.

  • The list must be modifiable.

Examples:

  • gnocchi, zucchini, peppers, cream, broth, milk, butter, onion, tomato, salt, bell pepper → gnocchi, zucchini, cheese, peppers, cheese, cream, broth, milk, butter, onion, cheese, tomato, cheese, salt, bell pepper.

  • Cheese → Cheese

Use a fixed set of vegetables.

1.2.11. Quiz: With nothing but trouble ⭐

Given the following code, delete all empty strings in the list. Does the code do this?

List<String> names = new ArrayList<>();
Collections.addAll( names, "", "Sonny", "Crockett", "Burnett",
                    "Ricardo", "", "Rico", "Tubbs", "Ricardo", "Cooper", "" );

for ( String name : names )
  if ( "".equals( name ) )
    names.remove( name );

1.2.12. Search elements with the iterator and find Covid Cough ⭐⭐

Bonny Brain runs to the port and looks for Covid Cough, who is stashing disinfectant in his ship. Each ship contains a list of passenger names. Ships are declared by the following small class:

class Ship {
  private List<String> persons = new ArrayList<>();
  void addName( String name ) { persons.add( name ); }
  boolean contains( String name ) { return persons.contains( name ); }
  @Override public String toString() {
    return "" + persons;
  }
}

There are 100 ships at the port, stored in a LinkedList<Ship>. Covid Cough is hiding in an unknown ship, let’s simulate that:

final int NUMBER_OF_SHIPS = 100;

List<Ship> ships = new LinkedList<>();
for ( int i = 0; i < NUMBER_OF_SHIPS; i++ )
  ships.add( new Ship() );

ships.get( new Random().nextInt( ships.size() ) ).addName( "Covid Cough" );

Bonny Brain arrives at one of the many entrances to the harbor and there are ships to her right and left:

int index = new Random().nextInt( ships.size() );
ListIterator<Ship> iterator = ships.listIterator( index );

The only access to the ships is given by the ListIterator. Keep in mind that the ListIterator can only be used to go forward and backward, there is no random access!

Task:

  • Visit the ships with the ListIterator, and find Covid Cough.

  • Is there a strategy how to find the person most efficiently? It is known how many ships there are in total, 100. Since the index is known where Bonny Brain enters the harbor, we also know how many ships are to the left and right of the entrance.

1.2.13. Move elements, play musical chairs ⭐

At a birthday party, the guests are playing musical chairs. People sit on chairs, and when the music starts playing, they get up and walk around the chairs. The names of the guests are in a list.

Task A:

  • Create a new class MusicalChairs.

  • Create a constructor MusicalChairs(String... names) that stores the names internally.

  • Implement the method toString() which returns the names comma separated.

  • Write a method rotate(int distance) that shifts the names in the list by the position distance to the right. The elements falling out to the right are pushed back in to the left. The operation is in place, so the (internal) list itself is changed, and the method does not return anything.

Use a suitable method from Collections for the task.

Example:

MusicalChairs musicalChairs =
    new MusicalChairs( "Laser", "Milka", "Popo", "Despot" );
musicalChairs.rotate( 2 );
System.out.println( musicalChairs ); // Popo, Despot, Laser, Milka

Task B:

  • Write another method void rotateAndRemoveLast(int distance), which first moves the list by distance positions to the right and then deletes the last element.

  • Add a method String play() that calls rotateAndRemoveLast(…​) in a loop until there is only one element left in the list; then the winner is determined, and it is returned as a string. The distance is random on each pass.

Consider the case where the list might be empty in the solution.

1.2.14. Programming a question game with planets ⭐⭐

Captain CiaoCiao is accepting new recruits, and to test their knowledge, he asks them the diameter of the planets in the solar system. He wants an interactive application for this, where a planet is randomly selected, and the recruits must know the diameter.

The planets are predefined as an enumeration type:

com/tutego/exercise/util/PlanetQuiz.java
enum Planet {

  JUPITER( "Jupiter", 139_822 ), SATURN( "Saturn", 116_464 ),
  URANUS( "Uranus", 50_724 ), NEPTUNE( "Neptune", 49_248 ),
  EARTH( "Earth", 12_756 ), VENUS( "Venus,", 12_104 ),
  MARS( "Mars", 6_780 ), MERCURY( "Mercury", 4_780 ),
  PLUTO( "Pluto", 2_400 );

  public final String name;
  public final int    diameter; // km

  Planet( String name, int diameter ) {
    this.name     = name;
    this.diameter = diameter;
  }
}

Task:

  • Program a console application that builds a random sequence of all planets in the first step. Consider how we can use the shuffle(…​) method from java.util.Collections for this.

  • Iterate over this random sequence of planets, and generate a console output that asks for the diameter of those planets. As a choice, the recruit should be shown four diameters in kilometers, where one diameter is the correct one and three diameters are from different planets.

  • If the recruit enters the correct diameter, a message appears on the screen; if the wrong diameter is entered, the console output reports the correct diameter.

Example:

What is the diameter of planet Uranus (in km)?
49248 km
50724 km
12756 km
139822 km
50724
Correct!

What is the diameter of planet Pluto (in km)?
12104 km
4780 km
2400 km
12756 km
11111
Wrong! The diameter of Pluto is 2400 km.

What is the diameter of planet Jupiter (in km)?
139822 km
6780 km
2400 km
49248 km
...

1.3. Sets

Sets contain their elements only once. They can be unsorted or sorted. Java provides the Set interface for abstraction, two important implementations are HashSet and TreeSet.

A whole series of questions arise with sets:

  1. Is the set empty?

  2. Which elements are in the set?

  3. Is a asked element in the set, yes or no?

  4. Given two sets, do they both contain the same elements?

  5. What does a new set look like when two sets are united?

  6. Does the set completely contain another set, so is one set a subset of another?

  7. What is the intersection of two sets, that is, what are the elements that occur in both sets?

  8. What is the difference set, that is, if you delete elements from one set that are present in another set?

Some of these operations can be answered directly using the Set data type. For example, there are the methods isEmpty() or contains(…​). Set operations in particular are not very well supported, and programmers sometimes have to take workarounds for them. For subsets, for example, there is the Collections method disjoint(Collection<?>, Collection<?>), but it returns a boolean that says whether the two collections have no common element.

Let’s answer some of the questions with tasks.

1.3.1. Form subsets, find common elements ⭐

Bonny Brain’s daughter is dating Cora Corona, and they want to find out if they are compatible. So they both write down what they like. It looks like this:

Set<String> me = new HashSet<>();
Collections.addAll( he, "Candy making", "Billiards", "Fishkeeping", "Eating", "Action figures", "Birdwatching", "Axe throwing" );
Set<String> she = new HashSet<>();
Collections.addAll( she, "Axe throwing", "Candy making", "Action figures", "Casemodding", "Skiing", "Satellite watching" );

Task:

  • What percentage of similarity do the two have? What methods can we use to answer the question?

Look up methods in Set to see if they can be used to form subsets or intersections.

1.3.2. Quiz: Great Swords ⭐

The following program will compile. What is the program output?

class Sword implements Comparable<Sword> {
  String name;

  public int compareTo( Sword other ) { return 0; }

  public boolean equals( Object other ) {
    throw new IllegalStateException();
  }

  public String toString() { return name; }

  public static void main( String[] args ) {
    Sword one = new Sword();
    Sword two = new Sword();
    one.name = "Khanda";
    two.name = "Kilij";
    Set<Sword> swords = new TreeSet<>();
    System.out.printf( "%s %s %s", swords.add( one ), swords.add( two ), swords );
  }
}

1.3.3. Remove duplicate elements from arrays ⭐

Task:

  • Create a static method double[] unique(double... values) that returns an array with all elements of the passed array in the same order, but no duplicate entries.

  • If the argument is null, the method must throw an exception.

Example:

com/tutego/exercise/util/UniqueArrayElements.java
System.out.println( Arrays.toString( unique() ) ); //                                    []
System.out.println( Arrays.toString( unique( 1, 2 ) ) ); //                      [1.0, 2.0]
System.out.println( Arrays.toString( unique( 1, 1 ) ) ); //                           [1.0]
System.out.println( Arrays.toString( unique( 1, 2, 1 ) ) ); //                   [1.0, 2.0]
System.out.println( Arrays.toString( unique( 1, 2, 1, Double.NaN ) ) ); //  [1.0, 2.0, NaN]
System.out.println( Arrays.toString( unique( 1, Double.NaN, Double.NaN ) ) ); // [1.0, NaN]
System.out.println( Arrays.toString( unique( -0, 0 ) ) ); //                [1.0, 2.0, NaN]

1.3.4. Get all words contained in a word ⭐⭐

Captain CiaoCiao intercepts a secret message, and the text consists of words that are seemingly unrelated. After some pondering, it occurs to him that there are other words in the words.

A program is to find out what valid words a given word contains. To find out what is a valid word, you can use a word list from the Internet:

Task:

  • Write a program with a static method Collection<String> wordList(String string, Collection<String> words) that generates all substring contained in string and returns exactly those words in a Collection that are valid words in the dictionary words.

Example for the English dictionary:

  • wordList( "wristwatches", words )[wrist, wristwatch, wristwatches, rist, is, twa, twat, wat, watch, watches, tch, tche, che, hes]

  • bibliophobia[abib, bib, bibl, bibliophobia, pho, phobia, hob, obi, obia]

A file with words can be transformed into a data structure like this:

private static final String WORD_LIST_URL =
    "https://raw.githubusercontent.com/creativecouple/all-the-german-words/master/corpus/de.txt";
    // "https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt";

private static Collection<String> readWords() throws IOException {
  URL url = new URL( WORD_LIST_URL ); //    370.000 words
  Collection<String> words = new HashSet<>( 500_000 );
  try ( InputStream is = url.openStream() ) {
    new Scanner( is ).forEachRemaining( s -> words.add( s.toLowerCase() ) );
  }
  return words;
}

1.3.5. Exclude duplicate elements with a UniqueIterator ⭐⭐

In other data structures, for example lists, elements can occur more than once. Write a UniqueIterator that returns elements of a Collection only once.

The generic types are declared as follows:

public class UniqueIterator<E> implements Iterator<E> {

  public UniqueIterator( Iterator<? extends E> iterator ) {
    // ...
  }

  // etc.
}

The constructor indicates that the new iterator gets an existing iterator as a parameter. So a call could look like this:

List<String> names = ...;
Iterator<String> UniqueIterator = new UniqueIterator( names.iterator( ) );

1.4. Map keys to values

A hash table associate keys with values. In other programming languages, they are also called dictionaries. Java uses the Map interface to specify the operations for all implementations. Two important implementations are HashMap and TreeMap. (Associative memoryDictionary)

1.4.1. Convert two-dimensional arrays to map ⭐

Data types that inherit from Collection are relatively flexible in accepting data; for example, the elements of a List can be copied into a Set via addAll(Collection). Arrays can also be used directly as Collection with Arrays.asList(…​).

The Map data type is less flexible, it is not possible to simply transfer arrays or other Collection collections into a Map.

Task:

  • Write a method Map<String, String> convertToMap(String[][]) that converts a two-dimensional array into a java.util.Map.

  • The first entry in the array should be the key, the second the value.

  • The keys correctly implement hashCode() and equals(…​).

  • If later in the array the same key occurs again, the method overwrites the earlier pair.

  • Keys and values must not be null and must lead to an exception.

Example:

String[][] array = {
    { "red",   "#FF0000" },
    { "green", "#00FF00" },
    { "blue",  "#0000FF" }
};
Map<String, String> colorMap = convertToMap( array );
System.out.println( colorMap ); // {red=#FF0000, green=#00FF00, blue=#0000FF}

1.4.2. Convert text to Morse code and vice versa ⭐

Captain CiaoCiao needs to send a message to a distant island using Morse code. A Morse code message consists of short and long symbols indicated by the characters . and -.

Copy the following definition into a new class Morse:

// A .-      N -.      0 -----
// B -...    O ---     1 .----
// C -.-.    P .--.    2 ..---
// D -..     Q --.-    3 ...--
// E .       R .-.     4 ....-
// F ..-.    S ...     5 .....
// G --.     T -       6 -....
// H ....    U ..-     7 --...
// I ..      V ...-    8 ---..
// J .---    W .--     9 ----.
// K -.-     X -..-
// L .-..    Y -.--
// M --      Z --..

Task:

  • Create a new class Morse.

  • Write two methods:

    • String encode(String string). It accepts a string and converts it to Morse code. Each character of the string is to be output in the corresponding Morse code. Each block is to be separated by a space in the output. Unknown characters are skipped. Lowercase letters shall be evaluated like uppercase letters. There are two spaces between words.

    • String decode(String string). Turns Morse code back into the original strings. The two spaces for word separators become single spaces again.

1.4.3. Remember word frequency with associative memory ⭐⭐

Girly Gossip listens in on the deck of a group so she can tell Captain CiaoCiao later what is being discussed. What is important is what is often mentioned as a word or phrase.

Task:

  • Write a method List<String> importantGossip(String... words) that returns, from a vararg of strings, exactly the five strings in a list that occur most often in the array passed.

Example:

String[] words = {
    "Baby Shark", "Corona", "Baby Yoda", "Corona", "Baby Yoda", "Tiger King",
    "David Bowie", "Kylie Jenner", "Kardashian", "Love Island", "Bachelorette",
    "Baby Yoda", "Tiger King", "Billie Eilish", "Corona"
};
System.out.println( importantGossip( words ) );

outputs

[Baby Yoda, Corona, Tiger King, Baby Shark, Bachelorette.]

Keep in mind that it is not about the individual words like Baby or Yoda, but always about the whole string, for example Baby Yoda or Baby Shark.

1.4.4. Read in and read out colors ⭐⭐

Bonny Brain gets a new design for their flags, but the designers only speak gibberish:

For the background, let's use #89cff0 or #bcd4e6, and for the text, maybe #fffaf0 or #f8f8ff.

She finds out that a specification like #RRGGBB stands for the red, green, blue part of a color, coded hexadecimal. Fortunately there are "translation tables" like https://tutego.de/download/colors.csv, which contains lines like

amber,"Amber",#ffbf00,255,191,0
aqua,"Aqua",#0ff,0,255,255
blush,"Blush",#de5d83,222,93,131
wine,"Wine",#722f37,114,47,55

Sometimes the file contains the color values only with three symbols, like in the example aqua with 0ff. In this case the individual color values are doubled, so #RGB then becomes #RRGGBB.

Task:

  1. Create a new class Color for the representation of colors. Each color has a name ( String name) and an RGB value ( int rgb). Write — or generate via the IDE — the method toString(). Add further methods if that would be useful.

  2. Create a new class ColorNames.

    • Give the class an object variable HashMap<Integer, Color> colorMap, so that ColorNames can internally remember all Color objects in a Map; the keys of the Map are the RGB values as integer, and the associated value is the corresponding Color object.

    • Copy the file https://tutego.de/download/colors.csv locally to disk.

    • Create a constructor that reads the file. We can use Scanner for this, or read the file completely with Files.readAllLines(Paths.get("colors.csv")), which returns a List<String>.

    • Split each line of the CSV source, extract the color name (2nd column) and RGB value (3rd column). Tip: The color value can be converted to an integer using a Java method: Integer.decode("#722f37") returns 7483191. Remember that color names can be in the form #RGB and #RRGBB.

    • Transfer the color name and integer value to Color objects, and place them in the Map.

    • Add a method decode(int rgb) that returns the associated Color object for an RGB value.

Example:

  • mapper.decode( 7483191 )Optional['Wine' is RGB #722F37]

  • mapper.decode( 7 )Optional.empty

1.4.5. Read in names and manage lengths ⭐

Bonny Brain likes to play name crossword puzzles where each entry is a name. Often she can’t think of a name with a certain length — a software should help!

Task:

  1. The file http://tutego.de/download/family-names.txt contains last names. Save the file on your own file system.

  2. Read the file. For this we can use for example the class Scanner or the Files method readAllLines(Path).

  3. Sort the names into a TreeMap<Integer, List<String>>: The key is the length of the name, the list contains all names with the same length.

  4. On the command line, list all names in ascending order of length.

  5. Ask from the command line for a length and output all names of that length as long as the length is not 0 or negative.

1.4.6. Find missing characters ⭐⭐

Captain CiaoCiao has scammed the Dead Sea Scrolls (Cumexhopp scrolls) and no one has been able to decipher the text yet. He wants to make it! However, many characters are unreadable, while other characters are easily readable. It is also easy to see how many characters the word has.

Task:

  • Create a new class with main(…​) method and copy the two lists into the program:

    List<String> words = Arrays.asList( "house", "mouse", "horn", "cannon" );
    List<String> missingLettersWords = Arrays.asList( "_ouse", "ho__", "ca__on", "gun", "__e__", "_____" );
  • Match each word from missingLettersWords with all possible words from the dictionary words where the underscore symbolizes unknown characters.

  • The length of the suggested words from the dictionary must be equal to the word length of the unreadable word.

  • At least one character must be given.

Example:

  • Possible screen output from the given lists:

    _ouse -> [mouse, house]
    ho__ -> [horn]
    ca__on -> [cannon]
    gun -> No results
    __e__ -> No results
    _____ -> No results

1.4.7. Calculate number of paths to the three-headed monkey ⭐⭐

After a night of drinking in Manhattan, Captain CiaoCiao misses his three-headed monkey. He must have lost the stuffed animal somewhere along the way! But where could it be? His team has to walk all the streets from start to finish. The only thing Captain CiaoCiao can remember is that he didn’t get across the diagonal.

Catalan number 4x4 grid example
Figure 2. Possible routes from the start to the finish (source: Wikipedia)

The image shows 4 × 4 street blocks and there are 14 possibilities. After some time of searching the crew finds the stuffed animal, they are lucky!

Captain CiaoCiao ponders: What if there were 5 or 10 blocks — wouldn’t the number of paths then be much too large to search?

The answer to the question is provided by mathematics. What is being searched for here is a monotonic path for a square with n × n cells. The number of possible paths provides the Catalan number, which is calculated as follows:

Cn = (2n)! / (n+1)! n!

Task:

  • Convert the formula by a method BigInteger catalan(BigInteger n). Use your own internal method BigInteger factorial(BigInteger n) for the factorial calculation.

  • Three factorials must be calculated in the formula: n!, (n+1)! and (2n)!. It is (n+1)! nothing else than n! × (n+1) is, so n! has to be calculated twice; also on the way to the calculation of (2n)! the intermediate result (n+1)! arises. So many multiplications have to be done twice, so the products should be cached: resort to the datatype WeakHashMap for this.

  • Compare the times when we call the catalan(…​) method twice with the same parameters. Use the following code as a template:

    long start = System.nanoTime();
    BigInteger catalan1000 = catalan( BigInteger.valueOf( 1000 ) );
    long end = System.nanoTime();
    System.out.println( catalan1000 );
    System.out.println( TimeUnit.NANOSECONDS.toMillis( end - start ) );

1.4.8. Manage holidays in a sorted associative store ⭐

Elements in a TreeMap are automatically sorted. TreeMap implements java.util.NavigableMap, which HashMap does not. The order is either determined by an external Comparator, or the elements have a natural order.

From the API documentation, we see that firstEntry() and lastEntry() return the smallest and largest element, respectively. The return type is Map.Entry<K,V>.

Given a key key, the following methods return relative to that key:

  • ceilingXXX(K key): returns a result greater than or equal to this key.

  • floorXXX(K key): Returns a result lower than or equal to the given key.

  • lowerXXX(K key): Returns a result that is true smaller than the given key.

  • higherXXX(K key): Returns a result that is truly greater than the given key.

All methods return null if there is no answer to the question.

For subsets, the following methods are useful:

  • SortedMap<K,V> subMap(K fromKey, K toKey)

  • NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)

In the first case, fromKey is inclusive and toKey is exclusive; this corresponds to the usual convention of Java. The second method allows more precise control over whether the start or end element belongs.

Task:

  • Build a sorted associative memory:

    NavigableMap<LocalDate, String> dates = new TreeMap<>();
    dates.put( LocalDate.of(...), "..." );

    The type <LocalDate, String> means that a temporal type LocalDate should be associated with a string.

  • The class LocalDate implements Comparable, which means that the elements have a natural order.

  • Fill the data structure with some pairs for real or fictitious holidays.

  • Answer the following questions using the appropriate methods of NavigableMap:

    • According to the data structure, what is the earliest and last holiday?

    • The Christmas vacations end on the 6th of January. What is the first holiday after the Christmas vacations?

    • Which date values are in the Christmas vacations from December 23 – January 6 (date values inclusive)?

    • Delete the Christmas vacations from the data structure.

1.4.9. Quiz: Keys in a HashMap ⭐⭐

Consider what appears on the screen for the following program:

Map<Point, String> map = new HashMap<>();
Point p = new Point( 1, 2 );
map.put( p, p.toString() );
p.setLocation( 2, 1 );
System.out.println( map );
System.out.println( map.get( p ) );
p.setLocation( 1, 2 );
System.out.println( map.get( p ) );

What must be true for keys of an associative store?

1.4.10. Determine commonality: Party set and souvenir ⭐

Bonny Brain plans a party, and all families contribute:

Set<String> gombonoGifts = new HashSet<>();
Collections.addAll( gombonoGifts, "Vodka", "BBQ Grill", "kneading soap" );

Set<String> banannaGifts = new HashSet<>();
Collections.addAll( banannaGifts, "Vodka", "drinking helmet" );

Set<String> cilimbiGifts = new HashSet<>();
Collections.addAll( cilimbiGifts,
                    "drinking helmet", "Money box", "Vodka", "water pistol" );

List<Set<String>> families =
    Arrays.asList( gombonoGifts, banannaGifts, cilimbiGifts );

Since Bonny Brain is a perfection strategist, she wants to know if things are brought multiple times.

Task:

  • Write a method printMultipleGifts(List<Set<String>> families) that outputs which things are brought how many times.

  • What was brought more than once?

Example:

  • Possible output for the upper assignments:

    {drinking helmet=2, kneading soap=1, water pistol=1, Money box=1, BBQ Grill=1, Vodka=3}
    drinking helmet
    Vodka

1.5. Properties

The class Properties is a special associative memory which associates only strings with strings. The class not only represents a data structure, but can also read and write files called property files. These are text files that are usually used for configuration. Key-value pairs are separated in the file by =. It is also possible to read and write the values in an XML format, but this is uncommon.

1.5.1. Develop comfortable properties decorator ⭐⭐

The Properties class contains key-value pairs, where the keys are always just strings. Possible conversions have to be done by developers themselves, which is inconvenient.

Task:

Write a class PropertiesConfiguration that decorates a Properties object. The most general method returns an Optional that is either filled or empty if the key does not exist:

  • Optional<String> getString(String key).

The advantage with the Optional is that alternatives for default values can easily be determined: conf.getProperty("rank").orElse("Captain").

Other methods of PropertiesConfiguration are to perform conversions:

  • Optional<Boolean> getBoolean(String key)

  • OptionalLong getLong(String key)

  • OptionalDouble getDouble(String key)

  • Optional<BigInteger> getBigInteger(String key)

If there was no associated value to the key, the container is empty. If the conversion to an error fails, that also results in an empty container.

Example for the API:

Properties root = new Properties();
root.setProperty( "likes-rum", "true" );
root.setProperty( "age", "55" );
root.setProperty( "income", "123456789012" );
root.setProperty( "hobbies", "drinking, gambling\\, games, swearing competitions" );
root.setProperty( "weakness_of_character", "" );
PropertiesConfiguration conf = new PropertiesConfiguration( root );
Optional<Boolean> maybeLikesRum = conf.getBoolean( "likes-rum" );
OptionalLong maybeAge = conf.getLong( "age" );
Optional<BigInteger> maybeIncome = conf.getBigInteger( "income" );

System.out.println( maybeLikesRum );       // Optional[true]
System.out.println( maybeAge );            // OptionalLong[55]
System.out.println( maybeIncome );         // Optional[123456789012]

Optional addition: query lists.

Advanced developers can implement the following method:

  • List<String> getList(String key). Returns a list of comma-separated strings. The comma itself can be masked out by \,.

Example:

List<String> hobbies = conf.getList( "hobbies" );
List<String> weaknessOfCharacter = conf.getList( "weakness_of_character" );

System.out.println( hobbies );             // [drinking, gambling, games, swearing competitions]
System.out.println( hobbies.size() );      // 3
System.out.println( weaknessOfCharacter ); // []

*Optional addition: store binary values

A java.util.HashMap can associate arbitrary types, for a Properties only strings can be associated with strings. If other data types, such as byte arrays, are to be stored, they must be converted to a string. A byte[] can be converted to an ASCII string in various ways, such as using BASE64 encoding; Java can do this using the class Base64.

Since Properties are read rather than written, the getXXX(…​) methods were sufficient for us so far. With the following addition, two new methods are to be written, one for setting and one for querying:

  • void putBinary(String key, byte[] bytes)

  • Optional<byte[]> getBinary(String key)

An example of use:

conf.putBinary( "binary", new byte[]{ 0, 1, 127, (byte) 254, (byte) 255 } );
System.out.println( conf.getString( "binary" ) ); // Optional[AAF//v8=]
byte[] binary = conf.getBinary( "binary" ).get();
System.out.printf( "%d %d %d %d %d", binary[0], binary[1], binary[2], binary[3], binary[4] );

1.6. Stack and queues

A general list in Java lets us access the elements by an index, we call such an access also random access, because we have the choice to ask for an element at any position. There are data structures that are much more restricted and can, for example, only insert or delete elements at the beginning or end. These include:

  • stack

  • queues

With a stack, you can only insert elements at one end and must remove the elements again at this end. The principle is also called LIFO: last in, first out. In contrast to this is the queue. With it that is read out first, which was added also as first. The principle is called FIFO: first in, first out.

Pure stacks and queues do not exist in Java, only interfaces implemented by lists.

1.6.1. Program UPN pocket calculator ⭐

We usually write mathematical expressions in infix notation, where the operators are placed between the operands, such as 47 + 11. In principle, however, the operator can also stand in front of the operands, as in + 47 11, or behind them, as in 47 11 +.

The Hewlett-Packard pocket calculators had established a special input in the 1980s, the inverted Polish notation (UPN). This is a postfix notation where the operators are placed after the values.The advantage for computers is that the precedence — point before line calculation — has already been resolved by users, simplifying program logic in the calculator. PostScript also uses this representation, because mathematical expressions can be easily evaluated via a stack.[2]

We want to program a UPN calculator.

Task:

  1. Write a program that first tokenizes a string like "12 34 23 + *". Hint: For splitting you can use split(…​) of String or a Scanner.

  2. After splitting the result is to be evaluated. Start with a fixed string for testing.

  3. Read in a string from the command line so that we have a real UPN calculator.

  4. What errors and problems need to be handled and caught? How should we handle errors?

1.7. BitSet

The class BitSet is a space-saving and performant alternative to boolean arrays. The data structure is useful when you need a mapping of an integer to a truth value. The data structure can quickly answer whether an index (a positive integer) is associated with true or false. If the number of bits becomes too large, or if there are large gaps, https://github.com/brettwooldridge/SparseBitSet is a good alternative.

1.7.1. Find duplicate entries, and solve the animal chaos ⭐

Captain CiaoCiao feeds the animals of his private zoo before going to bed. But being a bit tipsy from the rum, he forgets to close the gate. The next morning, Finian Fishbone and Fred Fritte notice that animals are missing. They quickly run to Captain CiaoCiao: "Some animals have escaped!" — "Scurvy baboon! Which ones?" asks the captain. The two ponder and record (writing is not their strong suit):

  • 🐩🐏🐴🦋🐙

  • 🐴🐏🐧🐸🦋🐌

Captain CiaoCiao notes that both have poor memories, and only wants to have animals searched for that are named by both.

Task:

  • Write a method String sameSymbols(String, String) that returns a string containing the common symbols. The order does not matter, all Unicode characters are possible.

  • Since we have to run over the string and it contains "higher" Unicode characters, which are moved out by two char, the solution is to use string.codePoints().forEach(consumer). This statement runs over all characters of the String string and calls the passed IntConsumer for each character. This is an application of the Stream API, which we will look at in more detail in the next chapter.

Examples:

  • sameSymbols("🐩🐏🐴🦋🐙", "🐴🐏🐧🐸🦋🐌")"🐏🐴🦋"

  • sameSymbols("abcy", "bcd")"bc"

  • sameSymbols("abc", "def")""

Since the result is urgent, implement the method so that the runtime is linear with the length of the strings, in computer science jargon: O(N+M) if N and M are the lengths of the strings. All Unicode characters are allowed.

1.8. Thread-safe data structures

For the previous tasks around the data structures ArrayList, LinkedList, HashSet, TreeSet etc. we never needed more than the main thread. In the following tasks, more threads and concurrent accesses come into play, and then we need to use thread-safe data structures. For the solutions we want to use the data types from the package java.util.concurrent, in which a whole set of thread-safe data structures are declared, which work correctly even with an arbitrary number of parallel accesses and have a very good performance.

1.8.1. Loading ship ⭐⭐

Captain CiaoCiao and the crew are getting ready for the next big adventure on Gazorpazorp Island. 5 employees put crates and barrels on the loading ramp, and 10 employees stow the goods in the ship. There can be no more than 5 objects on the loading dock at a time.

Task:

  • Create an ArrayBlockingQueue<String> of capacity 5 for the ramp.

  • Create two different Runnable implementations Loader and Unloader which get a reference to the ArrayBlockingQueue.

    • The Loader puts strings on the ramp (random strings from a set of product names).

    • The Unloader shall take strings from the ramp and output them to the screen.

      It takes Loader and Unloader randomly between 1 and 2 seconds for their work.

  • 5 threads shall be Unloader and 10 threads Loader.

There are different methods for adding and removing. The difference is important, otherwise program errors may occur:

Table 1. BlockingQueue methods for adding and removing elements.
operationexceptionnull returnblocked

insert

add(e)

offer(e)

put(e)

Remove

remove()

poll()

take()

You can’t deduce the semantics from the method names, you have to learn the difference. For our task only one column and these methods come into question.

1.8.2. Handle important messages first ⭐⭐

A PriorityQueue has an internal sorting so that the items with a higher priority move to the front. The priority comes from either the natural ordering of the elements implementing Comparable, or an external Comparator. "Small" elements have a higher priority and move to the front of the PriorityQueue. At the end of the queue are the elements with the lowest priority. (This is the same as with vaccinations: Prioritization group 1 gets the stuff first).

From different sides Captain CiaoCiao gets assigned tasks. The wishes of Bonny Brain always come first, of course. Captain CiaoCiao recognizes them by the fact that Bonny Brain’s work assignments contain the coseword "canon".

Task:

  • Write a class Message that stores a String for the job order and a timestamp of type long. Initialize the timestamp with System.nanoTime(). Implement/generate hashCode(), equals(Object) and toString().

  • For Message implement a Comparator which creates an order so that messages with the cosword are "smaller" than messages without the cosword, so that this can be evaluated as higher priority later. If both messages contain a term of endearment or both messages do not contain a term of endearment, they are equally "important".

  • Extend the Comparator by another comparison logic, so that the timestamp is considered and an earlier message is also processed earlier.

  • Initialize the PriorityQueue with messages, and watch how messages with the coseword move forward in the queue.

Example:

Assuming that PriorityQueue<Message> tasks is a correctly initialized data structure, the following program will produce the output shown:

tasks.add( new Message( "Treasure Hunt" ) );
System.out.println( tasks );

tasks.add( new Message( "Kanönchen, Family Movie Night!" ) );
System.out.println( tasks );

tasks.add( new Message( "Build a pirate ship" ) );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

tasks.add( new Message( "Capture the Flag" ) );
System.out.println( tasks );

tasks.add( new Message( "Bury the treasure, Kanönchen" ) );
System.out.println( tasks );

tasks.add( new Message( "Kanönchen, make a treasure map" ) );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

System.out.println( tasks.remove() );
System.out.println( tasks );

The output is:

['Treasure Hunt', 46400]
['Kanönchen, Family Movie Night!', 23700, 'Treasure Hunt', 46400]
['Kanönchen, Family Movie Night!', 23700, 'Treasure Hunt', 46400, 'Build a pirate ship', 70600]
'Kanönchen, Family Movie Night!', 23700
['Treasure Hunt', 46400, 'Build a pirate ship', 70600]
'Treasure Hunt', 46400
['Build a pirate ship', 70600]
['Build a pirate ship', 70600, 'Capture the Flag', 83200]
['Bury the treasure, Kanönchen', 10900, 'Capture the Flag', 83200, 'Build a pirate ship', 70600]
['Bury the treasure, Kanönchen', 10900, 'Kanönchen, make a treasure map',
71400, 'Build a pirate ship', 70600, 'Capture the Flag', 83200]
'Bury the treasure, Kanönchen', 10900
['Kanönchen, make a treasure map', 71400, 'Capture the Flag', 83200, 'Build a pirate ship', 70600]
'Kanönchen, make a treasure map', 71400
['Build a pirate ship', 70600, 'Capture the Flag', 83200]
'Build a pirate ship', 70600
['Capture the Flag', 83200]
'Capture the Flag', 83200
[]

1.8.3. If used up, create a new one ⭐⭐⭐

The expression new BigInteger(1024, new SecureRandom()) generates a large random number of type BigInteger.

Task:

  • Write a custom class SecureRandomBigIntegerIterator that implements Iterator and can return an infinite number of BigIntegers.

  • Whenever the number is queried and used up, a background thread should automatically compute a new random number.

1.9. Suggested solutions

1.9.1. Quiz: Search for StringBuilder

The program returns the output

true
false

The explanation for this lies in the implementation of the contains(Object) method. It internally falls back to a method that returns the location of the element, but we can read from the current implementation of the Java library quite well what must be true for a search:

Excerpt from java.lang.ArrayList.
int indexOfRange(Object o, int start, int end) {
   Object[] es = elementData;
   if (o == null) {
       for (int i = start; i < end; i++) {
           if (es[i] == null) {
               return i;
           }
       }
   } else {
       for (int i = start; i < end; i++) {
           if (o.equals(es[i])) {
               return i;
           }
       }
   }
   return -1;
}

The indexOfRange(…​) method searches for the position of the object o, and first distinguishes whether to search for the null reference or for a regular object. In our case, the object in the query is not null, so the equals(…​) method is used, that is, a loop compares each element in the list with our value via the equals(…​) method. Conversely, this means that the query will only work if we have also implemented a reasonable equals(…​) method. And this is exactly the problem: The String class provides an equals(…​) method, not the one from java.lang.Object, but an overridden method. The StringBuilder class, however, has no implementation of an equals(…​) method, but inherits this method from the superclass Object. In the superclass, however, only a reference comparison is implemented, which means that the content does not matter at all. However, since our StringBuilder objects in the list are always different, the reference comparison will never return true.

1.9.2. Singing and cooking: Traverse lists and check properties

There are different ways to solve the task. One variant is to remember the number of cooks in one variable and the number of musicians in another variable. Finally, the two variables are compared.

The solution suggestion realizes another variant. In the question of whether there is the same amount of two things, it is like having a scale where there must be the same amount of weight on the left and right side. The interesting thing is that the actual weight doesn’t matter at all, only that the scale is in balance.

com/tutego/exercise/util/SameNumberOfCooksAndMusicians.java
public static boolean areSameNumberOfCooksAndMusicians( List<CrewMember> crewMembers ) {
  int weight = 0;
  for ( CrewMember member : crewMembers ) {
    switch ( member.profession ) {
      case COOK     -> weight++;
      case MUSICIAN -> weight--;
    }
  }
  return weight == 0;
}

The solution variant implemented here loops over the list and counts up a variable weight if there is a cook, and counts down the variable if there is a musician in the list; of course, it could be the other way around. If the number of cooks and musicians is the same, weight will end up being 0.

The keyword switch can be used in another variant, as an expression:

com/tutego/exercise/util/SameNumberOfCooksAndMusicians.java
for ( CrewMember member : crewMembers ) {
  weight += switch ( member.profession ) {
    case COOK     -> +1;
    case MUSICIAN -> -1;
    default       ->  0;
  };
}

In this variant, we need to introduce a default branch. This basically creates one more line of code, and the notation is likely to be less attractive than the first notation or a variant with the conditional operator.

There is another way to solve the problem. It remains with the idea of creating a kind of scale, where some enumeration elements are transferred to +1 and the others to -1:

com/tutego/exercise/util/SameNumberOfCooksAndMusicians.java
int result = 0;
for ( CrewMember member : crewMembers ) {
  //                                                          CAPTAIN -+
  //                                                      NAVIGATOR -+ |
  //                                                    CARPENTER -+ | |
  //                                                       COOK -+ | | |
  //                                                 MUSICIAN -+ | | | |
  //                                                           v v v v v
  int zeroOrOneOrTwo = ((1 << member.profession.ordinal()) & 0b1_1_0_0_0) / 8;
  int minusOneOrZeroOrPlusOne = (zeroOrOneOrTwo / 2) - (zeroOrOneOrTwo & 1);
  result += minusOneOrZeroOrPlusOne;
}
return result == 0;

This approach might cause head shaking at first sight, but it is good to have seen and understood this way once. Let’s deduce the solution.

Given is an enumeration with various elements, which all have one position, the so-called ordinal number. CrewMember.Profession.CAPTAIN.ordinal() is 0, and CrewMember.Profession.COOK.ordinal() is 3. If we write 1 << x, and x is between 0 and 5, we get 1 shifted left by x positions and padded with zeros on the right. In other words, we get in binary notation the numbers

  • 0b000001 (CAPTAIN)

  • 0b000010 (NAVIGATOR)

  • 0b000100 (CARPENTER)

  • 0b001000 (COOK)

  • 0b010000 (MUSICIAN)

  • 0b100000 (DOCTOR)

We are interested in 0b001000 (COOK) and 0b010000 (MUSICIAN). To test whether the third or fourth bit is set in a number, we combine this number with the bit pattern 0b11000. If one of the two bits is set, the bit remains, all other bits are set to 0 by the AND operation with 0. In the end, because both bits cannot be set at the same time, we are left with 0 (no hit), 0b10000 (16) or 0b01000 (8). If we divide this value by 8 (or shift it three positions to the right), we get 0, 1 or 2.

If we want to use the principle of scales again, the numbers 1 and 2 do not help. We must bring either 1-1 and 2+1 or 1+1 and 2-1, and the 0 must remain 0. Of course, we could insert a condition statement, but we go to all the trouble to avoid an if statement. Let x be the number 0, 1, 2, then the expression (x / 2) - (x & 1) transforms exactly to the desired target, -1 and +1. We can add the expression and proceed in the same way as before.

Under normal circumstances, no one should program such solutions unless they are extremely performance critical and a profiler has shown that this variant is faster. Since we have here some mathematical operations — where /8, /2 are also cheap —, this should not be faster in the end than a small if. Condition statements are what people like to try to rewrite in microoptimization, but if you don`t know exactly what you`re doing here, it ends up being much more expensive.

Java 8 backport

The proposed solution uses the modern notation of switch, which has been around since Java 14. The classic notation is to write:

switch ( member.profession ) {
  case COOK: weight++; break;
  case MUSICIAN: weight--; break;
}

1.9.3. Filter comments from lists

com/tutego/exercise/util/RetainComments.java
public static void reduceToComments( List<String> lines ) {

  if ( lines.size() % 4 != 0 )
    throw new IllegalArgumentException(
        String.format( "Illegal size %d of list, must be divisible by 4", lines.size() ) );

  for ( int blockStart = lines.size() - 4; blockStart >= 0; blockStart -= 4 ) {
    // keep element at position blockStart + 3
    lines.remove( blockStart + 2 );
    lines.remove( blockStart + 1 );
    lines.remove( blockStart + 0 );
  }
}

For the algorithm to work correctly, the list length must be a multiple of 4. Therefore, the first condition statement checks if the length is divisible by 4; if not, there is an exception.

The following loop runs with an index blockStart in steps of four from back to front. The four sums blockStart + 0, blockStart + 1, blockStart + 2 and blockStart + 3 represent the index to the four elements of a block. blockStart + 3 is to be kept, all other lines we delete via the remove(..) method. You always have to be a little careful with this method, because it is overloaded.

  • The one variant remove(Object) deletes an equals(…​)-equal element from the list.

  • The second remove(int) method deletes an entry at the given position.

When deleting elements we go from the higher index towards the lower index. For lists (especially ArrayList) it is always reasonable to delete from the back, so that less elements have to be moved in memory. If we start at blockStart + 0, the element below the index is deleted, and all other elements move up. The solution would look like this:

lines.remove( blockStart );
lines.remove( blockStart );
lines.remove( blockStart );

1.9.4. Shorten lists, because there is no downturn

com/tutego/exercise/util/TrimNonGrowingList.java
static void trimNonGrowingNumbers( List<Double> numbers ) {

  if ( numbers.size() < 2 )
    return;

  double previous = numbers.get( 0 );
  for ( int i = 1; i < numbers.size(); i++ ) {
    double current = numbers.get( i );
    if ( current <= previous ) {
      numbers.subList( i, numbers.size() ).clear();
      break;
    }
    previous = current;
  }
}

At first glance, the task is simple: we run the list and see if the next element is larger. If this is not the case, we abort. Now the peculiarity is the following: We do not remember the elements in a new list, but we have to modify the list that was passed to us. That means, from a point where the elements become smaller, we have to delete the passed list until the end.

However, such a method does not exist in the List interface. Therefore, we have to reprogram the functionality by hand. There are two possible solutions:

  • There is a remove(int) method to which we can pass an index so that an element can be deleted at that point. Sensibly, we start from right to left, calling the method until we have shortened the list.

  • The second possibility takes advantage of a peculiarity of data structures that there are live views; this approach is also chosen by the proposed solution. The subList(…​) method returns a view of the list, but this one is live, and changes to this sublist are applied to the original, i.e. written through. If we clear this sublist with clear(), all elements in the original list disappear as well.

1.9.5. Eating with friends: Compare elements, find commonalities

com/tutego/exercise/util/FriendsSittingTogether.java
public record Guest(
    boolean likesToShoot,
    boolean likesToGamble,
    boolean likesBlackmail
) {
  public boolean hasDissimilarInterests( Guest other ) {
    return !(likesToShoot == other.likesToShoot ||
             likesToGamble == other.likesToGamble ||
             likesBlackmail == other.likesBlackmail);
  }
}

public static int allGuestsHaveSimilarInterests( List<Guest> guests ) {
  for ( int index = 0; index < guests.size(); index++ ) {
    Guest guest = guests.get( index );
    Guest rightNeighbor = guests.get( (index + 1) % guests.size() );
    if ( guest.hasDissimilarInterests( rightNeighbor ) )
      return index;
  }
  return -1;
}

We want to represent the guests as objects with three properties. This is done by the record Guest, which has an additional method hasDissimilarInterests(Guest); it compares itself with another Guest and checks if there are no common interests at all.

In the allGuestsHaveSimilarInterests(…​) method, a loop runs all guests. In doing so, we get the guest and its right neighbor, where the last element in the list has no element behind it. With the remainder operator, we come back out at the front of the list, which means the last element is compared to the first element. This is correct because all the guests are in a circle, and they all have a neighbor.

In the loop, hasDissimilarInterests(…​) determines if the two guests are without common interests. In this case, we return the index from our method. If the loop passes through all guests and they all have one in common, the return is -1.

1.9.6. Check lists for same order of elements

Let’s look at two proposed solutions. Both of them work on the same basic principle that the original list is doubled or, in case of the query after the last element, it starts again from the first element.

If we double the list from the task, we see that the second list occurs in it:

"Alexandre", "Charles", "Anne", "Henry", "Alexandre", "Charles ", "Anne", "Henry".

Suggested solution 1, copied lists
com/tutego/exercise/util/SameInTheCircle.java
List<String> names1 = Arrays.asList( "Alexandre", "Charles", "Anne", "Henry" );
List<String> names2 = Arrays.asList( "Anne", "Henry", "Alexandre", "Charles" );

ArrayList<String> duplicatedList = new ArrayList<>( names1 );
duplicatedList.addAll( names1 );
System.out.println( Collections.indexOfSubList( duplicatedList, names2 ) >= 0 );

For the first proposed solution, we copy all the names into a new list, because we don’t want to destroy the original list, and maybe the list is even immutable. With the method addAll(…​) we append to this copy the same elements from the source again. Thus we have duplicated the first list. The method Collections.indexOfSubList(List<?> source, List<?> target) implements the test, and returns the position where the list target occurs in the list source. We do not get a truth value via the method, but directly the position, and we only need to check if this position is greater than or equal to 0. The method returns -1 if the second list is not present in the first list.

We must not work with containsAll(…​), because the method does not check the order, but only checks if all elements of a second collection are present in the first collection, completely independent of the order; but the order is what matters.

The disadvantage of this solution is that we have to create a copy so that we can work with indexOfSubList(…​). With a little trick we can do without a copy.

Proposed solution 2, virtual duplicated list

What we need is a list that is virtually twice the size of the first one, and when accessing the element after the last element, starts again at the first element.

com/tutego/exercise/util/SameInTheCircle.java
private static <T> boolean isSameCircle( List<T> list1, List<T> list2 ) {

  if ( list1.size() != list2.size() )
    return false;

  AbstractList<Object> list1Duplicated = new AbstractList<>() {
    @Override public int size() {
      return list1.size() * 2;
    }

    @Override public Object get( int index ) {
      return list1.get( index % list1.size() );
    }
  };
  return Collections.indexOfSubList( list1Duplicated, list2 ) >= 0;
}

The method first checks whether the lists are the same size; this inquiry is also necessary in the first solution. Since isSameCircle(…​) can in principle work with all objects and not only with strings, the method is declared as a static generic method. Only a valid implementation of equals(…​) is required for the comparison.

The virtual list is implemented by a subclass of AbstractList. This base class is often used for list implementations in order to take over as much of the standard functionality as possible. We override two methods:

  • The size() method returns twice as many elements as the original list.

  • The method get(int) achieves by the remainder operator that if we go beyond the size with the index, it starts again at the beginning of the data structure.

This solution does not really create a new list in memory, but it is virtual and duplicated for outsiders. Of course the methods for modifying would not work at all, but size() and get(…​) are enough to work with indexOfSubList(…​) again.

1.9.7. And now the weather: Find repeated elements

com/tutego/exercise/util/WeatherOccurrences.java
record WeatherOccurrence( String weather, int occurrences, int startIndex ) { }

static WeatherOccurrence longestSequenceOfSameWeather( List<String> weather ) {

  int localMaxOccurrences = 1;
  int localStartIndex     = 0;

  int globalMaxOccurrences = localMaxOccurrences;
  int globalStartIndex     = localStartIndex;

  String recurringElement = weather.get( 0 );

  for ( int i = 1; i < weather.size(); i++ ) {
    String currentElement = weather.get( i );

    if ( Objects.equals( currentElement, recurringElement ) ) {
      localMaxOccurrences++;

      if ( localMaxOccurrences > globalMaxOccurrences ) {
        globalMaxOccurrences = localMaxOccurrences;
        globalStartIndex     = localStartIndex;
      }
    }
    else { // currentElement != recurringElement
      localStartIndex = i;
      localMaxOccurrences = 1;
      recurringElement = currentElement;
    }
  }

  return new WeatherOccurrence(
      weather.get( globalStartIndex ), globalMaxOccurrences, globalStartIndex );
}

To solve the problem, we need to consider two different sequences: a local longest sequence and a global longest sequence. Therefore, we need a number of variables in which to keep track of states. Two variables store the local maximum number of equal elements and the start index of this sequence, two other variables store the global maximum number of found elements and their position.

The program must answer the question whether an element occurs several times in a row. We initialize a variable recurringElement at the beginning with the first element and look in the further course whether this element repeats itself. The actual loop can start at index 1. The body of the loop reads the element and compares it with recurringElement to see if there are sequences of recurringElement. The test for equivalence is done by the static equals(…​) method of the Object class, because this has the advantage over calling equals(…​) on the elements that null does not lead to a problem. If the element repeats, the localMaxOccurrences counter is incremented by 1, and a condition statement checks if the local number of same occurring elements exceeds the global maximum. If it does, then the if block updates the globalMaxOccurrences and globalStartIndex variables. We don`t need to remember the actual element itself, because that only becomes relevant at the end, and then we can query the element, because we know the position of the element in the data structure.

If a non-equal object appears in the list, the starting position is set to the index by the new sequence, the number of repeated elements is set to 1 and recurringElement is reinitialized for the rest of the sequence.

At the end of the loop, the parameterized constructor builds a WeatherOccurrence with the three desired states.

1.9.8. Generate receipt output

com/tutego/exercise/util/Receipt.java
public class Receipt {
  public static class Item {
    public final String name;
    public final int centPrice;
    public final int occurrence;

    public Item( String name, int centPrice, int occurrence ) {
      if ( centPrice <= 0 )
        throw new IllegalArgumentException( "Price can not be <= 0" );
      if ( occurrence <= 0 )
        throw new IllegalArgumentException( "Occurrence can not be <= 0" );
      this.name = Objects.requireNonNull( name );
      this.centPrice = centPrice;
      this.occurrence = occurrence;
    }

    public Item( String name, int centPrice ) {
      this( name, centPrice, 1 );
    }

    public Item incrementOccurrence() {
      return new Item( name, centPrice, occurrence + 1 );
    }

    @Override public boolean equals( Object other ) {
      if ( other == null || getClass() != other.getClass() )
        return false;

      return    centPrice == ((Item) other).centPrice
             && name.equals( ((Item) other).name );
    }

    @Override public int hashCode() {
      return name.hashCode() * 31 + centPrice;
    }
  }

  private final List<Item> items = new ArrayList<>();

  public void addItem( Item item ) {
    int maybeIndex = items.indexOf( item );

    if ( maybeIndex >=0 )
      items.set( maybeIndex, items.get( maybeIndex ).incrementOccurrence() );
    else
      items.add( item );
  }

  @Override public String toString() {
    NumberFormat currencyFormatter = NumberFormat.getCurrencyInstance( Locale.GERMANY );
    StringBuilder result = new StringBuilder( 512 );
    int sum = 0;

    for ( Item item : items ) {
      int itemPriceTotal = item.centPrice * item.occurrence;
      String line = String.format( "%dx  %-20s%10s%10s%n",
                                   item.occurrence, item.name,
                                   currencyFormatter.format( item.centPrice / 100. ),
                                   currencyFormatter.format( itemPriceTotal / 100. ) );
      result.append( line );
      sum += itemPriceTotal;
    }

    result.append( "\nSum: " )
          .append( currencyFormatter.format( sum / 100. ) )
          .append( "\n" );

    return result.toString();
  }
}

First, let’s take a look at the Item class. There are two parameterized constructors:

  • The first constructor initializes all three pieces of information — the name, the price and the number of occurrences. In addition, the constructor checks the validity.

  • The second constructor is simply a simplification for the number 1.

Since Item objects are immutable, the incrementOccurrence() method returns a new Item object with an incremented count. The Item class overrides two methods from Object: the equals(…​) method and hashCode(). The compare method will become important later, as it allows us to search for Item objects in the data structure. occurrence is not considered, we will see why in a moment.

The receipt itself consists of a collection of Item objects. With the method addItem(Item) we add a new Item to the receipt. We don`t want to simply append the item, but do a reduction if an item with the same name and amount already exists, and then merge it. First indexOf(…​) searches for an equals(…​) like Item in the list, so occurrence had to be ignored. If indexOf(…​) finds an item, the result is >= 0, namely the index of the found item. The following condition statement distinguishes:

  • If the element was found, at the position the element is replaced by a new element where occurrence is increased by 1,

  • If no equals(…​)-equal Item was found in the list, it is appended at the end.

Finally we come to the toString() method. It must go through all entries and output the product name, the quantity, the price and the quantity multiplied by the price. We can implement price outputs in different ways; the solution chosen here uses the NumberFormat class to be able to support the currency symbol for different languages in the long run. The object built with NumberFormat.getCurrencyInstance(Locale.GERMANY) then automatically places the Euro sign behind the number. It is also the task of the toString() method to calculate the sum, which can then be output at the end. When dividing by 100. it is important to make sure that it is not an integer division, because otherwise we will miss the decimal places. The configured NumberFormat automatically sets two decimal places and fills up with 0.

1.9.9. Quiz: Arrays decorated

Result:

Exception in thread "main" java.lang.UnsupportedOperationException

asList(…​) implements the design pattern Adapter, which matches two incompatible APIs. In the case, it adapts the array type with the square brackets for reading and writing and the length attribute to a java.util.List. The operations on the list are live and are written through to the array. No list is created as a copy. Since the length of arrays cannot change after construction, elements cannot be deleted or added. If you try, an UnsupportedOperationException is thrown. This can be seen quite well in the original implementation:

From the OpenJDK implementation of java.util.Arrays
public static <T> List<T> asList( T... a ) {
  return new ArrayList<>( a );
}

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable {

  private final E[] a;

  ArrayList( E[] array ) {
    a = Objects.requireNonNull( array );
  }

  @Override
  public int size() { return a.length; }

  @Override
  public E get( int index ) { return a[ index ]; }

  ...
}
From the OpenJDK implementation of java.util.AbstractList
public void add( int index, E element ) {
  throw new UnsupportedOperationException();
}

The method asList(T... a) creates an instance of type ArrayList, where this does not refer to a java.util.ArrayList, but to a nested class in Arrays. It is easy to see that the read methods pass directly through to the array, but, for example, the add(…​) method throws an UnsupportedOperationException.

1.9.10. Quiz: Searched and not found

The output is as follows:

false
true
true

The method used here is declared as follows:

public static <T> List<T> asList(T... a)

The parameter type is a vararg, which is any object array. In the first case, we pass an array of primitive integers to asList(…​), and primitive data types are not reference types addressed by a generic type variable. This means that the type T stands for the reference type int[]; consequently, the resulting list is of type List<int[]>, and the contains(…​) method returns false.

Varargs do not exist within the JVM, they are just normal arrays with the main difference that when we call them we can directly pass a set of arguments that we collect and pass in an internal array. So with vararg methods, there are two ways to use them: by passing multiple arguments, which are then packed into an internal array, or by passing an array directly. This is exactly the variant we use here. The wrapper type Integer is the type argument for the type variable T; a List<Integer> is created and contains(…​) finds the 1 because the 1 becomes an Integer object via boxing and the wrapper objects implement equals(…​).

In the third part we use the variable argument list. First, the int elements are converted to Integer objects via boxing, then placed in the anonymous internal array and passed.

1.9.11. Everything tastes better with cheese: Insert elements into lists

When making changes in data structures, we can basically go two ways: build a new data structure with the desired properties or modify the data structure itself. All typical data structures like ArrayList, HashMap, TreeSet are modifiable, and so is this problem phrased, to insert elements into an existing data structure.

The assignment mentions a list, and elements in the list have a position. If something has to be introduced at a certain position, there are basically two possibilities: We can work with the index-oriented method add(int index, E element) or insert elements via a ListIterator. The index-oriented method has a disadvantage with a LinkedList, because it does not provide fast RandomAccess to the elements via an index. Since the method has the general parameter type List, we have to adjust for every possible list, and we don`t want to have miserable performance with LinkedList. For our output the ListIterator is perfect.

com/tutego/exercise/util/CheeseInserter.java
public static void insertCheeseAroundVegetable( List<String> ingredients ) {
  final String VEGETABLE = "Zucchini|Paprikas?|Zwiebeln?|Tomaten?";
  for ( ListIterator<String> iterator = ingredients.listIterator();
        iterator.hasNext(); ) {
    String ingredient = iterator.next();
    Pattern p = Pattern.compile( VEGETABLE );
    Matcher m = p.matcher( ingredient );
    if ( m.matches() )
      // The new element is inserted before the implicit cursor
      iterator.add( "Käse" );
  }
}

The proposed solution gets the ListIterator from the list and runs over all elements as usual with a combination of hasNext() and next(). After taking the element, matches(…​) asks if the element matches any of the predefined strings. So for this check, we use a regular expression that contains the different types of vegetables, even correctly with plural-s for selected types. If the string matches, "cheese" is inserted.

You can think of an iterator as a cursor that stands between the elements. After a next() the cursor is behind the element. The add(…​) method inserts the element before the cursor, that is, after the element supplied after next(). In other words, the cursor is not placed in front of the newly inserted element, but remains behind it. That is, the next next() will not supply the freshly inserted "cheese", but the next regular ingredient.

1.9.12. Quiz: With nothing but trouble

In a nutshell, no. There is an exception:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1012)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:966)

The program looks innocent: The extended for loop iterates over the list, we remove an element in the list. At first glance it is strange why removing elements leads to a ConcurrentModificationException, and what should be "concurrent" here? We do not work with threads!

"Concurrent" in our example is the iteration over the data structure and the "concurrent" deletion. Java recognizes when resuming the iterator that there has been a change to the data structure. In other words, the iterating and the removing are coupled by state. It works like this: an extended for loop does nothing but internally use an Iterator. If we rewrite the program a bit, as it actually is in bytecode, we get the following:

for ( Iterator<String> iterator = names.iterator(); iterator.hasNext(); ) {
  String name = iterator.next();
  if ( "".equals( name ) )
    names.remove( name );

    System.out.println( names );
 }
}

The implementation of List and the Iterator have a state in which they remember the number of modifications. When the Iterator is created, it initializes once with the modification counter of the list, and when the list makes modifications, it increments its modification counter. Later, when the Iterator goes to the next element, it compares its stored modification counter with the modification counter of the list, and if there is an inequality, there is the exception. In the code it looks like this:

class AbstractList {
  protected transient int modCount = 0;

  public Iterator<E> iterator() {
    return new itr();
  }

  private class Itr implements Iterator<E> {
    int expectedModCount = modCount;

    public E next() {
      checkForComodification();
      ...
    }

    final void checkForComodification() {
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
    ...
  }
  ...
}

The consequence is: We cannot make any change to the data structure inside the iteration loop. The expiration and deletion do not work this way, other solutions are needed for such tasks. A solution without a loop could look like this:

names.removeIf( ""::equals );

removeIf(…​) expects a predicate, and this very nice and compact method reference implements just such a predicate, testing whether the incoming object is equals(…​)-equal to the empty string.

1.9.13. Search elements with the iterator and find Covid Cough

We get an initialized Iterator and can only move left or right, not jump absolutely; restricted like a human. It is not easy to choose a right strategy, because we could go by probabilities here or try to reduce the maximum cost.

Strategy 1: Suppose we have 100 ships, and Bonny Brain is standing next to the 90th ship. That is, there are 90 ships in one direction, and the probability that the one we are looking for is there is 90%. Still, there is a 10% chance that the person we are looking for is not in that area, and then Bonny Brain would have to walk all the way back over the list to look at the rest afterwards. So, in the worst case, 90 + 90 + 10 = 190 ships would have to be visited.

Strategy 2: Bonny Brain knows if there are more ships on the left or right. The second strategy is to run the side with fewer ships first, then reduce the overall worst-case cost. For the 100 ship example, where Bonny Brain is on ship 90, this means 10 + 10 + 90 = 110 visits maximum.

The proposed solution implements strategy 2:

com/tutego/exercise/util/FindCovidCough.java
if ( iterator.nextIndex() >= NUMBER_OF_SHIPS / 2 ) {
  if ( searchRight( iterator ) )
    System.out.println( "-> at ship " + iterator.previousIndex() );
  else if ( searchLeft( iterator ) )
    System.out.println( "-> <- at ship " + iterator.nextIndex() );
  else
    System.out.println( "Not found" );
}
else {
  if ( searchLeft( iterator ) )
    System.out.println( "<- at ship " + iterator.nextIndex() );
  else if ( searchRight( iterator ) )
    System.out.println( "<- -> at ship " + iterator.previousIndex() );
  else
    System.out.println( "Not found" );
}

The Iterator method nextIndex() returns the absolute position, we use it to compare whether Bonny Brain is in the right or left half. Our own method searchRight(…​) uses the Iterator to first completely search the right side and returns true, if the person was found. If the method returns false, we have not found the searched person in the right half, but we have to run back from there and go all the way to the left. The search direction is indicated by the arrows in the output. If we reached the left side and searchLeft(…​) returns the result false, then the searched person did not exist in the list at all! The second major else branch tests the other case, that Captain CiaoCiao is on the left side relative to the center and first runs entirely to the left.

searchRight(Iterator<Ship>) and searchLeft(ListIterator<Ship>) are implemented like this:

com/tutego/exercise/util/FindCovidCough.java
static final String COVID_COUGH = "Covid Cough";

private static boolean searchRight( Iterator<Ship> iterator ) {
  while ( iterator.hasNext() )
    if ( iterator.next().contains( COVID_COUGH ) )
      return true;
  return false;
}

private static boolean searchLeft( ListIterator<Ship> iterator ) {
  while ( iterator.hasPrevious() )
    if ( iterator.previous().contains( COVID_COUGH ) )
      return true;
  return false;
}

The method to search to the right does not need a ListIterator, because the normal Iterator provides the two methods hasNext() and next() to traverse to the right and extract the next element. The method searchLeft(…​) needs a ListIterator because we have to walk to the left with the methods hasPrevious() and previous(). A normal Iterator can not run to the left or to the right arbitrarily. Only with the ListIterator we have the possibility to run multiple times over the data structure.

1.9.14. Move elements, play musical chairs

com/tutego/exercise/util/MusicalChairsGame.java
class MusicalChairs {

  private final List<String> names;

  public MusicalChairs( String... names ) {
    if ( names.length == 0 )
      throw new IllegalArgumentException( "no names are given, but names must not be empty" );
    this.names = new ArrayList<>( Arrays.asList( names ) );
  }

  public void rotate( int distance ) {
    Collections.rotate( names, distance );
  }

  public void rotateAndRemoveLast( int distance ) {
    if ( names.isEmpty() )
      throw new IllegalStateException( "names is empty, no names to remove" );

    rotate( distance );
    names.remove( names.size() - 1 );
  }

  public String play() {
    if ( names.isEmpty() )
      throw new IllegalStateException( "names is empty, no names to play with" );

    while ( names.size() > 1 ) {
      rotateAndRemoveLast( ThreadLocalRandom.current().nextInt() );
      System.out.println( names );
    }

    return names.get( 0 );
  }

  @Override public String toString() {
    return String.join( ", ", names );
  }
}

The class MusicalChairs has an object variable of type List, which contains the names. Although a vararg array is passed in the constructor, we are more flexible with lists if we want to use the rotate(…​) method of the Collections class later. The constructor converts the array in a list and checks beforehand if the array contains any elements at all — otherwise the constructor throws an exception. If the constructor was called with null, there is the usual NullPointerException.

About the three methods:

  • Our rotate(…​) method makes use of the Collections rotate(…​) method. This method works in place, so it modifies the list. Our list is internal and not accessible from outside.

  • rotateAndRemoveLast(…​) first performs the rotation and then deletes the last list element. But there is a possible error to report: If the game is played with multiple rounds, calling rotateAndRemoveLast(…​) repeatedly may cause the list to become empty. This case is checked by the first if statement and throws an exception if the list is empty. If there is more than one element, we rotate the list and delete the last element from the list. An ArrayList has no dedicated method to delete the last element. If instead of ArrayList we would take a LinkedList, then there would be a method removeLast() from the interface Deque.

  • The method play() is executing the game. Again it must be true that the list must not be empty. The while loop executes the body until the number of elements in the list becomes 1. If there is more than one name in the list, the list is rotated and printed. After the loop passes, the list contains exactly one element. We fall back to the first element. Again, a List does not provide a special method to grab the first element. The situation is different for data structures that implement the Queue interface: Here there is the remove() method.

  • The toString() method falls back on the static method String.join(…​), because this is the easiest way to create a comma-separated string with the elements.

1.9.15. Programming a question game with planets

com/tutego/exercise/util/PlanetQuiz.java
List<Planet> shuffledPlanets = new ArrayList<>( Arrays.asList( Planet.values() ) );
Collections.shuffle( shuffledPlanets );

for ( Planet question : shuffledPlanets ) {
  System.out.printf( "What is the diameter of planet %s (in km)?%n",
                     question.name );

  List<Planet> misleadingPlanets = new ArrayList<>( Arrays.asList( Planet.values() ) );
  misleadingPlanets.remove( question );
  Collections.shuffle( misleadingPlanets );

  List<Planet> choicePlanets = misleadingPlanets.subList( 0, 3 );
  choicePlanets.add( question );
  Collections.shuffle( choicePlanets );
  choicePlanets.forEach(
      planet -> System.out.println( planet.diameter + " km" )
  );
  if ( new Scanner( System.in ).nextInt() != question.diameter )
    System.out.printf( "Wrong! The diameter of %s is %d km.%n%n",
                       question.name, question.diameter );
  else
    System.out.printf( "Correct!%n%n" );
}

The proposed solution proceeds in several phases. In the first phase a new List is built and then shuffled with the shuffle(..) method. Now we can run over these shuffled planets with the extended for loop and ask a question for each of these planets that needs to be answered.

The next step is to select three random planets to the known planet. It is important to keep in mind that the random selection does not include the queried planet again. Therefore we build another list, remove the answer of the question (it is very convenient that the enumeration elements implement the equals(Object) method), randomize this list, select three planets from this list, append the answer to the list and randomize this list again. This guarantees that the answer is not always in the same position and that the three alternative answers are different.

What remains is the output on the screen and the query. If the planetary diameter is not correct, the solution is displayed.

1.9.16. Form subsets, find common elements

In the task, we are looking for the intersection set that cannot be formed directly with a single operation. There is no method in Collections or in Set or the implementation classes that returns a set with the elements from both sets. We therefore choose a workaround.

com/tutego/exercise/util/DatingCompatibility.java
Set<String> me = new HashSet<>();
Collections.addAll( me, "Candy making", "Camping", "Billiards",
  "Fishkeeping", "Eating", "Action figures", "Birdwatching", "Axe throwing" );
Set<String> she = new HashSet<>();
Collections.addAll( she, "Axe throwing", "Candy making", "Camping",
  "Action figures", "Casemodding", "Skiing", "Satellite watching" );

Set<String> smallerSet, largerSet;
if ( me.size() < she.size() ) {
  smallerSet = me; largerSet = she;
} else {
  smallerSet = she; largerSet = me;
}

Set<String> intersection = new HashSet<>( smallerSet );
intersection.retainAll( largerSet );
System.out.println( intersection );

ObjIntConsumer<String> print = ( format, size ) ->
  System.out.printf( format, (intersection.size() * 100) / size );

print.accept( "List 'me' matches list 'she' by %d%%.%n", me.size() );
print.accept( "List 'she' matches list 'me' by %d%%.%n", she.size() );

In the first step, we build a copy of one of the two sets. It does not matter which set we copy for its functionality; we take the smaller set for a reason we will look at in a moment. The reason for the copy is that the following method modifies the set, and we definitely don’t want to modify the incoming sets; possibly the sets passed into the method are also immutable, meaning exceptions would occur.

After building the copy, we call the Set method boolean retainAll(Collection<?>). It modifies the object on which the method is called, leaving only those elements in its own set that are also present in the passed collection. This is effectively forming an intersection. Two things are interesting about the signature:

  1. The parameter is not a set, but an arbitrary Collection. That is, we could also pass a list. If there are also elements in the list more than once, it wouldn`t matter.

  2. Moreover, in retainAll(Collection<?>) the <?> is interesting that the type of the collection passed is irrelevant. Internally, the objects are compared using equals(…​).

The implementation of retainAll(…​) is simple:

from the OpenJDK implementation of java.util.AbstractCollection.
public boolean retainAll( Collection<?> c ) {
 Objects.requireNonNull( c );
 boolean modified = false;
 Iterator<E> it = iterator();
 while ( it.hasNext() ) {
   if ( !c.contains( it.next() ) ) {
     it.remove();
     modified = true;
   }
 }
 return modified;
}

The default implementation walks the own set with an Iterator and checks with contains(…​) whether the element occurs in the passed collection. If so, the element is removed via the Iterator. If the passed Collection is a list, then the contains(…​) method is on average more expensive than if the query is on a TreeSet or HashSet.

Knowing this, we come back to the fact that we copied the smaller of the two sets. This has two consequences:

  1. First, copying small data structures is faster and more memory efficient than copying large collections.

  2. Second, the OpenJDK implementation of retainAll(…​) shows us that the iterator runs over its own set, meaning that if its own set is smaller, fewer elements are visited. One can counter that it is always necessary to test against a larger (or equally large) set, but if fewer queries are made overall, it is faster on average.

After forming the intersection, we set the size of the intersection with the number of hobbies the two people have, in correlation. If the two people have a different number of hobbies, the percentage match is not equal; it would be only if both partners specify an equal number of hobbies. The program output in our example is:

[Candy making, Axe throwing, Camping, Action figures]
List 'me' matches list 'she' by 50%.
List 'she' matches list 'me' by 57%.

1.9.17. Quiz: Great Swords

The output is

true false [Khanda]

There is no exception to this.

There are two possibilities for orderings in Java: Either objects can compare among themselves, in which case classes implement the Comparable interface, or a Comparator is looking at two objects and decides what the order between the two objects is. In our example, the class implements the Comparable interface for a natural order, but the compareTo(…​) method returns constant 0. The implication would be that all objects would then be the same, no matter what their name state. The assigned names are not included in the compare method at all.

When inserting elements into a Set, an element is only included if there is not already an equivalent element in the set. Usually the data structures access the equals(…​) method. TreeSet, which is a sorted set, is an exception because the implementation does not need the equals(…​) method and can use compareTo(…​) to read whether two objects are equivalent. Whether therefore a separate equals(…​) method is implemented or throws an exception does not matter, because equals(…​) is not called in the scenario.

The main(…​) method outputs three things: twice the results of the add(…​) method, and then the contents of the set via the toString() ` representation. The `add(…​) method of the set returns a boolean value whether an element has been added to the set. In the first case a string is added, so the return is true. On the second call to the add(…​) method, the TreeSet recognizes that, according to Comparable, the second string is equivalent to an already existing element of the set. Equal elements are not overwritten and replaced, but the element is discarded. Since nothing is added, the add(…​) method returns false. In the toString() representation of the set, only the first inserted element appears.

1.9.18. Remove duplicate elements from arrays

com/tutego/exercise/util/UniqueArrayElements.java
public static double[] unique( double... values ) {

  if ( values.length < 2 )
    return values;

  Set<Double> valuesSet = new LinkedHashSet<>( values.length / 4 );

  for ( double value : values )
    valuesSet.add( value );

  if ( valuesSet.size() == values.length )
    return values;

  double[] result = new double[ valuesSet.size() ];
  int i = 0;
  for ( Double value : valuesSet )
    result[ i++ ] = value;

  return result;
}

The solution can be well implemented using the LinkedHashSet data structure. A LinkedHashSet has the advantage that on the one hand the order of the inserted elements is preserved and on the other hand the data structure is still a set and contains the elements only once. The solution is a few lines longer due to some special checks, but these optimizations are not wrong.

In the first step, the method tests if there is no element or only one element in the array. If so, we return the array directly. By accessing the length attribute, we also get a check for null for free, because if null is passed, there will be the expected NullPointerException.

If there are more than two elements, there could be duplicates. Only now an instance of LinkedHashSet has to be created. The size estimation is difficult, because we don`t know if many elements are duplicates or not; therefore a quarter of the initial size might be too much or too little, practical tests have to show.

In the following step, the extended for loop iterates the primitive array and puts each value into the data structure. Boxing takes place, that is, the primitive values of type double are packed into the wrapper objects of type Double. Unlike integer values, Double does not perform any optimization on valueOf(…​) and does not utilize a cache. Therefore there are always as many wrapper objects as there are elements in the array.

After filling the LinkedHashSet our method compares the size of the data structure with the size of the array, and if both have the same number of elements, all elements were different. In that case we can directly return the array and forget about the data structure.

If there are fewer elements in the data structure than in the array, we have to build a small array that contains the same number of elements as the set. This time, an extended for loop runs over the data structure, which the Java compiler automatically implements by using an Iterator and calls to hasNext() and next(). The Iterator of a LinkedHashSet object takes into account the order of the inserted elements. The Double objects supplied by the Iterator are unpacked by unboxing and placed one after the other in the array as a double entry.

1.9.19. Get all words contained in a word

com/tutego/exercise/util/WordSequence.java
private static final int MIN_WORD_LENGTH = 3;

private static Collection<String> substrings( String string ) {
  Collection<String> result = new ArrayList<>(
      (int)(string.length() * (string.length() - 3L) / 2 + 1)
  );
  for ( int startIndex = 0; startIndex < string.length(); startIndex++ )
    for ( int len = MIN_WORD_LENGTH;
          len <= string.length() - startIndex;
          len++ )
      result.add( string.substring( startIndex, startIndex + len ) );

  return result;
}

public static Collection<String> wordList( String string,
                                           Collection<String> words ) {
  Collection<String> result = new ArrayList<>();

  for ( String substring : substrings( string.toLowerCase() ) )
    if ( words.contains( substring ) )
      result.add( substring );

  return result;
}

Before we implement the wordList(…​) method with dictionary access, we want to implement another method: substrings(String). The method returns a collection of all possible substrings. In essence, the method consists of two nested loops. The outer loop specifies the starting position, the inner loop generates all lengths starting from at least three characters, up to the maximum string length. The minimum size is determined by a constant, so it can be easily changed.

The results are built up in an internal list. The size of the list can be calculated. The strange type conversion has the reason that we blow up the value range when multiplying two large int values. The subtraction with 3L forces a conversion to long, and later the explicit type conversion changes the long back to an int.

Via the String method substring(…​) a partial string is formed and added to the result set. As data structure we choose an ArrayList, because it is very space-saving and will be run sequentially from front to back later. In addition, we can determine the number of elements to be expected in advance, so that at runtime the internal array does not have to be enlarged.

The implementation of wordList(…​) is short with the prework. Again, an ArrayList is built as container and return, and in the loop a word is placed in this container exactly when the word occurs in the passed dictionary.

1.9.20. Exclude duplicate elements with a UniqueIterator

The new iterator is a decorator around an existing iterator from which the actual data originates. However, since the original iterator can repeatedly provide elements that have already been passed to us, we need to remember if elements have occurred before. For this task a set is optimal. A data structure like a HashSet answers very quickly the question whether an element occurs in the set or not. So in principle we have to proceed in the solution in such a way that if we obtain an element in the new iterator, we have to ask the internal iterator in the background until a new element is delivered. This would be relatively simple in itself, but we must not forget the implementation of the hasNext() method. Therefore, we need to set up the implementation a little differently, and that’s what this approach shows.

com/tutego/exercise/util/UniqueIteratorDemo.java
class UniqueIterator<E> implements Iterator<E> {

  private final Iterator<? extends E> iterator;
  private final Set<E> hasSeenSet = new HashSet<>();
  private E next;

  public UniqueIterator( Iterator<? extends E> iterator ) {
    this.iterator = iterator;
    next = lookahead();
  }

  private E lookahead() {
    while ( iterator.hasNext() ) {
      E next = iterator.next();
      if ( ! hasSeenSet.contains( next ) )
        return next;
    }
    return null;
  }

  @Override
  public boolean hasNext() {
    return next != null;
  }

  @Override
  public E next() {
    E result = next;
    hasSeenSet.add( result );
    next = lookahead();
    return result;
  }
}

The constructor of the class takes the original Iterator and stores the reference in an internal object variable. In addition, there are two other object variables: one for the set of elements already seen, the other referencing the next element. next will be null if the original iterator cannot supply any more elements. The constructor has a second task, to reference the first element. The focus here is on the lookahead() method.

The method lookahead() reaches to the original Iterator and polls until there is an element that was not yet in the set of already seen elements. If the Iterator cannot return any more elements, the new UniqueIterator cannot return any elements either, and the method returns null. If the internal Iterator finds an element that does not yet occur in the set, lookahead() returns this element.

Let us summarize: When the constructor is called, the first element is queried immediately via the internal iterator and stored in the variable next. If next is equal to null, then there was no element in the underlying Iterator.

For an Iterator two methods have to be overridden:

  1. The implementation of hasNext() is accordingly simple: if next is not equal to null, then there is an element. The update is done by next().

  2. With the method next() we first note the assignment of next in an intermediate variable result. If the method next() is called from outside, then the result must be included in the set of elements already seen, so that it is considered known for the next time. The object variable next is updated with the lookahead() method for the next call to the Iterator methods. There may be a next element — in which case next will be non-zero — or there may be no element and next will be null. After updating the variable next, result will contain the previous value returned by the next() method.

So much for the algorithm. Iterators, like many other data types, are generic types. We also use this possibility. The class UniqueIterator has a type parameter E, which is inherited from the interface Iterator. This can be seen in the next() method, which returns something of type E. This type variable becomes interesting in the constructor, which assumes an Iterator<? extends E>, thus not only expecting an Iterator<E>, but allowing more possibilities. <? extends E> expresses that the original iterator may contain subtypes of E. In other words: For example, if we declare a UniqueIterator with a type argument Object, then the internal underlying Iterator can return String, for example, because String extends Object.

1.9.21. Convert two-dimensional arrays to map

com/tutego/exercise/util/ConvertToMap.java
public static Map<String, String> convertToMap( String[][] array ) {

  if ( array.length == 0 )
    return Collections.emptyMap();

  if ( array.length == 1 )
    return Collections.singletonMap( Objects.requireNonNull( array[ 0 ][ 0 ] ),
                                     Objects.requireNonNull( array[ 0 ][ 0 ] ) );

  Map<String, String> result = new HashMap<>( Math.max( array.length, 16 ) );

  for ( String[] row : array )
    result.put( Objects.requireNonNull( row[ 0 ] ),
                Objects.requireNonNull( row[ 1 ] ) );

  return result;
}

Multidimensional arrays in Java are nothing more than arrays that reference other arrays. In a two-dimensional array, we have one main array, descriptive for the column, which references many small arrays for the rows.

Two peculiarities show up in the program code:

  1. the optimization for empty arrays and arrays with only one key-value pair

  2. the check for `null

Arrays are objects in Java, so references come into play, which can be null. The first query on the length of the main array will throw a NullPointerException if null was passed to the method. If the row arrays do not exist and are null, access via array[index] will also throw a NullPointerException. Later calls to Objects.requireNonNull(…​) will test at the element level to make sure they are not null, and otherwise the method will throw an exception.

Associative stores have a much larger memory footprint than, say, an array. For two special cases we can reduce the memory requirement significantly, namely when a Map contains no elements and when a Map contains only one key-value pair. The Collections class provides two special methods for building empty associative stores and those with only one pair: the emptyMap() and singletonMap(…​) methods.

Only when there is more than one element a HashMap is built; the capacity is pre-initialized with the number of rows of the array, but at least with 16. But what is the capacity? The capacity is a kind of buffer. A HashMap has a DEFAULT_LOAD_FACTOR that defaults to 75%; if new elements are added and the associative memory has reached 75% capacity, a so-called rehashing is performed. The HashMap is enlarged, all elements are reclassified. Of course, one wants to reduce this cost. If we give the initial capacity for 16 elements, the HashMap can directly hold 12 elements without rehashing. Knowing this, we could also work with array.length / 0.75 + 1 and thus calculate the optimal size, but suppose we have a very large array, then multiplying by 1.3 leads to an overflow, the number becomes negative, and then there is an exception in the HashMap constructor. These are already very extreme special cases, but if we want to be outstanding software developers, we have to pay attention to such things. (Rehashing at Hash-Table

We can use a HashMap because the task says that equals(…​) and hashCode() are implemented. We would have a problem if the two methods were not implemented correctly, where the probability would be high that all entries of the array would be included in the associative memory anyway, because if equals(…​) and hashCode() were not overridden, from the superclass Object each non-identical object would also not be equivalent to another object, and the hash code would most likely always be different, so that the objects would have no connection to each other.

So if the array contains more than one element, a HashMap is built, the array is expired, and the key-value pairs are added to the associative store.

There is a subtle difference in the return: for no or one element, the return is an immutable associative store. For more than two entries, we get back a mutable data structure.

1.9.22. Convert text to Morse code and vice versa

com/tutego/exercise/util/MorseDemo.java
class Morse {
  private final Map<Character, String> charToMorse = new HashMap<>();
  private final Map<String, Character> morseToChar = new HashMap<>();

  Morse() {
    String encoded = "a.- b-... c-.- d-.. e. f..-. g--. h.... i.. j.--- k-. " +
                     "l.-.. m-- n-. o--- p.--. q--.- r.-. s... t- u..- v...- " +
                     "w.-- x-..- y-.-- z--.. 1.---- 2..--- 3...-- 4....- " +
                     "5..... 6-.... 7--... 8---.. 9----. 0-----";
    for ( String token : encoded.split( " " ) ) {
      charToMorse.put( token.charAt( 0 ),    token.substring( 1 ) );
      morseToChar.put( token.substring( 1 ), token.charAt( 0 ) );
    }
  }

  public String encode( String string ) {
    StringJoiner result = new StringJoiner( " " );
    for ( int i = 0; i < string.length(); i++ ) {
      char c = string.charAt( i );
      if ( c == ' ' )
        result.add( "" );
      else {
        String maybeMorse = charToMorse.get( Character.toLowerCase( c ) );
        if ( maybeMorse != null )
          result.add( maybeMorse );
      }
    }
    return result.toString();
  }

  public String decode( String string ) {
    StringBuilder result = new StringBuilder( string.length() / 4 );
    for ( String word : string.split( " {2}" ) ) {
      for ( String character : word.split( " " ) )
        Optional.of( character )
                .map( morseToChar::get )
                .ifPresent( result::append );
      result.append( ' ' );
    }
    return result.toString();
  }
}

For the mapping of the letters to the Morse code we use an associative memory of type HashMap. There is no need to sort the keys, so we don`t need a TreeMap. Since we would like to have a conversion in two directions, we use two maps. The first Map, charToMorse, associates the character with the Morse code, the second Map, morseToChar, associates the Morse code with the character. To build the Map, we could write lines like.

charToMorse.put( 'a', ".-" );
morseToChar.put( ".-", 'a' );
charToMorse.put( 'b', "-..." );
morseToChar.put( "-...", 'b' );

But is too much work. The next shortcut would be to just build one Map via the factory method

charToMorse = Map.of( Map.entry( 'a', ".-" ), Map.entry( 'b', "-..." ), ... );

and then later derive the second Map charToMorse from it:

charToMorse.forEach(
    (character, string) -> morseToChar.put(string, character ) );

The proposed solution uses another way, an encoding that a string consists of space-separated pairs, where in the pair the first symbol stands for the key and the sequence after it the Morse code characters.

The method encode(String) loops the string and converts it to Morse code. The result is built dynamically, which is actually a typical task of StringBuilder, but here a StringJoiner is used. This class is useful because on the one hand it is a dynamic data structure for strings, and on the other hand because it produces a result in which the individual substrings can be separated by a user-defined separator, in our case a space.

A simple for loop visits each character. If the character is a space, we put a space string in the StringJoiner, resulting in two spaces in the output. Why? Because " " + "" + " " just gives " ​​". If no space is considered, we convert the character to a lowercase letter and then query the associative memory charToMorse. The get(…​) method returns null if there is no corresponding Morse code for the character. In that case there is nothing to do. Otherwise we pass the Morse code to the StringJoiner.

The method decode(String) goes the opposite way. We get a long string of Morse code sequences that must be converted back to the original text. The result of the method is a string that is built dynamically using StringBuilder. We initialize it with a capacity and estimate how large the result will be; we estimate that it will be a quarter of the original size of the input string.

The Morse words are separated by two spaces, so the first thing we want to do is query the words. split(" {2}") will give us all the words; of course, a string with two spaces will also work, but it wouldn’t be as visible in the code. The split(…​) method directly returns an array, which is fine for small results; for indeterminately large results it makes sense to work via an iterator, for example via

new Scanner( string ).useDelimiter( " {2}" ).forEachRemaining( word -> ... )

Alternatively, tokens can be run directly using the hasNext() and next() methods, something like this:

for ( Scanner words = new Scanner( string ).useDelimiter( " {2}" ); scanner.hasNext(); ) {
  String word = words.next();
  ...
}

The letters and digits converted to Morse code are separated by spaces. Again we resort to split(…​), although a Scanner or StringTokenizer would also help. The extracted substring is used to query the second data structure morseToChar. The symbol string might not exist and get(…​) on the Map morseToChar would then return null. With Optional we can very well express this cascade:

  1. Build an Optional with the token, that will never be null.

  2. Map the token to the entry from morseToChar. If the Map has no associated value, the Optional will be empty.

  3. Append the associated value to the StringBuilder if there was an association.

Of course, encode(…​) can also be used to insert an optional, the proposed solution just plays a bit with the alternatives.

Finally we convert the StringBuilder to a String and return the result.

1.9.23. Remember word frequency with associative memory

com/tutego/exercise/util/ImportantGossip.java
public static final int LIMIT = 5;

public static List<String> importantGossip( String... words ) {

  Map<String, Integer> wordOccurrences = new HashMap<>( words.length );
  for ( String word : words )
    wordOccurrences.merge( word, 1, Integer::sum );

  Comparator<Map.Entry<String, Integer>> compareByWordOccurrence =
      Comparator.comparingInt(
          (ToIntFunction<Map.Entry<String, Integer>>) Map.Entry::getValue )
                .reversed()
                .thenComparing( Map.Entry::getKey );

  SortedSet<Map.Entry<String, Integer>> sortedSet =
      new TreeSet<>( compareByWordOccurrence );
  sortedSet.addAll( wordOccurrences.entrySet() );

  List<String> result = new ArrayList<>( LIMIT );
  for ( Map.Entry<String, Integer> element : sortedSet ) {
    result.add( element.getKey() );
    if ( result.size() >= LIMIT )
      break;
  }

  return result;
}

The proposed solution proceeds in three steps: First, we want to count the frequency for all words in the text. In the second step we sort by frequency. In the third step, the first five elements of the sorted data structure are taken and prepared for return.

To remember frequencies, we resort to an associative memory that associates a string with an integer, the frequency. With a loop we go over all words and put them into the Map. In doing so, we can fall back on a handy method from Java 8, the merge(…​) method:

default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction).

It can be used either to set an initial value for new keys (1 in our case) or to call a function for existing keys that combines the old value with the new value (1 again in our case) and then writes it back.

After running the loop, wordOccurrences stores each word and its frequency. An associative store can come in two different flavors: as a HashMap or as a TreeMap. No matter which we use, the keys are in the focus, the associated values are secondary. In our case, however, the associated values are important for the solution. Each Map provides a method we can use to read the key-value pairs together: entrySet(). The result is a set of Map.Entry objects. We can take these Map.Entry objects into a new data structure and then sort them by the frequency we get from the Map.Entry with getValue().

The proposed solution employs a TreeSet that is populated with the Map.Entry objects from wordOccurrences. TreeSet is a sorted set, and we need an ordering criteria. The order of the Map.Entry objects is determined by a Comparator compareByWordOccurrence. This must take the frequency of the Map.Entry object as the first criteria, and if the frequency is the same, the lexicographic order of the words should be taken into account as a comparison. The Comparator can be easily built using the static and default methods, it starts with Comparator.comparingInt(…​) to take the frequency, and since words with a large frequency must be in front and less frequent words in the back, we must reverse the default order, this is done by reversed(). If a frequency occurs twice, we use thenComparing(…​) to insert the second Comparator, which uses the order of the words as a second criterion.

The TreeSet is built with the Comparator compareByWordOccurrence, and all Map.Entry objects go into the sorted set — the TreeSet will automatically sort them by frequency when adding them. Now all we need to do from the sorted set is to read the first five elements. We do this with an Iterator. This is used indirectly by the extended for loop that we start using to run the set. Each element is put into our return, the ArrayList. If the ArrayList is five elements large, we break the loop, and the ArrayList is returned at the end. If there were less than five words in the word list, the loop will terminate before, and not by a controll statement. Then there are less than five elements in the ArrayList.

1.9.24. Read in and read out colors

com/tutego/exercise/util/ColorNames.java
public class ColorNames {
  public static class Color {
    private final String name;
    private final int rgb;

    private Color( String name, String rgb ) {
      this.name = Objects.requireNonNull( name );
      this.rgb  = decodeHexRgb( rgb );
    }

    public static int decodeHexRgb( String hexRgb ) {
      if ( ! hexRgb.startsWith( "#" ) )
        throw new IllegalArgumentException( "hex does not start with #" );
      if ( hexRgb.length() != 4 && hexRgb.length() != 7 )
        throw new IllegalArgumentException(
            hexRgb + " is not neither 4 (#RGB) nor 7 symbols (#RRGGBB) long" );


      if ( hexRgb.length() == 4 )
        hexRgb = "#" + hexRgb.charAt( 1 ) + hexRgb.charAt( 1 )
                     + hexRgb.charAt( 2 ) + hexRgb.charAt( 2 )
                     + hexRgb.charAt( 3 ) + hexRgb.charAt( 3 );
      return Integer.decode( hexRgb );
    }

    @Override public String toString() {
      return String.format( "'%s' is RGB #%06X", name, rgb );
    }
  }

  private final HashMap<Integer, Color> colorMap = new HashMap<>();

  public ColorNames( String filename ) throws IOException {
    for ( String line : Files.readAllLines( Paths.get( filename ) ) ) {
      String[] tokens = line.split( "([\",])+" );
      Color color = new Color( tokens[ 1 ], tokens[ 2 ] );
      colorMap.put( color.rgb, color );
    }
  }

  public Optional<Color> decode( int rgb ) {
    return Optional.ofNullable( colorMap.get( rgb ) );
  }
}

In the suggested solution, the Color class is included as a nested static class in ColorNames. This dependency makes sense, because Color objects are only relevant in the context of ColorNames. The Color object has the desired object variables for the name and RGB value, and provides a constructor that takes the name and RGB value. The object variables are private, and so is the constructor — the outer class can still use the private constructor, a feature of Java visibility. The constructor takes the RGB value as a string, which means it must be recoded. For this, the Color class declares its own method. If the constructor was not private, we could have used a record instead of a class.

int decodeHexRgb(String) first checks the validity of the string. If it does not start with a #, the specification is false. Also, if the string is not either 4 or 7 characters long, that is an error, and an IllegalArgumentException follows. While the RGB values in the file are correct, this public method is for everyone to use, and incorrect strings should be noticed. If the string contains only four symbols, then it is the shorthand notation, and the red, green, blue values are doubled. For the doubling we resort to a simple concatenation that is easy to read. There are also other possibilities, for example with an argument index in the formatting string; one solution would be

"#%1$s%1$s%2$s%2$s%3$s%3$s".formatted(
    hexRgb.charAt( 1 ), hexRgb.charAt( 2 ), hexRgb.charAt( 3 ) );

Since Formatter also knows relative indexing, it could also read:

"#%1$s%<s%2$s%<s%3$s%<s".formatted( ... );

It should be obvious that simple concatenation is the best readable. Integer.decode(…​) then returns the corresponding RGB value as an integer.

Also ColorNames has a constructor, and this one takes the file name. Files.readAllLines(…​) reads all lines of the file, and the extended for loop traverses them line by line. Each line is tokenized as a string with the split(…​) method, and we access the second and third elements in the array — that is, index 1 and 2 — and fill the constructor with them. We put the resulting Color object into the Map, where the RGB value as an integer is the key for the Color object associated with it.

The remaining method decode(String) queries the Map, and this may return null if there is no association between the RGB value and a color. Since we want to avoid null as a return value, Optional.ofNullable(…​) makes unknown RGB values become Optional.empty().

1.9.25. Read in names and manage lengths

com/tutego/exercise/util/FamilyNamesByLength.java
SortedMap<Integer, List<String>> namesByLength = new TreeMap<>();

InputStream resource = FamilyNamesByLength.class.getResourceAsStream( "family-names.txt" );
try ( Scanner scanner = new Scanner( resource ) ) {
  while ( scanner.hasNextLine() ) {
    String name = scanner.nextLine();
    namesByLength.computeIfAbsent( name.length(), __ -> new ArrayList<>() )
                 .add( name );
  }
}

namesByLength.forEach(
    (len, names) -> System.out.println( len + " " + names )
);

for ( int len; (len = new Scanner( System.in ).nextInt()) > 0; ) {
  int finalLen = len;
  Optional.ofNullable( namesByLength.get( len ) )
          .ifPresentOrElse(
              System.out::println,
              () -> System.out.printf( "No words of length %d%n",
                                       finalLen ) );
}

The type SortedMap<Integer, List<String>> represents the association of an integer with a list. Before the strings can be added to the list, the list must be created. A program must proceed as follows:

  1. It must check if there is already a list for the length, if so, the string can be appended;

  2. If there is no entry in the Map for the length yet, a list must be associated with the length and the first word with the length must be added to this list.

In code, this can be expressed as follows:

if ( ! namesByLength.containsKey( line.length() ) )
  namesByLength.put( line.length(), new ArrayList<>() );

namesByLength.get( line.length() ).add( line );

It tests containsKey(…​) if a list already exists for the string length, and if not, creates a new ArrayList for that string length. Adding it with put(…​) in the next statement will always succeed, since there is guaranteed to be a list for a length.

Since Java 8 we don`t have to write this out by hand, but can use the default method computeIfAbsent(…​). The description is a bit complicated, easier is to understand the method at the source code:

From the OpenJDK implementation of java.util.Map.
default V computeIfAbsent( K key,
                           Function<? super K, ? extends V> mappingFunction ) {
  Objects.requireNonNull( mappingFunction );
  V v;
  if ( (v = get( key )) == null ) {
    V newValue;
    if ( (newValue = mappingFunction.apply( key )) != null ) {
      put( key, newValue );
      return newValue;
    }
  }

  return v;
}

First, the get(…​) method is called, and there are two outputs:

  1. If the value is not null, it is returned directly. For our case, this means that a list for the string length has already been built.

  2. get(…​) returns null for the case that there was no association. (We ignore the case where there might be null associated with a key). If there is no associated value, the passed function is called with the key. The function returns a value, and under the key the value is stored, at least if it is not null. In our case, the function creates a new ArrayList, and the name of the key is unnecessary for this. Therefore, the program hides this identifier with two underscores . Question for readers: Instead of → new ArrayList<>(), what is the argument against the constructor reference ArrayList::new, which would also work?[3].

computeIfAbsent(…​) returns the list at the end in any case, and we can cascade add(…​).

After the program has read the file line by line and filled the data structure, the Map method forEach(BiConsumer) traverses all entries. Our BiConsumer gets the key and value and outputs the pairs to the screen.

The last part of the program is in a loop that terminates only if the input is 0 or negative. The program asks for an integer for the word length. Then get(…​) asks for the list, but the result could be null if there is no list for the input. Optional.ofNullable(…​) can wrap a possible null well into an Optional, because if there is no associated value to the key, Optional.isEmpty() is true. ifPresentOrElse(…​) is like a controll statement: if the Optional contains a value, our Consumer prints the list of names; if there is no associated value, a notice follows on the screen that no word of the desired length exists. The trick with the assignment int finalLen = len; is necessary because lambda expressions can only access final variables, but the counter len changes. The copy into an intermediate variable solves the problem.

1.9.26. Find missing characters

The solution consists of two parts: First, we build a data structure that is optimal for us, and in the next step we query the data structure.

com/tutego/exercise/util/FindMissingLetters.java
List<String> words = Arrays.asList( "house", "mouse", "horn", "cannon" );

Map<String, List<String>> map = new HashMap<>();

// Initialize the map
for ( String word : words ) {
  for ( int index = 0; index < word.length(); index++ )
    map.computeIfAbsent( index + "-" + word.charAt( index ),
                         __ -> new ArrayList<>() ).add( word );
}
System.out.println(map);

The task can be solved with a wide variety of data structures and approaches. The version chosen here does the following: It builds a Map<String, List<String>> in which the position of a letter is associated with a list of words. Let us take house and mouse as an example. Both words have an o at index 1. This association between index and letter is the key of an associative memory. The program shall transform the input house, mouse, horn, cannon into the following map:

{0-m=[mouse], 2-n=[cannon], 1-o=[house, mouse, horn], 3-n=[horn, cannon], 1-a=[cannon], 5-n=[cannon], 4-o=[cannon], 0-c=[cannon], 2-r=[horn], 3-s=[house, mouse], 2-u=[house, mouse], 0-h=[house, horn], 4-e=[house, mouse]}

To build the Map, an outer loop traverses all the words and then an inner loop over each letter of the selected word. The pair from the index, a minus sign and the position are put into the associative memory. Since the associative memory does not directly connect this key with the word, but the strings come into a list, the list must be rebuilt whenever the first word is to be put into the list. For such tasks computeIfAbsent(K key, Function mappingFunction) is perfect; if there is no list associated under the key yet, the mapping function is called and returns a new list which is then associated with the key. The result of the method computeIfAbsent(…​) is the associated value, i.e. our list, where we can add the word.

In the second part we can query the data structure and solve the problem with the unrecognized characters.

com/tutego/exercise/util/FindMissingLetters.java
// Query the data structure
Consumer<String> letterFinder = word -> {
  Set<String> matches = null;
  for ( int index = 0; index < word.length(); index++ ) {
    // Skip unknown chars
    if ( word.charAt( index ) == '_' )
      continue;
    List<String> wordCandidates = map.get( index + "-" + word.charAt( index ) );
    // Exit loop if no known entry
    if ( wordCandidates == null ) {
      // Remove possible previous matches for correct console output
      matches = null;
      break;
    }
    // Build a copy and remove words that don't match with the length
    wordCandidates = new ArrayList<>( wordCandidates );
    wordCandidates.removeIf( s -> s.length() != word.length() );
    // Join matches from all known letters
    if ( matches == null )
      matches = new HashSet<>( wordCandidates );
    else
      matches.retainAll( wordCandidates );
  }
  System.out.println( word + " -> " +
                      (matches == null || matches.isEmpty() ?
                         "No results" : matches) );
};

List<String> missingLettersWords =
    Arrays.asList( "_ouse", "ho__", "ca__on", "gun", "__e__", "_____" );

missingLettersWords.forEach( letterFinder );

The Consumer is a kind of subroutine that gets a word with underscores, then queries the Map data structure and prints the matching words on the screen. The matching words are collected in a set of matches. The algorithm proceeds as follows: Search for all possible words from each character that have the same character at the same position, put them into the set and later form intersections with the added characters at the following positions. At the beginning there could be quite a lot of candidates, which have for example an h at the first position, but later the set becomes smaller and smaller, with words, which have for example additionally an o at the second position.

A large main loop can be identified in the program. It runs the initial word from front to back, and all characters at the position 0, at the position 1 and so on are retrieved. Unknown characters are not helpful in recognition (but we can accept all words), so the program returns to the loop. If the character is not an underscore, we generate a key from the index, minus sign and the character. With this key we query the Map, and in the best case we get a list of candidates. However, there may be no list for this key, that is, there is a character in the source word, but no match; there is no solution, the set of matches becomes null, and we can abort the loop.

Once we have found a list of matching words for the character, the program first creates a copy of the list and in the second step removes all words that do not have the same length as the source word. Now we have to create an intersection between the previous words and the new words under the index, because the result must appear in both sets. If no words have been found before, matches is equal to null, and we build a new set with the current candidates. Only on the first hit, no intersection is built; if there were already results and matches was not null, retainAll(…​) deletes from matches all words that do not also occur in wordCandidates.

At the end of the loop, we have run over all known characters and kept reducing the set of matches. A console output shows us the contents of the set or a message if the set is empty.

1.9.27. Calculate number of paths to the three-headed monkey

The data structure WeakHashMap used for the cache utilizes so-called weak references. There are basically four types of references in Java:

  • Strong references are the usual references we deal with as Java programmers in everyday life. The garbage collector would never clear these references.

  • A WeakReference is a reference that is released when a garbage collector phase is running. It depends on the implementation of the JVM exactly when this is.

  • With a SoftReference the JVM tries to keep the object alive until it is close to an OutOfMemoryError.

  • With a PhantomReference we only get to know that the garbage collector has removed the object.

The WeakHashMap uses a WeakReference internally, so we have nothing to do with handling these references directly and cleaning up the bins. It is a usable data structure that keeps references as long as there is enough free memory, and then releases the objects when the garbage collector needs to make space. For our computation, this is a good choice, because the WeakHashMap is filled when it is needed for the factorial computation — but the factorials do not need to be in memory for an unnecessarily long time and are cleared away again.

The WeakHashMap is a special Map, that means we can use all known methods.

WeakHashMap UML
Figure 3. UML-diagram of WeakHashMap, which implements Map
com/tutego/exercise/util/CachedCatalan.java
private static final Map<BigInteger, BigInteger> factorialCache =
    new WeakHashMap<>();

private static BigInteger factorial( BigInteger n ) {
  BigInteger maybeCachedValue = factorialCache.get( n );

  if ( maybeCachedValue != null )
    return maybeCachedValue;

  // n < 2 ? 1 : n * factorial( n - 1 )
  BigInteger result = isLessThan( n, TWO )
                      ? ONE
                      : n.multiply( factorial( n.subtract( ONE ) ) );

  factorialCache.put( n, result );
  return result;
}

private static boolean isLessThan( BigInteger a, BigInteger b ) {
  return a.compareTo( b ) < 0;
}

public static BigInteger catalan( BigInteger n ) {
  // (2n)! / (n+1)!n!
  BigInteger numerator   = factorial( TWO.multiply( n ) );
  BigInteger denominator = factorial( n.add( ONE ) )
                               .multiply( factorial( n ) );
  return numerator.divide( denominator );
}

factorial(…​) is the method that needs to access the cache. So we first create an object variable factorialCache for the internal cache that can hold BigInteger. The association is a mapping from n to n!; both types are BigInteger.

There are two main steps in using a cache:

  1. When asked for a value, we first ask the cache if the value is contained. If it is in the cache, we are quickly done.

  2. If the value is not in the cache, it is computed and cached. This takes time.

The method factorial(…​) is implemented in the same way. The cache is queried, and maybe there is a result, maybe not. We already know the response behavior of get(…​) method of Map, which returns null if there is no associated value. This is the indicator for us whether we have a value in the cache or not. If the result is not equal to null, we have the BigInteger as a computed factorial in the cache and can return it directly. But if get(…​) returns null, we have to compute the factorial and then put the result in the factorialCache and return it. For comparing whether one BigInteger is larger or smaller than another, there is no special method in BigInteger because BigInteger has a natural ordering, so it implements Comparable. However, the readability with compareTo(…​) is not optimal; therefore, a separate method isLessThan(…​) was introduced. The BigInteger constants ONE and TWO were imported statically, which shortens the code a bit.

An alternative implementation could use computeIfAbsent(…​), but the code presented here is well understood and comprehensible.

The catalan(…​) method performs the documented calculations and accesses factorial(…​) three times. Many entries are already in the cache, so factorial(…​) can serve many responses from the cache.

1.9.28. Manage holidays in a sorted associative store

com/tutego/exercise/util/Holidays.java
NavigableMap<LocalDate, String> dates = new TreeMap<>();
dates.put( LocalDate.of( 2020, Month.JANUARY, 1 ), "Neujahr" );
dates.put( LocalDate.of( 2020, Month.APRIL, 10 ), "Karfreitag" );
dates.put( LocalDate.of( 2020, Month.MAY, 1 ), "Tag der Arbeit" );
dates.put( LocalDate.of( 2020, Month.JUNE, 1 ), "Pfingstmontag" );
dates.put( LocalDate.of( 2020, Month.OCTOBER, 3 ), "Tag der Deutschen Einheit" );
dates.put( LocalDate.of( 2020, Month.NOVEMBER, 1 ), "Allerheiligen" );
dates.put( LocalDate.of( 2020, Month.JULY, 1 ), "Pfingstmontag" );
dates.put( LocalDate.of( 2020, Month.DECEMBER, 25 ), "1. Weihnachtsfeiertag" );
dates.put( LocalDate.of( 2020, Month.DECEMBER, 26 ), "2. Weihnachtsfeiertag" );
dates.put( LocalDate.of( 2021, Month.JANUARY, 1 ), "Neujahr" );
dates.put( LocalDate.of( 2021, Month.APRIL, 20 ), "Karfreitag" );

System.out.println( dates.firstEntry() );
System.out.println( dates.lastEntry() );

LocalDate festiveSeasonStart = LocalDate.of( 2020, Month.DECEMBER, 23 );
LocalDate festiveSeasonEnd   = LocalDate.of( 2021, Month.JANUARY, 6 );

System.out.println( dates.higherEntry( festiveSeasonEnd ) );

SortedMap<LocalDate, String> festiveSeason =
    dates.subMap( festiveSeasonStart, true, festiveSeasonEnd, true );

System.out.printf( "%d Feiertage:%n", festiveSeason.size() );
festiveSeason.forEach(
    (date, name) -> System.out.printf( "%s am %s%n", name, date )
);

festiveSeason.clear();

System.out.println( dates );

The proposed solution uses the described methods firstEntry(), lastEntry(), higherEntry(K) and subMap(K, boolean, K, boolean).

Different methods from the NavigableMap return so-called views. A view is not a copy of the data, but operations on this view always go to the underlying data structure. Thus we can realize the deletion of the subarea via the clear() method on the view. Views are memory efficient and performant, but can lead to errors because you may accidentally modify the underlying data structure, but thought you were working on a copy. And it can lead to a problem if the underlying data structure is immutable, i.e. cannot be modified at all, but elements are inserted into the view, for example.

1.9.29. Quiz: Keys in a HashMap

The output of the program is as follows:

{java.awt.Point[x=2,y=1]=java.awt.Point[x=1,y=2]}
null
java.awt.Point[x=1,y=2]

The inserted key objects must be immutable, otherwise the dynamically computed hashcode will change and the objects will not be found.

1.9.30. Determine commonality: Party set and souvenir

com/tutego/exercise/util/CommonGifts.java
private static void printMultipleGifts( List<Set<String>> families ) {

  class Bag extends HashMap<String, Integer> {
    void add( String key ) { merge( key, 1, Integer::sum ); }
    // int getCount( String key ) { return getOrDefault( key, 0 ); }
  }

  Bag giftsToCounter = new Bag();

  for ( Set<String> gifts : families )
    for ( String gift : gifts )
      giftsToCounter.add( gift );

  System.out.println( giftsToCounter );

  giftsToCounter.forEach( (gift, counter) -> {
    if ( counter > 1 )
      System.out.println( gift );
  } );
}

We leave the counting and printing of the corresponding gifts to a method printMultipleGifts(…​). It gets a list of quantities, each what a family brings in gifts. Counting the same things is a common task, but it cannot be done with a built-in data structure in Java. Therefore, we construct a small local class Bag that extends HashMap. This class Bag associates a string, the present, with the integer for the frequency. We give this small class a method so that we can externally increment the frequency for a key; internally, the associated value is incremented by 1. Here we resort to the merge(…​) method provided by Map. If there is no value associated to a key yet, 1 is set, and if there was at least one value, 1 is added to the old value and the record is updated.

In our method, we then build an instance of Bag, run over all the sets of families with the gifts, then run all the gifts themselves and call the add(…​) method for each gift.

If we want to know which gift occurred more than once, we can use the forEach(…​) method of Map to run over all key-value pairs and ask if the counter was greater than 1, and in that case output the gift.

1.9.31. Develop comfortable properties decorator

com/tutego/exercise/util/PropertiesConfiguration.java
public class PropertiesConfiguration {
  private final Properties properties;

  public PropertiesConfiguration( Properties properties ) {
    this.properties = properties;
  }

  public Optional<String> getString( String key ) {
    return Optional.ofNullable( properties.getProperty( key ) );
  }

  public Optional<Boolean> getBoolean( String key ) {
    try { return getString( key ).map( Boolean::valueOf ); }
    catch ( Exception e ) { return Optional.empty(); }
  }

  public Optional<BigInteger> getBigInteger( String key ) {
    try { return getString( key ).map( BigInteger::new ); }
    catch ( Exception e ) { return Optional.empty(); }
  }

  public OptionalDouble getDouble( String key ) {
    try { return OptionalDouble.of( Double.parseDouble( properties.getProperty( key ) ) ); }
    catch ( Exception e ) { return OptionalDouble.empty(); }
  }

  public OptionalLong getLong( String key ) {
    try { return OptionalLong.of( Long.parseLong( properties.getProperty( key ) ) ); }
    catch ( Exception e ) { return OptionalLong.empty(); }
  }

  public List<String> getList( String key ) {
    List<String> result = getString( key )
                              .map( s -> s.split( "\\s*(?<!\\\\),\\s*" ) )
                              .map( Arrays::asList )
                              .orElse( Collections.emptyList() );
    result.replaceAll( string -> string.replace( "\\,", "," ) );
    return result;
  }

  public void putBinary( String key, byte[] bytes ) {
    String base64 = Base64.getEncoder().encodeToString( bytes );
    properties.setProperty( key, base64 );
  }

  public Optional<byte[]> getBinary( String key ) {
    return getString( key )
             .map( base64 -> Base64.getDecoder().decode( base64 ) );
  }
}

Our PropertiesConfiguration class has a constructor that accepts and stores the actual Properties. Our methods are more flexible than the methods provided by Properties, but our methods are internally based on the methods of the Properties class. That is, all of the methods we provide rely in some way on the methods of the Properties class. In the center is the getProperty(String) method and once to set properties we also use setProperty(…​).

  • Optional<String> getString(String): properties could exist or not; if we hit a property with the simple getProperty(String) method that does not exist, getProperty(…​) returns null. While there is a getProperty(String key, String defaultValue) method, it does not prevent null from being returned and the caller must perform null handling. Java provides a nice way to express that a requested value does not exist with the Optional data type. Also, Optional gives us a nice way to express alternatives, such as with the Optional methods orElse(T other) or orElseGet(Supplier<? extends T> other) or even orElseThrow(Supplier<? extends X> exceptionSupplier).

  • Optional<Boolean> getBoolean(String) and Optional<BigInteger> getBigInteger(String): The implementations make it clear that the Optional data type has a map(Function) method that we can use to convert the strings to the Boolean and BigInteger data types and pack them into the Optional. However, since the format might be wrong in the underlying Properties object, an exception might occur during the conversion. We catch this, and our methods return Optional.empty() in that case.

  • OptionalDouble getDouble(String), OptionalLong getLong(String key): For the primitive types double, long there are special data types, namely OptionalDouble and OptionalLong. The logic is similar.

  • List<String> getList(String): If we return a list, we use our own method getString(…​), because it returns an Optional, to which we can directly set a map(…​) to convert the individual entries, separated by a comma, into an array of strings. The next call to map(…​) converts the array into a list. If the source getString(…​) returns an Optional.empty(), orElse(…​) will give us back an empty list. We had the convention that a comma must be masked out by \ and then is not considered a separator. The other strings now still contain \, instead of ,. We solve this by using the List method replaceAll(…​), which executes a function to replace on each element.

  • void putBinary(String, byte[]), Optional<byte[]> getBinary(String): The previous methods were just convenient read methods. With putBinary(…​) we have a method that encodes a byte array Base64 and puts it into a Properties object. For the Base64 conversions Java provides the class Base64. The getEncoder() and getDecoder() methods return objects for converting a byte array to a string and the string to a byte array. The conversion of a string to an array is handled by our getBinary(…​) method. Again, our own getString(…​) method returns an optional, and the map(…​) method converts String to a byte[].

1.9.32. Program UPN pocket calculator

com/tutego/exercise/util/UPN.java
    String input = "160 50 30 + /";
    Queue<Integer> stack = Collections.asLifoQueue( new ArrayDeque<>() );

    Pattern operatorPattern = Pattern.compile( "[+*/-]" );
    Pattern numericPattern  = Pattern.compile( "\\d+" );
    for ( String token : input.split( "\\s+" ) ) {
      Matcher operatorMatcher = operatorPattern.matcher( token );
      Matcher numericMatcher  = numericPattern.matcher( token );
      if ( numericMatcher.matches() )
        stack.add( Integer.parseInt( token ) );
      else if ( operatorMatcher.matches() ) {
        int operand2 = stack.remove();
        int operand1 = stack.remove();
        switch ( token ) {
          case "+" -> stack.add( operand1 + operand2 );
          case "-" -> stack.add( operand1 - operand2 );
          case "*" -> stack.add( operand1 * operand2 );
          case "/" -> stack.add( operand1 / operand2 );
        }
      }
      else
        System.out.println( "Unknown type!" );
    }
    System.out.printf( "Result: %d", stack.remove() );

The UPN calculator works in two steps:

  1. Decomposing the string into tokens

  2. Handling the tokens. Here we make a difference whether the token is a number or a symbol.

The actual algorithm can be implemented in different ways. One approach would be to first collect all numbers on one stack and all operators on a second stack. Finally, the stack with the operators is processed together with the stack of values. We use a different approach with only one stack.

Java provides the data structure java.util.Stack, but this data structure belongs to the discarded types of Java 1.0, which should not be used anymore. Therefore we use a LIFO queue, where add(…​) appends something behind (Last In) and remove(…​) takes something away from the queue (First Out).

If the token is the string representation of an integer, then we convert the string to an integer and put it on the stack. Also, we use a regular expression to check if the token is a binary operator. With the order of the operators in the regular expression [+*/-] we have to take care that the - is not between the symbols, otherwise the minus stands for a range specification like a-z, which we don’t want of course.

If the token is an operator, we have to get two operands from the stack. It is important to take care to fetch the second operand from the stack first and then the first operand. Addition and multiplication are commutative, but subtraction and division are not. The switch instruction with the modern arrow notation helps us to perform the correct operation based on the token and to put the result back on the stack.

Since a binary operation always consists of three symbols, only one number remains after the resolution. If we have processed all tokens from the input and the number of numbers and operators was balanced, there is only one number left at the end, the result. Readers may consider what errors could occur due to incorrect input values.

Java 8 Backport

The switch statement with the arrow notation has been around since Java 14; this can be easily rewritten.

1.9.33. Handle important messages first

com/tutego/exercise/util/UrgentMessagesFirst.java
class Message {

  public final String message;
  public final long   timestamp;

  Message( String message ) {
    this.message   = Objects.requireNonNull( message );
    this.timestamp = System.nanoTime();
  }

  @Override public boolean equals( Object other ) {
    if ( other == null || getClass() != other.getClass() ) return false;
    return    message.equals( ((Message) other).message )
           && ((Message) other).timestamp == timestamp;
  }

  @Override public int hashCode() {
    return Objects.hash( message, timestamp );
  }

  @Override public String toString() {
    return "'" + message + '\'' + ", " + timestamp % 100_000;
  }
}

The Message class has a constructor that receives and stores the actual message; the timestamp comes from System.nanoTime() because the nanoseconds to a fixed but unspecified reference point have good resolution and come in handy for our comparisons. The equals(Object) method compares the message string and the timestamp. hashCode() is implemented for completeness, it is not called in our program. toString() encloses the message in single quotes and sets the last five digits of the timestamp, because this is enough for a quick visual comparison which message is younger or older.

com/tutego/exercise/util/UrgentMessagesFirst.java
String KEYWORD = "Kanönchen";

Comparator<Message> keywordComparator = ( msg1, msg2 ) -> {
  boolean msg1HasKeyword = msg1.message.contains( KEYWORD );
  boolean msg2HasKeyword = msg2.message.contains( KEYWORD );
  boolean bothMessagesHaveKeywordOrNot = msg1HasKeyword == msg2HasKeyword;
  return bothMessagesHaveKeywordOrNot ? 0 : msg1HasKeyword ? -1 : +1;
};

Comparator<Message> messageComparator =
    keywordComparator.thenComparingLong( message -> message.timestamp );
PriorityQueue<Message> tasks = new PriorityQueue<>( messageComparator );

The keywordComparator is at the heart of the solution. It takes the two messages from the message and checks for the presence of the cosword. To make the code a bit clearer, the result of contains(…​) is stored in two variables. Now there are four cases: Both messages contain the coseword, both messages do not contain it, or one of the two messages contains the searched word. If both contain the term or not, the Comparator returns 0, otherwise only one of the two messages contains the string. If the cosword is contained in the first message, this message is smaller according to this Comparator and the Comparator answers with a negative value. Otherwise, the cosword must be present in the second message, and the Comparator responds with a positive value.

A Comparator downstream of the keywordComparator is necessary in case the keywordComparator returns 0. In this case the time should be considered as a second criteria. An appended thenComparingLong(…​) adds a Comparator which considers the timestamp. The order is correct, because older messages carry a smaller timestamp.

The resulting messageComparator is passed to the constructor of PriorityQueue, and the data structure is initialized.

1.9.34. If used up, create a new one

com/tutego/exercise/thread/SecureRandomBigIntegerIteratorDemo.java
class SecureRandomBigIntegerIterator implements Iterator<BigInteger> {

  private final SynchronousQueue<BigInteger> channel =
      new SynchronousQueue<>();

  public SecureRandomBigIntegerIterator() {
    Runnable bigIntegerPutter = () -> {
      try {
        while ( true ) {
          BigInteger bigInteger = internalNext();
          System.out.printf( "> About to put number %s... into the queue%n",
                             bigInteger.toString().subSequence( 0, 20 ) );
          channel.put( bigInteger );
          System.out.println( "> Number was taken" );
        }
      }
      catch ( InterruptedException e ) { throw new IllegalStateException(e); }
    };
    ForkJoinPool.commonPool().submit( bigIntegerPutter );
  }

  private BigInteger internalNext() {
    return new BigInteger( 1024, new SecureRandom() );
  }

  @Override public boolean hasNext() {
    return true;
  }

  @Override public BigInteger next() {
    try {
      System.out.println( "< About to take a number" );
      BigInteger bigInteger = channel.take();
      System.out.println( "< Took a number out" );
      return bigInteger;
    }
    catch ( InterruptedException e ) { throw new IllegalStateException(e); }
  }
}

At the heart of the solution is the SynchronousQueue class. It differs significantly from a normal Queue and is essentially only used to pass an element from one thread to another. This is exactly the context in which we use SynchronousQueue.

Our class SecureRandomBigIntegerIterator implements the Iterator interface and can return infinitely large integers. The constructor of our class creates a Runnable and passes it to a preconfigured thread pool, the ForkJoinPool.commonPool(). Compared to a custom thread pool, the fork-join pool shuts down automatically when the application exits; however, this particular pool is not really necessary for the solution.

The Runnable contains an infinite loop that immediately starts requesting an integer; the random BigInteger comes from the internal method. That is, even if the next() method on the iterator is not called at all, our implementation goes ahead and fills the SynchronousQueue with the put(…​) method. In put(…​) the thread stays until the other party takes the element from the SynchronousQueue, then the thread continues with the infinite loop and the next number is determined.

The next(…​) method of the Iterator instance takes the number from the SynchronousQueue, exactly for this case we have included this construction. With the take() method the element is taken, which on the other side leads to the fact that again a new BigInteger is created and put into the queue. If there is always some time between the calls of the next(…​) method, the thread in the background will have already calculated a new random number, which means that the next(…​) method can immediately return a result and does not have to calculate the result first, because it was ready in the queue.

The methods put(…​) and take() can throw an exception if they receive an interrupt. For this case there is no special handling in the program, but only an IllegalStateException. It is a problem if the creator thread dies and the iterator waits forever for the element. With poll(long timeout, TimeUnit unit) an alternative method is offered, where a maximum waiting time can be specified. In our case this could mean: If we have no element in the queue after one second — the calculation never takes that long in life — we can assume that the thread has died.


1. The Compass Course (CC) is the angle between a ship’s path and compass north
2. Linux users usually have dc installed and can play a bit with the UPN, a short introduction is provided by https://de.wikipedia.org/wiki/Dc_(Unix).
3. The constructor reference is for ArrayList(int), i.e. the parameterized constuctor, so an ArrayList is created with the capacity from the word length — things are not related at all