Java Generics and Collections

Working with Arrays and Collections

• Use generics, including wildcards
• Sort collections and arrays using Comparator<T> and Comparable<T> interfaces
• Use a Java array and java.util.List<E>, java.util.Set<E>, java.util.Map<K,V> and java.util.Deque<E> collections, including convenience methods

• Generics
  • extendskeyword and generic classes
  • ? wildcard and generic classes
  • super keyword and generic classes
  • Erasure versus reification
  • Primitive versus generic arrays
  • Generic methods
• Java collection iteration
• Java sequences
• Java sets
• Java maps
• Java priority queues
• java.util.Collections and java.util.Arrays utility classes
• Immutable collections
• AVL tree (as user-defined collection)

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

Rule(s)

• A stack has a behavior (pop, push...), which does not depend upon the type of its stored elements (e.g., Character or Integer). Thus, generics allow the possibility of designing a class by referring to T as “any type”.

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)

• The key issue of generics is a sought compatibility with inheritance.

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)

• is_bigger_than_V2 method (contrary to is_bigger_than_V1 method) is signed with Garden<?> garden as single argument.

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)

• g1.is_bigger_than_V2(g2) demonstrates that g1 (type is Garden<Vegetable.Salad>) interoperates with any other garden (including any kind of vegetable) from the perspective of is_bigger_than_V2. In other words, g2 conforms to Garden<?>.

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)

• Java is based on the erasure mode.

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)

• & allows “multiple inheritance” in the way the formal type is constrained by some ancestor(s). Multiple ancestors may be described (and linked by means of &) provided that they are interfaces.

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)

• As an illustration, the java.util.Collection<E> type weirdly offers two methods for transforming a collection into a primitive array:
  1. Object[] toArray()
  2. <T> T[] toArray(T[] tab)
  The second form illustrates what is a generic method, i.e., a method parameterized by T, which is totally different from E that parameterizesjava.util.Collection<E>!
  The two forms are somehow redundant. The former remains for backward compatibility.

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)

• In fact, the unique parameter of toArray (absent in the former version) allows us to control the type of the returned result and where it is stored.

Example (second form)

Byte parameter[] = new Byte[0];
Byte result[] = deque.toArray(parameter);
assert (parameter == result);

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

Rule(s)

• Concrete sequence classes that comply with java.util.List<E> must be chosen among java.util.LinkedList<E>, java.util.ArrayList<E> (non thread-safe), java.util.Stack<E> (deprecated) and java.util.Vector<E> (thread-safe, but deprecated).
• One may note that java.util.LinkedList<E> also implements the java.util.Deque<E> interface (access from both ends) while java.util.ArrayDeque<E> is a concrete class that implements java.util.Deque<E> only.
• Parallel programming requires appropriate lists as for instance, java.util.concurrent.CopyOnWriteArrayList<E>.

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;
}

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)

• Insertion in Java sets requires an appropriate (overridden) equality function (i.e., public boolean equals(Object object)) in Prisoner or, when using java.util.TreeSet<Prisoner>, the adapted usage of Comparable<Prisoner>.
• One may note that java.util.TreeSet<E> uses as backbone a red-black tree; insertions, deletions and searches are then run in O(log(n)) complexity.

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

• E ⊂ F ⇔ E ⊆ F ∧ E ≠ F, i.e., strict_subset? (i.e., ⊂): Set_illustration x Set_illustration → Boolean with s1, s2: Set_illustration, strict_subset?(s1,s2) = subset?(s1,s2) ∧ ∼equals?(s1,s2)
• E - F = {t ∈ E ∧ t ∉ F}, i.e., difference: Set_illustration x Set_illustration → Set_illustration with s1, s2: My_set, ti: T, difference(s1,s2) = [remove(union(s1,s2),ti)]belongs?(ti,s2)

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'
        });
    }
}

Rule(s)

• Maps extend the classical notion of array in programming by allowing indexes that may be any kind of objects while arrays only use (positive in general) integers as indexes. Table indexes are called “keys” while stored objects in hash tables are named “values”.
• Array indexes lead to “direct” memory places. Instead, map indexes must be transformed into integers with hashCode in Java; any bad redefinition of this method slows down map access compared to native arrays. Therefore, user-defined hash algorithms often rely on preexisting ones from well-known types, e.g., String.

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)

• A key issue in Java is the presence of the hashCode method in the Object class. This method is systematically used by Java maps at access (insertion, deletion…) time. So, in tailor-made classes, it may be required to override this method in strict relation with the equals method. The formal rule to respect is as follows: o1 = o2 ⇒ hashCode(o1) = hashCode(o2), i.e., hashCode(o1) ≠ hashCode(o2) ⇒ o1 ≠ o2.
• Note that o1 ≠ o2 ⇒ hashCode(o1) ≠ hashCode(o2) is only a general precept. It shows that the hash algorithm is, in a functional way, robust (no or few conflicts).

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)

• Java memory management occurs in the following conditions: H(o) = └((hashCode(o) * Θ) modulo 1.) * max┘ with 0 < Θ < 1. This may be changed in Java when creating a new hash table object.

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)

• The root interface for maps is java.util.Map<K,V> while the main implemented classes may be chosen among java.util.Hashtable<K,V> (deprecated, no nullvalues), java.util.HashMap<K,V> (no synchronization), java.util.LinkedHashMap<K,V> (order preservation), java.util.TreeMap<K,V> (order preservation) and java.util.concurrent.ConcurrentMap<K,V> for thread-safe concurrent programming.
• One may note that java.util.TreeMap<K,V> uses as backbone a red-black tree; insertions, deletions and searches are then run in O(log(n)) complexity.

Internal representation

• left(x) is located in the array at the (2 * i) + 1 index where i is the index of x
• right(x) is located in the array at the (2 * i) + 2 index
• So, in the figure, the root, 13, is located at index 0 while 12 is located at index 2 * 0 + 1 = 1, etc. Access to the maximum value is then based on constant time complexity

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 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);
    }
}

Rule(s)

• The of static method of java.util.List, java.util.Set and java.util.Map allows the creation of immutable collections from Java 9.
• The copyOf static method from Java 10 creates an immutable collection from the original collection while the of static method accepts elements as arguments.

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());
}

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;
    }