Feeds:
Posts
Comments

Archive for the ‘Programming’ Category

QRPixel.com

Advertisements

Read Full Post »

Studying Java at University should give you enough grounding to get by in your day job, but can you really call yourself a Java programmer unless you know the language inside and out? In this series we will outline the lesser known features of how the language works, taken from the SCJP objectives. Mastering these will increase your understanding of the language, and possibly (no guarantees) elevate you to demi-god status in the workplace. If you are studying for the SCJP examination you may also find these examples to be useful revision.

Variable Names

Identifiers in Java can begin with a letter, underscore or $. The characters after the first one can include digits too. These are all valid variable declarations:

int myVar;
int $var;
int _var;
int _var2;
int $$$;

Normally you would stick to using the alphabet, with following words capitalised:

int myLongVariableName;

Beginning local variables with an underscore (_) is a common convention as well.

int _aLocalVariable;

Interface Constants

Given the following interface:

public interface ConstantInterface {
    int x = 2;
}

and an implementation of it

ConstantInterface impl = new ConstantInterface() {
   void test() {
      x = 2;
   }
};

This will not compile! The variable x is implicitly public static and final because it is declared in an interface. The code could be made more readable by capitalising the variable name, to show the intent that it is a constant. Alternatively, move the constant out of the interface as constant interfaces are rarely a good idea [1]

What do protected methods really mean?

Everyone knows that public methods can be called anywhere and that private methods can only be called within it’s own class. So what about protected methods? First, lets explain what no access modifier means:

package com.example.epiccode;
public class Ping {
   void myMethod() {
      System.out.println("fuzzy wuzzy was a bear");
   }
}

myMethod can be called from any class within the same package. i.e. any class that belongs to the package com.example.epiccode. This is because it has no (default) access modifier. If a class belonged to the package com.example.epiccode.winner it cannot call this method because it is in a different package (no exception made to sub-packages).

Protected methods follow exactly the same rules as default methods, except they also allow access to subclasses by inheritance only. This is a very subtle point as shown below.

package com.example.epiccode;
public class Ping {
   protected void myMethod() {
      System.out.println("I'm default yeh");
   }
}

We have changed myMethod to be protected. Now let’s subclass Ping.

package com.example.anotherpackage;
import com.example.epiccode.Ping;
public class Submarine extends Ping {
   void dive() {
     myMethod();
  }
}

This code is perfectly fine – dive can call myMethod because Submarine extends Ping (even though they are in different packages).

The following code will not compile:

package com.example.anotherpackage
import com.example.epiccode.Ping
public class Submarine2 extends Ping {
   void dive() {
     Ping p = new Ping();
     p.myMethod();
  }
}

We are not accessing myMethod through inheritance, instead we are creating a new instance of Ping and trying to call myMethod on it. This will not compile since Submarine is not in the same package as Ping. Funnily enough this subtlety is too much for Eclipse to handle:

eclipse error

The method is already protected, so the quick fix will not work.

References

[1] Effective Java 2nd Edition by Joshua Bloch – Item 19: Use interfaces only to define types.

Read Full Post »

Here’s a little script I wrote to look up words whilst reading a book or browsing the web. It uses the Aonaware web-service to get the definitions and prints them out to the console. And if you misspell a word it will offer some suggestions.

You will need to install the LWP::Simple and XML::XPath modules from CPAN to get it to work, but other than that it should be clean sailing.

If you have comments, bugs to moan about or feature requests then let me know 🙂

Read Full Post »

Enums are Brittle

We all know Integer constants are brittle

Consider this example from StackOverflow today:-

Calendar date = Calendar.getInstance();
date.set(2010, 03, 7);
if(date.get(Calendar.DAY_OF_WEEK) == Calendar.SUNDAY)
        System.out.println("OK");

The questioner mistakenly thought that the java.util.Calendar set(int year, int month, int date) method followed a sensible human format for representing dates, but in fact the API makes use of zero based int constants to represent the month. The questioner was encouraged to avoid this pitfall by changing his code to date.set(2010, Calendar.MARCH, 7). This of course is better, but the root of the problem lies with the poorly designed Calendar API.

If java.util.Calendar class has been written post Java 5 then the set method could have been defined as set(int year, Month month, int date) where Month is an enum type:-

public eum Month {
JANUARY,
FEBRUARY,
MARCH,
...
}

This would prevent any ambiguity over whether the month parameter is zero or one based.

To change and to change for the better are two different things.

Enums may be preferable to int constants, but they are not as flexible as regular Java classes. You may well find that when you come to modify an enum which was written months ago, you need to refactor the whole thing into a regular class. This of course is time-consuming and you would have been better off designing a class from the start.

