Generic Types and Algorithms, Part I

Introduction

This tutorial will introduce into generic typing. We will use it to build a generic algorithm to represent and process some data structures. To get accustomed with the basics I will show how to implement a token aggregator. Then we move on to implement a generic class that provides common data structures and methods to build and process an  arbitry binary tree structure. That generic class should provide the algorithms like tree traversal, listing leafs and their paths and a getters for the actual tree size and depth.

Generic types and classes

Classes define data structures and the algorithms to process them. Generic classes can expose these algorithms for different data types. Such classes were introduced with Java 1.5 in JSR-14 and are said to have a generic type. They are defined in a generic type declaration like class name<T1, T2, …, Tn> The angle brackets (<>) enclose the type parameter section. The type parameter Tn can be understood as type variables. By convention single uppercase letters are used to represent these type variables. Most commonly used type parameter names are:

  • E – Element (e.g. used by the Java Collections Framework)
  • K – Key
  • N – Number
  • T – Type
  • V – Value

Anyhow in a more specific application environment, it may make sense to use also multicharacter type variables, e.g. representing names of abstract super classes.

POJO Sample Class Aggregator_ng

To get into a first touch with a generic class I define a class Aggregator which is feed by a stream of tokens simple by adding them in sequence to the class. Identical tokens in a sequence will consumed only by incrementing the overall token count. All changes in the token streams should be detected and change count and the token sequence list should be updated. When token stream is a stream of integers, a class like Aggregator_ng will do the job:

package ch.lpno.generics;
import java.util.ArrayList;

/**
 * Copyright 2012 by Othmar Lippuner - Knowledgeshare Consulting; Switzerland
 * Aggregator can be feed by a stream of comparable tokens of type <T>
 * Each time the tokenvalue changes
 */
public class Aggregator_ng {

	int tokenCount;
	int changeCount;
	Integer previousToken;
	ArrayList<Integer> changeFlow;

	public int getTokenCount() {return tokenCount;}
	public int getChangeCount() {return changeCount;}
	public int getPreviousToken() {return previousToken;}
	public Integer getChangeFlow(int index) {return changeFlow.get(index);}

	public Aggregator_ng() {
          tokenCount = 0;
          changeCount = 0;
          previousToken = null;
	  changeFlow = new ArrayList();}

	void add(Integer token) {
		tokenCount +=1;
		if (!token.equals(previousToken) ) {
			changeCount += 1;
			changeFlow.add(token);
		}
		previousToken = token;
	}

}

You can testrun the class with this main stub:

public static void main(String[] args) {
	test_generic();
	//test_Pojo();
}
private static void test_Pojo() {
	Aggregator_ng ang = new Aggregator_ng();
	ang.add(2);ang.add(2);ang.add(2);ang.add(2);
	ang.add(3);ang.add(3);ang.add(3);
	ang.add(4);ang.add(4);
	ang.add(2);

	System.out.println("ang #tokenchanges:" + ang.getChangeCount());
	for (int i = 0; i < ang.changeCount;i++) {
		System.out.println("   ang #tokenchange"+i+": " +
                ang.getChangeFlow(i));

	}

}


Such a class may be further developed to be a helper for interpreting and processing the group changes in a sorted multicolumn table. Besides integer columns there also may be columns with String, Timestamps and others. In a non-generic approach, we would have to implement different classes for all needed different data types. The generic approach makes it possible to define one generic class with generic algorithms (aka methods)  to that job for all the different data types.

Generic Sample Class Aggregator

We will not transform the Aggregator class to be a generic class, by adding the type parameter <T>. Inside the class we use the type parameter T as if it was any primitive type or class. As this we get the generic class code:  


package ch.lpno.generics;
import java.util.ArrayList;

/**
 * Copyright 2012 by Othmar Lippuner - Knowledgeshare Consulting; Switzerland
 * http://www.knowledgeshare-consulting.ch/
 * Aggregator can be feed by a stream of comparable tokens of type <T>
 * Each time the tokenvalue changes
 */
public class Aggregator<T> {
	int tokenCount;
	public int getTokenCount() {return tokenCount;}
	public int getChangeCount() {return changeCount;}
	public T getPreviousToken() {return previousToken;}
	public T getChangeFlow(int index) {return changeFlow.get(index);}

	int changeCount;
	T previousToken;
	ArrayList<T> changeFlow;

	public Aggregator() {
		tokenCount = 0;
		changeCount = 0;
		previousToken = null;
		changeFlow = new ArrayList<T>();
	}

	void add(T token) {
		tokenCount +=1;
		if (!token.equals(previousToken) ) {
			changeCount += 1;
			changeFlow.add(token);
		}
		previousToken = token;
	}
}


While coding with generic types, the IDE (Eclipse) will support us with generics in the template proposals for code expansion:

Picture: Eclipse code template expansion of generic type

Such a class may be further developed to be a helper for interpreting and processing the group changes in a sorted multicolumn table. In contrast to the non generic approach, where we have to maintain different classes for each type used, these further code changes develop in one single spot your generic class code.

Generic Class Invocation

To use a generic class and process it’s given generic function you have to instantiate it. You do this with a generic type invocation, which replaces T with a concrete data type such as Integer or String. With the type invocation you pass a type argument to the class. The type argument <Integer> replaces the type parameter <T>, thus instead of Aggregator<T> we write Aggregator<Integer>. To test the class I will create two aggregators. A string aggregator will be fed with a sequence of string tokens. A integer aggregator will be fed with a sequence of int numbers.


private static void test_generic() {
	Aggregator<Integer> ai = new Aggregator<Integer>();
	Aggregator<String> as = new Aggregator<String>();
	ai.add(2);ai.add(2);ai.add(2);ai.add(2);
	ai.add(3);ai.add(3);ai.add(3);
	ai.add(4);ai.add(4);
	ai.add(2);

	as.add("This" );as.add("This" );as.add("This" );as.add("This" );
	as.add("is a" );as.add("is a" );as.add("is a" );
	as.add("string tokenstream" );as.add("string tokenstream" );
	as.add("and that" );

	System.out.println("ai #tokenchanges:" + ai.getChangeCount());
	for (int i = 0; i < ai.changeCount;i++) {
		System.out.println("   ai #tokenchanges:" + ai.getChangeFlow(i));
	}

	System.out.println("as #tokenchanges:" + as.getChangeCount());
	for (int i = 0; i < as.changeCount;i++) {
		System.out.println("   as #tokenchanges:" + as.getChangeFlow(i));
	}
}


The power of generic programming is show not only show when invoking generic classes with application specific class types, but already while coding. The IDE reads the invoking type information and fully provides it in code proposal and expansion:

Picture: Eclipse code template expansion of generic type after invokation with type arguement

Note the type information in variable ai is Integer now and nomore T as it is in the generic class.

Conclusion

We had a quick introduction into generic typing of classes and methods. In the next part of this tutorial we will learn how to implement a more complex sample. A generic binary tree package, that defines a binary tree structure for arbitrary data types and some commonly used methods to process them.

One thought on “Generic Types and Algorithms, Part I

  1. Note there wasan issue with the syntaxhighlighter with


    public class Aggregator <T>
    is filter to
    public class Aggregator

    This severly mutilated the correct rendering of the code samples above. This issue is posted and a solution is on the way.
    A first (temporary) solution has been establised at 13.9.2010. The rendering should now be correct.

    regards
    Othmar Lippuner

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>