Java Generics and Collections



Java SE 11 Developer certification (exam number 1Z0-819)

Working with Arrays and Collections

Headlines
Generics are the ability to express the behavior of a class by using anonymous types (a.k.a. “formal types”)

Rule(s)

Example Bound_stack.Java.zip 

public class Bound_stack<T> extends java.util.ArrayDeque<T> { // Note that 'java.util.Stack<T>' is deprecated...
    private final int _capacity;
    Bound_stack(final int capacity) {
        _capacity = capacity;
    }
    public boolean full() {
        return _capacity == size(); // From 'java.util.ArrayDeque<T>' without redefinition
    }
    public void push(final T t) {
        if (full()) {
            throw new RuntimeException("push");
        }
        super.push(t); // Omitting 'super' creates recursion
    }
}
…
public static void main(String[] args) {
    Bound_stack<Character> bs = new Bound_stack<>(10);
    bs.push('A');
    bs.push('B');
    // bs.removeFirst(); // 'A' would be removed while it's illegal for a stack!
    bs.pop(); // 'A'
}

extendskeyword and generic classes

Rule(s)

Example (inheritance tree) Vegetables.Java.zip 

abstract public class Vegetable {
    public enum Color {
        Green, Orange, Red // Etc.
    }
    abstract public Color getColor();
    class Salad extends Vegetable {
        @Override
        public Color getColor() {
            return Vegetable.Color.Green;
        }
    }
    class Batavia extends Salad {}
    class Lettuce extends Salad {}
}

? wildcard and generic classes

Rule(s)

Example (generic class) Vegetables.Java.zip 

public class Garden<Element extends Vegetable> {
    private java.util.Deque<Element> _vegetables = new java.util.ArrayDeque<>();
    public boolean is_bigger_than_V1(Garden<Element> garden) {
        return this._vegetables.size() > garden._vegetables.size();
    }
    public boolean is_bigger_than_V2(Garden<?> garden) {
        return this._vegetables.size() > garden._vegetables.size();
    }
    …
}

Example (usage) Vegetables.Java.zip 

Rule(s)

public static void main(String[] args) {
    Garden<?> g0 = new Garden<>(); // Any kind of 'Vegetable'...
    Garden<Vegetable.Salad> g1 = new Garden<>();
    Garden<Vegetable.Batavia> g2 = new Garden<>();
    Garden<Vegetable.Lettuce> g3 = new Garden<>();

    // Compilation error because 'Garden<Vegetable.Salad>' is not "similar" to 'Garden<Vegetable.Batavia>':
    // g1 = g2;
    g0 = g2; // Prior 'g0' moves to garbage collection...

    // Java does not support this notation because of "erasure":
    // assert (Garden<Vegetable.Salad>.class != Garden<Vegetable.Batavia>.class);

    // Compilation error because 'Garden<Vegetable.Salad>' and 'Garden<Vegetable.Batavia>' *ARE NOT* related to each other:
    // System.out.println(g1.is_bigger_than_V1(g2)); 
    System.out.println(g1.is_bigger_than_V2(g2)); // Great, no compilation error...
    …    
}

superkeyword and generic classes

Example Vegetables.Java.zip 

public class Garden<Element extends Vegetable> {
    …
    public void transfer_V1(Garden<Element> to) {
        while (!this._vegetables.isEmpty()) {
            to._vegetables.add(this._vegetables.remove());
        }
    }
    public void transfer_V2(Garden<? super Element> to) {
        while (!this._vegetables.isEmpty()) {
            to._vegetables.add(this._vegetables.remove());
        }
    }
}
// Sound compilation error because 'g2' may get salads, which *ARE NOT* batavias:
// g1.transfer_V1(g2);
// Compilation error (unexpected?):
// g2.transfer_V1(g1); // 'g1' only accepts *DIRECT* salads and not subtypes: Batavia, Lettuce...
g2.transfer_V2(g1); // Solution: 'g1' gets batavias from 'g2'!

Erasure versus reification

Rule(s)

Example

assert (g1.getClass() == g2.getClass());
assert (g1 instanceof Garden);
assert (g2 instanceof Garden);
assert (g1 instanceof Garden<?>);
assert (g2 instanceof Garden<?>);

Ampersand character (a.k.a. &)

Rule(s)

Example

interface Friendly { … }

interface Efficient { … }

class Startup<Employee extends Efficient & Friendly> { … }

Primitive versus generic arrays

Example (conversion of primitive array into -volatile- generic array)

Short tab[] = {13, 7, 6, 4, 12, 11, 8, 3}; // Caution: 'short tab[]' does not work!
java.util.Collections.sort(java.util.Arrays.asList(tab)); // 'tab' is converted into 'java.util.List<Short>' and next sorted
for (Short s : tab) { // Initial 'tab' array is physically sorted by side effect
    System.out.print("-" + s); // '-3-4-6-7-8-11-12-13' is displayed
}