Below is an example enum representing a 2D direction on a grid. Direction takes two parameters, deltaX and deltaY which represent the offset of moving in that direction. Given that co-ordinate (0, 0) on the grid is located in the top left hand corner, moving NORTH will result in a negative change in deltaY, EAST will result in a positive change in deltaX and so forth.

enum Direction {
	NORTH(0, -1), NORTH_EAST(1, -1), EAST(1, 0), 
        SOUTH_EAST(1, 1), SOUTH(0, 1), SOUTH_WEST(-1, 1), 
        WEST(-1, 0), NORTH_WEST(-1, -1);
	private int deltaX;
	private int deltaY;
	Direction(int deltaX, int deltaY) {
		this.deltaX = deltaX;
		this.deltaY = deltaY;
	}
	public int deltaX() {
		return deltaX;
	}
	public int deltaY() {
		return deltaY;
	}
}

Direction feels like it should be an enum, as we only have eight possible directions to move in, allowing for diagonal moves. Furthermore this example demonstrates another advantage enums have over int constants – enums support methods. In fact, this enum almost appears to be a regular class, besides the enum declarations at the top.

We encounter a problem with enums when we want to add a method that returns the opposite direction. i.e. the opposite of NORTH is SOUTH, NORTH_WEST is SOUTH_EAST and so on. Here is the first technique.

enum Direction {
	NORTH(0, -1), NORTH_EAST(1, -1), EAST(1, 0), 
        SOUTH_EAST(1, 1), SOUTH(0, 1), SOUTH_WEST(-1, 1),
	WEST(-1, 0), NORTH_WEST(-1, -1);
	private int deltaX;
	private int deltaY;
	Direction(int deltaX, int deltaY) {
		this.deltaX = deltaX;
		this.deltaY = deltaY;
	}
	public int deltaX() {
		return deltaX;
	}
	public int deltaY() {
		return deltaY;
	}
	public Direction getOpposite() {
		return new Direction(-deltaX, -deltaY);
	}
}

By simply negating the deltaX and deltaY values we get the opposite direction right? It doesn’t compile because we can’t invoke enum constructors directly, even from within the enum itself! Let’s try it another way: –

enum Direction {
	NORTH(0, -1, SOUTH), NORTH_EAST(1, -1, SOUTH_WEST), 
        EAST(1, 0, WEST), SOUTH_EAST(1, 1, NORTH_WEST),
	SOUTH(0, 1, NORTH), SOUTH_WEST(-1, 1, NORTH_EAST), 
        WEST(-1, 0, EAST), NORTH_WEST(-1, -1, SOUTH_EAST);
	private int deltaX;
	private int deltaY;
	private Direction opposite;
	Direction(int deltaX, int deltaY, Direction opposite) {
		this.deltaX = deltaX;
		this.deltaY = deltaY;
		this.opposite = opposite;
	}
	public int deltaX() {
		return deltaX;
	}
	public int deltaY() {
		return deltaY;
	}
	public Direction getOpposite() {
		return opposite;
	}
}

In the second technique we have hard-coded the opposite directions, passing them into the constructor. This doesn’t compiler either because you cannot refer to types before they are defined. e.g. SOUTH cannot be referenced in NORTH‘s constructor.

Finally we give up trying to find a work around with an enum and change the whole thing to be a regular class.

public class Direction {
	public static final Direction NORTH = 
        new Direction(0, -1);
	public static final Direction NORTH_EAST = 
        new Direction(1, -1);
	public static final Direction EAST = 
        new Direction(1, 0);
	public static final Direction SOUTH_EAST = 
        new Direction(1, 11);
	public static final Direction SOUTH = 
        new Direction(0, 1);
	public static final Direction SOUTH_WEST = 
        new Direction(-1, 1);
	public static final Direction WEST = 
        new Direction(-1, 0);
	public static final Direction NORTH_NORTH = 
        new Direction(-1, -1);
	private int deltaX;
	private int deltaY;
	private Direction(int deltaX, int deltaY) {
		this.deltaX = deltaX;
		this.deltaY = deltaY;
	}
	public int deltaX() {
		return deltaX;
	}
	public int deltaY() {
		return deltaY;
	}
	public Direction getOpposite() {
		return new Direction(-deltaX, -deltaY);
	}
}

The private constructor ensures that we cannot create any instances outside of the class. The eight public instances and the getOpposite() method provide the only means of access. Note that in this class we can write the getOpposite() method using the first technique.

In conclusion, enums may be an improvement over int constants, but are definitely less flexible than a regular class. If you do decide to create an enum, consider that it may outgrow itself, like Direction did. Creating a regular class from the start may be the better option. In some cases a class may be more verbose than an enum, but then Java is pretty verbose language anyway!

