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.

nil, NULL, and release

Just a quick note about how to check whether an object is null or not in Objective-C. In java, it is easy to do that through 'null' keyword. While in Objective-C, there are two keywords, 'NULL' and 'nil', to deal with that action. What is the difference? NOTHING. Both keywords point to __DARWIN_NULL which is defined as : #define NULL ((void *)0) . It means, they point to address 0 in memory.

When we release an object using [object release], don't forget to set it to nil or NULL because when we compare it in 'if' statement, it won't be true because it is still pointing to its old address.

For example:

MyViewController c = [[MyViewController alloc] init];
[c release];

If we compare it in 'if' statement if(c), the statement will return true because the pointer is still pointing to its address even tough we have released it before. We need to set it to nil or NULL c = nil to make it point to address 0. After we do that, if(c) will return 0, which is false in C.

Objective-C Event Handling Overview

Objective-C manages user input event as responder chain. It goes backward up from the first responder (object that user is interacting with) until application delegate at the top most.



UIResponder contains methods to catch events. When we create a view as subclass of UIView, it inherits methods to access the events.



We can handle the events by implementing those methods. Following MVC pattern, usually we will delegate it to a controller.

-(void) touchesEnded:(NSSet *)touches withEvent:(UIEvent *)event {
[controller doSomething];
}

UIControl Target Action Events

When we work with events, the UIResponder class holds many of the methods critical for event control. Similarly, we can access a lot of the methods important to SDK controls through the UIControl class. UIControl is a child of UIView (and thus UIResponder).

The UIControl object introduces a whole new event-handling infrastructure that takes touch events and (eventually) converts them into simple actions, without having to worry about the specifics of how a user accessed control.



When a touch event arrives at a UIControl object (via normal dispatching along the responder chain), the control does something unique. Inside the standard UIResponder methods (such as touchesBegan:withEvent:), a UIControl object turns standard touch events into special control events. These control events broadly describe how the user has interacted with the controls rather than just recording gestures. For example, they might report that a button has been pushed or a slider moved.

Once a standard event has been turned into a control event, a sequence of additional methods is called. First, the UIControl object calls sendActionsForControlEvents:. That in turn breaks down the events it’s been sent and calls sendAction:to:forEvent:, once per event. Here the control event is turned into an action, which is a specific method that’s going to be run in a specific target object. Finally the UIApplication method sendAction:to:fromSender:forEvent: is called by the control, again once per event.

That whole process can be slightly exhausting, and fortunately we shouldn’t normally need to know its details. For our purposes, we should be aware that a UIControl object turns a touch event first into a control event and then into an action with a specific recipient. Even better, it’s only the last part of that conversion, from control event into targeted action, which we need to code.

Summary

Events are catched by the view (UIView) and then, following MVC pattern, they are delegated to the controller to be handled.

Delegate

Usually if we want to add new behavior in an existing object, we do inheritance. For example if we have class Apple below:



If we want the Apple class to have a new behavior such as growAppleInDesert(), we have some options:
1. Put the new method in interface or parent class, IFruit. This will apply to all subclasses, however.
2. Put the new method in Apple class. This can be done; however, if our Apple class is a simple UI, adding the action growAppleInDesert() here will break layering pattern.
3. Subclass Apple to create new class, say DesertApple. This is what OO design pattern suggested.
4. Create new class, say AppleGrowAction which contains growAppleInDesert() , growAppleInMeadow(), etc. Our current Apple object can then refer to the new AppleGrowAction class to call its methods. This is known as delegate.
5. Using "Category" feature of Objective-C. This will be explained later.

Another example is if we want to create a new component from an existing one. We have some options:
1. We can inherit the existing component; however, if the component has so many methods, we will end up having those methods in our class.
2. Put the component as delegate, our new component will only need to call methods in existing component.

In Cocoa Framework, delegate usually implemented as protocol. For example if we have a control UITextField, we will need to implement UITextFieldDelegate protocol in order to handle text field event.



In Java it is common to do (3) or (4), but, in Objective-C, (4) is widely used. It is called delegation because we delegate some tasks to another object.

Category

Category is an Objective-C feature that allows us to extend the capability of a given class. This feature works even if we do not have access to the source code of the class we are extending. When we extend a given class through a category, the extension is inherited by all its subclasses. Of course, the additional methods defined by the category are only seen by our program.

To illustrate this feature, let us extend the NSObject class by adding an instance method to it:

Java reference, Objective-C retain count

Java

How Java's garbage collector knows that an object must be destroyed? An object is a candidate for garbage collector if they lose all its references. For example Object B below. It is referred by variable B1 and B2. Once both B1 and B2 lose reference to it, none knows that it exists, then it becomes candidate for garbage collector.



Objective-C

Objective-C on the other hand, uses different approach. Each object holds a variable named retainCount. It is set to 1 the first time the object created. It is incremented anytime the object retained or copied. It is decremented anytime it is released. When the retainCount equals zero, the object is destroyed.

Those differences happen because they use different approach in memory management. Java depends on its garbage collection algorithm to release unused memory, while Objective-C gives programmers more responsibility to release their objects. If you allocate memory, it is your responsibility to release it.

However, since XCode 4.2 Apple has put new feature called ARC (Automatic Reference Counting) to ease developers’ job dealing with allocating and releasing memory. It is sort of AOP implementation in Objective-C for me.

Using ARC, we don’t need to release memory we allocated before, in other words we don’t need to deal with retain-release code anymore. The compiler takes care the code of retaining-relasing objects. At compile time, the compiler crosscuts your code and adds some line of retain-release code. Using ARC we now only have to deal with our logic.

Java Environment

The picture above tells us a big picture of Java. Some codes written in Ada, Cobol, and C can be compiled into java byte code. The .class java byte code then translated by JVM into native machine language.

So, what is JVM? Lets see java installation directory:
1. JDK = java programs (java.exe, javac.exe, jar.exe, etc) + JRE
2. JRE = collection of Java API (lang, util, text, io, net, math, nio)
3. JVM = instance of JRE

Another term is JIT which is a part of JVM that compiles java byte codes that have similar functionality at the same compiling time so it will reduce compile time.

Java Heap Space

Heap is a part of memory used by JVM to allocate objects. There are three types of Java heap space:
1. Young Generation: Space to save short-live objects, they are method-scope objects or loop-scope objects.
2. Old/Tenured Generation: Space to save long-live objects, they are class-scope and application-scope objects.
3. Permanent Generation (permgen): Space to save class definition and its metadata.

There are some arguments that can be used to configure heap space:
1. -Xmx256M : Maximum heap space value is 256 MB.
2. -Xms128M: Initial heap space value is 128 MB. It will grow until xmx value is reached.
3. -Xmn64M: Heap space allocated for young generation.

There is nothing mentioned about default java heap space. It varies between machine, but wikipedia says it is 128M.

Java Block (Static, Non static, Constructor)

Hanya untuk pengingat saja, daripada terus googling

public class TestBlock {

{
System.out.println("This is object block...");
}

public TestBlock() {
System.out.println("This is constructor...");
}

static {
System.out.println("This is static block...");
}

public static void main(String args[]) {
TestBlock obj1 = new TestBlock();
TestBlock obj2 = new TestBlock();
}

}

Hasil :

This is static block...
This is object block...
This is constructor...
This is object block...
This is constructor...

Dari hasilnya, ketahuan urutan eksekusi dan jumlah eksekusi.