Example (conversion of generic array into primitive array)

java.util.Deque<Short> deque = new java.util.ArrayDeque<>();
deque.addLast((short) 13);
…
Short other_tab[] = deque.toArray(new Short[0]);

Example (parameterized (generic) class with T does not support array of type T) Generics.Java.zip 

public class My_class<T> {
    T _tab_containing_T_elements[]; // Declaration is OK
    My_class() {
        // Instantiation failed at compilation time: 'error: generic array creation':
        _tab_containing_T_elements = new T[1000];
    }
    …

Generic methods

Rule(s)

Example (first form)

java.util.Deque<Short> deque = new java.util.ArrayDeque<>();
deque.addLast((short)13);
deque.addLast((short)7);
 …
Short result[] = (Short[])deque.toArray(); // Mandatory cast from 'Object[]' to 'Short[]'

Example (second form) Generics.Java.zip 

Short result[] = deque.toArray(new Short[0]); // Great, no cast!

Rule(s)

Example (second form)

Byte parameter[] = new Byte[0];
Byte result[] = deque.toArray(parameter);
assert (parameter == result);
Collection iteration has been simplified in Java 5

Example

java.util.Collection<Boolean> my_collection = new java.util.LinkedList<>(); // Diamond-based instantiation
java.util.Random random = new java.util.Random();
// Old style:
for(int i = 0;i < 5;i++) {
    boolean b = random.nextBoolean();
    my_collection.add(b);
}
// New style:
for(Boolean b : my_collection) System.out.print("\t" + b);
Java sequences are basic collections including (advanced) arrays (e.g., java.util.Vector<E>), lists, etc. Java offers the java.util.List<E> interface as key functional entry point

Rule(s)

Example (basic usage)

public class Prisoner {
    …
    final java.util.List<Criminal_case> _all_criminal_cases = new java.util.LinkedList<>(); // Ver. 1
// First alternative:
//  final java.util.List<Criminal_case> _all_criminal_cases = new java.util.ArrayList<>(); // Ver. 2
// Second alternative:
//  final java.util.Deque<Criminal_case> _all_criminal_cases = new java.util.ArrayDeque<>(); // Ver. 3
// Insertion in Java sequences:
    public void involve(Criminal_case criminal_case) {
        boolean result = _all_criminal_cases.add(criminal_case);
        assert result;
    }
    …
}

Example (advanced usage)

// Adding at the end ('_all_criminal_cases' is typed with 'java.util.List<>'):
_all_criminal_cases.add(criminal_case)
// Adding at the beginning ('_all_criminal_cases' is typed with 'java.util.List<>'):
_all_criminal_cases.add(0,criminal_case);
// Adding at the end ('_all_criminal_cases' is typed with 'java.util.LinkedList<>'):
_all_criminal_cases.addLast(criminal_case);
// Adding at the beginning ('_all_criminal_cases' is typed with 'java.util.LinkedList<>'):
_all_criminal_cases.addFirst(criminal_case);
// Getting the last one:
public Criminal_case last() { // ('_all_criminal_cases' is typed with 'java.util.LinkedList<>')
    return _all_criminal_cases.isEmpty() ? null : _all_criminal_cases.getLast();
}
// Getting the last one, alternative:
public Criminal_case last() { // ('_all_criminal_cases' is typed with 'java.util.List<>')
    Criminal_case last = null;
    java.util.ListIterator<Criminal_case> iterator = _all_criminal_cases.listIterator();
    while(iterator.hasNext()) last = iterator.next();
    return last;
}
Java sets are collections without duplicates. Java offers two interfaces as functional entry points: java.util.Set<E> and java.util.SortedSet<E>

Example (basic usage)

public class Jail {
    final java.util.Set<Prisoner> _prisoners = new java.util.HashSet<>(); // Loss of insertion order
// First alternative:
//  final java.util.Set<Prisoner> _prisoners = new java.util.LinkedHashSet<>(); // Preservation of insertion order
// Second alternative:
//  final java.util.Set<Prisoner> _prisoners = new java.util.TreeSet<>(); // Preservation of insertion order with 'Comparable<T>'
// Insertion in Java sets:
    public void incarcerate(Prisoner prisoner) {
        boolean result = _prisoners.add(prisoner);
        assert result;
    }
    …
}

Rule(s)

Example (overriding equals, and therefore hashCode, inherited Java functions)

public class Prisoner {
    final String _prison_file_number;
    Prisoner(String prison_file_number) {
        _prison_file_number = prison_file_number;
    }
    public boolean equals(Object object) {
        return this == object ? true : object instanceof Prisoner ?
            _prison_file_number.equals(((Prisoner)object)._prison_file_number) : false;
    }
    public int hashCode() {
        return _prison_file_number.hashCode();
    }
    …
}

Example (advanced usage)

Specification
Implementation Set_illustration.Java.zip 
public class Set_illustration<T> extends java.util.HashSet<T> {
    public boolean strict_subset(final Set_illustration<T> s) {
        return s.containsAll(this) && !s.equals(this);
    }
    public Set_illustration() {
        super();
    }
    public Set_illustration(java.util.Collection<? extends T> s) {
        super(s);
    }
    public Set_illustration<T> difference(final Set_illustration<T> s) { // 's' = F
        Set_illustration<T> difference = new Set_illustration<>(this); // 'this' = 'E'
        difference.removeIf((T t) -> s.contains(t));
        return difference;
    }
    public Set_illustration<T> symmetrical_difference(final Set_illustration<T> s) {
        Set_illustration<T> symmetrical_difference = new Set_illustration<>(this);
        symmetrical_difference.addAll(s);
        Set_illustration<T> intersection = new Set_illustration<>(this);
        intersection.retainAll(s);
        // Formally, symetrical symmetrical_difference is 'union - intersection':
        symmetrical_difference.removeIf((T t) -> intersection.contains(t));
        return symmetrical_difference;
    }
    public static void main(String args[]) {
        Set_illustration<Character> E = new Set_illustration<Character>();
        Set_illustration<Character> F = new Set_illustration<Character>();
        E.add('a');
        F.add('a');
        F.add('b');
        System.out.println("E strictly included in F ? " + E.strict_subset(F)); // 'true'
        E.add('b');
        System.out.println("E strictly included in F ? " + E.strict_subset(F)); // 'false'
        F.remove('b');
        F.add('c');
        Set_illustration<Character> difference = E.difference(F);
        System.out.print("E - F: ");
        difference.forEach((c) -> {
            System.out.print(c + " "); // 'b'
        });
        System.out.print("\nE - F (symmetrical): ");
        Set_illustration<Character> symmetrical_difference = E.symmetrical_difference(F);
        symmetrical_difference.forEach((c) -> {
            System.out.print(c + " "); // 'b', 'c'
        });
    }
}
Java maps are hash tables (a.k.a. dictionaries, hash maps or maps for short), i.e., associative containers

Rule(s)

Example (hashCode algorithm for String)

String s = "CC"; // ASCII value of 'C' is '67'
assert(s.hashCode() == 2144); // Algorithm: 67 * 31pow(0) + 67 * 31pow(1) = 2144

Example (basic usage)

java.util.Map<Integer,Double> polynomial = new java.util.HashMap<>();
polynomial.put(1,-12.D);
polynomial.put(39,8.D);

java.util.Map<Object,String> my_map = new java.util.HashMap<>();
Object o1 = new Object();
my_map.put(o1,"inserted string at the ‘o1’ index (key)");
String s = my_map.get(o1);
assert(s.equals("inserted string at the ‘o1’ index (key)") == true);

Rule(s)

Example (String objects differ in terms of content) Hashtable_illustration.Java.zip 

String s1 = "Franck";
String s2 = "Franck";
assert (s1 != s2); // 's1' and 's2' are NOT the same memory object
assert (s1.equals(s2)); // However, 's1' equals 's2'
assert (s1.hashCode() == s2.hashCode());

Example (String as “key” type)

java.util.Map<String, Integer> my_map = new java.util.HashMap<>();
String s1 = "A";
String s2 = "A";
my_map.put(s1, 1);
my_map.put(s2, 2);  
System.out.println(my_map.get(s1)); // '2'

Rule(s)

Example (advanced usage) Hashtable_illustration.Java.zip 

int max = 100;
float theta = 0.5F;
java.util.Map<String, String> given_names__dictionary = new java.util.HashMap<>(max, theta);
given_names__dictionary.put("Franck", "German origin...");
given_names__dictionary.put("Frank", "English origin...");
assert (given_names__dictionary.size() == 2);

java.util.Map<Object, String> hashtable_with_possible_null_keys = new java.util.HashMap<>();
hashtable_with_possible_null_keys.put(null, "Allowing 'null' keys");
System.out.println(hashtable_with_possible_null_keys.get(null));

Rule(s)

Java priority queues (a.k.a. heaps) keep a natural ordering or apply the ordering, which is provided by java.util.Comparator<T>

Internal representation

Example Heap.Java.zip 

java.util.Comparator<Short> comparator = (Short i, Short j) -> {
    return i - j;
};

java.util.PriorityQueue<Short> my_priority_queue = new java.util.PriorityQueue<>(10, comparator);
short native_tab[] = {13, 12, 11, 8, 7, 6, 4, 3};
for (short s : native_tab) {
    my_priority_queue.add(s);
}
my_priority_queue.forEach((s) -> {
    System.out.print("\t" + s); // '3   4   6   8   11  12  7   13' is displayed...
});
java.util.Collections and java.util.Arrays utility classes

java.util.Collections and java.util.Arrays utility classes support collection creation, conversion (from native arrays especially), searching, sorting… generic algorithms like C++ generic algorithms in the Standard Template Library -STL-.

Example (sorting & searching) Binary_tree.Java.zip 

java.util.ArrayList<Integer> tab = new java.util.ArrayList<>();
tab.add(11);
tab.add(28);
tab.add(6);
tab.add(15);
tab.add(22);
java.util.Collections.sort(tab);
assert (java.util.Collections.binarySearch(tab, 22) >= 0);
assert (java.util.Collections.binarySearch(tab, 23) < 0);

Example

short native_tab[] = {3, 4, 6, 7, 8, 11, 12, 13};

java.util.List<Short> advanced_tab = new java.util.ArrayList<>();
for (int i = 0; i < native_tab.length; i++) advanced_tab.add(native_tab[i]);

java.util.Collections.shuffle(advanced_tab); // Random permutation of elements to loose the initial order
for (short s : advanced_tab) System.out.print("\t" + s);

System.out.print(java.util.Collections.binarySearch(advanced_tab, (short) 0)); // '-1' (insertion point) is returned since '0' is not present in 'advanced_tab'

java.util.Collections.sort(advanced_tab);
for (short s : advanced_tab) System.out.print("\t" + s);

Example (concatening) Primitive_array_concatenation.Java.zip 

public class Primitive_array_concatenation {

