Simple 2-Way Chat with Java

In this post, I'm going to discuss how to create a simple chat application with Java. Basically, this is going to be a tutorial on Socket API and Java Thread API.

Here is the basic idea. A chat class should be running two tasks simultaneously: one is to send messages that the user inputs, and the other is to receive incoming message from the other side. Because these two tasks should be run simultaneously, we will need to implement a multi-threaded application.

I am going to let the main thread take care of user input and transmitting over to the other side, and a separate thread for receiving any incoming messages. Here we go.

So, the base class is ChatThread, which pretty much takes care of what I described above. The main thread takes care of user input and transmitting over to the other side, whereas a separate thread is going to run in the background, which receives incoming messages.

For this 2-way simple application, there are only two sides: one for server and the other for client. The server needs to take care of creating the server socket and wait for a client to join. Once the client joins, the server starts the ChatThread. The client will simply join the server and start the chatThread.

The implementation here is very basic and doesn't take care of properly exiting the connections. However, this should give you good introduction as to how to deal with socket programming and threading.

Happy hacking!

Java Comparable and Comparator

In this tutorial, I will go over two similar but very different interfaces in Java: comparable and comparator. For official documentations on these, refer to here and here.

Comparable and Comparator are both Java interfaces to compare two or more objects. The difference is that comparable is the default comparator of the object, whereas comparator is a custom comparison implementation.

For example, assume you are entering personal info. For each personal info object, you have one's name, year, month, and date of birth. One way to sort a list of personal info objects is by their names, but another way is to sort by the date of birth. In Java, one will be able to sort by name or date of birth by providing corresponding comparator to the class. On the other hand, if one is to simply sort the objects without any comparator provided, then the list will be sorted by the class' comparable interface.

Let's take a look at an example.

To run it, simply type in
$ javac Personal.java && java Personal

Sorting by default
Bob 1999, 1, 2
Charles 1955, 7, 4
Mike 2011, 4, 1
Tom 2011, 4, 4
Tony 2000, 5, 5
Tony 1987, 12, 11

Sorting by date of birth
Charles 1955, 7, 4
Tony 1987, 12, 11
Bob 1999, 1, 2
Tony 2000, 5, 5
Mike 2011, 4, 1
Tom 2011, 4, 4

Sorting by name
Bob 1999, 1, 2
Charles 1955, 7, 4
Mike 2011, 4, 1
Tom 2011, 4, 4
Tony 1987, 12, 11
Tony 2000, 5, 5

In the first sorting, no comparator is provided, so the list is sorted by Personal's comparable interface, namely compareTo method. For the second and third sorting, DobComparator and NameComparator is provided, so the list is sorted by the date of birth and name, respectively. The comparator classes provide compare method which specifies the order in which the list is to be sorted.

Assertion: Great Practice for Software Development

In this post, I will discuss recommended usage of assertion in programming. For both C/C++/Java, assert is a great way to alert a programmer that there is something against his expectation.

Let's do a quick example. Say you are implementing quick sort. In particular, you are trying to validate your partition method. You can insert an assertion to make sure that your partition method is functioning as expected, as below:

Well, you must agree that assertion is a very great tool for debugging, as it tells you exactly where it could have gone wrong. Unfortunately, assertion will slow down the performance and is not needed for production code, so do we need to comment them out when releasing the code for production?

In fact, both C/C++ and Java has a nice way to disable and enable the entire assertion statements. For C/C++, you simply need to define a macro NDEBUG, which will disable all assertions. Otherwise, assertions are enabled by default, unless of course you define NDEBUG macro in your source files explicitly. Therefore, you need disable assertions at compile time for production binary:

$ g++ *.cpp -DNDEBUG

Here, -D is the option for implicit #define macro, so the option -DNDEBUG will define NDEBUG macro for all files.

For Java, there is -da and -ea options which will disable and enable assertions, respectively at the runtime. In fact, assertions are by default disabled in Java, so you need to enable with -ea option when debugging, as below:

$ java -ea SomeClass

