Archive for April, 2013

This is a continuation of an introductory Generics tutorial, previous part of which can be found here.

Generics Instantiation Syntax

In the previous post we have learned how to declare a generic class. We have also learned its formal definition. Now it’s time to learn how to create instances of the generic class, formally.

To create an instance of a generic type, we do generic type invocation, which replaces the type parameter with a concrete type. We have seen multiple examples of this in the previous article. Remember our MyPrettySimpleGenericClass from the previous post? If you don’t, here is the definition –

public class MyPrettySimpleGenericClass<E> {

    private E item;

    public void setItem(E item) {
        this.item = item;
    }

    public E getItem() {
        return item;
    }

    public void printItem() {
        System.out.println(item.toString());
    }

Then, to create an instance of this class, we do the following –

MyPrettySimpleGenericClass<Integer> item = new
    MyPrettySimpleGenericClass<Integer>;

In the above code, we have performed a generic type invocation by replacing the type parameter with a concrete type Integer, which makes this object to work with all the integer values. We call Integer a type argument in this case. An invocation of a generic type in this way creates what we call a parameterized type. Our parameterized type in this case is MyPrettySimpleGenericClass<Integer>.

You can pass any non-primitive type as a type argument. You can even pass another parameterized type too, because they are also non-primitive. Consider the following example –

MyPrettySimpleGenericClass<List<Integer>> item = new
    MyPrettySimpleGenericClass<List<Integer>>();

In the above example, the type parameter is another parameterized type, which was obtained by parameterizing the List<E> generic interface (it’s part of the standard Java API, specifically the Collection API and I intend to write something about them too!).

You can see that this generic method invocation thingy looks somewhat similar to method invocation, except that during a method invocation you pass values as arguments (yes, Java is pass-by-value, and if you are wondering about it, please have patience as I intend to write a post about it in future), and here you pass types as arguments.

Now, some of you might be wondering about the constructor syntax of a generic type, after seeing the <Integer> part right before the parentheses in the above code. Do we also have to put type parameters in the constructor of a generic type?

Short answer – No. You declare a constructor of a generic type like any other constructor. You don’t need to put a type parameter right before the constructor parentheses (in fact you’ll get a compilation error if you try something like that) – putting it right after the class name is enough, unless your constructor itself is a Generic Method (I promise I won’t run away until I write a post about it) which introduces a new type parameter!

In JDK 7 and later, you can omit the type argument during the invocation of the constructor of the generic type, provided that the compiler can determine, or infer (yes, Type Inference will be coming up in a future post), the type argument from the context. Taking advantage of this feature, we can modify our previous object instantiation in the following way –

MyPrettySimpleGenericClass<Integer> item = new
    MyPrettySimpleGenericClass<>();

This pair of angle brackets, right before the parentheses, is conventionally known as the diamond. It’s of great convenience when writing generics  as you have to type less.

Enough theoretical stuff. Let’s put all these things together and write something useful, because the best way to learn something is by actually doing it.

A Useful Example – Implementing a Generic Stack

In this example, we will build a Stack. This stack will be generic – we will use it for different types of items based on different type arguments.

Let’s see the declaration of our Stack class –

import java.util.NoSuchElementException;

public class Stack<E> {
    private long size;
    private long count;
    private StackElement top;

    private class StackElement {
        private E element;
        private StackElement next;
    }

    public Stack() {
        this(Long.MAX_VALUE);
    }

    public Stack(long size) {
        this.size = size;
        this.count = 0;
    }

    public long getSize() {
        return size;
    }

    public long getCount() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return getCount() == size;
    }

    public void push(E element) throws UnsupportedOperationException {
        if (isFull()) {
            throw new UnsupportedOperationException("Push operation is " +
                "not supported on full stack");
        }

        StackElement elem = new StackElement();
        elem.element = element;
        elem.next = top;
        top = elem;
        count++;
    }

    public E pop() throws NoSuchElementException{
        if (isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }

        StackElement topElement = top;
        top = top.next;
        count--;

        return topElement.element;
    }

    public E peek() throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }

        return top.element;
    }
}

Some points about the above stack implementation –

  1. We generally use arrays to store stack elements. This approach won’t work here, because we cannot create an array of generic types. Instead, we will be using the Linked List implementation.
  2. We have created an inner class to represent a linked list element. This is a perfect example of when an inner class should be used. We wanted to make a type which will store an element of type E, and will also hold a reference to the next element. If we make it a top-level class, we won’t be able to access the type parameter E from it. So, we needed a type which will have access to internal information of another type. As a result, we use an inner class (yes, more on inner classes will come next, in the near future, perhaps within the next ten years…..hmmmmmm……..).
  3. Notice that we have declared our inner class as private. If we don’t declare it as such, then it may also be accessed from outside Stack, thus leaking our implementation detail in the outside world.
  4. Notice the declaration of pushpop and peek method. The first one throws an UnsupportedOperationException if an element is pushed while the stack is full, and the last two throws a NoSuchElementException when these operations are done in an empty stack. Some might think of using other exception classes, or building their own with more customization. As for this example, it’s a simple one, so I will be using these two.

