Generics

Type Erasure:

Type erasure is the process by which the Java compiler removes type parameters and replaces them with:

• Their bounds (usually Object)
• Appropriate casts in the bytecode

Key implications:

1. Generic type information exists only at compile time, not runtime
2. At runtime, List<String> and List<Integer> are both just List
3. Cannot use methods like instanceof with parameterized types
4. Cannot create arrays of parameterized types directly (e.g., new List<String>[10] is illegal)
5. Cannot use primitive types as type parameters (must use wrapper classes)
6. Cannot overload methods where type erasure would make signatures identical

   // Illegal - both erase to process(List)
   void process(List<String> stringList) { }
   void process(List<Integer> intList) { }

7. Cannot catch exceptions of parameterized types

Why erasure exists: Implemented for migration compatibility to ensure interoperability between generic code and legacy pre-generic code.

Example of erasure:

// Source code with generics
List<String> strings = new ArrayList<>();
strings.add("hello");
String s = strings.get(0);

// After erasure (conceptual equivalent)
List strings = new ArrayList();
strings.add("hello");
String s = (String) strings.get(0);

Handling Casting with Generic Collections:

Key Principles:

1. Properly parameterized collections shouldn't require explicit casts when retrieving elements
2. The compiler inserts necessary casts automatically when using parameterized types
3. Raw types require manual casting and are unsafe

Potential Pitfalls:

1. Using raw types for collections:

   // Dangerous - requires explicit cast and can fail at runtime
   List stamps = new ArrayList();
   stamps.add(new Stamp());
   Stamp s = (Stamp) stamps.get(0); // Explicit cast required

2. Mixing parameterized and raw types:

   // Dangerous - compiler allows adding any object
   List<Stamp> stamps = new ArrayList<>();
   addToCollection(stamps); // Passing to raw type method
   Stamp s = stamps.get(0); // ClassCastException possible
   
   void addToCollection(Collection c) { // Raw type
       c.add(new Coin()); // Corrupts type invariant
   }

3. Unchecked casts:

   // Dangerous - compiler warns but allows
   @SuppressWarnings("unchecked")
   List<String> strings = (List<String>) unknownCollection;

Best Practices:

1. Always use parameterized types:

   List<Stamp> stamps = new ArrayList<>();
   stamps.add(new Stamp());
   Stamp s = stamps.get(0); // No cast needed

2. Use wildcards for flexibility:

   // Safe - accepts any List type
   void printCollection(Collection<?> c) {
       for (Object o : c) {
           System.out.println(o);
       }
   }

3. Only suppress warnings when necessary and on smallest scope:

   // If cast is truly safe, restrict warning suppression
   @SuppressWarnings("unchecked") 
   T result = (T) getResult();

4. Properly document why suppressed warnings are safe:

   // This cast is safe because we've verified all elements are strings
   @SuppressWarnings("unchecked")
   List<String> strings = (List<String>) someCollection;

Remember: The compiler inserts invisible casts when retrieving elements from a properly parameterized collection, making your code both safer and cleaner.

Array-based Implementation:

public class ArrayBased<E> {
    private E[] elements; // Actually Object[] at runtime
    
    @SuppressWarnings("unchecked")
    public ArrayBased(int capacity) {
        // Must use this workaround and cast
        elements = (E[]) new Object[capacity];
    }
}

List-based Implementation:

public class ListBased<E> {
    private List<E> elements;
    
    public ListBased(int capacity) {
        // Clean, no cast needed
        elements = new ArrayList<>(capacity);
    }
}

Tradeoffs:

Array Advantages:

• Better memory efficiency for primitive types (with specialized arrays)
• More compact memory layout
• Potentially better performance for certain operations
• Direct indexed access with O(1) time complexity
• No boxing/unboxing for primitive types (with specialized arrays)

Array Disadvantages:

• Requires unchecked cast during creation
• Fixed size (requires manual resizing)
• Type safety relies on programmer discipline
• Need for SuppressWarnings annotation
• Cannot create true generic arrays (new E[] is illegal)

List Advantages:

• Full generic type safety
• Dynamic resizing handled automatically
• No unsafe casts required
• Cleaner, more maintainable code
• No warnings to suppress
• Better interoperability with Java collections framework