For more info, please refer to this and this official documentations.

Happy coding!

Setting up Environment for Coursera's Algorithm Class

Yes, I am taking the very basic algorithm class from Coursera. In fact, this class is very good. It is actually a course from Princeton, and I really like the course, except that they use Java, which I am not as familiar with compared to C/C++.

On top of that, the author provides custom jar library which I must use for compiling and running Java projects. Although the instructions are written very clearly on the official website, I still want to go over this bit, because I spent quite some time figuring this out.

In order to compile Java with a custom library, one must specify the library's path with -classpath flag as below:
$ javac -classpath /path/to/custom/library.jar SomeClass.java -g

Also, it is handy to include -g flag so that one can debug it later. If you are compiling a program that uses algs4.jar library file provided by the author, you must download the file and specify it with -classpath flag.

In order to run the program, you need to do the same thing, but with the path to source files as well:
$ java -classpath /path/to/custom/library.jar:/directory/to/source/files SomeClass 

Finally, to debug, you need to do the same thing:
$ jdb -classpath /path/to/custom/library.jar:/directory/to/source/files SomeClass

Let's do an example. Let's assume that you have downloaded algs4.jar file to ~/Downloads folder. Say you have created Queue.java file in ~/Documents folder.

You will need to run the following commands to compile, run, and debug Queue.java, respectively:
$ javac -classpath ~/Downloads/algs4.jar ~/Documents/Queue.java -g
$ java -classpath ~/Downloads/algs4.jar:~/Documents Queue
$ jdb -classpath ~/Downloads/algs4.jar:~/Documents Queue

Happy coding algorithms!

Local Thresholding from Zxing Library (Java)

Although OpenCV has its own local threshold method, such as adaptiveThreshold, I was looking for something a bit sophisticated and better. After some search, I came across Zxing's HybridBinarizer class that does the job much better than simple adaptiveThreshold from OpenCV. So, below is a very rough code to make use of this excellent library in Java. If you want to do this in C++, refer to this tutorial.

I admit that the code above is a bit messy, but it is just for testing out to see this actually works. In writing the code, I would like to acknowledge the following especially helpful references.

Zxing

Java - get pixel array from image

To compile the file and run it, first, create Test.java with the code above. Then, download Zxing's core library file (most recent version at the time of writing this is core-3.3.0.jar) form here. Then, run the following, assuming the jar file is in the same directory.

$ javac Test.java -cp ".:core-3.3.0.jar"
$ java -cp ".:core-3.3.0.jar" Test image_to_test.jpg

This will output the local thresholded image binary_output.jpg to the same folder. If you want to know more about java and javac -cp option, refer to this tutorial.

Java Compilation with Package and Jar Dependencies

In this tutorial, I will go over Java package and dependencies basics.

Let's go over the simplest java code with package declaration. Let's assume we are working on ~/java_package directory. Create Hello.java file below in the current directory:


To compile and execute this, we will first create a directory whose name is equal to the package name. In this case, the directory name should be pkgtest. So, create this directory and move Hello.java file into this. Run all of the following from ~/java_package directory:
$ mkdir pkgtest
$ mv Hello.java pkgtest/

Next, we need to compile. This is very simple.
$ javac pkgtest/Hello.java

Finally, we need to run it.
$ java pkgtest/Hello
hello

Note that you must run this from ~/java_package directory; otherwise java will complain with the error below:
$ cd pkgtest
$ java Hello
Error: Could not find or load main class Hello


Next, we will see how to import the package. Modify pkgtest/Hello.java and create ./JarTest.java as below:


To compile and run, run the following from ~/java_package directory:
$ javac JarTest.java
$ java JarTest
hello
hi


Next, we will create a jar library file and use this to compile and run. First, let's create the jar library. Run the following in ~/java_package directory
$ javac pkgtest/Hello.java
$ jar cvf pkgtest.jar pkgtest/Hello.class
added manifest
adding: pkgtest/Hello.class(in = 648) (out= 372)(deflated 42%)

