Saturday 6 December 2008

Generate all combinations of chars

Generating all combinations of the characters is not a simple task and one must think before starting any coding. The problem size (example 4 represents all combinations between 'a' and 'ZZZZ') can vary and this makes the problem more complex to solve but simpler to program! There are various ways how to solve this problem. The solution discussed here describes how to convert an integer into a sequence of characters.

This article describes how to write a Java program which returns all combinations of characters for a given length. Note that even though this is a programming related article it requires a good knowledge of mathematics. The examples make use of logs and power of to carry out the calculations required.

An overview of the solution

The solution discussed here describes how to convert an integer into a sequence of characters. Let's have a simple example, the integer 0 is equivalent to ['a'], while integer 1 is equivalent to ['b'] and the integer 51 is equivalent to ['Z']. This is great for a problem of size one. What about a problem of size two? In this case 0 is still ['a'] and 1 is still ['b'] and 51 is still equivalent to ['Z']. Now 52 is (or should be) equivalent to ['a', 'a']. The array size has changed from one to two. The integer 53 is equivalent ['a', 'b'] and so on.

Not everything that shines is gold! Let's switch to numbers instead of characters for now so we appreciate the problem that this will lead us into. We have ten numbers, from 0 until 9. The leading 0s are usually ignored and are not used. This creates a problem for our solution as the 0 is representing the char 'a'. What I'm saying here? In numbers the value 00140 is equivalent to 140, but this is not the case with our solution as the combination: 'aabda' is not equivalent to 'bda'. To avoid this problem we have to build sets of combinations with unique size. Thus the value 0 for problem size 4 is 'aaaa' while the same value for a problem with size 7 will be: 'aaaaaaa'. This is covered mathematically below.

Let's start with the simplest version of the problem when the size is one, that is, all the characters available in the English alphabet.

Convert an int into a char

We need to provide map for all characters in the alphabet. The following function does so by returning the char 'a' for the integer 0 and the char 'z' for the int 25. The char 'A' is returned for the int 26 while the char 'Z' is returned for the int 51. Integer values outside the mentioned range (0 and 51 inclusive) will throw an illegal argument exception.


public static char getCharForInt(int i) 
                   throws IllegalArgumentException {
  if (i < 0 | i >= BASE) {
    throw new IllegalArgumentException(
              "Integer value out of range: " + i);
  }
  int length = (BASE) / 2;

  // Lower case char
  if (i < length) {
    return (char) (i + 'a');
  }
  // Upper case char
  return (char) (i - length + 'A');
}

This method is quite straight forward and simple to understand. This method returns just a single character which is only valid for a problem with size one. We need yet another method to generate an array of these. And that's what we're discussing next. Like here, this method will expect an integer and it will return the relative array of chars for the given integer. But before we proceed it's good to note that the method makes use of a constant named BASE which is declared at class level as illustrated below.


private static final int BASE = ('z' - 'a') + ('Z' - 'A') + 2;

Build an array of chars for a given int

If we can provide a map of chars to ints programmatically, then we can also provide a map between an integer (referred to as key in this method) to an array of chars in conjunctions with the previous method. How? Let's have a numerical example first. The number 143 (base 10) can be expressed as: 1 * 102 + 4 * 101 + 3 * 100. So to convert the number 14310 into the array of chars ['1', '4', '3'] we need to perform the following steps:


0) 143 / 102 = 1
1) 143 – (102*1) / 101
1) 143 – (100) / 101 = 4
2) 143 - ((102*1) + (101*4)) / 100
2) 143 - (140) / 100 = 3

Using the above approach we can convert the key integer value into an array of characters by changing the base from 10 to our base: 52. Before we can sing victory, we have to appreciate that this approach has a limitation. It will work well for the least significant character but it will miss one on the other characters. What am I saying? Let's have another example first:

Key Expression Value Expected Output
0 0 * 520 0 'a' 'a'
52 52 * 521
0 * 520
1
0
'aa' 'ba'

When dividing 52 by 52 we get 1, which is equivalent to 'b' not the answer we wanted! A simple way around this problem the solution and to reduce the number conditions we're going to make a small change to solution discussed before. We'll build sets of combinations with unique size. Thus the key value 0 for problem size 4 is ['a', 'a', 'a', 'a'] while the same value for a problem with size 7 will be: ['a', 'a', 'a', 'a', 'a', 'a', 'a'] .

This immediately provokes the following question, how are we going to generate all combinations? We can still obtain all combinations by first generating all combinations for size one and size two and so on.

With that out of the way, we can proceed in our adventure. The following code provides the algorithm used to generate all combination for a specific size.


private static char[] getCharsFormKey(int key, int size) {
  char[] chars = new char[size];
  for (int i = size - 1, j = 0; i >= 0; i--, j++) {
    // Get the divider for this character position
    int divider = (int) Math.pow(BASE, i);
    // Calculate the character index by dividing the 
    // key with the divider
    int c = key / divider;
    chars[j] = getCharForInt(c);
    // Deduct the processed numbers
    key -= (c * divider);
  }
  return chars;
}