List Disadvantages:

• Potentially higher memory overhead
• May have slightly worse performance in some scenarios
• Autoboxing overhead for primitive types
• Additional indirection

Choose lists when type safety and code clarity are priorities; choose arrays when performance is critical and you can ensure type safety manually.

A recursive type bound is when a type parameter is bounded by an expression involving that type parameter itself.

For the max() method that uses natural ordering:

// Returns the maximum element in a collection using natural ordering
public static <E extends Comparable<E>> E max(Collection<E> c) {
    if (c.isEmpty())
        throw new IllegalArgumentException("Empty collection");
        
    E result = null;
    for (E e : c) {
        if (result == null || e.compareTo(result) > 0)
            result = Objects.requireNonNull(e);
    }
    return result;
}

The recursive type bound <E extends Comparable<E>> means:

• E must implement Comparable<E>
• E can be compared to other E instances
• This expresses "mutual comparability" among elements
• Every element must be comparable to every other element in the collection

This is commonly used with natural ordering interfaces like Comparable where a type needs to compare with itself.

Bounded Type Parameters

• Specified in the class or method declaration
• Establish requirements for all uses of that generic type
• Form: <T extends BoundingType>

// T must implement Comparable<T>
class SortedPair<T extends Comparable<T>> {
    private final T first, second;
    
    public SortedPair(T a, T b) {
        if (a.compareTo(b) <= 0) {
            first = a; second = b;
        } else {
            first = b; second = a;
        }
    }
    // Methods can rely on T being Comparable
}

Bounded Wildcards

• Used in specific variable declarations or method parameters
• Allow flexibility in accepting generic types
• Forms: <? extends BoundingType> or <? super BoundingType>

// Accept collection of any Number subtype
void sum(Collection<? extends Number> nums) {
    double sum = 0;
    for (Number n : nums) sum += n.doubleValue();
}

When to use:

• Bounded Type Parameters: When the entire class or method requires certain capabilities from its type parameter

  • When multiple parameters need the same bound
  • When methods need to return the exact parameterized type

• Bounded Wildcards: When specific parameters need flexibility

  • For input parameters that produce values (use ? extends T)
  • For input parameters that consume values (use ? super T)
  • When you need to accept a range of generic types, not just one specific type

Bounded type parameters define constraints on a type throughout its scope, while bounded wildcards allow flexibility at specific points of use.

A robust implementation must handle both primitive wrapper classes and other comparables using a more complex recursive bound:

/**
 * Returns maximum element in a collection using natural ordering.
 * Works with both direct and indirect Comparable implementations.
 */
public static <T extends Comparable<? super T>> T max(Collection<T> collection) {
    if (collection.isEmpty())
        throw new IllegalArgumentException("Empty collection");
        
    T result = null;
    for (T element : collection) {
        if (result == null || element.compareTo(result) > 0)
            result = Objects.requireNonNull(element);
    }
    return result;
}

The key is the type parameter definition: <T extends Comparable<? super T>>

This means:

• T must implement Comparable of T or some supertype of T
• Handles wrapper classes correctly since:
  • Integer implements Comparable<Integer>
  • Classes with indirect implementations like ScheduledFuture<V> which implements Comparable<Delayed>

Comparison with simpler version:

• <E extends Comparable<E>> - Works only for types that directly implement Comparable of themselves
• <T extends Comparable<? super T>> - Works for direct implementers AND classes that implement Comparable of their supertype

To support a wider range of types, always prefer the more flexible recursive bound with the wildcard.

Never use bounded wildcard types as return types because:

1. It forces clients to use wildcards in their code, propagating complexity outward
2. Return types should provide precise, usable types to clients
3. It reduces the API's clarity and increases mental burden for users
4. It prevents direct use of returned values in many contexts

Problematic example:

// Bad design - wildcard in return type
public static Set<? extends Number> getNumbers() {
    // implementation
}

// Client code now forced to use wildcards
Set<? extends Number> numbers = getNumbers();
// Can't add to the set!
// numbers.add(Integer.valueOf(42)); // Compile error

Correct approach:

// Good design - precise return type
public static <T extends Number> Set<T> getNumbers() {
    // implementation
}

// Client code is simpler
Set<Number> numbers = getNumbers();
numbers.add(Integer.valueOf(42)); // Works fine

