Insertion sort

Akhirnya sempat juga ngeblok di sela-sela ngoding iPhone ;)). Tak terasa sudah lama meninggalkan pulau Java. Sekarang ini sedang demam mempelajari kembali algoritma-algoritma yang sudah bertahun-tahun ditinggalkan. Sebagai permulaan sebaiknya mulai dari Insertion Sort. Berikut adalah implementasinya di Java:

public class Algoritma {

public static void main(String[] args) {
int[] input = new int[] {5, 2, 4, 6, 1, 3};
insertionSortIncrease(input);
System.out.println("\n");
insertionSortDecrease(input);
}

private static void insertionSortIncrease(int[] input) {
for (int j = 1; j < input.length; j++) {
int key = input[j];
int i = j - 1;
while (i >= 0 && input[i] > key) {
input[i + 1] = input[i];
i--;
}
input[i + 1] = key;
}
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + " ");
}
}

private static void insertionSortDecrease(int[] input) {
for (int j = 1; j < input.length; j++) {
int key = input[j];
int i = j - 1;
while (i >= 0 && input[i] < key) {
input[i + 1] = input[i];
i--;
}
input[i + 1] = key;
}
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + " ");
}
}

}

Pattern Builder and Factory

Builder and Factory are two different pattern, obviously. But sometimes I get confused because of their name. Both patterns act as object manager, they create object and hide the creation from user.

Factory is used to create object in an object family. Usually I pass a static number and the factory will go through if-else condition to decide what object to create.

Builder on the other hand, create an object based on some object characteristics. For example we have an xml file that holds object's state, and we want to create an object based on the file. We then pass the xml, then the Builder will create the object for us.

Thread: synch, lock, wait, notify, join

Synchronization

Synchronization in java works with object lock. Every object in java has a built-in lock that only comes into play when the object has synchronized method code. Since there is only one lock per object, if one thread has picked up the lock, no other thread can enter the synchronized code (which means any synchronized method of that object) until the lock has been released. Typically, releasing a lock means the thread holding the lock (in other word, the thread currently in the synchronized method) exits the synchronized method. At that point, the lock is free until some other thread enters a synchronized method on that object.

An example of synchronization is on account withdrawal. Usually, before making withdrawal, we check the account balance. We must guarantee that those two actions are never split apart. We need them to always be performed as one operation.

private synchronized void makeWithdrawal(int amt) {
if (acct.getBalance() >= amt) {
System.out.println(Thread.currentThread().getName() + " is going to withdraw");
try {
Thread.sleep(500);
} catch(InterruptedException ex) { }
acct.withdraw(amt);
System.out.println(Thread.currentThread().getName() + " completes the withdrawal");
} else {
System.out.println("Not enough in account for " + Thread.currentThread().getName() + " to withdraw " + acct.getBalance());
}
}

In previous code we simulate account checking and withdrawal as two action by making the thread to sleep. By putting those two actions in a single synchronized method, we make them as one operation.

Because each object has a built-in lock, we can synchronize a block of code instead of a method as in synchronized(obj). That means, the currently running thread is acquiring obj's lock so that no other thread can execute any synchronized method and block of code in object obj.

Thread Interaction

Consider the following scenario for thread interaction.

class Reader extends Thread {
Calculator c;

public Reader(Calculator calc) {
c = calc;
}

public void run() {
synchronized(c) {
try {
System.out.println("Waiting for calculation...");
c.wait();
} catch (InterruptedException e) {}
}
System.out.println("Total is: " + c.total);
}

public static void main(String [] args) {
Calculator calculator = new Calculator();
calculator.start();
new Reader(calculator).start();
new Reader(calculator).start();
new Reader(calculator).start();
}
}

class Calculator extends Thread {
int total;

public void run() {
synchronized(this) {
for(int i=0;i<100;i++) {
total += i;
}
notifyAll();
}
}
}

The Calculator object is responsible for calculating the total value. It extends Thread, and the calculating process is wrapped inside run method. Another class is the Reader class. This class responsibility is to display the total value, calculated by Calculator before, to console. Because both classes extend Thread, they will be run on their own thread. We need some way to let Calculator finish calculating first and then display the result to console.

Java provides methods to deal with that condition. Those methods are wait(), notify(), and notifyAll(). In order to use those methods, we must have the lock on the target object, in this case is Calculator (that's why we synchronized both run method). In the code above, we have three Reader referencing to one shared Calculator. When any of the Reader object runs, it will hold the Calculator lock and make the other Reader blocked. It will then wait for the Calculator by releasing the lock (when a thread calls wait() in an object, it will release the object's lock). Once the lock is released, other Reader object go to their own run method and they all will be blocked when calling c.wait, just like the first Reader. Now calculator has it's turn to execute it's synchronized run method and notify all waiting thread.

Java specs says that there is no guarantee on thread execution order. It means that the notify call (on Calculator thread) can take place first before Reader thread calls wait method. If this happens, the thread will never wake up. To prevent this, we can use wait method that accepts a number of milisecond as max time to wait.

Another approach is to check whether the total has been calculated or not, for example:


try {

if (!c.isFinished()) { // means the calculation is not finished yet
 System.out.println("Waiting for calculation...");
 c.wait();

}
} catch (InterruptedException e) {}

Using previous approach makes the thread waiting for the notification only when the calculation is not finished, not blindly waiting the notification.
 

Join

First time I learnt about join and wait/notify, it was pretty the same. After awhile, I can see the difference on the purpose / scenario. The above calculator example is about thread communication, two or more threads are talking to each other. An example of join is if we want to have a calculator for a reader. In that situation we can join the reader to calculator to make the reader waiting the calculator to finish and dead.