Given a key integer and a size, this method returns the equivalent array of chars mapping the given key integer. Note that an illegal argument exception is thrown if the key integers requires a larger array that the specified size. This immediately brings us the following question: can we calculate the size automatically to fit the given key value? Yes and to do so we need to make use of the BigDecimal class to perform some calculations. We can determine the number of digits within a number by calculating the log to base 10 of that number incrementing it by one. In our case we have to calculate the log to base 52. There is not function ready which does that. But we can calculate the log of any base by using log to base 10 or ln as logn(X) is equivalent to log10(X) / log10(n).


private static char[] getCharsFormKey(int key) {
  int size = 1;
  if (key > 0) {
    BigDecimal keyDB = 
                 new BigDecimal(String.valueOf(Math.log(key)));
    size = (int) (keyDB.divide(
                   BASE_LOG_BD, RoundingMode.HALF_UP).doubleValue()
                  ) + 1;
  }
  return getCharsFormKey(key, size);
}

This method may be more attractive as it requires less parameters. The calculations involved here take some time and affect the performance. This method is mentioned for the sake of completeness and should be avoided if possible. This method makes use of a constant named BASE_LOG_BD which is declared at class level as illustrated below. Also note that the string version of the big decimal class is used as the double version is more prone to error as discussed at: http://www.opensourcestrategies.com/ofbiz/ofbiz_bigdecimal_cookbook.txt.


private static final BigDecimal BASE_LOG_BD = 
    new BigDecimal(String.valueOf(Math.log(52)));

Generating all combinations

To generate all combinations for a problem size 4, that is, generate all combinations starting from 'a' until 'ZZZZ'. We need two loops in order to achieve this: one to generate all combinations for a specific size or length, while the other to go through all sizes/lengths starting from 1 until the problem size, four in this case.


int size = 4;
for (int i = 1; i <= size; i++) {
  int maxKeyForSize = (int) Math.pow(BASE, i);
  for (int j = 0; j < maxKeyForSize; j++) {
    char[] chars = getCharsFormKey(j, i);
    String text = String.copyValueOf(chars);
    System.out.println(text);
  }
}

Conclusion

This article describes how to generate all combinations of characters for a given size using the mathematical functions ln and power of.

Friday 14 November 2008

Sorting Objects using Comparator

Sorting is common functionality required by many applications. Questions like: How do we sort in Java? or What should we use as sorting algorithm? need to answered before we can perform any kind of sorting. Definitely we're not the first ones who require this feature and others have already done it before for us. So we can simple use the Java API provided to perform sorting.

The following article explains the concept of sorting and how to use the Java API to solve this problem and closes with some programming tips.

Concept behind sorting

In order to be able to sort elements we need to be able to compare them. What does this mean? If you have two things and you need to pick one of them, which one would you pick? Let's make this more realistic. If you're not rich and you can choose between €1 and €100, which one would you choose? I don't know what would you do, but I would go for the hundred. Why? Because 100 is greater than 1! I was able to make this decision because I was able to compare the choice at hand. If instead of numbers I said choose between A and B, where A and B can be anything, would you be able to do an informed decision? No, it would be pure gamble - a matter of luck. There is no way to compare A and B without further knowledge.

In order to be able to sort two elements (or more), you need to be able to compare them. Similar to the problem discussed above, we need to be able to evaluate elements and then sort them based on this value. For example, if we need to sort the following list: {8, 5, 9}, we know that 5 is less than 8 so these two have to be swapped. Sorting numbers is very simple and straight forward. We cannot say the same for any other object (Java and real). For example, if we have a list of boxes, how would we sort them? If we're sorting by size, we first determine the size of each and then using the size value (a number) as sorting criteria. So in order to sort any kind of object, all we need to do is to convert the object into a number that we can compare with. So if we have the following list of objects: {a, b, c, d} (the letters in the previous list is used only to define the object name and has no effect on the sorting) with sorting values {4, 3, 7, 5} respectively, we know that object b should come first while object c should be placed last and so on.

How do we implement this in Java?

Java provides a set of classes and interfaces which we can use to sort lists and arrays. Most of the following examples will use lists but the same concept can be applied for arrays. A final example will show this.

Let's start by creating a list of Integers and sort these using the Collections.sort method. The Collections class (part of the Java Collection Framework) provides a list of static methods which we can use when working with collections such as list, set and the like. So in a nutshell, we can sort a list by simply calling: java.util.Collections.sort(the list) as shown in the following example:


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example1 {
  public static void main(String[] args) {
    List<Integer> ints = new ArrayList<Integer>();
    ints.add(4);
    ints.add(3);
    ints.add(7);
    ints.add(5);

    Collections.sort(ints);
    System.out.println(ints);
  }
}

The above class creates a list of four integers and, using the collection's sort method, sorts this list (in one line of code) without us having to worry about the sorting algorithm.

Java was able to sort this list because it knows how to compare integers as the Integer class implements the Comparable interface. Note that, as from Java 1.5, the primitive int value is autoboxed into an Integer (the object wrapper for int) before added to the list. Thus in order to be able to make use of the collection's sort method, all we need to do is implement the comparable interface by our objects.

Let's take this example one step further and create our own class. Let's create a list of students and sort them by their grade (which is a number). The student class will have two fields: name and grade. In order to be able to use the sort method from the collections class, as we did in the above example (Example1), we have to implement the comparable interface and its method, as illustrated below:


public class Student1 implements Comparable<Student1> {

  private int grade;
  private String name;

  public Student1(String name, int grade) {
    setName(name);
    setGrade(grade);
  }