This creates pkgtest.jar file, which contains Hello class.

Next, we will rename the pkgtest directory so that we don't compile from the source.
$ mv pkgtest pkgtest_bk

Let's see what happens if don't specify the jar file as we compile.
$ javac JarTest.java
JarTest.java:1: error: package pkgtest does not exist
import pkgtest.Hello;
              ^
JarTest.java:5: error: cannot find symbol
        Hello.print("hello");
        ^
  symbol:   variable Hello
  location: class JarTest
JarTest.java:6: error: cannot find symbol
        Hello h = new Hello();
        ^
  symbol:   class Hello
  location: class JarTest
JarTest.java:6: error: cannot find symbol
        Hello h = new Hello();
                      ^
  symbol:   class Hello
  location: class JarTest
4 errors

As you can see above, java compiler complains that it cannot find some symbols, since we renamed the package directory. To resolve this, let's link the jar file:
$ javac -cp ".:pkgtest.jar" JarTest.java
$ java -cp ".:pkgtest.jar" JarTest
hello
hi

Viola! Let's call it a day.

Java Threading: Synchronization II

In the previous post, we looked at how synchronized methods can be used to ensure safe access to a single object, where multiple threads try to read/write to it.

Here, we improve upon the example. In the last post, I mentioned that there were still fixes to be made, and today we will discuss one of them.

Below is the copy from the previous lesson. Take a closer look at the run() method of removeThread, line 54-57 below:


You will notice that the thread continuously checks whether there is at least 1 or more elements in the queue, and when there is, it calls dequeue() method. The question is: can we guarantee that element in the queue will remain in between the two calls? That is, what if another thread calls dequeue() in between, intercepting the element first? This is certainly possible...

Solution? I'd say we fix this issue by having dequeue() method check for the number of elements in the queue. Since dequeue() method is synchronized, it is guaranteed that if there is an element, it will be able to retrieve it for sure. What if there is no element in the queue? It will return immediately with an exception stating that there is no element to retrieve. Thus, we need to modify removeThread run() method to loop dequeue() method continuously until it does not throw an exception. Take a look at code below for implementation.


The modified code above certainly is better than the previous version, but we are not done yet. There are still a few more fixes to be made, and we will tackle one by one in the subsequent posts!

Android Threading: Handler Example

In this post, we will go over a very simple Handler example for Android development. Hopefully this post will explain and demonstrate why and how to use Handler class in Android.

Consider a very simple app, where you have two buttons: task button and increment button.

Upon click, the task button will notify the user that the task is now running, and carry out some heavy task, which may take up to seconds. When complete, it will notify the user that the task is finally done.

Upon click, the increment button will simply increment counter and display its current value.

Let's take a look at a crude attempt to implement this using a simple Thread. Here is the layout file.

Here is the implementation activity file.


Here, upon the task button click, it launches the task, which is simulated by sleep(3000), on a separate thread so that we don't slow down the main UI thread. However, the problem is that we must wait for this task thread to complete because we need to update the button's text upon completion. Thus, we use join() method to wait for the task to complete. With this implementation, we find that the UI thread becomes unresponsive while waiting. This is NOT a good way of implementing the task.

The core problem is that we ask the task thread to carry out some heavy task, and we need to make sure that the main UI thread does not just sit and wait, but rather do its jobs on its own. The task thread then must communicate with the UI thread and let it know the task is complete, at which point, the UI thread can update the UI accordingly.

The Handler class in Android achieves exactly this, and below is modification that makes use of the Hander class.


As you can see, the task thread will do its job, and when the task is complete, it notifies the main UI thread that the job is done through handler. The handler is created in the main activity, so it is bound to the main UI thread. When the handler receives a message from the task thread that the job is complete, it will then update the button's text. In the meantime, the main UI task carries out its own tasks, such as incrementing the counter when the increment button is pressed.

Of course, one can implement this without using the Handler class, shown below. However, this solution is possible because we are communicating with the UI thread in this example. If, however, you have two different task threads that must communicate with each other, then you need to use the Handler.