    private final static String[] _Author = {"Franck", "Barbier"};
    // Delimited word: [^\w] <=> [^a-zA-Z_0-9]
    private final static java.util.regex.Pattern _Word = java.util.regex.Pattern.compile("[^\\w]");

    public static void main(String[] args) {
        String string = "Primitive array concatenation from";

        String[] words = _Word.split(string);

        String[] concatenation = java.util.Arrays.copyOf(words, words.length + _Author.length);
        System.arraycopy(_Author, 0, concatenation, concatenation.length - _Author.length, _Author.length);
    }
}
Immutable collections

Rule(s)

Example From_Java_9.Java.zip 

Mammutidae m0 = new Mammutidae("Macron");
Mammutidae m1 = new Mammutidae("Poutine");
Mammutidae m2 = new Mammutidae("Trump");
// Immutable collections (e.g., a set):
try {
    java.util.Set.of(m1, m2).add(m0); // Poutine and Trump don't want Macron!
} catch (UnsupportedOperationException uoe) {
    System.err.println("In essence, immutable collections do not support changes like additions: " + uoe.toString());
}

Example From_Java_9.Java.zip 

java.util.Set<Integer> primes = new java.util.HashSet<>() { // <- Creation of an anonymous inner class, which extends 'java.util.HashSet'
    { // <- Block initialiser
        add(2);
        add(3);
    }
};
try { // Java 10 'copyOf':
    java.util.Set.copyOf(primes).add(4);
} catch (UnsupportedOperationException uoe) {
    System.err.println("In essence, immutable collections do not support changes like additions: " + uoe.toString());
}
AVL tree

A user-defined collection is a kind of new container in Java. For example, a AVL tree may be designed from a user perspective.

Example Binary_tree.Java.zip 

public class Binary_tree<T> {
    protected T _content;
    protected Binary_tree<T> _left, _right, _super;
    public void infix() {
        if (_left != null) {
            _left.infix();
        }
        System.out.println();
        if (_right != null) {
            _right.infix();
        }
    } // a+b-c*d

    public void prefix() {
        System.out.println();
        if (_left != null) {
            _left.prefix();
        }
        if (_right != null) {
            _right.prefix();
        }
    } // +a*-bcd
    public void postfix() {
        if (_left != null) {
            _left.postfix();
        }
        if (_right != null) {
            _right.postfix();
        }
        System.out.println();
    } // abc-d*+
    public int h() {
        if (_super == null) {
            return 0;
        }
        return _super.h() + 1;
    }
    public int H() {
        int H_left, H_right;
        if (_left != null) {
            H_left = _left.H() + 1;
        } else {
            H_left = 0;
        }
        if (_right != null) {
            H_right = _right.H() + 1;
        } else {
            H_right = 0;
        }
        return H_left < H_right ? H_right : H_left;
    }
    public boolean isAVL() {
        if (_left == null && _right == null) {
            return true;
        }
        if (_left == null) {
            return _right.H() < 1;
        }
        if (_right == null) {
            return _left.H() < 1;
        }
        return false;
    }