  @Override
  public int compareTo(Student1 o) {
    return grade - o.grade;
  }

  @Override
  public String toString() {
    return name + " " + grade;
  }

  // Getters and setters are removed for brevity
} 

The compareTo method should return a negative integer, zero, or a positive integer if this student's grade is less than, equal to, or greater than the specified/given student's grade. The simplest way to do it is to subtract the grades of these students. Why and how would that help sorting? If this student's grade is larger than the grade of the given student, then a positive number is returned, while if the grades are equal, zero is returned. This follows the method's contract/specifications. Note that our job is to provide information to the sorting algorithm and not sorting the objects ourselves.

The toString method was overridden so that we can see readable results when we print the list. Otherwise the output will look something like: [Student1@19821f, Student1@addbf1, Student1@42e816, Student1@9304b1] (instead of: [Joe Vella 47, Paul Galea 52, Albert Attard 65, Mary Borg 93]) which is not readable.

Let's modify the previous class (Example 1) and sort a list of students.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example2 {
  public static void main(String[] args) {
    List<Student1> students = new ArrayList<Student1>();
    students.add(new Student1("Albert Attard", 65));
    students.add(new Student1("Mary Borg", 93));
    students.add(new Student1("Joe Vella", 47));
    students.add(new Student1("Paul Galea", 52));

    Collections.sort(students);
    System.out.println(students);
  }
}

Making full use of the API

How can we sort the student by both name and grade? In order to achieve this using the comparable interface (above) we have to add more fields to the student class in order to be able to determine which field we're sorting on. The following approach is not recommended and included here only for demonstration and comparisons purposes. Changes are shown in bold.


public class Student2 implements Comparable<Student2> {

  private int grade;
  private String name;
  private int sortBy;

  public Student2(String name, int grade, int sortBy) {
    setName(name);
    setGrade(grade);
    setSortBy(sortBy);
  }

  @Override
  public int compareTo(Student2 o) {
    switch (sortBy) {
    case 1: // Sort by name
      return name.compareTo(o.name);
    default: // Sort by grade by default
      return grade - o.grade;
    }
  }

  // Getters, setters and toString method are removed for 
  // brevity
}

We had to add a new field in the student class, called sortBy, which we have to set to 1 in order to sort the students by their name. Any other value will sort the students by their grade as illustrated in the following example. Ideally we use enums instead of int as the data type of the sortBy field which will prevent illegal values. Changes are shown in bold.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example3 {
  public static void main(String[] args) {
    List<Student2> students = new ArrayList<Student2>();
    students.add(new Student2("Albert Attard", 65, 1));
    students.add(new Student2("Mary Borg", 93, 1));
    students.add(new Student2("Joe Vella", 47, 1));
    students.add(new Student2("Paul Galea", 52, 1));
    
    // Sort by name
    Collections.sort(students);
    System.out.println(students);
    
    // Change these to sort them by grade
    for(Student2 student:students){
      student.setSortBy(0);
    }
    Collections.sort(students);
    System.out.println(students);
  }
}

This approach has two main pitfalls. First, the student class has to include fields and methods that are not related to the student object. Sorting properties are not student properties. The other issue is that for any new fields or sorting order we have to change the student class and emend the compareTo method accordingly, adding complexity to a method making it harder to maintain. Also, the sorting method is bound with the student class and cannot be used alone (apart from the object). The sorting state are saved with the object's state which is not what we want. For every student we have an instance of the sortby field, which we cannot make static. Why? If we have two lists, one to be sorted by name and the other by grade, then the static value will be shared by all instance of student and may effect the sorting outcome.

Java provides another way to compare objects. Instead of implementing the comparable interface (Student2), we can implement the Comparator interface. What's the difference? The main difference between these two interfaces is that the comparable interface defines one method compareTo, which takes one parameter. This parameter is compared with this object (the instance of student). In other words, the student object has a method which makes it able to compare to another student. On the other hand, the comparator interface defines one method (in reality two, but we're not interested from the second one) that takes two parameters (of the same type) and returns the comparison of these two objects (an int exactly the same as the method compareTo from the comparable interface). As such, the comparator allows us to remove the unnecessary fields and methods from the student class and move these elsewhere as illustrated below.

With reference to the Student1 class defined above.


import java.util.Comparator;

public class StudentGradeComparator1 implements Comparator<Student1> {

  @Override
  public int compare(Student1 a, Student1 b) {
    return a.getGrade() - b.getGrade();
  }
}

How can we use this? The collections class has an overloaded version of the sort method (http://java.sun.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List, java.util.Comparator)). The overloaded version accepts two parameters: the list to be sorted and an instance of comparator. The comparator outcome will be used by the sorting algorithm to determine the elements' magnitude and relation. Changes from the previous examples, are shown in bold.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example4 {
  public static void main(String[] args) {
    List<Student1> students = new ArrayList<Student1>();
    students.add(new Student1("Albert Attard", 65));
    students.add(new Student1("Mary Borg", 93));
    students.add(new Student1("Joe Vella", 47));
    students.add(new Student1("Paul Galea", 52));

    Collections.sort(students, new StudentGradeComparator1());
    System.out.println(students);
  }
}

How can we sort by name? We can create another class that implements comparator and compare the student class as required. All we need to do is replace the compare method as shown below.


  @Override
  public int compare(Student1 a, Student1 b) {
    return a.getName().compareTo(b.getName());
  }