Ok, now let’s see a simple test drive –

public class Main {
    public static void main(String[] args) {
        Stack<Integer> intStack = new Stack<>();
        intStack.push(10);
        intStack.push(20);
        intStack.push(30);
        while(!intStack.isEmpty()) {
            System.out.println(intStack.pop());
        }

        Stack<Double> doubleStack = new Stack<>();
        doubleStack.push(10.5);
        doubleStack.push(20.34);
        doubleStack.push(30.56);
        while(!doubleStack.isEmpty()) {
            System.out.println(doubleStack.pop());
        }

        Stack<String> stringStack = new Stack<>();
        stringStack.push("Hello");
        stringStack.push("to");
        stringStack.push("Generics!");
        while(!stringStack.isEmpty()) {
            System.out.println(stringStack.pop());
        }
    }
}

See how we are using our stack for different types? Aren’t generics awesome 😀 ?

Play with it as long as you want. Tweak the example in as many ways as you like. Try creating an Integer stack and pushing a string into it. Do it the other way round. See what errors/exceptions you get. Also, try to implement other data structures, like Queue, with generics. See how awesome they become!

I have put this implementation in my github repository along with couple of simple test cases (yes, if it was a production quality code, there would have been more and more test cases), in case anyone wants to play with it.

And this is where I’d like to finish the second part. Hope to see you soon!

Advertisements

Generics play an important role in the development of Java applications. They provide stronger type checks at compile time, reduce the amount of typecasting needed and help to develop algorithms/procedures that can be reused for multiple types. In this series I will try to write a short tutorial about them.

A typical Generics Use Case – Implementing a Sorting Algorithm

Rather than learning generics by definition, let’s try learning it from one simple use case – implementing Insertion Sort.

We all know how Insertion Sort works. We are given an array of elements. Then the algorithm removes one element from the array, repeat over the existing ones, find the appropriate place for the removed element, and then inserts it there.

Let’s consider a simple implementation of this program in Java –

public class InsertionSort {
  private int[] elements;

  public int[] getElements() {
      return elements;
  }

  public void setElements(int[] elements) {
    this.elements = elements;
  }

  public void sort() {
    if (this.elements == null || this.elements.length <= 1) {
      return;
    }

    int i;
    for (i = 1; i <= elements.length - 1; i++) {
      int valueToInsert = elements[i];
      int holePos = i;

      while (holePos > 0 && valueToInsert < elements[holePos - 1]) {
        elements[holePos] = elements[holePos - 1];
        holePos--;
      }

      elements[holePos] = valueToInsert;
    }
  }
}

The above class implements a simple insertion sort algorithm. To sort an array of elements, we can use this class in the following way –

public class Main {
  public static void main(String[] args) {
    int[] elements = {3, 7, 4, 9, 5, 2, 6, 1};
    InsertionSort insertionSort = new InsertionSort();
    insertionSort.setElements(elements);
    insertionSort.sort();
    elements = insertionSort.getElements();

    // print the sorted array
    System.out.println();
    for (int i = 0; i < elements.length; i++) {
      System.out.print(elements[i]);

      if (i + 1 != elements.length) {
        System.out.print(", ");
      }
    }
    System.out.println();
  }
}

Now what if we want to sort array of floats, or doubles? Or, array of some custom objects? Can we use the above implementation for those cases?

No. Period.

The above algorithm only sorts simple integers. It cannot sort doubles, or floats, because in Java you cannot pass array of doubles to a method which expects an array of integer. So, if you want to sort doubles or floats, you’ll have to write another implementation which will then sort an array of doubles.

This approach has some serious drawbacks. For one, you’ll now have to maintain two different sorting algorithms, just to ensure that they operate on different types, even though the algorithm to sort them is exactly the same. From the principles of good Object Oriented Design, we know that this is bad, really really bad.

So, how can we change this implementation so that it works for doubles, or better yet, works for any types which can be compared with each other? Let’s pause for a moment here and try to think it by ourselves.

Really, don’t go read the next section. Thinking about why we need, or should use a language feature will help us to truly master it and use it effectively in our application.

Generics to the Rescue!

Ok, so you thought it through, right? If this is the case, then carry on!

What we will do is that we will somehow parameterize the above class so that it will now take types as its argument. This way, we will pass a new type as its argument whenever we will create a new instance of this class, which will then enable us to use the above algorithm for that type!

This is exactly what generics do! They enable types to be parameters when defining classes, interfaces and methods! From the official Oracle Java tutorial page

In a nutshell, generics enable types (classes and interfaces) to be parameters when defining classes, interfaces and methods. Much like the more familiar formal parameters used in method declarations, type parameters provide a way for you to re-use the same code with different inputs. The difference is that the inputs to formal parameters are values, while the inputs to type parameters are types.