Read Full Post »

Since I started my new job as a Java Software Engineer, I’ve been doing some training in the form of reading Effective Java by Joshua Bloch. Today I came across the rather baffling method signature below: –

Public static <T extends Comparable<? Super T>> T max(List<? Extends T> list)

“OMG… What is that all about?” I thought at first glance. The description informs me that the method max takes a list of any comparable type and returns the object with the maximum value as defined by the implementation of the Comparable interface’s compareTo method.

So what’s with all the bloat? The answer is that generics are invariant rather than covariant in Java. For example List<String> is not a subclass of List<Object>. In order to make your generic methods as flexible as possible it is necessary to support the inheritance of parameter types, which can cause quite a headache. I think I’ve just about got my head round this example so I will do my best to explain it.

max is a method with modifiers public and static. Its return type is the generic type T.

Generic methods declare a type parameter list which goes in between the modifiers (public static) and the return type (T). The type parameter for max is  T extends Comparable<? Super T>>. This means that T is type that is comparable with itself or its super class.

To break this down, let’s consider the simpler parameter type T extends Comparable<T>>. In this example, T is the type that is comparable with itself only. Adding the bounded wildcard type <? Super T> allows T to be comparable with its super types as well. This is necessary if we apply T as a class that subclasses a class E that implements Comparable<E>. One example of this that the book gives is the java.util.concurrent.ScheduledFuture interface which is a sub-interface of java.util.concurrentDelayed. Delayed extends Comparable<Delayed> whereas ScheduledFuture does not extend the Comparable interface directly.

The final brain teaser is the sole parameter list of type List<? Extends T>. This means that list can be a List of any type that is a subclass of T (remember everything is a subclass of itself).

Phew, I hope this made some sense. Please appreciate I’m hardly an expert in this field, so if you spot an error in my description then let me know!

Read Full Post »

Perhaps one of the least exciting things to happen in 2008 was the failure of the 30GB Microsft Zune yesterday. But springing back into life certainly is the most interesting thing I’ve read this year!

If you have no idea what I’m talking about read this. It concerns an algorithm to calculate the number of days and years that have passed since 1980, which attempts to take leap years into account. The problem is that the algorithm enters an infinite loop on the last day of a leap year, which is why 30GB Zunes broke yesterday on 31st December 2008, but miraculously started working again today on 1st January 2009.

Now I know that quite a few people have posted their fixes on Reddit, but I wanted to write my own. Here it is in a neat little program that runs on its own.  Once you’ve compiled it, you can run it as: –

./days_years g|b days

Where g is the good (correct) algorithm implemented by yours truly, and b is the bad (erroneous) algorithm implemented by Freescale/Microsoft.

days is the number of days that have elapsed since 1980. Entering 10593 will recreate the 31st December 2008 scenario.

I decided to implement a recursive algorithm to show that we can prove it will always halt. Proving its correctness is probably a good idea for something described as Real-time clock (RTC) routines! It could be done by hand as an induction or using a tool!

However, if I was in charge of programming this routine I would probably scrap the algorithm completely and hard-code all the leap years between 1980 and 2050. After all, no one is going to be using their Zune after that length of time.

There are only 18 leap years, which are the exceptions – so why worry about algorithms and termination clauses?

Read Full Post »

fruit

Eureka! It’s the halting problem, or to be more precise Collatz’s Conjecture. The algorithm is as follows:

while (n > 1)
{
  if (n is even)
    n := n / 2;
  else
    n := 3n + 1;
}

where n is an integer greater than 0.

If we try a test cases the pattern is as follows:

n = 2: 2, 1, halt.

n = 3: 3, 10, 5, 16, 8, 4, 2, 1, halt.

n = 7: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, halt.

Hopefully, none of you have ever written any code like this. The question is, will this algorithm always terminate (halt), or are their certain values of n for which it will loop forever?

Collatz is a classic example of the Halting Problem, which Alan Turing proved that there is no way we can write a generic program that can tell if all possible programs will halt or not. Obviously the halting problem is solvable for some/most programs – the first Hello World! you ever wrote hopefully did halt. Microsoft’s Terminator research project can be used to tell whether a large numer of typical programs will halt or not, but the Collatz’s algorithm still eludes them!

If you want to have a play around with this, I have written a Java program to save you the effort (albeit minimal) of doing it yourself. Let me know how you get on – I suggest trying the number 27.

A final thought: what is the best way to visualise all the data: say n = 1 to 1,000,000?

Read Full Post »

Older Posts »