Making the difference

Let's analyse the StudentGradeComparator1 class created above. This class has no fields, thus we can say that this class is stateless. Do we need to create more than one instance of this class? No. We don't need to have more than one instance of this class as the fields of this class (that are none) never change. So we can have one instance a always use it. This is referred to the singleton pattern. In simple terms, this pattern prevents the user to create more than one instance of this object. For more information about this, please refer to: http://java.sun.com/developer/JDCTechTips/2006/tt0113.html article. Why should we have it? Every object created consumes memory. Since our class (StudentGradeComparator1) is stateless, there is no need to enable/allow the user to create hundreds or thousands instance of this class as these will be identical. Changes are shown in bold.


import java.util.Comparator;

public class StudentGradeComparator2 implements Comparator<Student1> {

  private static final StudentGradeComparator2 instance = 
      new StudentGradeComparator2();

  public static StudentGradeComparator2 getInstance() {
    return instance;
  }

  private StudentGradeComparator2() {
  }

  @Override
  public int compare(Student1 a, Student1 b) {
    return a.getGrade() - b.getGrade();
  }
}

This got more complex, but in reality it got simpler. The student class only contain code related to the student, while the sorting classes contain the code required by the comparator. This means that each class is doing only thing.

How can we use it? Instead of creating an instance of the comparator, we call the get instance method: Collections.sort(students, StudentGradeComparator2.getInstance()) as shown in bold below:


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example5 {
  public static void main(String[] args) {
    List students = new ArrayList();
    students.add(new Student1("Albert Attard", 65));
    students.add(new Student1("Mary Borg", 93));
    students.add(new Student1("Joe Vella", 47));
    students.add(new Student1("Paul Galea", 52));

    Collections.sort(students, 
        StudentGradeComparator2.getInstance());
    System.out.println(students);
  }
}

How can we sort the students by their grade but in descending order? Taking this another level, we can have two instances of the comparator class (not singleton anymore): one to sort ascending and the other descending. Here we're extending the singleton concept to prevent the user from freely creating instances. We can remove the get instance method and allow access to the static fields as shown below. Since, the class is radically changed, no changes are highlighted.


import java.util.Comparator;

public class StudentGradeComparator3 implements Comparator {

  public static final StudentGradeComparator3 ASC = 
      new StudentGradeComparator3(1);

  public static final StudentGradeComparator3 DESC = 
      new StudentGradeComparator3(-1);

  private final int order;

  private StudentGradeComparator3(int order) {
    this.order = order;
  }

  @Override
  public int compare(Student1 a, Student1 b) {
    return order * (a.getGrade() - b.getGrade());
  }
}

Here we removed the get instance method and included two instances ASC and DESC. We added an integer (named order) with values 1 or -1 which is used to switch the sorting polarity. Note that when a number is multiplied by a negative number, its sign (negative or positive) is changed. Changing the sign will change the sorting order. This field is constant (not static) and is set through the solo private constructor by the two static fields.


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Example6 {
  public static void main(String[] args) {
    List<Student1> students = new ArrayList<Student1>();
    students.add(new Student1("Albert Attard", 65));
    students.add(new Student1("Mary Borg", 93));
    students.add(new Student1("Joe Vella", 47));
    students.add(new Student1("Paul Galea", 52));

    Collections.sort(students, StudentGradeComparator3.ASC);
    System.out.println(students);

    Collections.sort(students, StudentGradeComparator3.DESC);
    System.out.println(students);
  }
}

Arrays