Java Threading: Synchronization I

In this example, we will look into a simple example that uses java's synchronized keyword.
Consider the following unsafe shared queue example first.

public class SharedQueueUnsafe
{
    private int[] queue;
    private int head, tail, num_elems;
    private int size;

    public SharedQueueUnsafe(int size)
    {
        this.size = size;
        queue = new int[size];
        for (int i=0; i<size; i++)
            queue[i] = -1;
        head = tail = num_elems = 0;
    }
    public void enqueue(int data)
    {
        num_elems++;
        System.out.println("inserting " + data + " into the queue");
        try
        {
            Thread.sleep(100);
        }
        catch (InterruptedException ie)
        {
        }
        queue[head] = data;
        head = (head + 1) % size;
    }
    public int dequeue()
    {
        num_elems--;
        int ret = queue[tail];
        tail = (tail + 1) % size;
        return ret;
    }
    public int getElementsInQueue()
    {
        return num_elems;
    }
    static public void main(String[] args)
    {
        SharedQueueUnsafe sharedQueue = new SharedQueueUnsafe(10);
        Thread insertThread = new Thread()
        {
            public void run()
            {
                sharedQueue.enqueue(12345);
            }
        };
        Thread removeThread = new Thread()
        {
            public void run()
            {
                while (sharedQueue.getElementsInQueue() <= 0)
                    ;
                int element = sharedQueue.dequeue();
                System.out.println("retrieved " + element);
            }
        };
        insertThread.start();
        try
        {
            Thread.sleep(50);
        }
        catch (InterruptedException ie)
        {
        }
        removeThread.start();
    }
}

Two threads are created such that one thread is inserting elements while the other is retrieving. To demonstrate racing condition, the enqueue method is designed to be intentionally slow. When I compile and run this, I get

$ javac SharedQueueUnsafe.java && java SharedQueueUnsafe
inserting 12345 into the queue
retrieved -1

This is because the retrieving thread accessed the queue before it was actually inserted, so that it retrieved the initialization value of -1 rather than 12345.

A crude solution to prevent this happening is rather trivial. We simply make sure that enqueue, dequeue, and getElementsInQueue methods to execute exclusively for a single object. That is, however many threads want to access these methods simultaneously, we force only a single thread can actually access only one of the synchronized methods at any given time. This will of course bring up side effect: performance issue, but for not let's not worry about it yet. We just want to solve the racing condition here.

Java language supports keyword synchronized for methods for this purpose. We simply let each method synchronized such that only a single thread can run any one synchronized method at a given time. Other threads must wait until the current thread is done executing the method. This is rather trivial in this case, and the code is as follows:

public class SharedQueueSafe

{

    private int[] queue;

    private int head, tail, num_elems;

    private int size;

    public SharedQueueSafe(int size)

    {

        this.size = size;

        queue = new int[size];

        for (int i=0; i<size; i++)

            queue[i] = -1;

        head = tail = num_elems = 0;

    }

    public synchronized void enqueue(int data)

    {

        num_elems++;

        System.out.println("inserting " + data + " into the queue");

        try

        {

            Thread.sleep(100);

        }

        catch (InterruptedException ie)

        {

        }

        queue[head] = data;

        head = (head + 1) % size;

    }

    public synchronized int dequeue()

    {

        num_elems--;

        int ret = queue[tail];

        tail = (tail + 1) % size;

        return ret;

    }

    public synchronized int getElementsInQueue()

    {

        return num_elems;

    }

    static public void main(String[] args)

    {

        SharedQueueSafe sharedQueue = new SharedQueueSafe(10);

        Thread insertThread = new Thread()

        {

            public void run()

            {

                sharedQueue.enqueue(12345);

            }

        };

        Thread removeThread = new Thread()

        {

            public void run()

            {

                while (sharedQueue.getElementsInQueue() <= 0)

                    ;

                int element = sharedQueue.dequeue();

                System.out.println("retrieved " + element);

            }

        };

        insertThread.start();

        try

        {

            Thread.sleep(50);

        }

        catch (InterruptedException ie)

        {

        }

        removeThread.start();

    }

}

