Twitter @Anywhere and PHP Symfony. Implementing login action

While playing with the Twitter @Anywhere and PHP Symfony I have implemented "Sign in with Twitter" method for RoundTeam app (http://roundteam.co).

How it was done:

Creating a placeholder to represent "Sign in with Twitter" button.
mainpageSuccess.php:

<span id="login" class="twit_login">Sign in with Twitter</span>

I am not going to describe CSS part here.

Enabling Twitter connection using @Anywhere
javascript (rt.js):

$(document).ready(function() {
    twttr.anywhere(function(T) {
        $("#login").bind('click', function () {
            T.signIn();
        });
    }

Now when user clicks on "Sign in with Twitter" button he will be prompted to login using Twitter credentials. On this step "twitter_anywhere_identity" cookie is created (more details about this cookie and how to interpret it on server side see here: https://dev.twitter.com/docs/anywhere/welcome).

Okay, now we need to notify server that login has happened.
Here is one of the ways to implement this using PHP Symfony:

routing.yml

rt_get_user:
  url: /rt/user
  param: {module: connect, action: user}

action.class.php (for module "connect"):

public function executeUser(sfWebRequest $request) {
$cookie = $request->getCookie('twitter_anywhere_identity');
$this->logMessage('got auth request');
if ($cookie) {
$twitter_data = explode(':', $cookie);
$userId = $twitter_data[0];
$secret = $twitter_data[1];
$calculatedSecret = sha1($userId.RoundTeam_auth::SECRET);

if ($secret === $calculatedSecret) {
$this->logMessage('secret verified');
$userJson = $request->getParameter('user');
if ($userJson) {
$this->logMessage('user found!');
$user = json_decode($userJson);

$this->data = $user;

$this->logMessage($userJson);

$screenName = $this->data->screenName;
if (TeamTable::getInstance()->exists($screenName) == false) {
$this->logMessage('authenticated: '.$screenName);
$this->getUser()->signIn($this->data);
} else {
$this->logMessage('Failed to login using team: '.$this->$screenName, 'err');
}
} else {
$this->logMessage('user not found');
}
}
}
$this->redirect('@rt');
}

The last step is to post user data to server and reload page:

T.bind("authComplete", function (e, user) {
        post('rt/user', {user: JSON.stringify(user)}, function(response) {
        location.reload();
    });
});

That's it. Now user may login using his twitter credentials without leaving the round-team.com page. User data is passed to server and server authenticates user to enter.

It means that user stays logged in on both client side and server side. That said when you implement logout don't forget to log out user from server side:

$this->getUser()->setAuthenticated(false);

and client side:

twttr.anywhere.signOut();

Complete js code listing may be found on http://round-team.com

Mozilla Firefox -- getting Social

Let me share my experience of how to make Mozilla Firefox more "social" browser. So it will keep you up-to-date with your communication channels, like social networks, mail accounts, news feeders etc.

Twitter, Facebook, LinkedIn

Yonoo plug-in for Firefox keeps me connected. Some features:

• All updates in one line -- no more different tabs of several lines of updates. Twitter, Facebook, YouTube, LinkedIn and many other instant messengers/social networks feeds are listed in one place (being still distinguishable)
• Minimum extra space -- when collapsed it costs me one small column to the left of the browser window. I use 11'inch laptop for my daily work, so, being concerned about every pixel, I am totally fine with this size
• Simple yet flexible user interface
• Amount of new items is shown even if main view is collapsed
• Pop-up notifications in bottom-right corner of browser (may be turned off)

Google reader

I use Google Reader Watcher to stay updated with the latest news. Be careful not to install this plug-in instead.

What I don't like about this plug-in is that it is located in status bar thus not visible in full-screen mode. Well, it's still better than open a new tab.

Gmail

Have a look at Gmail Watcher. The only Gmail Firefox add-on which is installed into navigation bar (not status bar). Also, it doesn't require to enter login/password.

These add-ons all together provide me constant connectivity to the community.

If you have other cool socializing Firefox add-on to share -- please comment on this post!

Yet another "Like" button

Google has introduced own Facebook-"Like" button named "+1".
Yet another "+1" button...

Have a look at the article on CNN.com announcing it:
http://money.cnn.com/2011/03/30/technology/google_button/index.htm

It has 9(!) links with partially duplicated functionality to share this article.
With Google's it will be 10. Too many, as for me. How do you think?

Also considering various integrations supported by many social applications like
Facebook <-to-> Twitter <-to-> LiveJournal <-to-> LinkedIn <-to-> Facebook -- for more and more people that becomes irrelevant to make this choice. Because any choice will produce the same result. I do not see any reason for this number of "like and share it" links. That amount produces minimum value for end-user (read contributors) and noises web-pages.

However that's a political move, that's clear. That's pity that companies like Google always being thinking about the end-user first start to produce things which are good for Google, less for googlers.

Java 7 support in IDE's

Eclipse versions up to 3.6 (Helios) do not support Java SE 7 features completely.
I have installed JDK 7 on Ubuntu laptop, however this is not possible now programming using it within Eclipse.

Java 7 support is expected in the next Eclipse release which 3.7 aka Indigo planned for June 2011.

IDEA update 10.5 planned for Spring 2011 will include Java 7 support.

And of course, Java 7 is already supported in NetBeans. Are you surprised?..

Mergesort in Java

A simple implementation of Mergesort in Java.
Mergesort algorithm is used in Java SE Collections.sort() method.
Provided implementation has an optimization which prevents already ordered arrays to be merged thus guarantees O(n*log n) time performance.

Mergesort is particularly useful for "online" sorting which means that all amount of data is not known in advance and is becoming available to sorting mechanism chunk-by-chunk.
In this case algorithm can sort each new chunk and then effectively merge it into existing sorted structure. For such cases mergesort is much more effective than quicksort.

One of the "cons" for mergesort is that it uses O(n) auxiliary memory in distinct of quicksort which operates in constant O(1) memory.

It is possible to implement merge sort to be in-place (use constant auxiliary memory) and stay stable, however these algorithms are overcomplicated and their complexity usually is not balanced by their benefit.

public class Mergesort {
 public static int[] sort(int... array) {
  return new Mergesort().sort(array, 0, array.length - 1);  
 }
 
 private int[] sort(int[] array, int start, int end) {
  if (start >= end) {
   return array;   
  }
  int pivot = start + (end - start) / 2 + 1;
//  At this point end may become bigger than start because of integer
//  division. If pivot == start => pivot - 1 < start
  sort(array, start, pivot - 1);
  sort(array, pivot, end);
  merge(array, start, pivot, end);
  return array;
 }

 public int[] merge(int[] array, int start, int pivot, int end) {
  if (start == end) {
//   array of one element is already sorted
   return array;
  }
  
  if (array[pivot - 1] <= array[pivot]) {
//   Handling the case when array is already properly sorted. This optimization
//   guarantees O(n*log n) sorting time 
   return array;
  }
  
  int length = end - start + 1;
  int[] merged = new int[length];
  for (int i = start, j = pivot, storeIndex = 0; i < pivot || j <= end; storeIndex++) {
   if (i == pivot) {
    merged[storeIndex] = array[j++];
   } else if (j > end) {
    merged[storeIndex] = array[i++];
   } else {
    merged[storeIndex] = array[i] <= array[j] ? array[i++] : array[j++];
   }
  }
  System.arraycopy(merged, 0, array, start, length);
  return array;
 }
}

Don't trust Wiki blindly

Sometimes Wiki contains inconsistencies even for basic computer science articles. Wiki page for merge sort states that Java SE 7 uses merge sort as a default implementation for Arrays.sort() method. However that's not true.


Oracle Java SE 7 documentation for Arrays.sort() clearly states that the default implementation is based on tuned Double-Pivot version of Quicksort.

This is important if some applications depend on stable sorting algorithms.
Merge sort is stable, quicksort is not (in most implementations).

Quicksort in Java

Java implementation of Quicksort

Best case O(n*log n)
Worst case O(n^2) -- the worst case is appeared when the worst pivot is taken for every iteration. In this case Quicksort acts very similar to bubble-sort.

public class Quicksort {
 public static int[] sort(int... array) {
  Quicksort quicksort = new Quicksort();
  return quicksort.sort(array, 0, array.length - 1);
 }

 private int[] sort(int[] array, int start, int end) {
  if (end - start <= 0) {
//   TODO: Consider other sorting for short arrays
   return array;
  }
  int pivotIndex = selectPivotIndex(array, start, end);
  pivotIndex = partition(array, start, end, pivotIndex);
  sort(array, start, pivotIndex - start);
  sort(array, pivotIndex + 1, end);
  return array;
 }

 private int partition(int[] array, int start, int end, int pivotIndex) {
  int pivotValue = array[pivotIndex];
  int storeIndex = start;
  swap(array, pivotIndex, end);
  
  for (int i = start; i < end; i++) {
   if (array[i] < pivotValue) {
    swap(array, i, storeIndex++);
   }
  }
  swap(array, storeIndex, end);
  return storeIndex;
 }

 private void swap(int[] array, int index1, int index2) {
  int temp = array[index1];
  array[index1] = array[index2];
  array[index2] = temp;
 }

 private int selectPivotIndex(int[] array, int start, int end) {
//  TODO: Consider better pivot selection
  return start + (end - start) / 2;
 }
}

Setting up J2ME environment

First of all it is needed to download and install WTK from Oracle. There is a distributives for Windows and Linux platforms.

After downloading the WTK I have launched the installer and got an error: No suitable Java interpreter was detected. After this message occurred there is an option to specify path to Java interpreter manually. I have provided path /usr/lib/jvm/java-6-openjdk/bin/ and completed the installation.

Since this is the first J2ME application I am developing, I need some examples and getting started materials. First of all I have tried maven archetype for J2ME applications. Well, it was good and produced working J2ME application out of the box, however it does not provide any capabilities for Eclipse integration. No emulator launch from Eclipse, no debug, no device customization etc. etc... So, maven is not an option.

Next try was MTJ (Mobile tools for Java) -- Eclipse plug-in to develop J2ME applications. This plug-in is quite powerful and allows to do many things like localization and device/profile configuration easily from UI.

For localization this plug-in generates two classes which handle the resource bundles. However, these classes do not work well with UTF-8, so Russian characters were corrupted on my HTC Diamond Touch2 running Windows Mobile 6.1. I have also tried to write Russian characters in UTF-8 format like \uXXX (which is usually well-understood by JVM), but generated parser does not treat these notation correctly. Debug also did not work for me here. Breakpoints were skipped while logs contained timeout errors. Another thing is that MJT builds JAR/JAD for some one predefined device/profile which is not always handy (if development considers running on several device types).

Polish framework

Eventually I have downloaded Polish framework for J2ME applications. After it was downloaded and installed (it, of course also requires WTK), I have imported all sample applications provided with the installation to Eclipse (simply File -> Import -> Existing projects into workspace) and got good example base. All projects go with the Ant build.xml file which has goals for build, launching emulator and debug. So, currently I have stopped on this configuration and going to use it for my project.

Bit operators in Java

Today I was understanding how eventually operators >>, >>> and << work in Java.

First of all, Java uses two's complement integer representation. This representation is very fast because allows to operate with negative and positive numbers in exactly the same way.

Let's consider Java's primitive type byte. It is actually represented by single byte having 8 bits correspondingly. This type is signed and may hold values in range [-128, 127]. (Note that the only unsigned numeric type in Java is char which is used to hold numeric values of UTF-16 symbols, thus it is always positive).

Why so? The answer is in binary representation of two's complement integers:
127: 01111111
-128: 10000000

Two's complement: binary to decimal conversion

Decimal numbers are calculated from their binary representation in two's complement notation as following:
If the leftmost bit is 0 -- number is positive. So, bits 1-7 are taken and converted to decimal form as usual by formula

bit7*2^6 + bit6*2^5 + bit5*2^4+ bit3*2^2+ bit2*2^1+ bit1*2^0

If leftmost bit is 1 -- it indicates that number is negative, so the following process applies:

1. Inverse bits [1-7]
2. Calculate decimal number as usual by above formula
3. Add 1 to the obtained number
4. Assign "-" to the obtained number

Example: 11111110
The leftmost bit is 1 -- this is negative number

1. Inverse bits [1-7]: 0000001
2. Calculate decimal number: 1
3. Add 1 to obtained number: 2
4. Assign sign "-" to obtained number: -2

So, 11111110 represents -2 in two's complement notation.

Corner cases

Now let's understand corner cases using byte type as an example:
Example 1: 0-1=-1
Binary (two's complement): 00000000-00000001=11111111
So, 11111111 represents -1 in binary (two's complement single byte type)? Don't believe me, let's verify:

Converting 11111111 to decimal. Leftmost bit is negative -- number is negative

1. Inverse: 0000000 (7 bits)
2. Convert to decimal: 0
3. Add 1: 0+1=1
4. Assign "-" sign: -1

Example 2: 00000001+11111111=00000000
That's natural, 11111111=-1 => 1-1=0

Example 3:
The next case is more interesting: 01111111+00000001=10000000

This expression is totally correct in binary world. But what about decimal interpretation in two's complement notation? As you can see, 01111111 is positive, 00000001 is also positive, however, their sum is negative since 10000000 is negative number. This is the main "magic" of two's complement integers since one may become confused of this code written in Java:

byte b = (byte) (127 + 1);
System.out.println(b);

Output is: -128

Note casting to byte is important since all operations are performed in int space by default, thus the result without casting will be just 128.

If you understand the logic above -- this is not a surprise for you, just convert 10000000 to decimal number using provided algorithm.

Generalizing this information:

Integer.MAX_VALUE + 1 == Integer.MIN_VALUE
Integer.MIN_VALUE - 1 == Integer.MAX_VALUE


Shift operators

Understanding two's complement it is easy to understand bit operators in Java as well. In order to do that you just need to understand how the number looks in binary system, perform shift and convert it back to decimal. This is exactly what is going on when you write something like

System.out.println((byte) (64 << 1));
Output: -128

Really:

• 64 = 01000000
• 01000000 << 1 = 10000000
• 10000000 = -128

Right shift operator or "<<" just shifts all bits to the right and fills rightmost bits with zero's.

There are two left-shift operators: ">>" and ">>>". Let's see their difference:

Difference between ">>" and ">>>" operators

Operator ">>" is called "signed" left shift, which means it preserves the sign of the number upon shifting.
Example: Integer.MIN_VALUE >> 2

Integer.MIN_VALUE = -2147483648
-2147483648 : 10000000000000000000000000000000
Integer.MIN_VALUE >> 2
-536870912 : 11100000000000000000000000000000

That's said, leftmost bits before and after shift are always the same when using ">>"

For example: 5 >> 1 = 2
5 : 00000000000000000000000000000101
2 : 00000000000000000000000000000010

Operator ">>>" or "unsigned" right shift always sets leftmost bit to zero
Example: Integer.MIN_VALUE >>> 2
-2147483648 : 10000000000000000000000000000000
536870912 : 00100000000000000000000000000000

Bit operators performance

Bit operators works more than 10 times faster than usual / and * operators.
Consider the following code
Example:

long start = System.currentTimeMillis();
  for (int i = 0; i < 100000000; i++) {
   int p = i / 2;
   p = i * 2;
  }
  System.out.println(System.currentTimeMillis() - start);
  start = System.currentTimeMillis();
  for (int i = 0; i < 100000000; i++) {
   int p = i >> 1;
   p = i << 2;
  }
  System.out.println(System.currentTimeMillis() - start);

Output is similar to this:

5089
300

That's it. As a bonus I provide a piece of code which represents Java values of type int to full binary form.

public void printNumber(int b) {
  String binaryRepresentation = Integer.toBinaryString(b);
  StringBuilder leadingZeros = new StringBuilder();
  for (int i = 0; i < Integer.numberOfLeadingZeros(b); i++) {
   leadingZeros.append("0");
  }
  System.out.println(String.format("%-12d: %s%s", b, leadingZeros, binaryRepresentation));
  
 }
}