We can easily adopt the above example for arrays. Instead of using collection's sort method we use the array's version (http://java.sun.com/javase/6/docs/api/java/util/Arrays.html#sort(T[], java.util.Comparator)).


import java.util.Arrays;

public class Example7 {
  public static void main(String[] args) {
    Student1[] students = { new Student1("Albert Attard", 65),
        new Student1("Mary Borg", 93), 
        new Student1("Joe Vella", 47),
        new Student1("Paul Galea", 52) };

    Arrays.sort(students, StudentGradeComparator3.ASC);
    System.out.println(students);
  }
}

The same comparator is used to sort the array of students.

Conclusion

This article discusses how to perform sorting without having to worry about the sorting algorithm. From the collections Java doc:

"...the sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place...

One thing to take away from this article is don't reinvent the wheel. Before implementing something, have a look around as most probably others did it before you

Sunday 28 September 2008

Practical Example of Swing Timer

If you have to do something repetitively, what would you use? The first quick answer would be: loops (iteration). But that would prevent other things from happening until the loop is done! Threads can solve the seizing of control problem. But threads may be complex for someone who is new to programming and require some skill. What else can we use? Swing Timer!

Swing Timer

Swing timer provides a unique wrapper which presents threads in an event driven fashion. Imagine we need to display the text "hello" in the console every one second without having to seize the control. How would we do that using the swing timer class?

Note that there are three Timer classes in the Java API. We're using javax.swing.Timer. Make sure you have the correct import.


ActionListener listener = new ActionListener(){
  public void actionPerformed(ActionEvent event){
    System.out.println("hello");
  }
};
Timer displayTimer = new Timer(1000, listener);
displayTimer.start();

The swing timer has only one constructor which takes two parameters: the time gap (sometimes referred to as delay, in milliseconds) and an action listener. The swing timer fires an action event at specific intervals, which is handled by the action listener. The interval can be adjusted and more listeners can be added (and removed) as needs be using the setDelay(int) and addActionListener(ActionListener) (and removeActionListener(ActionListener)) methods. But let's keep it simple. For more details about available functionality provided by the swing timer class please refer to the javax.swing.Timer API.

Start the timer

No action will happen until the start() method is invoked. When the start method is invoked the timer waits for some time (referred to as initial delay) before it fires the first action event. This is governed by the initial delay which is initially set equal to the time gap provided as the constructor's first parameter. The initial delay can be adjusted accordingly using the setInitialDelay(int) method. It's important to set this value before invoking the start method.


Timer displayTimer = new Timer(1000, listener);
displayTimer.setinitialDelay(0);
displayTimer.start();

The above example will fire the first action immediately, as the initial delay is set to 0 milliseconds. It will trigger subsequent events with a one second (1000 milliseconds) interval.

Stop the timer

One of the best features provided by the swing timer is the ability to start and stop and even restart the timer without having to worry about the thread lifecycle.

Those who already worked with threads know that a thread cannot be restarted. Once ready, it must die (unreferenced) and another instance has to be instantiated in order to perform the thread's work.

To stop the swing timer, simple call the stop() method. This will stop the swing timer from firing any subsequent action events.


displayTimer.stop();

The swing timer can be restarted by simply calling the start() method again.

Restarting the swing timer

The swing timer can be restarted using the stop() start() methods. Alternatively, the restart() method can be used which cancels any pending firings of events and starts all over.


displayTimer.restart();

A graphical example

Let's create a simple applet which has a bouncing ball. The ball will stop moving once the user presses any key and starts bouncing again once another key is pressed again. This example will toggle the state of the swing timer between running and stopped. The swing timer provides a method called isRunning() which returns true if the swing timer is running, false otherwise.


    addKeyListener(new KeyAdapter() {
      @Override
      public void keyPressed(KeyEvent e) {
        if (moveBallTimer.isRunning()) {
          moveBallTimer.stop();
        } else {
          moveBallTimer.start();

        }
      }
    });

The full applet code listed below


import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.awt.geom.Ellipse2D;

import javax.swing.JApplet;
import javax.swing.Timer;

public class SwingTimerAppletDemo1 extends JApplet {

  private static final long serialVersionUID = 656209471758159755L;

  private Ellipse2D ball;
  private Timer moveBallTimer;
  private int moveX;
  private int moveY;

  @Override
  public void init() {
    ball = new Ellipse2D.Double(0, 0, 10, 10);
    moveX = 5;
    moveY = 5;

    moveBallTimer = new Timer(100, new ActionListener() {
      @Override
      public void actionPerformed(ActionEvent e) {
        moveBall();
        repaint();
      }
    });

    addKeyListener(new KeyAdapter() {
      @Override
      public void keyPressed(KeyEvent e) {
        if (moveBallTimer.isRunning()) {
          moveBallTimer.stop();
        } else {
          moveBallTimer.start();

        }
      }
    });
  }

  protected void moveBall() {
    int width = getWidth();
    int height = getHeight();

    Rectangle ballBounds = ball.getBounds();
    if (ballBounds.x + moveX < 0) {
      moveX = 5;
    } else if (ballBounds.x + ballBounds.width + moveX > width) {
      moveX = -5;
    }
    if (ballBounds.y + moveY < 0) {
      moveY = 5;
    } else if (ballBounds.y + ballBounds.height + moveY > height) {
      moveY = -5;
    }
    ballBounds.x += moveX;
    ballBounds.y += moveY;

    ball.setFrame(ballBounds);
  }

  @Override
  public void paint(Graphics g) {
    super.paint(g);

    Graphics2D g2d = (Graphics2D) g;
    g2d.setColor(Color.RED);
    g2d.fill(ball);
  }

  @Override
  public void start() {
    moveBallTimer.start();
  }

  @Override
  public void stop() {
    moveBallTimer.stop();
  }
}

The above program is mainly doing two things: listens for user input through the keyboard and moving/bouncing the ball around the applet. This was possible as the swing timer makes use of threads to fire an action event and wait until the delay is over to fire the next action event. While waiting, the application can do other things such as listens to the user input.

What will happen if an action event is fired before the previous one has finish execution? By default the swing timer will merge consecutive action events into one. This behaviour is determined by the coalesce property. If set to false using the setCoalesce(boolean) method, the swing timer will fire all action event. This will cause queuing of action events as these are triggered at a faster rate than are handled.

Conclusion

The swing timer is a good candidate for invoking repetitive tasks without seizing the control. On the other hand, the tasks cannot be long lasting ones as otherwise it may block other things from happening making the application less responsive. The swing worker should be used for long lasting jobs.

Thursday 4 September 2008

Practical Example of Swing Worker

Please note that this page has moved to: http://www.javacreed.com/swing-worker-example/.

Java provides a neat way to carry out long lasting jobs without have to worry about threads and hanging the application. It's called SwingWorker. It's not the latest thing on Earth (released with Java 1.6) and you may have already read about it. What I never came across was a practical example of the swing worker.

Swing Worker

SwingWorker is an abstract class which hides the threading complexities from the developer. It's an excellent candidate for applications that are required to do tasks (such as retrieving information over the network/internet) which may take some time to finish. It's ideal to detach such tasks from the application and simply keep an eye on their progress. But before we hit the road and start working with the swing worker we have to see what "eye" are we going to put on our worker so to say.

The following example illustrates a simple empty worker that will return/evaluate to an integer when the given task is finished. It will inform the application (the "eye" thing) with what's happening using objects of type string, basically text messages.


import javax.swing.SwingWorker;
 
public class MyBlankWorker extends SwingWorker<Integer, String> {
 
  // Some code must go here
 
}

The string worker class provides two place holders (generics). The first one represents the type of object returned when the worker has finished working. The second one represents the type of information that the worker will use to inform (update) the application with its progress. The swing worker class also provides means to update the progress by means of an integer which has nothing to do with the two generics mentioned before.

Practical Example

Example: Let say we need to find the number of occurrences of a given word with in some documents. So we would be writing something like:

 
import java.io.File;
import javax.swing.SwingWorker;
 
public class SearchForWordWorker 
             extends SwingWorker<Integer, String> {
 
  private final String word;
  private final File[] documents;
 
  public SearchForWordWorker(String word, File[] documents){
    this.word = word;
    this.documents = documents;
  }
 
  @Override
  protected Integer doInBackground() throws Exception {
    int matches = 0;
    for(int i=0, size=documents.length; i<size; i++){
      // Update the status: the keep an eye on thing
      publish("Searching file: "+documents[i]);
 
      try {
        // Do the search stuff
        // Here you increment the variable matches
      } finally {
        // Close the current file
      }
 
      // update the progress
      setProgress( (i+1) * 100 / size);
    }
 
    return matches;
  }
}

The first thing that comes into mind is where is the text "Searching file: ..." is going? The swing worker class provides another method called process which accepts a list (of type string in our case) and used to process the published information (which can be an object of any kind). Overriding this method, allows us to take full control of this information.


  @Override
  protected void process(List<String> chunks){
    for(String message : chunks){
      System.out.println(message);
    }
  }

The above example is not much useful. We may need to update the status bar of an application or the text of the progress bar or a label sitting somewhere in the application. Since we may be monitoring this worker from various UI components, ideally we add a level of isolation between the worker and the UI components. In many examples, the worker was fed UI components as constructor parameters. I would go for interfaces instead to make the design pluggable when possible.

In other occasions a worker may be used to populate a table which information is coming from a slow source. In this case we may use the table model as one of the workers parameter and the array of objects representing the row. The following example makes use of the default table model as the design is simpler.

 
import java.util.List;
import javax.swing.SwingWorker;
import javax.swing.table.DefaultTableModel;
 
public class PopulateTableWorker 
             extends SwingWorker<DefaultTableModel, Object[]> {
 
  private final DefaultTableModel model;
 
  public PopulateTableWorker(DefaultTableModel model){
    this.model = model;
  }
 
  @Override
  protected DefaultTableModel doInBackground() throws Exception {
    // While there are more rows
    while(Math.random() < 0.5){
      // Get the row from the slow source
      Object[] row = {1, "Java"};
      Thread.sleep(2000);
 
      // Update the model with the new row
      publish(row);
    }
 
    return model;
  }
 
  @Override
  protected void process(List<Object[]> chunks){
    for(Object[] row : chunks){
      model.addRow(row);
    }
  }
}

Note that the table model interface does not support addition of new rows. Alternatively we can make use of the table model interface. The model must be able to add a new row when this is required as otherwise an exception may be thrown.


import java.util.List;
import javax.swing.SwingWorker;
import javax.swing.table.TableModel;
 
public class PopulateTableWorker 
             extends SwingWorker<TableModel, Object[]> {
 
  private final TableModel model;
  private int rowIndex = 0;
 
  public PopulateTableWorker(TableModel model){
    this.model = model;
  }
 
  @Override
  protected TableModel doInBackground() throws Exception {
    // While there are more rows
    while(Math.random() < 0.5){
      // Get the row from the slow source
      Object[] row = {1, "Java"};
      Thread.sleep(2000);
 
      // Update the model with the new row
      publish(row);
    }
 
    return model;
  }
 
  @Override
  protected void process(List<Object[]> chunks){
    for(Object[] row : chunks){
      for(int columnIndex=0, size=row.length; 
                                      columnIndex<size; 
                                      columnIndex++){
        model.setValueAt(row[columnIndex], rowIndex, columnIndex);
      }
    }
    rowIndex++;
  }
}

Back to our example, we can have an interface called Informable (or you can pick a name of your liking) with one method: messageChanged(String message), which will be invoked whenever some progress is made and published.

 
public interface Informable {
    void messageChanged(String message);
}

The worker also requires an instance of the interface as it will be used to publish the results through.

 
import java.io.File;
import java.util.List;
import javax.swing.SwingWorker;
 
public class SearchForWordWorker 
             extends SwingWorker<Integer, String> {
 
  private final String word;
  private final File[] documents;
  private final Informable informable;
 
  public SearchForWordWorker(String word,
                                File[] documents,
                                Informable informable){
    this.word = word;
    this.documents = documents;
    this.informable = informable;
  }
 
  @Override
  protected Integer doInBackground() throws Exception {
    int matches = 0;
    for(int i=0, size=documents.length; i<size; i++){
      // Update the status: the keep an eye on thing
      publish("Searching file: "+documents[i]);
 
      try {
        // Do the search stuff
        // Here you increment the variable matches
      } finally {
        // Close the current file
      }
 
      // update the progress
      setProgress( (i+1) * 100 / size);
    }
 
    return matches;
  }
 
  @Override
  protected void process(List<String> chunks){
    for(String message : chunks){
      informable.messageChanged(message);
    }
  }
}

The above worker can be easily plugged into the application as show in the following example. This application has three graphical components: a label acting as a title displaying the latest message published by the worker; a text area which displays all messages published by the worker; and a progress bar showing the progress made.

Demo: Swing Worker Application

The label and text area are governed by Informable interface. The progress bar is governed by the worker's progress property.

 
import java.awt.*;
import java.beans.*;
import java.io.*;
import javax.swing.*;
 
public class Application extends JFrame {
 
  // The UI Components
  private JLabel label;
  private JProgressBar progressBar;
  private JTextArea textArea;
 
  private void initComponents(){
    // The interface will update the text of the UI components
    Informable informable = new Informable(){
      @Override
      public void messageChanged(String message){
        label.setText(message);
        textArea.append(message + "\n");
      }
    };
 
    // The UI components
    label = new JLabel("");
    add(label, BorderLayout.NORTH);

    textArea = new JTextArea(5, 30);
    add(new JScrollPane(textArea), BorderLayout.CENTER);
 
    progressBar = new JProgressBar();
    progressBar.setStringPainted(true);
    add(progressBar, BorderLayout.SOUTH);
 
    //  The worker parameters
    String word = "hello";
    File[] documents = {new File("Application.java"),
                        new File("Informable.java"),
                        new File("SearchForWordWorker.java")};
 
    // The worker
    SearchForWordWorker worker =
           new SearchForWordWorker(word, documents, informable){
       // This method is invoked when the worker is finished
       // its task
      @Override
      protected void done(){
        try {
          // Get the number of matches. Note that the 
          // method get will throw any exception thrown 
          // during the execution of the worker.
          int matches = get();
          label.setText("Found: "+matches);
 
          textArea.append("Done\n");
          textArea.append("Matches Found: "+matches+"\n");

          progressBar.setVisible(false);
        }catch(Exception e){
          JOptionPane.showMessageDialog(Application.this, 
                        "Error", "Search", 
                        JOptionPane.ERROR_MESSAGE);
        }
      }
    };

    // A property listener used to update the progress bar
    PropertyChangeListener listener = 
                               new PropertyChangeListener(){
      public void propertyChange(PropertyChangeEvent event) {
        if ("progress".equals(event.getPropertyName())) {
          progressBar.setValue( (Integer)event.getNewValue() );
        }
      }
    };
    worker.addPropertyChangeListener(listener);
 
    // Start the worker. Note that control is 
    // returned immediately
    worker.execute();
  }
 
  // The main method
  public static void main(String[] args){
    SwingUtilities.invokeLater(new Runnable(){
      public void run(){
        Application app = new Application();
        app.initComponents();
        app.setDefaultCloseOperation(EXIT_ON_CLOSE);
        app.pack();
        app.setVisible(true);
      }
    });
  }
}

The above example builds the application and kicks off the worker. The worker updates the application through the Informable instance. While the worker is performing it task, the application can carry on doing other things (event listening and painting) without hanging.

Cancel the Worker

Can we cancel the task? Yes. The worker can be stopped or better cancelled. The worker provides a method called cancel which accepts a parameter of type boolean. This parameter determines whether or not the worker should be waked up should it be found sleeping.

 
import java.awt.*;
import java.awt.event.*;
import java.beans.*;
import java.io.*;
import javax.swing.*;
 
public class Application extends JFrame {
 
  private JLabel label;
  private JProgressBar progressBar;
  private JTextArea textArea;
  private JButton  button;
  private SearchForWordWorker worker;
 
  private void initComponents(){
    // The interface will update the text of the UI components
    Informable informable = new Informable(){
      @Override
      public void messageChanged(String message){
        label.setText(message);
        textArea.append(message + "\n");
      }
    };
 
    // The UI components
    label = new JLabel("");
    add(label, BorderLayout.NORTH);
 
    textArea = new JTextArea(5, 30);
    add(new JScrollPane(textArea), BorderLayout.CENTER);

    // The cancel button 
    button = new JButton("STOP");
    button.addActionListener(new ActionListener() {
      public void actionPerformed(ActionEvent event) {
        // Cancel the worker and wake it up should it be sleeping
        worker.cancel(true);
      }
    });
    add(button, BorderLayout.EAST);
 
    progressBar = new JProgressBar();
    progressBar.setStringPainted(true);
        add(progressBar, BorderLayout.SOUTH);
 
    //  The worker parameters
    String word = "hello";
    File[] documents = {new File("Application.java"),
                        new File("Informable.java"),
                        new File("SearchForWordWorker.java")};
                        
    // The worker
    worker = new SearchForWordWorker(word, documents, informable){
      @Override
      protected void done(){
        try {
          int matches = get();
          label.setText("Found: "+matches);

          textArea.append("Done\n");
          textArea.append("Matches Found: "+matches+"\n");
 
          progressBar.setVisible(false);
        }catch(Exception e){
          JOptionPane.showMessageDialog(Application.this, 
                       "Error", "Search", 
                       JOptionPane.ERROR_MESSAGE);
        }
      }
    };

    // A property listener used to update the progress bar
    PropertyChangeListener listener = 
                               new PropertyChangeListener(){
      public void propertyChange(PropertyChangeEvent event) {
        if ("progress".equals(event.getPropertyName())) {
          progressBar.setValue( (Integer)event.getNewValue() );
        }
      }
    };
    worker.addPropertyChangeListener(listener);
    
    // Start the worker. Note that control is 
    // returned immediately
    worker.execute();
  }
 
  public static void main(String[] args){
    SwingUtilities.invokeLater(new Runnable(){
      public void run(){
        Application app = new Application();
        app.initComponents();
        app.setDefaultCloseOperation(EXIT_ON_CLOSE);
        app.pack();
        app.setVisible(true);
      }
    });
  }
}

This will cause the worker's get method to throw the exception CancellationException to indicate that the worker was forced cancellation.

Conclusion

One thing to take from this article is: when possible do not refer to UI components directly from the worker. The worker is better viewed as the subject of the observer pattern. Provide an interface which the worker will use to communicate with its owner (application).

Monday 1 September 2008

Automatic logon on Intranet Sites from Java Web Application

We can have Microsoft Internet Explorer providing information of the current logged in user when accessing intranet sites. Then we can use NTLM to retrieve such information as discussed in this article.

Note that Kerberos is more secure than NTLM.

Configure Internet Explorer for Windows Native Authentication

The following article is an abstract from: http://download.oracle.com/docs/cd/B28196_01/idmanage.1014/b15995/odip_actdir.htm#i1010999

Configure Internet Explorer to use Windows Native Authentication. How you do this depends on which version you have.

  • Internet Explorer 5.0 and Later
  • Internet Explorer 6.0 Only

Internet Explorer 5.0 and Later

To configure Internet Explorer 5.0 and later, perform the following steps:

  1. From the menu bar, select Tools, then, from the Tools menu, select Internet Options.
  2. In the Internet Options dialog box, select the Security tab.
  3. On the Security tab page, select Local Intranet, then select Sites.
  4. In the Local intranet dialog box, select Include all sites that bypass the proxy server; then click Advanced.
  5. In the advanced version of the Local intranet dialog box, enter the URL of the middle tier server.
  6. Click OK to exit the Local intranet dialog boxes.
  7. In the Internet Options dialog box, select the Security tab; then choose Local intranet; then choose Custom Level.
  8. In the Security Settings dialog box, scroll down to the User Authentication section and then select Automatic logon only in Intranet zone.
  9. Click OK to exit the Security Settings dialog box.

Internet Explorer 6.0 Only

If you are using Internet Explorer 6.0, perform the above steps in "Internet Explorer 5.0 and Later" then perform the following steps:

  1. From the menu bar, select Tools, then, from the Tools menu, select Internet Options.
  2. In the Internet Options dialog box, select the Advanced tab.
  3. On the Advanced tab page, scroll down to the Security section.
  4. Select Enable Integrated Windows Authentication (requires restart).

The above setting can be applied using Group Policy Objects. Please refer to: http://support.microsoft.com/kb/274846 for further information about this.

Retrieve username from Java Servlet

The following code is also available at: http://www.rgagnon.com/javadetails/java-0441.html

The method doIt (within a Servlet) gets the authorisation from the request header if it is available.


protected void doIt(HttpServletRequest request,
     HttpServletResponse response) throws IOException {

 String auth = request.getHeader("Authorization");
 if (auth == null) {
  response.setStatus(response.SC_UNAUTHORIZED);
  response.setHeader("WWW-Authenticate", "NTLM");
  response.flushBuffer();
  return;
 }

 if (auth.startsWith("NTLM ")) {
  byte[] msg =
   new sun.misc.BASE64Decoder()
        .decodeBuffer(auth.substring(5));
  int off = 0, length, offset;
  if (msg[8] == 1) {
   byte z = 0;
   byte[] msg1 =
   { (byte)'N', (byte)'T', (byte)'L', (byte)'M', (byte)'S',
     (byte)'S', (byte)'P', z, (byte)2, z, z, z, z, z, z, z,
     (byte)40, z, z, z, (byte)1, (byte)130, z, z, z, (byte)2,
     (byte)2, (byte)2, z, z, z, z, z, z, z, z, z, z, z, z };
   response.setHeader("WWW-Authenticate",
          "NTLM " 
          + new sun.misc.BASE64Encoder().encodeBuffer(msg1));
   response.sendError(response.SC_UNAUTHORIZED);
   return;
  } else if (msg[8] == 3) {
   off = 30;

   length = msg[off + 17] * 256 + msg[off + 16];
   offset = msg[off + 19] * 256 + msg[off + 18];
   String remoteHost = new String(msg, offset, length);

   length = msg[off + 1] * 256 + msg[off];
   offset = msg[off + 3] * 256 + msg[off + 2];
   String domain = new String(msg, offset, length);

   length = msg[off + 9] * 256 + msg[off + 8];
   offset = msg[off + 11] * 256 + msg[off + 10];
   String username = new String(msg, offset, length);

   PrintWriter out = response.getWriter();
   out.println("Username: " + username);
   out.println("RemoteHost: " + remoteHost);
   out.println("Domain: " + domain);
  }
 }
}