The API should encapsulate the complexity of generics and provide clean interfaces for clients.

The problem occurs because:

1. Varargs create an array behind the scenes
2. Arrays are reified (retain runtime type information)
3. Generics use type erasure (lose type information at runtime)
4. This mismatch creates possible type safety violations

When a varargs parameter has a generic type:

• At compile time: Treated as T[]
• At runtime: Created as Object[] due to type erasure
• This discrepancy between declared and actual types can lead to ClassCastExceptions

Example of problematic code:

static <T> T[] pickTwo(T a, T b, T c) {
    T[] result = (T[]) new Object[2]; // Unsafe cast!
    result[0] = a;
    result[1] = b;
    return result; // Returns Object[] when T[] was promised
}

Java doesn't prohibit this combination because:

1. It would break backward compatibility
2. Many common and useful patterns rely on this combination
3. With care, these methods can be implemented safely
4. The @SafeVarargs annotation allows marking known-safe methods

The compromise is to permit the combination but issue warnings about potential heap pollution, which can be suppressed with @SafeVarargs when the developer confirms safety.

Eligibility for @SafeVarargs

A method with generic varargs is eligible for @SafeVarargs when:

• It doesn't store anything in the varargs parameter array
• It doesn't expose the array (or a clone) to untrusted code
• The method cannot be overridden

Eligible Method Types

• Static methods
• Final instance methods
• Private instance methods (since Java 9)
• Constructors (since Java 9)

Alternative Approach: Using List Instead of Varargs

// Instead of:
@SafeVarargs
static <T> List<T> flatten(List<? extends T>... lists) { ... }

// Use:
static <T> List<T> flatten(List<List<? extends T>> lists) {
    List<T> result = new ArrayList<>();
    for (List<? extends T> list : lists)
        result.addAll(list);
    return result;
}

Tradeoff Comparison

| @SafeVarargs Approach | List Parameter Approach | |---|---| | ✅ More concise client code | ❌ More verbose: flatten(List.of(list1, list2)) | | ✅ Consistent with Java idioms | ✅ Compiler-verified type safety | | ❌ Requires manual verification | ✅ No heap pollution possibility | | ❌ Limited to non-overridable methods | ✅ No unchecked warnings | | ❌ Can't be used for methods returning arrays | ❌ Extra wrapper object overhead |

Note: Choose the List approach when in doubt about safety or when method doesn't meet @SafeVarargs eligibility requirements. Use @SafeVarargs when client code conciseness is important and you can guarantee type safety.

Heap Pollution: A situation where a variable of a parameterized type refers to an object that is not of that parameterized type, compromising Java's generic type safety system.

Primary Causes:

1. Mixing raw types with generics:

   List rawList = new ArrayList();
   rawList.add(42);         // Unchecked call
   List<String> stringList = rawList;  // Unchecked assignment
   String s = stringList.get(0);  // ClassCastException at runtime

2. Generic Varargs Methods (Key risk area):

   static <T> T[] toArray(T... args) {
       Object[] array = args;  // Valid
       array[0] = new Object(); // Type safety compromised
       return args;  // Exposing polluted array to caller
   }

Why Varargs Are Particularly Problematic:

• Java implements varargs by creating an array at runtime
• With generics, this creates an array of the erased type
• Type information doesn't exist at runtime due to erasure
• The array could potentially store incompatible types
• Compiler cannot guarantee type safety across method boundaries

Consequences:

• Runtime ClassCastExceptions in seemingly type-safe code
• Bugs that manifest far from their actual cause
• Unpredictable behavior (works in testing, fails in production)

Prevention Best Practices:

1. Use @SafeVarargs annotation on methods that properly handle generic varargs
2. Never store elements of types not compatible with the varargs parameter type
3. Don't expose the varargs parameter array to clients
4. Avoid returning the varargs parameter array directly
5. Consider using collection parameters instead of varargs
6. Minimize suppressing unchecked warnings

Example of Safe Implementation:

@SafeVarargs // Proper annotation
static <T> List<T> asList(T... elements) {
    List<T> result = new ArrayList<>();
    for (T element : elements) {
        result.add(element);  // Safe copying
    }
    return result;  // Return new collection, not the array
}