Dependency Inversion Principle

DIP:

Depend upon abstraction. Code to interfaces and not to concrete implementations.

This is similar to the OO principle: "program to an interface and not to an implementation". However, the DIP makes an even stronger statement about abstraction. It means any component (high or low level) within an application should depend upon abstractions. A high level component is one whose behavior is defined in terms of other lower level components.

The following guidelines help in avoiding OO designs that violate the DIP:

  1. No variable should hold a reference to a concrete class. Do not use new, use factories.
  2. Do not derive from concrete classes. Derive from abstract or interfaces. If your are deriving from concrete classes then there is a dependence on the concrete class.
  3. Do not override base class methods. Those concrete methods in the base class are meant to be shared between all the derived classes.

Inverson of control:

This generic term is also synonymous with Dependency Injection.

The assembler injects the dependency and reduces tight coupling between classes.

Java Collections and Insertion Sort

Insertion Sort:

It is used for smaller size arrays. In Java Collections, insertion sort is applied to an array of size 7 or else. This cutoff is based on empirical studies. The best choice for the cutoff is actually machine ]dependent.

Method implementation:

public void insertionSort(int x[])

{

   int off = 0, len = x.length;

   for (int i = off; i < len; i++)

      for (int j = i; j > off && x[j-1] > x[j]; j–)

          swap(x, j, j-1);

}

public void swap (int x[]; int a, int b)

{

    int t = x[a]; x[a] = x[b]; x[b] = t;

}

Analysis:

The outer for loop runs n times (where n is the length of the array).

The inner for loop runs 0, 1, 2, 3 … (n-1) for the worst case scenario wherein the array is in descending order.

Therefore the worst case scenario = > n(n-1)/2

At every inner for loop step a decision is made whether to swap. If we assume that at each step there is a 50% chance of swapping, then the average case scenario would be: (n(n-1)/2 ) / 2 approx.

The best case behavior would be visible when the array is already sorted => insertion sort would be linear in n.

Bubble Sort:

Unlike insertion sort wherein the smaller element flows towards the beginning, here the larger element flows towards the end. Although the name might be catchy but it is not used industrially – there are other sorting algorithms that provide better perfomance.

Visitor Family of Design Patterns

Driver: The visitor family allows separation of concerns and allows functionality (basically one or more methods) to be added to a hierarchy of classes without modifying anything in the hierarchy.

For instance: in the visitor pattern, the visitable classes would just define a single method (accept) in the simplest case and within that a ploymorphic call would be made to the passed in Visitor instance’s visit() method.

OCP principal: (the Open Closed Principle): The visitor family allows changing the behavior of existing classes (for instance, in the case of the Visitor Pattern, these classes are termed as Visitable) without updating the existing codebase.

The main patterns of interest in this family are:

  • Visitor
  • Decorator

The Visitor Pattern:

There is a dual dispatch happening wherein the first dispatch is to invoke the correct accept method in case there are more than one.

The second dispatch is to invoke the correct visit() method on the Visitor instance.

One of the main benefits of the visitor pattern is that it is extremely fast as it involves only two polymorphic dispatches.

The Decorator Pattern:

This one is different from visitor although they are members of the same family of patterns – the Visitor family. It is primarily different  ’cause it does not require the interface of the Visitable to be updated with the addition of the accept() method. There are no dual dispatches.

This pattern is also called the toolkit pattern since new tools (new behavior) can be acquired at run time => the application therefore can be termed to be using new tools.

The SRP principle (Single Responsibility Principle) underlines the separation of concerns in a good design. This implies, in a decorator context, that a class (such as one representing the entity: CAR)  should not burden itself with a characteristic (such as the alloy wheels) that is not intrinsic to its behavior. In the case of the preceding example of a CAR, the decorator can implement the interface of the CAR and delegate all calls to the CAR instance but "decorate" the one for getPrice() by taking into account the presence of alloy wheels and adding that to the base price and thereafter delegating to the CAR instance.

 

Generics

Have been studying on Generics in Java and have evaluated the following:

  • Thinking in Java has a comprehensive chapter on Generics although towards the end, I found some inaccuracies.
  • The Generics tutorial linked from Java Docs is thorough but for someone who is hitting Generics aka templates in C++ for the first time, I would recommend starting with "Thinking in Java".
  • Any doubts that you might have can be quickly cast aside by checking out the immensely useful site: http://angelikalanger.com/GenericsFAQ/FAQSections/ParameterizedTypes.html

Hopefully some of you might find this information useful.