Let’s see the implementation first, then we will slowly understand how to write generics in the code and what syntax to use –

public class InsertionSort<E extends Comparable<E>> {
  private E[] elements;

  public E[] getElements() {
    return elements;
  }

  public void setElements(E[] elements) {
    this.elements = elements;
  }

  public void sort() {
    if (this.elements == null || this.elements.length <= 1) {
      return;
    }

    for (int i = 1; i <= elements.length - 1; i++) {
      E valueToInsert = elements[i];
      int holePos = i;

      while (holePos > 0 && valueToInsert.compareTo(elements[holePos - 1]) < 0) {
        elements[holePos] = elements[holePos - 1];
        holePos--;
      }

      elements[holePos] = valueToInsert;
    }
  }
}

Now, let’s dissect the above implementation to understand the syntax of generics –

  1. Take a look at the first line, the class declaration. Notice the extra <E extends Comparable<E>> part which is new? This is the part which adds generic behavior to the previous implementation. Here, E is the type parameter. We will go into the syntax details in the next section.
  2. Take a look at the elements declaration. After you declare a type parameter in the class declaration, you can then use it to declare a reference of that type. In our case, it’s an array.
  3. Similarly, our setter and getter now takes and returns array of type E, respectively.
  4. Take a look at the condition check inside the while loop, in the sort method. It has been changed to use the implementation of the Comparable interface. Keep a note of this because it will be explained in a later post.

and voila! With the above changes we can now use this class for lots of different types, provided that they all are of non-primitive types (yes, Generics don’t support primitive types) and implement the Comparable interface (this is to make sure that the elements can be compared with each other).

A sample use of the above class is as follows –

public class Main {
  public static void main(String[] args) {
    /**
     * Use the object wrapper for integer, because
     * generics don't support native types. The
     * following line will work due to Autoboxing.
     */
    Integer[] arr = {3, 7, 4, 9, 5, 2, 6, 1};

    /**
     * Check out the following line. It demonstrates
     * the way to pass type arguments to the
     * type parameters.
     */
    InsertionSort<Integer> sort = new InsertionSort<Integer>();
    sort.setElements(arr);
    sort.sort();
    arr = sort.getElements();

    System.out.println();
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i]);

      if (i + 1 != arr.length) {
        System.out.print(", ");
      }
    }
    System.out.println();

    /**
     * Let's use the implementation for
     * doubles!
     */
    Double[] anotherArray = {3.5, 7.2, 4.4, 9.45, 5.01, 2.50, 6.9, 1.11};
    InsertionSort<Double> anotherSort = new InsertionSort<Double>();
    anotherSort.setElements(anotherArray);
    anotherSort.sort();
    anotherArray = anotherSort.getElements();

    System.out.println();
    for (int i = 0; i < anotherArray.length; i++) {
      System.out.print(anotherArray[i]);

      if (i + 1 != anotherArray.length) {
        System.out.print(", ");
      }
    }
    System.out.println();
  }
}

Cool, eh 😀 ?

Generics Declaration Syntax

To declare a class as a generic one, we use the following format –

class name<T1, T2, ..., Tn> { /* ... */ }

The portion delimited by angle brackets in the type parameter section where you define the type parameters (they are also called type variables sometimes). The above declaration specified n type parameters – T1, T2, ….., Tn, and is called a generic type declaration. A type variable can be anything – any class type, interface, array or anything else, provided that it’s a non-primitive type.

After you declare a class in the above way and specify a type parameter, you can then use it like any other type inside that class, subject to the following conditions –

  1. You cannot create an instance of a type parameter.
  2. You cannot declare any static field whose type matches a type parameter.
  3. You cannot typecast or use instanceof operator with type parameters.
  4. You cannot catch or throw objects of parameterized types.

I know that the example I’ve provided looks more complex than the simple declaration syntax above. Keep your patience, I will certainly explain it in a future post (if I don’t, you are given the permission to poke me with a stick).

Let’s see another simple declaration of a generic class –

public class MyPrettySimpleGenericClass<E> {
  private E item;

  public void setItem(E item) {
    this.item = item;
  }

  public E getItem() {
    return item;
  }

  public void printItem() {
    System.out.println(item.toString());
  }
}

and a simple use case –

public class Main {
  public static void main(String[] args) {
    MyPrettySimpleGenericClass<Integer> item = new
        MyPrettySimpleGenericClass<Integer>();
    item.setItem(20);
    item.printItem();               // prints 20 to the console

    MyPrettySimpleGenericClass<Double> anotherItem = new
        MyPrettySimpleGenericClass<Double>();
    anotherItem.setItem(39.60);
    anotherItem.printItem();        // prints 39.60 to the console
  }
}

So now we’ve seen a simple use case of Generics. Thankfully that wasn’t too complex to understand.

That’s it for today, folks. Hopefully I will write the next post of this series pretty soon. If anything in the current post seems difficult to understand, or if you find any errors, please feel free to comment in!