With this new class, we get correct result.

$ javac SharedQueueSafe.java && java SharedQueueSafe

inserting 12345 into the queue

retrieved 12345

Well, the solution above is only a temporary crude solution. There are some more fixes to be made, but let's not worry about them for now. We will revisit this example in subsequent posts (part II).

Java Threading: Simplest Example

In the series of posts, I will present Java's threading APIs. Today's example is the simplest threading example using anonymous class in Java.

public class SimpleThread
{
    public static void main(String[] args)
    {
        Thread thread1 = new Thread()
        {
            public void run()
            {
                int i = 0;
                while (i < 10)
                {
                    System.out.println(++i);
                    try
                    {
                        sleep(100);
                    }
                    catch (InterruptedException ie)
                    {
                    }
                }
            }
        };
        Thread thread2 = new Thread()
        {
            public void run()
            {
                int i = 0;
                while (i < 10)
                {
                    System.out.println(++i + 10);
                    try
                    {
                        sleep(100);
                    }
                    catch (InterruptedException ie)
                    {
                    }
                }
            }
        };
        thread1.start();
        thread2.start();
    }
}

To compile and run
$ javac SimpleThread.java && java SimpleThread
1
11
2
12
13
3
4
14
5
15
6
16
7
17
8
18
9
19
10
20

This example is easy enough and self-explanatory!

Transition from C/C++/Java to Python

I am trying to learn Python myself, as it greatly expedites prototype development compared to C/C++/Java.
Here is quick conversion of C/C++/Java common codes into Python:

