Saturday, October 30, 2010

List of interface and classes in collections

Covering the interface one by one
Covering the classes
  • HashSet and TreeSet Classes
  • ArrayList and LinkList Classes
  • HashMap and TreeMap Classes
  • Vector and Stack classes

Thursday, October 28, 2010

Class Objects as Type Literals

Class objects can be used as type specifications too, at runtime. For instance, you can create a generified method like this:

public static <T> T getInstance(Class<T> theClass)
throws IllegalAccessException, InstantiationException {

return theClass.newInstance();

Here are a few examples of calls to the getInstance() method:

String string   = getInstance(String.class);

MyClass myClass = getInstance(MyClass.class);

As you can see the return type changes depending on what class object you pass in as parameter to the method. This can be quite handy in database API's like Butterfly Persistence where you read objects from a database. Here is an example method definition:

public static <T> T read(Class<T> theClass, String sql)
throws IllegalAccessException, InstantiationException {

//execute SQL.

T o = theClass.newInstance();
//set properties via reflection.

return o;

Here is how you would call the read() method:

Driver employee   = read(Driver.class, "select * from drivers where id=1");

Vehicle vehicle = read(Vehicle.class, "select * from vehicles where id=1");

Upper Bounded Wildcards in generics

Suppose we want to write a generic method which takes a list and print it only when it contains elements subclassing one particular class. So here we need upper bound.
It is possible to set the upper bound of the wildcard like this:
List<? extends Vehicle> vehicles = new ArrayList<? extends Vehicle>();    

In this example I have specified the upper bound to be the class Vehicle. I can now define the printElements() method like this:

public void printElements(List<? extends Vehicle> elements){
   for(Vehicle o : elements){

As you can see it is now safe to cast each element in the list to a Vehicle, as it is done by the new for loop inside the method.
Furthermore, it is now safe to call the method using a List<Car> instance, provided that Car extends Vehicle. Here is an example:
List<Car> elements = new ArrayList<Car>
// ... add Car elements to the list.

But, even when using a wildcard with an upper bound it is not safe to write to the List. After all, a Car is always a Vehicle, but a Vehicle is not always a Car.

The type parameterization <? extends E> is called an "upper bounded wildcard" because it defines a type that could be any type so long as it is bounded by the superclass E. It provides covariant relationship such that the referenced object's (eg. Car ) type parameter is a subclass ofVehicle's type parameter

Wildcards in Generics

We just saw here about generic methods. But how generic are they?
Suppose we have to write a generic method which takes list of elements and prints elements onto screen. Element can be String, Integer,Object...So one can think of using object as type parameter. But this will be a mistake. See here for this.
So solution is wildcards.


The wildcard operator is a solution to the problem explained above.
The character '?' is a wild-card character and it stands for any Java type. It can be java.lang.Object type or some other type. It is just a place-holder that tells that it can be assigned with any type. Considering this case, the following are now valid syntaxes. 

List<?> anyObjects = null; 
List<Integer> integers = new ArrayList<Integer>();
anyObjects = integers;
List<Double> doubles = new ArrayList<Double>();
anyObjects = doubles;

Here is how you write a generic List using the wildcard operator:

List<?> listOfUnknown = new ArrayList<?>();    

Generic method using wildcards
We can now define the printElements() method like this:

public void printElements(List<?> elements){
   for(Object o : elements){
You can call the printElements() with any generified List instance. For instance:
List<String> elements = new ArrayList<String>
// ... add String elements to the list.

When you upcast a List<String> to a List<?> you can now read all elements of the List<?> safely as Object instances. But you still cannot insert elements into the List<?>. The ? could represent any type, and thus it would be possible to insert types that did not match the original definition of the List.

Generics and Subtyping

Let’s test our understanding of generics. Is the following code snippet legal?

List<String> ls = new ArrayList<String>(); //1
List<Object> lo = ls; //2

Line 1 is certainly legal. The trickier part of the question is line 2. This boils down
to the question: is a List of String a List of Object. Most people’s instinct is to answer:
Well, take a look at the next few lines:

lo.add(new Object()); // 3
String s = ls.get(0); // 4: attempts to assign an Object to a String!

Here we’ve aliased ls and lo. Accessing ls, a list of String, through the alias lo, we
can insert arbitrary objects into it. As a result ls does not hold just Strings anymore,
and when we try and get something out of it, we get a rude surprise.
The Java compiler will prevent this from happening of course. Line 2 will cause a
compile time error.
In general, if Foo is a subtype (subclass or subinterface) of Bar, and G is some
generic type declaration, it is not the case that G<Foo> is a subtype of G<Bar>.
This is probably the hardest thing you need to learn about generics, because it goes
against our deeply held intuitions.
So we had list of String not subtype of list of Objects.

The problem with that intuition is that it assumes that collections don’t change.
Our instinct takes these things to be immutable.
For example, if the department of motor vehicles supplies a list of drivers to the census
bureau, this seems reasonable. We think that a List<Driver> is a List<Person>,
assuming that Driver is a subtype of Person. In fact, what is being passed is a copy
of the registry of drivers. Otherwise, the census bureau could add new people who are
not drivers into the list, corrupting the DMV’s records.
In order to cope with this sort of situation, it’s useful to consider more flexible
generic types. The rules we’ve seen so far are quite restrictive.

Generic classes in java vs templates in C++

Here is a small excerpt from the definitions of the interfaces List and Iterator in package :
public interface List<E> {
  void add(E x);
  Iterator<E> iterator();
public interface Iterator<E> {
  E next();
  boolean hasNext();

This should all be familiar, except for the stuff in angle brackets. Those are the
declarations of the formal type parameters of the interfaces List and Iterator.
Type parameters can be used throughout the generic declaration, pretty much where
you would use ordinary types (though there are some important restrictions.

In the introduction, we saw invocations of the generic type declaration List, such
as List<Integer>. In the invocation (usually called a parameterized type), all occurrences of the formal type parameter (E in this case) are replaced by the actual type argument (in this case, Integer).

You might imagine that List<Integer> stands for a version of List where E has been uniformly replaced by Integer:
public interface IntegerList {
  void add(Integer x);
  Iterator<Integer> iterator();

This intuition can be helpful, but it’s also misleading.
It is helpful, because the parameterized type List<Integer> does indeed have methods that look just like this expansion.
It is misleading, because the declaration of a generic is never actually expanded in this way. There aren’t multiple copies of the code: not in source, not in binary, not on disk and not in memory. If you are a C++ programmer, you’ll understand that this is very different than a C++ template.

A generic type declaration is compiled once and for all, and turned into a single class file, just like an ordinary class or interface declaration. Type parameters are analogous to the ordinary parameters used in methods or constructors. Much like a method has formal value parameters that describe the kinds of values it operates on, a generic declaration has formal type parameters. When a method is invoked, actual arguments are substituted for the formal parameters, and the method body is evaluated.
When a generic declaration is invoked, the actual type arguments are substituted for the formal type parameters.

The Motivation for Generics : dealing with casting of objects

Consider the following code:
List myIntList = new LinkedList(); // line no. 1
myIntList.add(new Integer(0)); // line no. 2
Integer x = (Integer) myIntList.iterator().next(); //line no. 3

The cast on line 3 is slightly annoying. Typically, the programmer knows what kind of data has been placed into a particular list. However, the cast is essential. The compiler can only guarantee that an Object will be returned by the iterator.
To ensure the assignment to a variable of type Integer is type safe, the cast is required.
Of course, the cast not only introduces clutter, it also introduces the possibility of a run time error, since the programmer might be mistaken.

Removing the cast
What if programmers could actually express their intent, and mark a list as being restricted to contain a particular data type?
This is the core idea behind generics.
Here is a version of the program fragment given above using generics:

List<Integer> myIntList = new LinkedList<Integer>(); // 1’
List<Integer> myIntList = new LinkedList(); // 1’

myIntList.add(new Integer(0)); //2’
Integer x = myIntList.iterator().next(); // 3’

Now, you might think that all we’ve accomplished is to move the clutter around.

Instead of a cast to Integer on line 3, we have Integer as a type parameter on line 1’. However, there is a very big difference here. The compiler can now check the type correctness of the program at compile-time. When we say that myIntList is declared with type List<Integer>, this tells us something about the variable myIntList, which holds true wherever and whenever it is used, and the compiler will guarantee it. In contrast, the cast tells us something the programmer thinks is true at a single point in the code.

The net effect, especially in large programs, is improved readability and robustness.

A big big note on Generics
Generics provides a sort of a syntactic sugar that might spare you some casting operation. But behind the scenes, after compilation the byte code is same. See Type Erasure with Generics to see how.

Pattern and Matcher

In addition to the regular expression methods that are available in the String class (see String Regular Expressions), there are two classes that are specifically user for regular expression matching.

  • java.util.regex.Pattern precompiles regular expressions so they can be executed more efficiently. It also has a few utility functions. This same pattern can be reused by many Matcher objects.
        Pattern pat = Pattern.compile(regexString);

  • java.util.regex.Matcher objects are created from a Pattern object and a subject string to scan. This class provides a full set of methods to do the sacnning.
        Matcher m = pat.matcher(subject);

Common methods

The following variables represent elements of their declared type in the prototypes below.

import java.util.regex.*;
. . .
boolean b; // may be used in if statement.
int i; // index or character position.
int g; // group number
int n; // number of groups
CharSequence cs; // effectively either String or StringBuffer
String s; // Subject string.
String regex; // Regular expression string.
StringBuffer sb; // Used to build up string from repeated scans.
Pattern p = Pattern.compile(regex); // Compiles regular expression into Pattern.
Matcher m = p.matcher(s); // Creates Matcher with subject s and Pattern p.


Creating a Pattern

p =
Creates Pattern based on regex. May throw PatternSyntaxException.

p =
Pattern.compile(regex, f);
As above. Flag f can be Pattern.CASE_INSENSITIVE, ....

Finding pattern matches

b =
True if pattern can be found in the subject string. First call starts trying at beginning of string. Subsequent calls start after last character previously matched, which makes it good for a while loop.

b =
True if pattern can match somewhere at or after position i.

b =
True if pattern matches entire subject string.

b =
Pattern.matches(regex, s);
As above, but less efficient if regex used more than once.

b =
True if pattern matches starting at first char.

Getting results of last pattern match. Corresponds to group 0, then entire match.

s =;
String which was matched.

i =
Index of first character of match.

i =
Index of last character plus 1 of match.

Getting group results of last match

s =;
String which was matched by group g.

i =
Index of first character of group g.

i =
Index of last character plus 1 of group g.

n =
Number of groups that were matched.


m =
Resets Matcher m so that next find starts at beginning.

m =
Resets Matcher m to match subject cs.

Replacing text

s =
Returns string which is subject with first match replaced by rep.

s =
Returns string with all matches replaced by rep.

Building replacement in a StringBuffer

m =
m.appendReplacement(sb, s);
When it matches, (1) everything skipped before the match is appended to the StringBuffer sb, then (2) it appends s, with "$n" replaced by group n.

sb =
Appends last part that m didn't match to StringBuffer. Useful after loop calling appendReplacement() to finish.

Other Resources

Regular Expression in Java

Regular expressions are the most common programming technique to search for patterns in strings, extracting, and replacing substrings. They are an essential part of many languages, editors, and utilities, for example, Perl, JavaScript, awk, sed, vi, ....

They are powerful and useful. Simple regexes are simple, but large regexes are extremely difficult to debug. They are often not the right solution for complex parsing problems. Two quotes illustrate some feelings about them. Despite the name, as someone said, Regular expressions are neither regular nor expressions. And Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. Regular expressions form a quirky, error-prone, terse, but useful, programming language for pattern matching.

Java, as of version 1.4, has extensive support for regular expressions in two areas.

  • additional String methods. See String Regex Methods.
  • Additional classes, java.util.Pattern and java.util.Matcher, allow use of precompiled regular expressions as well as providing many additional functions. See Pattern and Matcher.

Regular expressions provide more general mechanisms for parsing input strings than, eg, StringTokenizer.

Programming language. Regular expressions (often refereed to as regex) are essentially a programming language of their own.

Other Resources

Display Extension

This program reads in a file name and displays the extension (that last part of the name after the final dot).

import javax.swing.*;

public class FileExt {

public static void main(String[] args) {
//... Declare local variables.
String fileName; // The file name the user entered.
String extension; // The extension.

//... Input a file name and remove whitespace.
fileName = JOptionPane.showInputDialog(null, "Enter file name.");
fileName = fileName.trim();

//... Find the position of the last dot. Get extension.
int dotPos = fileName.lastIndexOf(".");
extension = fileName.substring(dotPos);

//... Output extension.
JOptionPane.showMessageDialog(null, "Extension is " + extension);

Array to String

Here is a simple, but slow, program to concatenate all of the strings in an array, each separated by a specifed string separater.

//-------------------------------------------------- arrayToString()
// Convert an array of strings to one string.
// Put the 'separator' string between each element.

public static String arrayToString(String[] a, String separator) {
String result = "";
if (a.length > 0) {
result = a[0]; // start with the first element
for (int i=1; i<a.length; i++) {
result = result + separator + a[i];
return result;

The problem with the above program is that a new String object is created each time thru the loop, and the old String object becomes eligible for garbage collection. This constant creation and abandoning objects is terribly inefficient. A more efficient way to do this is to use a StringBuffer or the equivalent Java 5 StringBuilder, which will grow as needed, but generally only has to expand a few times to do the job.

//-------------------------------------------------- arrayToString2()
// Convert an array of strings to one string.
// Put the 'separator' string between each element.

public static String arrayToString2(String[] a, String separator) {
StringBuffer result = new StringBuffer();
if (a.length > 0) {
for (int i=1; i<a.length; i++) {

return result.toString();

Change Extension (string)

Problem: Change the extension of a file name

//============================================== changeExtension
// changes extension to new extension
// example: x = changeExtension("data.txt", ".java")
// will assign "" to x.
static String changeExtension(String originalName, String newExtension) {
int lastDot = originalName.lastIndexOf(".");
if (lastDot != -1) {
return originalName.substring(0, lastDot) + newExtension;
} else {
return originalName + newExtension;
}//end changeExtension

Example - Palindrome test

//========================================================= isPalindrome
// This method returns 'true' if the parameter
// is a palindrome, a word that is spelled the
// same both forwards and backwards, eg, radar.

public static boolean isPalindrome(String word) {
int left = 0; // index of leftmost unchecked char
int right = word.length() -1; // index of the rightmost

while (left < right) {
// continue until they reach center
if (word.charAt(left) != word.charAt(right)) {
return false;// if chars are different, finished
left++; // move left index toward the center
right--; // move right index toward the center

return true; // if finished, all chars were same

This method uses two indexes that point to the left and right ends of the string. You could also write this with a for loop that goes only to the middle.

Replace word

Problem: Write a method to replaces all occurences a word in a string with another word. Assume the method signature is

   static String replaceWord(String original, String find, String replacement)

Note that Strings are immutable, so we must create a new String. The word "replace" is probably misleading. Also, the method is static because it doesn't reference instance variables. This allows some optimizations by the compiler.

A simple, but incorrect, solution

This first attempt only replaces one word, but we could fix that up later with a loop -- but it's not worth the effort because it's wrong anyway.

//--------------------------------------------- replaceWord() 
static String replaceWord(String original, String find, String replacement) {
int i = original.indexOf(find);
if (i < 0) {
return original; // return original if 'find' is not in it.

String partBefore = original.substring(0, i);
String partAfter = original.substring(i + find.length());

return partBefore + replacement + partAfter;

This example method replaces the first occurrence of a one string with another. If we execute the following code,

   t = "A great man";
s = replaceWord(t, "man", "woman");

the value in s will be "A great woman". Ok, but what if we changed the orginal string to contain the word "human", or anything else that contained a substring, but not a separate word, that has "man" in it.

   t = "A great human";
s = replaceWord(t, "man", "woman");

Now s will contain "A great huwoman". Not what was intended.

The solution is to know about "words"

Simply finding a substring isn't sufficient. There are several ways to solve the problem.

  • Check the character preceding and following the string to see if they are delimiters, and can't be part of a word, or the word boundary is at the beginning or end of the string.
  • Use java.util.StringTokenizer. This is a common solution, but has been superceded by regular expressions (see below).
  • Java 1.4 added Regular Expressions, which is the most common way to solve the problem in most other programming languages. [TO DO: Write solution using regular expressions.]

StringTokenizer solution

This replaces all occurences of a "word", not just the first.

static String replaceAllWords1(String original, String find, String replacement) {
String result = "";
String delimiters = "+-*/(),. ";
StringTokenizer st = new StringTokenizer(original, delimiters, true);
while (st.hasMoreTokens()) {
String w = st.nextToken();
if (w.equals(find)) {
result = result + replacement;
} else {
result = result + w;
return result;

This breaks the string into tokens, consisting of the text between delimiters, as well as the tokens consisting of the delimiters. The true parameter causes the delimiters to also be returned as tokens. You might not need them if you are only interested in what comes between them. Naturally, you would choose the delimiters appropriate to your problem.

Buiding a string by sucessive concatenations is inefficient, as it creates new string as it is immutable and should be replaced by StringBuilder (or the equivalent pre-Java 5 StringBuffer) for efficiency. See below.


Using StringBuilder to build a String

Creating new strings in a loop can be inefficient because of the number of new objects that are created and discarded. It's better to use a StringBuilder (introduced Java 5) or the slightly slower, synchronized, StringBuffer, which has been in Java from the beginning.

static String replaceAllWords2(String original, String find, String replacement) {
StringBuilder result = new StringBuilder(original.length());
String delimiters = "+-*/(),. ";
StringTokenizer st = new StringTokenizer(original, delimiters, true);
while (st.hasMoreTokens()) {
String w = st.nextToken();
if (w.equals(find)) {
} else {
return result.toString();
This creates a StringBuilder with an initial capacity equal to the original string. It will expand if necessary, so this initial capacity isn't critical. The append(...) method is used to add to the end of it. The toString() call at the end returns a String. This is an efficient conversion.

String to "tokens"

It's common to have to separate a string into separate "tokens". These tokens can be words, numbers, commands, or whatever. There are several ways to do this, but all of the good solutions use regular expressions.
  • String split(regex) - Probably the easiest.
  • java.util.Scanner - This can "read" from strings. Very general.
  • The java.util.regex. Pattern and Matcher use regular expressions - The most powerful solution.
  • java.util.StringTokenizer - This has been superceded by regular expressions, Scanner, and split().

Easy - String split(...) method

The easiest way to split a string into separate "tokens" is to use the split(...) method. For example,
String test = "It's the number 1 way.";
String[] tokens = test.split(" ");       // Single blank is the separator.
Produces the following output:
[It's, the, number, 1, way.]

Good - Scanner

Scanner can be used to "read" strings. Here's the previous example using Scanner, but because it doesn't produce arrays, the results are added to an ArrayList.
String test = "It's the number 1 way.";
ArrayList<String> tokens = new ArrayList<String>();
Scanner tokenize = new Scanner(test);
while (tokenize.hasNext()) {
Produces the same output as above:
[It's, the, number, 1, way.]
It doesn't care about what makes up a "token", only that they must be separated by single blanks. To allow one or more blanks as a separator, use " +", which means one or more blanks.
Scanner has numerous methods for working more generally with regular expressions to identify the token you want to read or the delimiters you want to skip.
Numbers. One advantage of using a Scanner is that you can easily switch back and forth between reading strings and numbers.

Converting Strings to Numbers

To convert a string value to a number (for example, to convert the String value in a text field to an int), use these methods. Assume the following declarations:
String s; int i;  long l;  float f;  double d;
typeExample statement
int i = Integer.parseInt(s);
long l = Long.parseLong(s);
float f = Float.parseFloat(s);
double d = Double.parseDouble(s);
If s is null or not a valid representation of a number of that type, these methods will throw (generate) a NumberFormatException. See below.

Handling NumberFormatExceptions

Put number conversions inside a try . . . catch statement so that you can do something if bad input is entered. The conversion method will throw a NumberFormatException when there is bad input. Catch the NumberFormatException, and do something to handle this error condition. Put your conversion in the try clause, and the error handling in the catch clause. Here is an example of the kind of utility function you might write to do this checking.
//--- Utility function to get int using a dialog.
public static int getInt(String mess) {
    int val;
    while (true) { // loop until we get a valid int
        String s = JOptionPane.showInputDialog(null, mess);
        try {
            val = Integer.parseInt(s);
            break;  // exit loop with valid int >>>>>>>>>>>>>>>>>>>>>>
        }catch (NumberFormatException nx) {
            JOptionPane.showMessageDialog(null, "Enter valid integer");
    return val;
}//end getInt

Non-decimal Integers

Convert integers with some base (radix) other than 10 by using these two methods. Typically these will be hexadecimal (base 16) or binary (base 2) numbers.
typeExample statement
int i = Integer.parseInt(s, radix);
long l = Long.parseLong(s, radix);
For example, to convert a string containing the hexadecimal number "F7" to an integer, call
i = Integer.parseInt("F7", 16)

Related data structure classes: EnumSet and EnumMap

The java.util.EnumSet class provides an efficient implementation of sets of enums as bit maps, or powersets as they were called in Pascal. EnumSet can also generate an Iterable for use with subsets in the for-each statement.
java.util.EnumMap provides an efficient implementation of a map for enums based on an array.

They provide a compact and efficient implementation for enum types. These collections are not synchronized and when used in multi-threaded environment, applications should take care of synchronizing the operations on the collection. EnumMap and EnumSet are homogenous collections of the same enum type. They cannot be used to operate on different enum types at the same time.

public enum Color {
public static EnumSet<Color> getPrimaryColors() {
return EnumSet.of(RED, BLUE, YELLOW);
public static EnumSet<Color> getSecondaryColors() {
return EnumSet.complementOf(getPrimaryColors());

public static void main(String[] args) {
System.out.println("Primary Colors: "+Color.getPrimaryColors());
System.out.println("Secondary Colors: "+Color.getSecondaryColors());
System.out.println("Universe: "+EnumSet.allOf(Color.class));

Convert string to enum

public enum Shape { RECTANGLE, CIRCLE, LINE } 
The valueOf() method can be used to convert a string value to an enum value. Here is an example of reading in a Shape value from a Scanner object in.
drawing = Shape.valueOf(;
drawing = Shape.valueOf("RECTANGLE") 
We can have custom methods to deal with this, if we dont want to have some extra customization.
eg. If the text is not the same to the enumeration value:
public enum Blah {

  private String text;

  Blah(String text) {
    this.text = text;

  public String getText() {
    return this.text;

  public static Blah fromString(String text) {
    if (text != null) {
      for (Blah b : Blah.values()) {
        if (text.equalsIgnoreCase(b.text)) {
          return b;
    return null;

toString() for Enums

public enum Shape { RECTANGLE, CIRCLE, LINE }
Shape drawing = Shape.RECTANGLE;   // Only a Shape value can be assigned.
System.out.println(drawing);    // Prints RECTANGLE

Override toString method for All Enums
A semicolon after the last element is required to be able to compile it. More details on overriding enum toString method can be found.
public enum Color {
WHITE, BLACK, RED, YELLOW, BLUE;  //; is required here.

@Override public String toString() {
//only capitalize the first letter
String s = super.toString();
return s.substring(0, 1) + s.substring(1).toLowerCase();

Override toString method element by element
The default string value for java enum is its face value, or the element name. However, you can customize the string value by overriding toString() method. For example,
public enum MyType {
public String toString() {
return "this is one";

public String toString() {
return "this is two";
Running the following test code will produce this:
public class EnumTest {
public static void main(String[] args) {
this is one
this is two
Another interesting fact is, once you override toString() method, you in effect turn each element into an anonymous inner class. So after compiling the above enum class, you will see a long list of class files:

Enum and their super-class

All java enum E implicitly extends java.lang.Enum. Since java doesn't allow multiple inheritance, enum types can't have superclass. They can't even extend from java.lang.Enum, nor java.lang.Object. It also means enum A can't inherit or extend enum B.

For example, the following is an invalid enum declaration:
public enum MyType extends Object {
Compiler error: '{' expected
public enum MyType extends Object {  expected
2 errors
The correct form should be:
public enum MyType {

Enum that implements interfaces

Enum can implement any interfaces. All enum types implicitly implements, and java.lang.Comparable.
public enum Color implements Runnable {

public void run() {
System.out.println("name()=" + name() +
", toString()=" + toString());
A sample test program to invoke this run() method:
for(Color c : Color.values()) {;
for(Runnable r : Color.values()) {;

Enum with additional fields and custom constructor

Enum constructors must be either private or package default, and protected or public access modifier is not allowed. When custom constructor is declared, all elements declaration must match that constructor.
public enum Color { //Color is of type enum
 WHITE(21), BLACK(22), RED(23), YELLOW(24), BLUE(25);
private int code;

private Color(int c) {
code = c;
 public int getCode() {
return code;

Switch statement on enums

public enum Shape { RECTANGLE, CIRCLE, LINE }

The switch statement was enhanced to allow a convenient use of enums. Note that the case values don't have to be qualified with the enum class name, which can be determined from the switch control value.
switch (drawing) {
    case RECTANGLE: g.drawRect(x, y, width, height);
    case CIRCLE   : g.drawOval(x, y, width, height);
    case LINE     : g.drawLine(x, y, x + width, y + height);

Formatted conversion to String

Format conversion

You can use a format, a string which tells how you want values converted to string.

Formatting numbers with %d (integers) and %f (floating point)

The basic support is in the java.util.Formatter class, where a Formatter object is created and it's format method is called. However, it's more common to use one of these convenience methods:

  • String.format(format, values...)
  • System.out.printf(format, values...) or System.err.print.

Basic format structure for three types

  • Formatting most values

  • Formating Calendar values

  • Non-argument values

Like C's printf. If you are familiar with C's printf formats, you will be very comfortable with Java's formats, although they are slightly different.

Full description of formatting

Sun's Java documentation has a full description of the formatting codes. You should download the latest version of the API documentation. Here is a link to Java version 5 documentation: .

String Related types and classes

The basic class for strings. String objects can NOT be changed.

Primitive type for 16-bit Unicode characters.

Primarily useful for its utility functions for working with characters.

StringBuffers are used to build or change strings. Conversion between String and StringBuffer is easy.

StringBuilder was added in Java 5. It is the same as StringBuilder, but slightly faster because it's unsynchronized.

Used to break a String into tokens (words).

Useful for reading and writing text files.

Pattern, Matcher
JDK 1.4 added java.util.Pattern and Matcher to do regular expression matching.

Wednesday, October 27, 2010

Collections Class

The java.util.Collections class contains static utility methods for manipulating collections.


Some useful Collections methods

Assume the following declarations have been made, where T is a class or interface type.

   int i; 
List<T> listC; // List of the Comparable objects.
List<T> list; // Any kind of list. Need not be Comparable.
Comparator<T> comp;
T key;
T t;
Collection<T> coll; // Any kind of Collection (List, Set, Deque).
Collection<T> collC; // Any kind of Collection implementing Comparable.

Rearranging - Sorting, Shuffling, . . .

Sorts listC. Elements must be Comparable<T>. Stable, O(N log N).

Collections.sort(list, comp)
Sorts list using a comparator.

Puts the elements of list in random order.

Reverses the elements of list.


i =
Collections.binarySearch(listC, key)
Searches list for key. Returns index of element or negative value if not found. See Binary Search.

i =
Collections.binarySearch(list, key, comp)
Searches in list for key using Comparator comp.

t =
Returns maximum valued Comparable object in collC.

t =
Collections.max(coll, comp)
Maximum valued object in coll using Comparator comp.

t =
Returns minimum valued Comparable object in collC.

t =
Collections.min(coll, comp)
Minimum valued object in coll using Comparator comp.

There are many additional methods in Collections, but the above are a good start.


Searching may also be implemented in data structure classes

All List and Set classes implement the contains() method, which performes a linear search on lists (O(N)), a binary search for TreeSets (O(log N)), and a hashed search for HashSets (O(1)).

Maps define get() to search for the key. For HashMaps the search is O(1), and for TreeMaps the search is O(log N).


Sorting may be implicit in a data structure class

TreeSet data and TreeMap keys are sorted at all times. They are implemented as binary trees, so insertion and search are both O(log N). An iterator can be used to get retrieve the data (TreeSets) or keys (TreeMaps) in sorted order. Either the element class must be Comparable, or a Comparator must be supplied.

Bitwise Operators - Uses

  • Efficient storage.
    • Status bits. Eg, Mouse event key mask.
    • Eg, representing Connect-Four board.
    • Packing or unpacking values into a single int/long.
      A common use of the bitwise operators (shifts with ands to extract values and ors to add values) is to work with multiple values that have been encoded in one int. Bit-fields are another way to do this. For example, let's say you have the following integer variables: age (range 0-127), gender (range 0-1), height (range 0-128). These can be packed and unpacked into/from one short (two-byte integer) like this (or many similar variations).
      //define the variables 

      int   age, gender, height;
      short packed_info;
      . . .
      // packing
      packed_info = (((age << 1) | gender) << 7) | height;
      . . .
      // unpacking
      height = packed_info & 0x7f;
      gender = (packed_info >>> 7) & 1;
      age = (packed_info >>> 8);

    • Setting flag bits
      Some library functions take an int that contains bits, each of which represents a true/false (boolean) value. This saves a lot of space and can be fast to process.

  • Efficient computation

    • On some (esp old) machines, shifting is faster than multiplying or dividing by powers of two.
      y = x << 3;        // Assigns 8*x to y.
      y = (x << 2) + x; // Assigns 5*x to y.

    • Flipping between on and off with xor

    • Sometimes xor is used to flip between 1 and 0.

      x = x ^ 1;      // Or the more cryptic x ^= 1;

      In a loop that will change x alternately between 0 and 1.

  • Problems

Bitwise Operators Summary

  • Integers (int and long) can be considered as collections of 32 or 64 bits.
  • Bitwise operators perform logical operations on each bit position, where 1 is regarded as true and zero false.
  • Bitwise and (a & b) - Result is 1 in every bit position where both operands have a 1.
  • Bitwise or (a | b) - Result is 1 only in positions where one or both operands have a 1.
  • Bitwise xor (a ^ b)- Result is 1 in positions where the two corresponding bits are different.
  • Bitwise not (~a) - Unary operator. Result is each bit of operand inverted.
  • Shift left (a << n) - Shifts bits n positions left. Zeros added on right.
  • Shift right (a >> n) - Shifts bits n positions right. High-order bit inserted on left.
  • Shift right (a >>> n) - Shifts bits n positions right. Zeros inserted at left.
  • Operator Precedence

    Precedence determines order of evaluation

    Mathematical tradition, which programming languages generally try to match, dictates that some operations are done before others (for example, multiplication and division are done before addition and subtraction).

    a+b*c is the same as a+(b*c), not (a+b)*c.

    Ever operator has a precedence (a number) associated with it. The precedence determines which operations will be performed first. Multiplication has higher precedence than addition, as illustrated in the previous example..

    Equal precedence operations generally performed left-to-right

    In addition to the precedence of each operator, the compiler also knows whether equal-precedence operators should be performed left-to-right (almost all) or right-to-left (basically only assignment).

    Parentheses can be used to control the order of evaluation

    If you have any doubt about the order of evaluation, or have a potentially confusing expression, use parentheses. Remember that one of your goals should be to make your programs as readable as possible. Use parentheses when it makes an expression easier to read, not must when they are absolutely required. Few programmers know the precedence of all operators, so it's common for extra parentheses to be used.

    Unary (one operand) versus binary (two operand) operators

    Unary operators have only one operand, for example, in

       a = -b;

    The "-" operator is the unary (one operand) operator which changes the sign of its operand.

       a = b - c

    The "-" operator is a binary (two operand) operator which subtracts c from b.

    Most unary operators are performed before binary operators (exceptions "." (qualification), "[]" (subscription), and "()" (method call).

    Example - Parentheses

    When you can work out the precedence, it's often useful to use parentheses to figure out the order of evaluation. For example, let's say you're evaluating the following expression.

     1 + 2 - 3 * 4 / 5

    Addition and subtraction are equal in precedence and lower than multiplication and division, which are equal. Form the parenthesized form and work out the values in steps.

    1. 1 + 2 - 3 * 4 / 5
    2. = (1 + 2) - ((3 * 4) / 5)
    3. = 3 - (12/5)
    4. = 3 - 2 The result of the integer division, 12/5, is 2 .
    5. = 1

    Precedence table

    This table gives the precedence of all operators. You may not be familiar with all operators, but take the advice on the right side and only learn a few precedences.

    Operator Precedence

    . [] (args) post ++ --
    ! ~ unary + - pre ++ --
    (type) new
    * / %
    + -
    << >> >>>
    < <= > >= instanceof
    == !=
    = += -= etc

    Remember only

    1. unary operators
    2. * / %
    3. + -
    4. comparisons
    5. && ||
    6. = assignments
    Use () for all others

    Alternative notation - Dataflow diagram

    Let's look at the expression x = a+b-c*d/e, which can be parenthesized as x = ((a+b) - ((c*d)/e)). Instead of parentheses, we can draw a diagram.

    This dataflow diagram shows another way to think about expression evaluation.

    Boxes represent values in memory, ovals represent operations, and arrows show the direction of data flow. The assignment operator ("=") is treated as an operator with low precedence by the compiler, but from a dataflow point of view it only moves data so it's represented as an arrow, not an operation.

    Dataflow diagrams show which operations must necessarily be performed before others, but doesn't show which are actually performed first. Java performs most operations left-to-right, so the addition would, in principle, be performed before the multiplication. I believe reordering of operations that can have no side effects is allowed, however.

    Alternative notation - Postfix - RPN

    Postfix. Altho it's not directly relevant to learning Java, there are other systems for writing expressions that don't need parentheses or precedence. Normal mathematical notation is called infix notation because the operators occur in between the operands. A common alternative is called postfix notation where the operator is written after its two operands.

    Example. For example, a+b would be written as ab+ , and x = a+b-c*d/e would be written as xab+cd*e/-=.

    RPN. This is often called Reverse Polish Notation in honor of the Polish mathematician Jan Lukasiewicz.

    Postfix notation is used in the following, among others.

    • Hewlett-Packard makes RPN calculators.
    • The Postscript printer control language is postfix.
    • The Forth programming language is RPN.
    • Java source code is translated into postfix notation!

    Bitwise Operators

    Java's bitwise operators operate on individual bits of integer (int and long) values. If an operand is shorter than an int, it is promoted to int before doing the operations.

    It helps to know how integers are represented in binary. For example the decimal number 3 is represented as 11 in binary and the decimal number 5 is represented as 101 in binary.
    Negative integers are store in two's complement form. For example, -4 is 1111 1111 1111 1111 1111 1111 1111 1100.

    Bitwise operators can fall under 2 categories.>>,>>>,<< operators are called shift operators, which is covered in this post. Other operators are ~,&,| and ^ operators.
    ~ Not operator
    ^ Xor or Exclusive OR
    | OR
    & And operator
    >> Right shift
    >>> Unsigned right shift
    << left shift

    Note that operands for Bitwise operators must be numeric datatypes(char, short, int, or long).

    Examples - The bitwise operators

    Operator Usage Example Result Reason
    & or and Operator a & b 3 & 5 1 1 if both bits are 1.
    | OR operator a | b 3 | 5 7 1 if either bit is 1.
    ^ or xor operator a ^ b 3 ^ 5 6 1 if both bits are different.
    ~ or not operator ~a ~3 4 Inverts the bits.
    Left shift n << p 3 <<< 2 12 Shifts the bits of n left p positions. Zero bits are shifted into the low-order positions.
    Right shift n >> p 5 >> 2 1 Shifts the bits of n right p positions. If n is a 2's complement signed number, the sign bit is shifted into the high-order positions.
    Unsigned right shift n >>> p -4 >>> 28 15 Shifts the bits of n right p positions. Zeros are shifted into the high-order positions.


    Tuesday, October 26, 2010

    ==, .equals(), compareTo(), and compare()

    ==,equals, compareTo, compare all help in comparing the object in one or other way.

    == & != Operator
    Compares references, not values. The use of == with object references is generally limited to the following:
    • Comparing to see if a reference is null.
    • Comparing two enum values. This works because there is only one object for each enum constant.
    • You want to know if two references are to the same object

    equals() method
    Usage : a.equals(b) 
    Compares values for equality. Because this method is defined in the Object class, from which all other classes are derived, it's automatically defined for every class. However, it doesn't perform an intelligent comparison for most classes unless the class overrides it. It has been defined in a meaningful way for most Java core classes. If it's not defined for a (user) class, it behaves the same as ==.
    It turns out that defining equals() isn't trivial; in fact it's moderately hard to get it right, especially in the case of subclasses. The best treatment of the issues is in Horstmann's Core Java Vol 1. See equals() method here.

    Also to see == vs equals() , refer here.

    compareTo() method
    a.compareTo(b) is present in Comparable interface. Compares values and returns an int which tells if the values compare less than, equal, or greater than. If your class objects have a natural order, implement the Comparable<T> interface and define this method. All Java classes that have a natural ordering implement this (String, Double, BigInteger, ...).
    For more on Comparable interface, refer here.

    compare(a,b) method
    Usage  : compare(a, b) 
    is implemented using Comparator interface. Compares values of two objects. This is implemented as part of the Comparator<T> interface, and the typical use is to define one or more small utility classes that implement this, to pass to methods such as sort() or for use by sorting data structures such as TreeMap and TreeSet. You might want to create a Comparator object for the following.

    • Multiple comparisons. To provide several different ways to sort something. For example, you might want to sort a Person class by name, ID, age, height, ... You would define a Comparator for each of these to pass to the sort() method.
    • System class. To provide comparison methods for classes that you have no control over. For example, you could define a Comparator for Strings that compared them by length.
    • Strategy pattern. To implement a strategy pattern, which is a situation where you want to represent an algorithm as an object that you can pass as a parameter, save in a data structure, etc.
    If your class objects have one natural sorting order, you may not need this.
    For more on Comparator interface refer here.

    Implementing compareTo (why we need it?)

    The compareTo method is the sole member of the Comparable interface, and is not a member of Object. However, it is quite similar in nature to equals and hashCode. It provides a means of fully ordering objects.
    Implementing Comparable allows
    • calling Collections.sort and Collections.binarySearch
    • calling Arrays.sort and Arrays.binarySearch
    • using objects as keys in a TreeMap
    • using objects as elements in a TreeSet
    The compareTo method needs to satisfy the following conditions. These conditions have the goal of allowing objects to be fully sorted, much like the sorting of a database result set on all fields.
    • anticommutationx.compareTo(y) is the opposite sign of y.compareTo(x)
    • exception symmetry : x.compareTo(y) throws exactly the same exceptions as y.compareTo(x)
    • transitivityif x.compareTo(y)>0 and y.compareTo(z)>0, then x.compareTo(z)>0  (and same for less than)
    •  if x.compareTo(y)==0, then x.compareTo(z) has the same sign as y.compareTo(z)
    • consistency with equals is highly recommended, but not required : x.compareTo(y)==0, if and only if x.equals(y) ; consistency with equals is required for ensuring sorted collections (such as TreeSet) are well-behaved.
    One can greatly increase the performance of compareTo by comparing first on items which are most likely to differ. When a class extends a concrete Comparable class and adds a significant field, a correct implementation of compareTo cannot be constructed. The only alternative is to use composition instead of inheritance. (A similar situation holds true for equals. See Effective Java for more information.)

    Compare the various types of fields as follows :
    • numeric primitive : use < and >. There is an exception to this rule: float and double primitives should be compared using, float) and, double). This avoids problems associated with special border values.
    • boolean primitive :  use tests of the form (x && !y)
    • Object : use compareTo. (Note that possibly-null fields present a problem : while x.equals(null) returns false, x.compareTo(null) will always throw a NullPointerException)
    • type-safe enumeration : use compareTo, like any Object
    • collection or array : Comparable does not seem to be intended for these kinds of fields. For example, List, Map and Set do not implement Comparable. As well, some collections have no definite order of iteration, so doing an element-by-element comparison cannot be meaningful in those cases.
    If the task is to perform a sort of items which are stored in a relational database, then it is usually much preferred to let the database perform the sort using the ORDER BY clause, rather than in code. An alternative to implementing Comparable is passing Comparator objects as parameters. Be aware that if a Comparator compares only one of several significant fields, then the Comparator is very likely not synchronized with equals.
    All primitive wrapper classes implement Comparable. Note that Boolean did not implement Comparable until version 1.5, however.

    import java.util.*;
    public final class Account implements Comparable<Account> {
      enum AccountType {CASH, MARGIN, RRSP};
    public Account (
          String aFirstName,
          String aLastName,
          int aAccountNumber,
          int aBalance,
          boolean aIsNewAccount,
          AccountType aAccountType
      ) {
          //..parameter validations elided      fFirstName = aFirstName;
          fLastName = aLastName;
          fAccountNumber = aAccountNumber;
          fBalance = aBalance;
          fIsNewAccount = aIsNewAccount;
          fAccountType = aAccountType;
      * @param aThat is a non-null Account.
      * @throws NullPointerException if aThat is null.
      public int compareTo( Account aThat ) {
        final int BEFORE = -1;
        final int EQUAL = 0;
        final int AFTER = 1;
        //this optimization is usually worthwhile, and can    
    //always be added    
    if ( this == aThat ) return EQUAL;
        //primitive numbers follow this form    
    if (this.fAccountNumber < aThat.fAccountNumber) return BEFORE;
        if (this.fAccountNumber > aThat.fAccountNumber) return AFTER;
        //booleans follow this form    if (!this.fIsNewAccount && aThat.fIsNewAccount) return BEFORE;
        if (this.fIsNewAccount && !aThat.fIsNewAccount) return AFTER;
        //objects, including type-safe enums, follow this form    //note that null objects will throw an exception here    int comparison = this.fAccountType.compareTo(aThat.fAccountType);
        if ( comparison != EQUAL ) return comparison;
        comparison = this.fLastName.compareTo(aThat.fLastName);
        if ( comparison != EQUAL ) return comparison;
        comparison = this.fFirstName.compareTo(aThat.fFirstName);
        if ( comparison != EQUAL ) return comparison;
        if (this.fBalance < aThat.fBalance) return BEFORE;
        if (this.fBalance > aThat.fBalance) return AFTER;
        //all comparisons have yielded equality    //verify that compareTo is consistent with equals (optional)    assert this.equals(aThat) : "compareTo inconsistent with equals.";
        return EQUAL;
       * Define equality of state.
       @Override public boolean equals( Object aThat ) {
         if ( this == aThat ) return true;
         if ( !(aThat instanceof Account) ) return false;
         Account that = (Account)aThat;
           ( this.fAccountNumber == that.fAccountNumber ) &&
           ( this.fAccountType == that.fAccountType ) &&
           ( this.fBalance == that.fBalance ) &&
           ( this.fIsNewAccount == that.fIsNewAccount ) &&
           ( this.fFirstName.equals(that.fFirstName) ) &&
           ( this.fLastName.equals(that.fLastName) );
       * A class that overrides equals must also override hashCode.
       @Override public int hashCode() {
         int result = HashCodeUtil.SEED;
         result = HashCodeUtil.hash( result, fAccountNumber );
         result = HashCodeUtil.hash( result, fAccountType );
         result = HashCodeUtil.hash( result, fBalance );
         result = HashCodeUtil.hash( result, fIsNewAccount );
         result = HashCodeUtil.hash( result, fFirstName );
         result = HashCodeUtil.hash( result, fLastName );
         return result;
       ////  PRIVATE  ///////
       private String fFirstName; //non-null   private String fLastName;  //non-null   private int fAccountNumber;
       private int fBalance;
       private boolean fIsNewAccount;
       * Type of the account, expressed as a type-safe enumeration (non-null).
       private AccountType fAccountType;
       * Exercise compareTo.
       public static void main (String[] aArguments) {
         //Note the difference in behaviour in equals and compareTo, for nulls:     String text = "blah";
         Integer number = new Integer(10);
         //x.equals(null) always returns false:     System.out.println("false: " + text.equals(null));
         System.out.println("false: " + number.equals(null) );
         //x.compareTo(null) always throws NullPointerException:     //System.out.println( text.compareTo(null) );     //System.out.println( number.compareTo(null) );
         Account flaubert = new Account(
          "Gustave", "Flaubert", 1003, 0,true, AccountType.MARGIN
         //all of these other versions of "flaubert" differ from the     //original in only one field     Account flaubert2 = new Account(
           "Guy", "Flaubert", 1003, 0, true, AccountType.MARGIN
         Account flaubert3 = new Account(
           "Gustave", "de Maupassant", 1003, 0, true, AccountType.MARGIN
         Account flaubert4 = new Account(
           "Gustave", "Flaubert", 2004, 0, true, AccountType.MARGIN
         Account flaubert5 = new Account(
           "Gustave", "Flaubert", 1003, 1, true, AccountType.MARGIN
         Account flaubert6 = new Account(
           "Gustave", "Flaubert", 1003, 0, false, AccountType.MARGIN
         Account flaubert7 = new Account(
           "Gustave", "Flaubert", 1003, 0, true, AccountType.CASH
         System.out.println( "0: " +  flaubert.compareTo(flaubert) );
         System.out.println( "first name +: " +  flaubert2.compareTo(flaubert) );
         //Note capital letters precede small letters     System.out.println( "last name +: " +  flaubert3.compareTo(flaubert) );
         System.out.println( "acct number +: " +  flaubert4.compareTo(flaubert) );
         System.out.println( "balance +: " +  flaubert5.compareTo(flaubert) );
         System.out.println( "is new -: " +  flaubert6.compareTo(flaubert) );
         System.out.println( "account type -: " +  flaubert7.compareTo(flaubert) );

    A sample run of this class gives:
    >java -cp . Account
    false: false
    false: false
    0: 0
    first name +: 6
    last name +: 30
    acct number +: 1
    balance +: 1
    is new -: -1
    account type -: -1

    Revised Reverse

    The reverse() method reverses the order of the characters in a StringBuffer object. Unlike the methods of immutable objects, this method changes the data of its object. For practice, let us write another method that does this.
    The append() method puts a new character at the end of a StringBuffer object. No new object is created. We can use this method to build up the reversed characters as the original String is scanned from right to left:
    public class ReverseTester
      public static String reverse( String data )
        StringBuffer temp = new StringBuffer();
        for ( int j=data.length()-1; j >= 0; j-- )  // scan the String from right to left
          temp.append( data.charAt(j) );            // append characters on the right
        return temp.toString();      // return a String created from the StringBuffer
      public static void main ( String[] args )
        System.out.println( reverse( "Hello" ) );
    In this version of reverse(), only two new objects are created: the StringBuffer and the String object that is returned to the caller.

    Note that program does not make any assumptions about the size of the original String

    StringBuffer Methods

    Usually, if execution speed is a concern, you should declare a StringBuffer to be somewhat larger than you might need. This doesn't waste much space and puts fewer demands on the run-time system.
    As with arrays, StringBuffer indexes start at 0 and go up to length-1. Some StringBuffer methods are:
    StringBuffer Methods
    StringBuffer append( char c ) append c to the end of the StringBuffer
    StringBuffer append( int i ) convert i to characters, then append them to the end of the StringBuffer
    StringBuffer append( long L ) convert L to characters, then append them to the end of the StringBuffer
    StringBuffer append( float f ) convert f to characters, then append them to the end of the StringBuffer
    StringBuffer append( double d ) convert d to characters, then append them to the end of the StringBuffer
    StringBuffer append( String s ) append the characters in s to the end of the StringBuffer
    int capacity() return the current capacity (capacity will grow as needed).
    char charAt( int index ) get the character at index.
    StringBuffer delete( int start, int end) delete characters from start to end-1
    StringBuffer deleteCharAt( int index) delete the character at index
    StringBuffer insert( int index, char c) insert character c at index (old characters move over to make room).
    StringBuffer insert( int index, String st) insert characters from st starting at position i.
    StringBuffer insert( int index, int i) convert i to characters, then insert them starting at index.
    StringBuffer insert( int index, long L) convert L to characters, then insert them starting at index.
    StringBuffer insert( int index, float f) convert f to characters, then insert them starting at index.
    StringBuffer insert( int index, double d) convert d to characters, then insert them starting at index.
    int length() return the number of characters.
    StringBuffer reverse() Reverse the order of the characters.
    void setCharAt( int index, char c) set the character at index to c.
    String toString() return a String object containing the characters in the StringBuffer.


    The reversed String could be built up character by character in an array. Since arrays can be altered at any time, only one new object would be constructed. This is essentially the idea of the StringBuffer class.
    A StringBuffer object holds characters that can be changed by appending and by inserting characters. Also, a StringBuffer object includes many useful character manipulation methods. Constructors for StringBuffer are:
    StringBuffer constructors
    public StringBuffer() create an empty StringBuffer
    public StringBuffer(int capacity) create a StringBuffer with initial room for capacity characters
    public StringBuffer(String st) create a StringBuffer containing the characters from st
    If you insert characters into a StringBuffer, it automatically grows to the length you need.

    StringBuffers grow to the size needed, so starting with a length of zero works correctly and does not waste memory.