Saturday, March 22, 2014

Aggregation vs Composition through example in Java

There is a very thin line between Aggregation and Composition relationship between two classes. Both of these are a has-a relationship and that makes life difficult. Aggregation is a weak has-a relationship whereas Composition is a strong has-a relationship.

Let's take a simple example of three classes; Company, Department and Employee. Company consists of (or has ) Department and Department consists of Employee.

Aggregation vs Composition

The diamond end in both the cases points towards the whole class (or bigger and fatter class), with the only difference that Composition diamond is filled up (whereas Aggregation diamond is unfilled).

Another difference is that, in the case of Composition, the composite object has full responsibility for the component object. So a component object can't exist without the composite object in case of Composition. But in the case of Aggregation the coupling between the component and the composite is not so tight and thus component can enjoy life even without composite. 

What it means here is, Department can't exist without Company but Employee can exist even without Department. So, the association between Company and Department is stronger/tighter compared to that of between Department and Employee. 

Java Implementation

Aggregation, as well as composition, are implemented in the almost similar way in Java through Composition. The main difference lies in how you encapsulate the contained object. If the contained object is properly encapsulated inside the whole object then it will be composition. So in the case of Composition, the contained object doesn't have it's own identify. It comes and goes with the whole object.

To bring home the point, let's take a different example of two classes School and Student. The student is contained inside School. Also, School consists of more than one Student.

 /**  
  * Simple Student class     
  * @author Sid  
  */  
 class Student {  
      private String name;  
      private int standard;  
      public Student(String name, int standard) {  
           super();  
           this.name = name;  
           this.standard = standard;  
      }  
      //other attributes/methods  
 }  

 import java.util.ArrayList;  
 import java.util.List;  
 /**  
  * Simple School class  
  * @author Sid  
  */  
 public class School {  
      String name;  
      List<Student> students;  
      public School(String name) {  
           this.name = name;  
           this.students = new ArrayList<Student>();  
      }  
      // Enrolls new student  
      public boolean enrollStudent(String name, int standard) {  
           Student s = new Student(name, standard);  
           students.add(s);  
           return true;  
      }  
      // other attributes and methods  
 }  

 /**  
  * Class to test Student, School relationship  
  * @author Sid  
  */  
 public class SchoolClient {  
      public static void main(String[] args) {  
           School school = new School("DAV Public School");  
           school.enrollStudent("Sid Rai", 12);  
           school.enrollStudent("Rob D", 12);  
      }  
 }  

The relationship between Student and School is Aggregation or Composition?
Another way to put it is, Can an instance of Student exist without an instance of School?

Notice that, the creation of Student is encapsulated inside School class ( through enrollStudent(..) method).
By now, it should be obvious. Above code demonstrate Composition.

Just for completeness, How can you make the relationship as Aggregation in above example?
The simplest way is, refactor enrollStudent(..) method as :

       public boolean enrollStudent(Student s){....}

Similarly, you can achieve it in an Object Oriented Language.

References
---
do post your feedback !!!

Sunday, March 16, 2014

Bit Manipulation in Java