for (int i=0; i<N; i++) {
for i in range(N):

if (x==y) {
if x==y:

!true
not True

else if {
elif:

printf("%d\n", i)
print i

printf("%d ", i)
print i,

for (int i : array) {
for i in array:

vector<int> v;
v.push_back(1);
v.push_back(2);
v = [1,2]

// C++
vector<int> u,v;
...
v = u;
import copy
v = copy.copy(u) // OR // v = u[:]

// C++ vector<int> &u, &v;
...
v = u;
v = u

How to Change Default JDK with AlternativesI

Here is how to set Oracle's JDK as your default. You can apply this to set OpenJDK as default as well very easily.

First, you will need to download Oracle's JDK. Visit here to download the latest JDK for your system.

For Debian-based Linux, you simply need to download the tar.gz archive and extract to a folder. For example,

$ tar xvfz jdk-8u101-linux-x64.tar.gz

$ sudo mv jdk1.8.0_101 /opt/

Next, set Oracle's JDK as an alternative:

$ sudo update-alternatives --install /usr/bin/java java /opt/jdk1.8.0_101/bin/java 100

$ sudo update-alternatives --install /usr/bin/javac javac /opt/jdk1.8.0_101/bin/javac 100

Finally, set whichever version you would prefer:

$ sudo update-alternatives --config java

$ sudo update-alternatives --config javac

That's it!

Tower of Hanoi using Induction and Recursion

Induction is a very powerful method in mathematics; it provides simple yet elegant proofs. One of the most well-known problems that can be very easily tackled using induction is the Tower of Hanoi.

The problem is stated as follows.

There are three identical rods, and we are given N disks of varying sizes. All the disks are initially stacked up onto one of the rods in the descending order of the disk size from bottom to top, i.e., the largest on the bottom and the smallest on the top. We are to move all the disks from one rod to another with three rules:

1. Only one disk can be moved at a time.
2. Only the top-most disk can be moved from one rod and be placed onto a different rod.
3. No disk can be placed on top of a smaller disk.

With these rules, what is the method for moving some arbitrary N disks? What is the minimum number of moves required to do so?

It is rather a difficult problem at first glance. Probably the simplest way to solve this mathematically is by induction.

As with any other mathematical induction problem, one starts with the base case: N=1. We simply move the only disk from one rod to another. That's it. Very simple. So, the it requires f(1)=1 move, where f(n) represents the minimum number of moves required to solve the problem for n disks.

Next, we assume that we have a way of solving the case for some N=n. Utilizing this, can we solve the case for N=n+1? You bet! Assume that initially n+1 disks are stacked onto rod 1. We break the process of moving n+1 disks into three steps:
1. Move the upper n disks to a different rod, say rod 2 using the aforementioned assumption.
2. Move the largest disk to the other rod, say rod 3.
3. Move the n disks on rod 2 onto rod 3, again using the same method.

Note that these processes all obey the three rules for the Tower of Hanoi. In addition, this must be the minimum number of moves; there simply is no way to do it with fewer moves while still obeying the rules.

So, if it requires f(n) moves to solve the problem for the case of N=n, then we readily see that f(n+1)=2*f(n)+1, i.e., it requires 2*f(n)+1 moves to solve the problem for the case of N=n+1. Now, I will argue that f(n)=2^n-1. Let's prove this by induction.

Base case: f(1) = 2^1-1 = 1
Assumption: f(n) = 2^n-1
Next case: f(n+1) = 2*f(n)+1 = 2*(2^n-1)+1 = 2^(n+1)-1

That's it. We have proved it using induction. Now, it is time to implement in program. We do this by recursion. With it, I can get the step by step move instruction for moving, say 4 disks from rod 1 to 3.

$ javac Hanoi.java
$ java Hanoi 4
Move #1: disk1; rod 1==>2
Move #2: disk2; rod 1==>3
Move #3: disk1; rod 2==>3
Move #4: disk3; rod 1==>2
Move #5: disk1; rod 3==>1
Move #6: disk2; rod 3==>2
Move #7: disk1; rod 1==>2
Move #8: disk4; rod 1==>3
Move #9: disk1; rod 2==>3
Move #10: disk2; rod 2==>1
Move #11: disk1; rod 3==>1
Move #12: disk3; rod 2==>3
Move #13: disk1; rod 1==>2
Move #14: disk2; rod 1==>3
Move #15: disk1; rod 2==>3
Total moves required is 15

Below is the implementation in Java.

// Hanoi.java

public class Hanoi

{

  static int moves = 0;

  /** implements the Tower of Hanoi problem via recursion

   *  the argument to the program should be an integer N > 0

   */

  public static void main (String[] args)

  {

    int N;

    if (args.length == 0)

    {

      System.out.println ("Error: Provide a positive integer number N");

      System.exit(-1);

    }

    N = Integer.parseInt(args[0]);

    if (N < 1)

    {

      System.out.println ("Error: N must be positive");

      System.exit(-1);

    }

    int moves = moveDisks (N, 1, 3);

    if (moves != Hanoi.moves)

    {

      System.out.println ("Error: Something is wrong with the implementation!!");

      System.exit(-1);

    }

    System.out.println ("Total moves required is " + moves);

    return;

  }

  /** recursively move n disks to a different rod

   *  three rods are indexed 1,2,3

   *

   * @param n is the number of disks to move

   * @param from is the rod index from which to move

   * @param to is the rod index to which to move

   * @return the minimum number of moves

   */

  static int moveDisks (int n, int from, int to)

  {

    if (n == 1)

    {

      /* base case */

      moves++;

      System.out.println ("Move #" + moves + ": disk1; rod " + from + "==>" + to);

      return 1;

    }

    /* index number of the remaining rod */

    int rem = 1;

    for (int i=1; i<=3; i++)

    {

      if (rem == from || rem == to)

        rem++;

      else

        break;

    }

    /* move n-1 disks from FROM to REM */

    int sum = moveDisks (n-1, from, rem);

    /* move the largest disk */

    moves++;

    System.out.println ("Move #" + moves + ": disk" + n + "; rod " + from + "==>" + to);

    sum++;

    /* move the n-1 disks back from REM to TO */

    sum += moveDisks (n-1, rem, to);

    return sum;

  }

}