Java inherited bit manipulation from C. As a programmer you might not use it often, but still, it's quite important. Java integers are of 32 bits (4 bytes) and are signed. This means that left most bit (Most Significant Bit / MSB) works as the sign identifier. If it's 1, the number is negative (and positive if it's 0). Let's go in detail on the binary form of numbers:

Binary Representation of Numbers

Integer 1 in binary form  = 00000000000000000000000000000001  or 1
Integer -1 in binary form =11111111111111111111111111111111

In Java, you can get the binary representation of any number by calling toBinaryString() method of Integer class (Integer.toBinaryString(1)). The binary representation of -1 might be confusing if you are not aware of how negative numbers gets stored. Negative numbers get stored as two's complement which can be achieved by adding 1 to the NOT of the unsigned number i.e. ~number +1

Another way to look at it is, the weight of the MSB or leftmost bit is negative. So when this bit is 1, the number becomes negative. The binary form of -1 can be represented as:
   -2^31*1+ 2^30*1 + 2^29*1 + 2^28*1+ .... ......+ 2^1*1+2^0*1

Note that, the highest weighted component is negative (-2^31*1). This will result in the overall number being negative. We can cross check it by assuming a 4-bit number system.

1111 = -2^3*1 + 2^2*1 + 2^1*1 + 2^0*1
         = -8 +4 + 2 +1
         = -1

Using two's complement technique, -1 = ~1 +1
       -1 = ~1+1
          =  ~0001 + 1
          =   1110 + 1
          =   1111      

So either way, you will get the same representation of a negative number.

Bitwise Operators

We have used NOT binary operator above, now it's time to go over Java binary operators in detail. 

~ (NOT)
Flips or reverses all bits. Thus, every 1 becomes 0 and every 0 becomes 1. Also known as one's complement operator. It's a urinary operator so takes only one argument.
~101 produces 010

| (OR)
Produces one in output if at least one of the bit is 1 and produces 0 if both bits are 0.
101 | 10 produces 111

& (AND)
Produces 1 in output if both input bits are 1, otherwise, it results in 0.
101 & 10 produces 000

^ (EXCLUSIVE OR / XOR)
Produces 1 in the output if either of the bit is 1 (not both), otherwise 0
101 ^ 10 produces 111
2 ^ 10 produces 8  ( equivalent to 10 ^ 1010 )

Important Note
  • Difference between bitwise operators (&, |) with logical operators && and ||. Bit operators take integers and results in other integers but logical operators take booleans and return a boolean result.
  • Only NOT (~) is urinary, others are binary operators. 
  • Binary operators (i.e. | , & and ^) can be combined with the = sign like &=, |= and ^=

Shift Operators

Now let's go to the Java's powerful shift operators. 

<< (Left Shift Operator)
Used for shifting bits of a number on left side (i.e. 8 << 1 or 00001000 << 1). The value to the right of the operator indicates how many positions to shift the bits. Bits that fall off on the left side are lost and empty bits on the right side are filled up with 0. 
Note, the value can change sign depending on the state of first bit. 

>> (Signed Right Shift Operator)
Used for shifting bits of a number on the right side ( 8 >> 1). The value to the right of the operator indicates how many positions to shift the bits. 
  • When the sign is positive (leftmost bit is 0),  empty bits on left side fills up with 0. So it retains the sign. 
  • When the sign is negative (leftmost bit is 1), it performs sign extension. Fills up the empty bits on the left side with 1s. 
>>> (Unsigned Right Shift Operator)
Regardless of the sign, zeros are inserted to the left side or higher order bits.

Let's take a simple example to illustrate above operators
 public class BinaryOperators {  
      public static void main(String[] args) {  
           int i = 17;  
           System.out.println(" i :" + Integer.toBinaryString(i));  
           System.out.println(" ~i : " + Integer.toBinaryString(~i));  
           System.out.println(" -1 : " + Integer.toBinaryString(-1));  
           System.out.println(" -1 & i : " + Integer.toBinaryString(-1 & i));  
           System.out.println(" -1 ^ i : " + Integer.toBinaryString(-1 & i));  
           System.out.println(" i >> 2 : " + Integer.toBinaryString(i >> 2));  
           System.out.println(" i >>> 2 : " + Integer.toBinaryString(i >>> 2));  
           System.out.println(" i << 2 : " + Integer.toBinaryString(i << 2));  
           System.out.println(" -1 >> 2 : " + Integer.toBinaryString(-1 >> 2));  
           System.out.println(" -1 >>> 2 : " + Integer.toBinaryString(-1 >>> 2));  
           System.out.println(" -i >>>= 2 : " + Integer.toBinaryString(i >>>= 2));  
      }  
 }  

Output:

 i :10001
 ~i : 11111111111111111111111111101110
 -1 : 11111111111111111111111111111111
 -1 & i : 10001
 -1 ^ i : 10001
 i >> 2 : 100
 i >>> 2 : 100
 i << 2 : 1000100
 -1 >> 2 : 11111111111111111111111111111111
 -1 >>> 2 : 111111111111111111111111111111
 -i >>>= 2 : 100

Important Observations: 

  • Multiplication and Division:
      Shift operators can be used to multiply or divide a number. So if there is a need to multiply or divide a number by multiple of 2; you should prefer shift operators as it's more efficient. 

          int i = 5;
          i <<= 2 ;    //value of i becomes 20 i.e. 5*2*2

          i = 10;
          i >>=2;   // value of i becomes 2 i.e. 10/(2*2) = 2

          i = -4
          i >>=2 ;   // value of i becomes -1
  • Finding bit at a position:
           If you & a bit with 1; you will get the same bit.
           i.e. 0 & 1 = 0 ; 1&1 = 1
           This can be used to get the bit value in a number at the given position. 
           
           5 & 1 = 1   // 1001 & 1 
           5 &  10  = 0 // 1001 & 10; second last bit is 0 so the output is 0
----
that's it for now...do post your feedback about this post. 

Sunday, March 2, 2014

wait and notify in Java

The lock/monitor mechanism provided in Java prevents more than one thread from accessing a shared resource. Java achieves it by allowing only one thread to get hold of methods/block using synchronization technique. Thread safety comes at the cost of no direct communication between threads.

Some problem require inter-thread communication, though; like producer-consumer problems. Producers and consumers co-operate with each other and decide next action, which is difficult to achieve using default monitor lock. There is a need to bring in coordination between multiple threads. Java provides wait/notify methods to handle such problem which require two or more threads/tasks to talk to each other.

wait and notify methods

These methods are part of the superclass, Object. Let's cover them briefly before jumping to the example:

wait/wait(..): This method provides a way to synchronize activities between tasks. Within a task when you call wait(), the execution of the task gets suspended and the lock on the object is released. Once the lock is released, it can get acquired by another task.
Overloaded wait method (i.e. wait(100) takes an argument in milliseconds (similar to sleep). 

notify/notifyAll: Obvious question after call to wait is, what makes the task to resume? 
Task resumes if the same object calls notify or notifyAll method. If more than one tasks are in wait state, then notifyAll needs to be called instead of notify. So notify wakes up task(s) which is/are in wait state.

Example to understand wait and notify

Let's take a trivial example to show co-operation between two threads using wait and notify methods. ThreadCoordination class has two methods, one generates the random number and other one prints the same (getNextRandom() method waits until the next number is generated through the method, generateNextRandom()). The main method, test these two methods by creating two threads. These threads are generating and printing first ten random numbers.

 import java.util.Random;  
 import java.util.concurrent.TimeUnit;  
 public class ThreadCoordination {  
      private volatile int randomNum = 0;  
      Random rand = new Random(101);  
      public synchronized void generateNextRandom() throws InterruptedException{  
           while(randomNum != 0){  
                wait();  
           }  
           TimeUnit.SECONDS.sleep(2); //delay of 2 seconds  
           randomNum = rand.nextInt(101);  
           notify();  
      }  
      public synchronized void getNextRandom() throws InterruptedException {  
           while(randomNum == 0){  
                wait();  
           }  
           System.out.println(" Next Number is : "+ randomNum);  
           randomNum = 0 ; //reset the value  
           notify();  
      }  
      //Test method  
      public static void main(String[] args) {  
           final ThreadCoordination tc = new ThreadCoordination();  
           new Thread(){  
                public void run(){  
                     for(int i=0; i<10; i++){  
                          try {  
                               tc.getNextRandom();  
                          } catch (InterruptedException e) {  
                               e.printStackTrace();  
                          }  
                     }  
                }  
           }.start();  
           new Thread(){  
                public void run(){  
                     for(int i=0; i<10; i++){  
                          try {  
                               tc.generateNextRandom();  
                          } catch (InterruptedException e) {  
                               e.printStackTrace();  
                          }  
                     }  
                }  
           }.start();  
      }  
 }  

Output:

 Next Number is :21
 Next Number is :27
 Next Number is :82
 Next Number is :60
 Next Number is :69
 Next Number is :13
 Next Number is :11
 Next Number is :43
 Next Number is :17
 Next Number is :56

Note, both methods are using wait as well as notify to complement each other.  getNextRandom() waits until next random number gets generated in method generateNextRandom(). And generateNextRandom() waits until the generated number gets printed (and variable gets resets).
Also, wait() needs to be called from the loop; calling it from an if condition will not help. 

BlockingQueue Example

Let's take another classic example of coordination between two different tasks. Below is a simplified blocking queue example.

 import java.util.LinkedList;  
 import java.util.Queue;  
   
 public class SimpleBlockingQueue<T> {  
      private Queue<T> queue = new LinkedList<T>();  
      private int size;  
   
      public SimpleBlockingQueue(int size) {  
           this.size = size;  
      }  
      public synchronized void put(T element) throws InterruptedException {  
           while (queue.size() == size) {  
                wait();  
           }  
           queue.add(element);  
           notify();  
      }  
      public synchronized T take() throws InterruptedException {  
           while (queue.isEmpty()) {  
                wait();  
           }  
           T item = queue.remove();  
           notify();  
           return item;  
      }  
 }  

Note, Java provides a BlockingQueue API; prefer it instead of re-inventing the wheel. 

 

Some Important Points 

why wait and notify are part of the base class?
Sounds more like thread concepts but put in superclass, Object. This is required because these methods get called from the synchronized block/ method and they manipulate locks. And these locks are objects (in Java). 

sleep vs wait
The lock doesn't get released during the call of sleep but that's not the case with wait. If wait is called without any parameter, it can come out due to notify() or notifyAll(). If wait is called with parameter then it can respond to time out as well as notify()/notifyAll().
Also, wait is always called from synchronized block/method but sleep can be called within non-synchronized methods as well. 

what if wait/notify is called from non-synchronized block/method
The program will compile. But you will get a runtime exception, IllegalMonitorStateException. This basically means that task calling wait(), notify(), or notifyAll() MUST own the lock for the object.

prefer API provided by the language
Instead of writing code using wait/notify mechanism, prefer inbuilt Java API. 

---
keep coding !!!