Collection Filtering Algorithm with Bit Operation - Part.1

Background

Collection must be the most commonly used data model in programming. And there are a number of data structure that represents collection in memory, in which Array and Liked List must be the most well known ones.

When dealing with collection, filtering must be one of the most widely used operation being used. Such as find item(s) satisfies specific criteria from the collection. Although filtering is used a lot, but it isn’t actually a simple or easy operation to apply, especially dealing with tremendous data volume.

In fact, there are a number of derived topics about collection filtering, which is impossible to cover them all in the article. This article will focus on bit operation, probably a not widely known but really interesting topic to introduce.

Problem: Find the missing integer

Problem
Suppose there is a collection of integers L.
Name the collection that contains integers from 1 to N as G
Then L contains all the elements of G except one number x.
Items in L are in random order.
Find x.

TIP: This problem be too easy to experienced developers and algorithm hackers. But it is a good opening words to the following 2 problems in this series. Also it reveals the core concept of some other advanced technologies, such as CRC or bloom filter.

When got this problem, the very intuitive(means do it manually by human being) idea is to compare the elements in L and G, find each element in L and remove it from G, then the only left item in G is x.

Here is the code:

1
2
3
4
5
6
7
8
9
10
# @param Integer[] L
# @param Integer N
# @return Integer x
def find_missing_x(L, N)
G = [*(1..N)] # Create G with all integers from 1 to N
L.each { |i| G.delete(i) } # Traverse L, and remove each item in L from G
return G.last # Return the only rest item from G
end

Well this is a work but brute algorithm, which is not efficient in both time and space:

  • Instantiate G means it has space complexity N
  • Find and remove i from G means it has time complexity at O(N*Log(N))

Yes, the algorithm can be optimized, with bit operation. In fact the problem can be resolved with time complexity O(N) and space complexity O(1).

Exclusive-Or Operation

Exclusive-Or(Or XOR for short, written as ^ in this article) is a basic bit operation, here is an Venn Diagram explains it:

XOR

XOR is an important bit operation because it has following interesting features:

  1. A ^ B = B ^ A (aka Commutativity)
  2. (A ^ B) ^ C = A ^ (B ^ C) (aka Associativity)
  3. A ^ A = 0
  4. A ^ 0 = A

Commutativity and Associativity ensure that XOR can be used despite of order. The 3rd and 4th feature establishes a critical position for XOR in cryptology and encoding.

Solution: with XOR

By making use of XOR, previous problem can ben resolved in a much more graceful way:

  • Given y is the xor result of all items in G
  • And z is the xor result of all items in L
  • Then x = y ^ z
1
2
3
4
5
6
7
8
9
10
11
12
# @param Integer[] L
# @param Integer N
# @return Integer x
def find_missing_x(L, N)
x = 0 # Set x to 0, since A ^ 0 = A
(1..N).each { |i| x ^= i } # Calculate the xor result for G
L.each { |i| x ^= i } # Keep xor all elements in L
return x # Return the only rest item from G
end

Let’s prove it mathematically:

1
2
3
4
5
6
7
Given x'= y ^ z
Then x' = (n1 ^ n2 ^ n3 ^ ... ^ x ^ ... ^ nN) ^ (n1 ^ n2 ^ n3 ^ ... ^ nN)
Since ^ obeys commutativity and associativity
Then = (n1 ^ n1) ^ (n2 ^ n2) ^ ... ^ (nN ^ nN) ^ x
As n ^ n = 0 and n ^ 0 = n
Then x'= 0 ^ 0 ^ ... ^ 0 ^ x
= x

Actually the code can be more concise by using reduce, with 2-lines of code

1
2
3
4
5
6
7
8
# @param Integer[] L
# @param Integer N
# @return Integer x
def find_missing_x(L, N)
x = (1..N).reduce(&:^) # Calculate the xor result for G
L.reduce(x, &:^) # Keep xor all elements in L and return
end

Or C version:

1
2
3
4
5
6
7
8
9
int find_missing_x(long N, long* L) {
long x = N;
for(long i = 0; i < N - 1; i++) { // L has size of N-1
x ^= i ^ L[i];
}
return x;
}

Extending problems

So far the problem has been gracefully resolved. But it is yet the end, here is a couple of extending questions:

  1. If G is collection with random but unique numbers (Not continues integer from 1 to N). How to write the code?
  2. Based on 1, if there are 2 numbers are missing? How to find them both?
  3. Based on 1, but L contains the members from G except xfor exactly 2 times. That means L might contain 0 or 1 x, but exactly 2 for any other members from G. How to find x?
  4. Based on 1, but G isn’t a collection of integer, but a collection of web urls. How to find the one missing url?
  5. Based on 4, G is a collection of url, L is subset of G (might contains fewer members other than exactly N - 1). How can we know a randomly picked member from G is absolutely not contained by L. Given the tolerance to mistake on saying a member from G is in L but it doesn’t.

These problems will be explained in the following posts.

A clean way to test rejected promise

To test the the exception in a rejected promise could be a little bit painful.

And Mocha is Promise-friendly, which means it fails the test if exception is not caught.

So as a result, here is a simple code example to explain how it is being done:

1
2
3
4
5
6
7
8
9
it 'should throw session-expired exception'
new Session().generateId().bindUserFromRedis()
.then ->
null
.catch (ex) ->
ex
.then (ex) ->
expect(ex).to.be.instanceof(ResponseError)
.and.that.have.property('errorName', 'session-expired')

Update: A Chai Plugin can mitigate the pain

1
2
3
4
5
it('should throw session-expired exception', () => {
return expect(new Session().generateId().bindUserFromRedis())
.to.evetually.rejected
.and.that.have.property('errorName', 'session-expired')
})

Update 2: With async, it can be converted into normal test

1
2
3
4
5
it('should throw session-expired exception', () => {
return expect(async () => await new Session().generateId().bindUserFromRedis())
.to.throw
.and.that.have.property('errorName', 'session-expired')
})

Typical EventBus Design Patterns

EventBus is an special Publish & Subscribe Pattern implementation. EventBus enable message to be delivered between components without requiring the components to register itself to others.

Comparing EventBus to other Pub & Sub implementations, EventBus is:

  1. Designed to replace the original event distribution system, which requires the components register itself to each other.
  2. Not designed for general use, EventBus adds additional complexity and runtime overhead to the system. So it is not designed to replace normal method calls.
  3. Not designed for inter-process communication as some other Pub&Sub.

EventBus saves Android developers’ life

When developing Android application, I strongly recommend developer to introduce an EventBus library. EventBus from GreenRobot, Otto from Squqre are good solutions. Or even to choose the original EventBus in Guava library from Google.

With EventBus, components can communicate with each other without need to hold direct reference of each other. This is very important to avoid app crashes when calling a method on a detached or destroyed component. Usually this kind of issue isn’t that easy to handle due to Android’s over-complicated life cycle management. So even in the worst case that one component is sending message to another component which has been destroyed (which should unregister itself from EventBus on that time), it only triggered a norecipient waring instead of crashing the app.

Also with EventBus as intermedia, you can avoid to exposing objects to root activity or application just for registering callbacks on each other. Components are higher cohesion & lower coupling.

As the result, EventBus saves tons of time to debugging crash, and make your code more readable, maintainble, extensible, and flexible.

Abusing EventBus kills your app easily

EventBus is awesome! It is so convenient, so let’s replace everything with event”… This kind of saying is commonly heard from the developers who just realized the benefits from EventBus. Since EventBus is too convenient to use, they tends to replace everything with EventBus.

But we mentioned in the introduction of EventBus that EventBus is design to replace traditional event system in Java, and is not designed for general use. Abusing makes your code hard to understand, hard to debug. Long event chain is a common reason that cause of unexpected behavior.

Broadcast Event, Command and Request

EventBus is powerful, but can be easily abused. To make a better use of EventBus, I learn a number of EventBus usages, and evaluated the scenario, and summarized out 3 typeical EventBus usage patterns: Broadcast Event, Command and Request.

Broadcast Event

Broadcast Event is a special kind of event that used by a specific component to broadcast its status updated to other components.

Declaration

Broadcast Event should be used when several components cares about the specific component’s status update. So usually Broadcast Event should have more than one recipients or, at least, potential recipients.

Broadcast Event should be an immutable data object, so:

  1. It is immutable, so once it is created, its status should not changed, which guarantees the equality between recipients.
  2. It is data object, so it should not has methods that might change other classes status.
  3. It might have methods that helps its consumer to consume the data it contains.
  4. It should be declared as a nested static class of publisher.

NOTICE
If you thought a Event is “Broadcast Event”, but later you found it has only one recipient, then you might need to consider refact it into a Command or a Request.

Command

Command is a special kind of event that has the ability to update specific object or specific type of objects. In most cases, Command should have only one recipient. In some special cases, it might has a group of recipients with exactly same type.

Precisely, the latter case is a variant of Command pattern, Batch Command, which works as same as Command but have multiple recipients so it can update multiple instances in a batch.

Command should be a immutable object that able to update specific object, so:

  1. It should have 1 execute method with 1 parameter, which represents the target that the command updates.
  2. When invoking execute method shouldn’t change its own status, so it does exactly same thing when applying it to multiple targets.
  3. It behavior should be stable across time, so its behavior won’t change when it is apply asynchronously.
  4. The object that execute method accepts is not necessarily to be the recipient. It could be the object that recipient holds or it has access to.
  5. It should be declared as nested static class of the recipient.
  6. If recipient accepts multiple events, these events are recommended to derived from the same base class. So The recipient could subscribe to the base class, rather than every command.

NOTICE
Command can be seen as recipient’s special method that can be invoked without known recipient instance. So its behavior should fully contained in the class. The subscribing method on recipient should contain one line of code to invoke execute method on command.

Request

Request is a special kind of event that has the ability to accept data from another object. If the request has multiple recipients, to avoid ambiguous behavior, there should be only one of Request‘s respond the request.

But there is one exception, that is for the request collects data from multiple objects, multiple objects might respond to the request. This special kind of Request is called Collector.

Request should be a object that accept data from recipient, so:

  1. It should have respond method with 1 parameter, which represents the data the request asks for.
  2. Request should contains enough information for the recipients to determine whether to respond the request.
  3. The recipients should check request’s status to determine whether it should respond request.
  4. The request can update the publisher directly in the respond method
  5. It should be declared as nested class of publisher. If possible, also declare it as static, which will be helpful to simplify the tests.
  6. Request might has methods to help recipient to determine whether to respond the request.

NOTICE
Request can be seen as a special method that publisher exposes to a specific recipient, so the specific recipient can invoke the method to provide data. For Request, you might need to aware that that sometimes request might not found proper recipient to respond. If the responder is not guaranteed to exist, then the publish to watch out no-recipent warning from EventBus.

Understand Styles in Android - Part 1. What it is for and how to used it


In android, view hierarchy usually are created via layout xml file. In the file, to instantiate a TextView we write:

1
2
3
4
<TextView
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="Sample 1" />

Usually, we need to specify the visual of the TextView, so we keep adding attributes to the TextView element:

1
2
3
4
5
6
7
8
9
10
11
12
<TextView
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="Sample 1"
android:background="@drawable/category_indicator_background"
android:gravity="center"
android:maxLines="1"
android:paddingBottom="12dp"
android:paddingLeft="22dp"
android:paddingRight="22dp"
android:paddingTop="12dp"
android:textSize="12sp" />

Usually to fully customize visual representation of a view needs a lot of attributes and resources. Such as in this example. we added background, gravity, maxLines, padding and textSize, which is a lot of code.

And if we want to create another TextView with exactly same visual representation, we need to copy all the values again:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<TextView
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="Sample 1"
android:background="@drawable/category_indicator_background"
android:gravity="center"
android:maxLines="1"
android:paddingBottom="12dp"
android:paddingLeft="22dp"
android:paddingRight="22dp"
android:paddingTop="12dp"
android:textSize="12sp" />
<TextView
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="Sample 2"
android:background="@drawable/category_indicator_background"
android:gravity="center"
android:maxLines="1"
android:paddingBottom="12dp"
android:paddingLeft="22dp"
android:paddingRight="22dp"
android:paddingTop="12dp"
android:textSize="12sp" />

Obviously, in this piece of code, there are a lot of duplications. We need to compare all the values to figure out the 2 TextViews have the same visual. If we want to change the style, we need to update 2 TextViews. And the last, if we want to create the 3rd TextView or even more ones, we need copy the code again and again, which makes the issue become more troublsome.

In a short word, the code has bad readability, bad maintainability, bad reusability. In the book Refactor, we know that code redundancy is bad smell. To mitigate the issue, we need to extract the shared code into another “unit”, and replace all the occurrences with the reference.

In Android layout xml, the extract “unit”, which represents the shared attributes, are called Style. After introduced Style, we have:

1
2
3
4
5
6
7
8
9
10
11
<TextView
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="Sample 1"
style="@style/TextView.Customized"/>
<TextView
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="Sample 2"
style="@style/TextView.Customized"/>
1
2
3
4
5
6
7
8
9
10
11
12
13
<resources>
<style name="TextView.Customized">
<item name="android:gravity">center</item>
<item name="android:background">@drawable/category_indicator_background</item>
<item name="android:paddingLeft">22dp</item>
<item name="android:paddingRight">22dp</item>
<item name="android:paddingTop">12dp</item>
<item name="android:paddingBottom">12dp</item>
<item name="android:textAppearance">@style/CategoryIndicator.Text</item>
<item name="android:textSize">12sp</item>
<item name="android:maxLines">1</item>
</style>
</resources>

Well, this is the basics about the Style: why we need it and how it is used.

Perform Clicks in Android Robolectric Unit Test

Robolectric is an awesome library that makes UI unit test on Android a lot easier and faster. In UI test, one of the most basic thing is to simulate user interaction, such as clicking a button.

Click on individual View

Click should be the most basic user interaction, besides invokeing the View.performClick() method, Robolectric provides a more smarter version Robolectric.clickOn(View), which checks the view visibility and enabled status before actually “click” the view. If a view is either not visible or disabled, the click action will not be performed. This mechanism is useful to avoid some silly cases in automated tests.

Long Click on individual View

Long click is a more advanced click action. To simulate a long click action, View.performLongClick() can be invoked. But since Robolectric doesn’t provide any long click helper, make sure you do it by yourself, including checking whether view is long-clickable, which usually will be set manually or more often, when View.setOnLongClickListener is invoked; view is visible and enabled as what click does. Although Long click is avaible to use, but from my experience, long click on a individual view is rarely used in real UI design, instead long click is usually performed on an item of list view or grid view. This is the trickest case that I’ll leave it to the last.

Click on item of List/Grid

Click on List View or Grid View item. Well, idally, this shouldn’t be so much different than click on a indiviual view. But in Android implementation, item click is handled by the list view with a much more complicated API. To perform an item click, boolean performItemClick(View v, int position, long id) can be invoked. performItemClick requires 3 parameters, the first one is the view being clicked, the second one is the position of clicked view’s corresponding data item in adapter and the last is the if of clicked view’s corresponding data item. Complicated, isn’t it?

In Android implementation, item view displayed in ListView/GridView is actually provided by its adapter. Adapter works like a presenter in MVP pattern that creates/update item view based on the item data it holds. It also provides the id for the item. So to perform a item click, besides the ListView/GridView, you also need its adapter.

Following implementation explains how it works:

1
2
3
4
5
public static void clickItem(AbsListView listView, int position) {
ListAdapter adapter = listView.getAdapter();
View itemView = adapter.getView(position, null, listView);
listView.performItemClick(itemView, position, adapter.getItemId(position));
}

In the code, AbsListView is the base class of ListView and GridView. To click the item, you need

  1. Get the adapter of the AbsListView
  2. Create an item view for specific position with adapter
  3. Calculate the item id of corresponding position
  4. Invoke performItemClick method with data we got before.

In the implementation, for simplicity reason, we ignored some cases, such as convertView reusing. From my experience, in most cases, it won’t impact the functionality, so we don’t need to worry about it, unless you clearly know that matters, then you need to cover them in your tests.

Long click and item of List/Grid

Well, this action is also not a commonly used. It is only used in limited cases, such as selecting multiple item or displaying context menu for specific item.
To perform a long click on the item is the most trickest case. In previous 3 cases, we either directly or indrectly depends on View.perform***Click method. But not sure why, android doesn’t provide similar public API method of item long click. By diving into Anrdoid source code, we can figure out that Item Long Click isn’t really handled by ListView itself, instead it is handled by a Runnable named CheckForKeyLongPress. To invoke method on this object isn’t that streight forward, and might involes unnecessary multithread issue.

I just want to click a item, why I have to deal with these unnecessary complicates? So I learnt from the CheckForKeyLongPress implementation, and implmented my own “API”:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void longClickItem(AbsListView listView, int position) {
if (!listView.isLongClickable())
return;
OnItemLongClickListener listener = listView.getOnItemLongClickListener();
if (listener == null)
return;
ListAdapter adapter = listView.getAdapter();
View itemView = adapter.getView(position, null, listView);
listener.onItemLongClick(listView, itemView, position, adapter.getItemId(position));
listView.performHapticFeedback(LONG_PRESS);
}

My main purpose of perform a click is to trigger the corresponding listener, so I tried to invoke the listener directly with some necessary pre-checks. This aporach will not triggers these UI effects, but I assume it can meet most test cases.

APPENDIX UIActions helper class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package me.timnew.robolectric.utils;
import android.app.Activity;
import android.app.Fragment;
import android.view.View;
import android.widget.AbsListView;
import android.widget.ListAdapter;
import org.robolectric.Robolectric;
import static android.view.HapticFeedbackConstants.LONG_PRESS;
import static android.widget.AdapterView.OnItemLongClickListener;
public class UiActions {
public static boolean clickOn(View view) {
return Robolectric.clickOn(view);
}
public static boolean clickOn(Activity activity, int targetViewId) {
return Robolectric.clickOn(activity.findViewById(targetViewId));
}
public static boolean clickOn(View parentView, int targetViewId) {
return Robolectric.clickOn(parentView.findViewById(targetViewId));
}
public static boolean clickOn(Fragment fragment, int targetViewId) {
//noinspection ConstantConditions
return Robolectric.clickOn(fragment.getView().findViewById(targetViewId));
}
public static void pressBackButton(Activity currentActivity) {
if (currentActivity.getFragmentManager().getBackStackEntryCount() > 0)
currentActivity.getFragmentManager().popBackStackImmediate();
else
currentActivity.onBackPressed();
}
public static void clickItem(AbsListView listView, int position) {
ListAdapter adapter = listView.getAdapter();
View itemView = adapter.getView(position, null, listView);
listView.performItemClick(itemView, position, adapter.getItemId(position));
}
public static void longClickItem(AbsListView listView, int position) {
if (!listView.isLongClickable())
return;
OnItemLongClickListener listener = listView.getOnItemLongClickListener();
if (listener == null)
return;
ListAdapter adapter = listView.getAdapter();
View itemView = adapter.getView(position, null, listView);
listener.onItemLongClick(listView, itemView, position, adapter.getItemId(position));
listView.performHapticFeedback(LONG_PRESS);
}
}

2 Modules Android project with Robolectric, Gradle, Android Studio

Start a new Android project this week, so I started to setup the development environment. To be honest, it is not an easy experience to me.

Features

Here are the features I got now:

  • Unit test with Robolectric. (Very fundamental requirement)
  • Unit tests are separated into an independent module. (Provide flexibility when project growing larger. And provide a more clear view of code organization)
  • Running unit tests recognized by Android Studio/IntelliJ unit test plugin and debug UTs in IDE. (This is very important when diagnose failure UT)
  • Running unit tests via CLI with gradle wrapper. (This is necessary requirement for CI servers)
  • Using resources in Robolectric test. (Avoid Resource Not Found exception in unit tests)
  • Test Android Annotation powered async implementation. (AA introduces new Async implementation, which is not supported by Robolectric by default)
  • AssertJ core support. (Fest has been deprecated since no one is maintain it now.)

Versions

The major difficulties that I met are version compatibility, I almost tried all available version combinations to make them all works. Here are the versions that I uses

  • Gradle: 2.1
  • Groovy: 2.3.6
  • Ant: 1.9.3
  • JVM: 1.6.0_65 (Apple Inc. 20.65-b04-462)
  • OS: Mac OS X 10.9.5 x86_64
  • Android Studio: 0.8.11 (build AI-135.1446794)
  • IntelliJ: IDEA 14 CE EAP, build IC-138.2458.8
  • Android gradle plugin: com.android.tools.build:gradle:0.13.0
  • Android ADT gradle plugin: com.neenbedankt.gradle.plugins:android-apt:1.4+
  • Compile SDK version: 20
  • Build tool version: 20.0.0
  • Robolectric: 2.3

Known Issues

My current solution isn’t perfect. But for now, I haven’t working solution for them. Hope it could be fixed in the future

  • AAR is not supported in Unit Test. (A tricky issue, I’ll explain more in detail later)
  • AssertJ-Android is not supported. (Cause by AAR support issue, alternative available.)

Project Structure and configurations

Here are the project structure:

1
2
3
4
5
6
7
8
RootProject
|- settings.gradle
|- build.gradle
|- Launcher
\- builde.gradle
\- UnitTest
|- build.gradle
\- UnitTest.iml

Here are the contents

\Settings.gradle
1
include ':Launcher', ':UnitTest'
\build.gradle
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
buildscript {
repositories {
mavenCentral()
}
dependencies {
classpath 'com.android.tools.build:gradle:0.13.0'
}
}
allprojects {
repositories {
mavenLocal()
mavenCentral()
}
}
\Launcher\build.gradle
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
buildscript {
repositories {
mavenCentral()
}
dependencies {
classpath 'com.android.tools.build:gradle:0.13.0'
classpath 'com.neenbedankt.gradle.plugins:android-apt:1.4+'
}
}
repositories {
mavenLocal()
mavenCentral()
}
apply plugin: 'com.android.application'
apply plugin: 'android-apt'
android {
compileSdkVersion 20
buildToolsVersion '20.0.0'
defaultConfig {
minSdkVersion 9
targetSdkVersion 19
versionCode 1
versionName "1.0"
}
buildTypes {
debug {
runProguard false
proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.txt'
}
release {
runProguard false
proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.txt'
}
}
}
apt {
arguments {
androidManifestFile variant.processResources.manifestFile
resourcePackageName 'me.timnew.game.launcher'
}
}
def AAVersion = '3.1'
dependencies {
apt "org.androidannotations:androidannotations:$AAVersion" // Process AA annotations
/*
* Android Studio will remove this line if you try to edit project configuration with GUI.
* It seems it is a bug of Android Studio since it does not understand DSL `apt`
*/
compile "org.androidannotations:androidannotations-api:$AAVersion" // AA Runtime API. Becareful
compile 'de.greenrobot:eventbus:2.2.1'
compile 'org.easytesting:fest-reflect:1.4.1'
compile 'com.google.guava:guava:18.0'
compile 'com.koushikdutta.ion:ion:1.3.8'
compile fileTree(dir: 'libs', include: ['*.jar', '*.aar']) // Well although I mentioned aar here, but it doesn't load correctly.
compile 'com.android.support:support-v4:20.0.0'
compile 'com.android.support:support-annotations:20.0.0'
compile 'com.android.support:appcompat-v7:20.0.0'
}
\UnitTest\build.gradle
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
buildscript {
repositories {
mavenCentral()
}
dependencies {
classpath 'com.android.tools.build:gradle:0.13.0'
}
}
apply plugin: 'java'
repositories {
mavenLocal()
maven { url "$System.env.ANDROID_HOME/extras/android/m2repository" } // Fix 'com.android.support:*' package not found issue
mavenCentral()
}
dependencies {
def appModule = project(':Launcher')
compile appModule
testCompile appModule.android.applicationVariants.toList().first().javaCompile.classpath // Include classes from main project
testCompile appModule.android.applicationVariants.toList().first().javaCompile.outputs.files
testCompile files(appModule.plugins.findPlugin("com.android.application").getBootClasspath())
testCompile('junit:junit:4.+') {
exclude module: 'hamcrest-core' // Exclude problematic 'hamcrest'
}
testCompile 'org.robolectric:robolectric:2.3'
testCompile 'org.mockito:mockito-core:1.9.5'
testCompile 'org.assertj:assertj-core:1.6.1'
}
tasks.withType(Test) {
scanForTestClasses = false
include "**/*Should.class"
include "**/*Test.class"
include "**/*Tests.class"
}

Why uses java plug-in instead of android unit test plug-ins

Well, Gradle DSL provides a lot of flexibility to developer. But it also brought a lot complexity to IDE implementation. To figure out project configuration, IDE need to parse and understand the gradle scripts. Not only DSLs provided by gradle but all stuff come with plug-ins. From IDE, this is almost an impossible mission. So IDE need to figure out a way to simplify the process, such as support a subset of DSL.

For Android project, IntelliJ has difficulties to understand the all variations of android unit test plug-ins. So it is not easy to make unit test runnable from IDE. To solve the issue, you either try to teach IDE about the DSL by providing plug-in to IDE, or uses some languages that IDE understood.

I tried some plug-in available today, but none of them works for me. So I decide to use java DSL, which IntelliJ understood natively. As a trade off, since java gradle plugin doesn’t understand Android Library, so it cannot import .aar libries.

Besides I tried all android unit test gradle plugins, I found all of them depends on android gradle plugin. And android plugin depends on AndroidManifest.xml and some other stuff. It is wield to provide an manifest for your unit test.

So as the final solution, I uses java plug-in, avoid using aar in the test.

Why so complicate

Configurate an working Android project isn’t as easy as it sounds. Differ from iOS community, Google isn’t strong-minded as Apple. As a consequence that Android community is fragmented and lack of unified solution. There are tons of solutions available, but you might need to try them one by one to figure out which fits your requirement.

To make your tool chain, dependencies, IDE work together, compatibility is always your enemy. Even Google has to publish Version Compatibility Table to mitigate the pain.

What a mess!!!!!

References posts, plugins or template projects

Here is a list of things that I tried but failed to fit my requirement. List here since it might be helpful to other people.

Trello Confetti Effect

Trello just created a page to celebrate their user number reaches 5 million. In their celebration page, they introduce an interesting effect, a number of blue squares rotating and falling from the sky.

By inspecting their source code, I extracted the effect implementation from the page.

As you can see, the effect is implemented with Canvas animation. Trello guys created a light weight particle system.

  • ConfettiMachine is the particle system controller, which takes the responsibility to create new particles and call draw method on them one by one.
  • Particle is the representation of the blue square, it takes the rotation, fading out and rendering.

The source code is extracted for study purpose, all code and credits belongs to Trello guys.

Otto and Android Annotations Compatibility Issue Analysis

Introduction

Otto is a great Android event bus solution developed by SquareUp guys. These guys extract the event bus related classes from Google’s Guava, and optimized it for Android. Event Bus is a great solution to keep your code away from messy anonymous or internal classes only used for event handling! And Otto’s simplicity and performance makes it used to be the most popular event bus solution in Android development.

Android Annotations, as known as AA, is another great library that makes Android developers’ lives a lot easier. Just annotating the code, AA helps developer handles the most boring or error-proning tasks for you, including binding widgets binding, asynchronous tasks, life time management, etc…

Issue

Otto and AA are the libraries focusing on different aspects. Theoretically speaking, there shouldn’t be any compatibility issue between them. But the reality Otto event is never delivered to AA annotated classes. By inspecting the code with step by step debugging, I found the root cause of the issue is Otto failed to located @Produce and @Subscribe annotated methods in AA generated code.

Analysis

After a few study work, I finally understood what is the reason behind:

For performance consideration, Android Annotations actually does it work during the compilation time instead of Runtime. AA will derive the annotated classes, and generate some code according to the annotations applied. During the runtime, the classes got instantiated is actually the derived classes instead of the original one, although in the code is accessed via the original class as interface.

Here is a simple example:

I have the class ServerListAdapter, which is used to provide data for a grid view.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
@EBean
public class ServerListAdapter extends AdvBaseAdapter<InetAddress, ServerView> {
@RootContext
protected Context context;
@SystemService
protected LayoutInflater inflater;
@Bean
protected Bus bus;
public ServerListAdapter() {
super(new ArrayList<InetAddress>());
}
@AfterInject
protected void afterInject() {
bus.register(this);
}
@Override
protected ServerView createView(ViewGroup parent) {
return ServerView_.build(context);
}
@Override
protected ServerView updateView(ServerView itemView, InetAddress item) {
itemView.update(item);
return itemView;
}
@Subscribe
public void fetchServerStatus(DiscoveryStatusEvent event) {
setItems(event.addresses);
}
@Subscribe
public void onServerStatusUpdated(DiscoveryStatusChangedEvent event) {
switch (event.type) {
case SERVER_ONLINE:
getItems().add(event.address);
break;
case SERVER_OFFLINE:
getItems().remove(event.address);
break;
}
notifyDataSetChanged();
}
}

And this is the derived class generated by AA during the compiling-time:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public final class ServerListAdapter_
extends ServerListAdapter
{
private Context context_;
private ServerListAdapter_(Context context) {
context_ = context;
init_();
}
public static ServerListAdapter_ getInstance_(Context context) {
return new ServerListAdapter_(context);
}
private void init_() {
inflater = ((LayoutInflater) context_.getSystemService(Context.LAYOUT_INFLATER_SERVICE));
context = context_;
bus = Bus_.getInstance_(context_);
afterInject();
}
public void rebind(Context context) {
context_ = context;
init_();
}
}

And here is how it is consumed:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
@EFragment(R.layout.fragment_server_list)
public class ServerListFragment extends Fragment {
@Bean
protected DiscoveryService discoveryService;
@Bean
protected ServerListAdapter adapter;
@ViewById(R.id.server_list)
protected GridView serverGridView;
@AfterViews
protected void afterViews() {
serverGridView.setAdapter(adapter);
discoveryService.start();
}
@Override
public void onDetach() {
super.onDetach();
discoveryService.stop();
}
}

As you can see, in the ServerListFragment, the ServerListAdapter instance injected into bean is actually the instance of ServerListAdapter_. And due to polymorphic, the instance just behaves like a ServerListAdapter instance.

On the other hand, according to the description on Otto’s Home Page:

In order to receive events, a class instance needs to register with the bus.

Registering will only find methods on the immediate class type. Unlike the Guava event bus, Otto will not traverse the class hierarchy and add methods from base classes or interfaces that are annotated. This is an explicit design decision to improve performance of the library as well as keep your code simple and unambiguous.

Otto only search annotations in direct class, which is ServerListAdapter_ in instance, and there isn’t any annotation included. As a consequence, all the @Subscribe annotated methods are ignored by com.squareup.otto.AnnotatedHandlerFinder. So the posted events become dead event due to no subscriber found.

Comments

There is rumor that this issue will be fixed in Otto 2.0. But according to the comment from Jake Wharton, Otto’s developer, Otto 2.0 will take forever to release.

In fact Otto 2.0 Repo has been not touched for 2 years already. Although we could check out the code and build Otto 2.0 by ourselves, but it takes efforts. Especially when some bug is found.

Conclusion

Luckily, although Otto turns into “maintenance mode”, the compatibility issue takes forever to resolve. I found a great Otto alternative, EventBus from GreenRobot. A boring name, but great library.

According to EventBus‘s document, it provides richer feature and better performance than Otto.
The most important EventBus is friendly to AndroidAnnoations. They two works well together.

EventBus and Otto Feature Comparison

EventBus Otto
Declare event handling methods Name conventions Annotations
Event inheritance Yes Yes
Subscriber inheritance Yes No
Cache most recent events Yes, sticky events No
Event producers (e.g. for coding cached events) No Yes
Event delivery in posting thread Yes (Default) Yes
Event delivery in main thread Yes No
Event delivery in background thread Yes No
Asynchronous event delivery Yes No

EventBus and Otto Performance Comparison

EventBus over Otto
Posting 1000 events, Android 2.3 emulator ~70% faster
Posting 1000 events, S3 Android 4.0 ~110% faster
Register 1000 subscribers, Android 2.3 emulator ~10% faster
Register 1000 subscribers, S3 Android 4.0 ~70% faster
Register subscribers cold start, Android 2.3 emulator ~350% faster
Register subscribers cold start, S3 Android 4.0 About the same

Trick to use CoffeeScript in Hexo

Hexo has a scripts folder, and the files under which are loaded by Hexo when start. I usually uses this folder as the development folder for my plug-in scripts. And extract them into independent package after polished it into package-ready quality.

Usually, the files under scripts should be javascripts. But as I’m a fan of Coffee Script, so I wish to use coffee-script to write the plug-ins. For the formal package, I compile the coffee scripts into javascripts before release. But for development, I wish to use coffee script directly.

In node.js, it is possible to require coffee-script directly, if you registered the coffee-script runtime compiler:

1
require('coffee-script/register');

And as how node.js require function is implemented, you cannot register coffee-script runtime compiler in .coffee file. Or the compiler will complain:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[error] HexoError: Script load failed: plugin.coffee
SyntaxError: Unexpected string
at Module._compile (module.js:439:25)
at Object.Module._extensions..js (module.js:474:10)
at Module.load (module.js:356:32)
at Function.Module._load (module.js:312:12)
at Module.require (module.js:364:17)
at require (module.js:380:17)
at /usr/local/lib/node_modules/hexo/lib/loaders/scripts.js:17:11
at Array.forEach (native)
at /usr/local/lib/node_modules/hexo/lib/loaders/scripts.js:15:13
at /usr/local/lib/node_modules/hexo/lib/util/file2.js:339:7
at done (/usr/local/lib/node_modules/hexo/node_modules/async/lib/async.js:135:19)
at /usr/local/lib/node_modules/hexo/node_modules/async/lib/async.js:32:16
at /usr/local/lib/node_modules/hexo/lib/util/file2.js:335:11
at Object.oncomplete (evalmachine.<anonymous>:107:15)

Theoretically, it is possible to put the coffee-script registration code in a javascript file and also put it under /scripts folder. SO Hexo will load it when start-up.

Well, this approach doesn’t really work. If you try it, it is very likely to get the exactly same error as before. The reason is related to Hexo implementation. Hexo uses Scripts Loader to require files under /scripts. The loader doesn’t really provide an explicit way to specify which file is loaded before another. So the registration file is guaranteed to be loaded before any .coffee.

So far, it seems that there is no cure to this problem! But actually it does. There is undocumented feature will help to solve this issue.

Hexo uses [Script Loader] to load the scripts. In Scripts Loader use hexo.util.file2 to populate the source files under /scripts. And hexo.util.file2 use fs.readdir to actully populate the file system entries. For fs.readdir, there is a undocumented feature, that the populated entries are actually sorted alphabetically, which means a.js is loaded before b.coffee.

With this feature, we can put our coffee-script registration in a file with lower alphabetic-order name. Personally, I’d like called ___register_coffeescript.js, since _ is smaller than any letter or number.

⚠️WARNING: fs.readdir yielding sorted files is an undocumented behavior, which means it is not guaranteed either to work across platforms or not get changed in the future. So for, it works on Mac, and I expect it behaves similar on Linux. But not sure about Windows, since fs uses a different native binding on Windows.

Favicon is not as simple as you think

Favicon is the little icon that displayed on the title bar or tab bar when you browsing a web site. At very beginning, it is used to be the little icon displayed in favoriate bar when user add the website to favorites. Then later, it becomes the the standard way to specify custom icon for a website.

Most web site provides favico, developer add one line description in the <head>:

1
<link rel="shortcut icon" href="/favico.ico" type="image/x-icon">

This simple piece of code works, but there are a lot of issues with this declaration. Actually specify the favico isn’t as simple as you might expect!

For this piece of code, according to W3C document how to favicon, there are 2 issues with it:

First, shortcut isn’t a standard value for rel, it is only for IE.

Second, ico format is a Microsoft oriented file type, not all platform likes it. Linux, Mac, iOS, Android, do not really appreciate this format.

Beides the 2 issues described above, the size of the favicon also matters.

Someone says it should be 16x16. Yes, 16x16 icon is used in tab or tree view. Some other says it should be 32x32. Well, this is also true. 32x32 icon is displayed in toolbar.

16x16 and 32x32 are the most used sizes for favico, but that’s not all. The reality is a lot complicated, I’ll explain this issue later. Let focus on this 2 size first.

To provide the image with 2 different sizes. For ico it is not an issue, since ico is a image container file format, which can encapsulate several images with different sizes and color in a single file. It is convenient for developer, but not for users. Because it means the users need to download a big file, most of the data in which is not used at all.

For the recommended png, it is no way to provide multiple images in a single file. So we have to provide 2 different separate files, and specify them with 2 different <link> tags with sizes attribute. This is a more efficient way, but unfortunately, you’re living in the world has something called Internet Explorer. The favico in png is not supported by IE until IE 11. What a hell!

Actually, there is a lot of issue with IE in this case. There is an great article by Mathias Bynen that discussed this issue in detail, which provides a lot of interesting information related to favico.

Microsoft Windows 8

Besides typical browser usage, Favicon is also used to create Metro Tile by IE 10 and IE 11 on Windows 8. It requires something quite different. Here is a MSDN document that described how to create custom tiles for IE11 websites. For these tile icon, Windows 8 also asks for a background color other than the icon itself.

Android

In the age of mobile internet, favicon is not just used by the desktop browser, but also mobile devices. On mobile devices, there are some more specific requirements.

On android, the screen size and resolution varies between devices. So the visual elements on Android are measured in dp. According to the screen resolution, there are different conversion ratios between dp and px. And to have pixel perfect image on Android, developer should provide several images for different dp-px-ratios.

Google have a well written document that described how to create icon for the web app that added to homescreen.

iOS

For iOS, it is simliar to Android, but seems to be much more complicated. On iOS, it is also possible to create a shortcut for the web apps. Apple named such icon as apple touch icon, which is used by Safari and other browsers on iOS.

For the iOS devices, iPhone and iPad have different screen sizes, so they have different size requirements for touch icon.

Furthermore, there are device with retina display and with normal one. To have pixel perfect image on retina display, it requires the resolution of the image to be doubled.

And since iOS 7, iOS changed its UI style, the icon size used by iOS 7 is also slightly changed. So you should provide new icons for iOS 7 devices!

To make the icon fit iOS visual style best, Apple recommend web application to provide precomposed icon, which is a icon that added rounded corner and background by itself.

To have the pixel perfect icon on iOS, you might need to provide around 10 different images files as apple touch icon.

What a hell!!!! The touch icon on iOS is totally a mess!!!!

Here is a document from Apple that describes how configure web application icon.

Other

Besides all cases that describe above, favicon is also used in some special cases, such as Google TV, Opera Speed Dial, Chrome Web App. They all requires different size of favico.

Conclusion

In a short description, favico isn’t as simple as it looks. And it actually used wrongly by most websites.
To provide proper favico for all platforms and devices is not a simple work to do.
Here is the favico declaration that used this blog:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<link rel="apple-touch-icon" sizes="57x57" href="/apple-touch-icon-57x57.png">
<link rel="apple-touch-icon" sizes="114x114" href="/apple-touch-icon-114x114.png">
<link rel="apple-touch-icon" sizes="72x72" href="/apple-touch-icon-72x72.png">
<link rel="apple-touch-icon" sizes="144x144" href="/apple-touch-icon-144x144.png">
<link rel="apple-touch-icon" sizes="60x60" href="/apple-touch-icon-60x60.png">
<link rel="apple-touch-icon" sizes="120x120" href="/apple-touch-icon-120x120.png">
<link rel="apple-touch-icon" sizes="76x76" href="/apple-touch-icon-76x76.png">
<link rel="apple-touch-icon" sizes="152x152" href="/apple-touch-icon-152x152.png">
<link rel="icon" type="image/png" href="/favicon-196x196.png" sizes="196x196">
<link rel="icon" type="image/png" href="/favicon-160x160.png" sizes="160x160">
<link rel="icon" type="image/png" href="/favicon-96x96.png" sizes="96x96">
<link rel="icon" type="image/png" href="/favicon-16x16.png" sizes="16x16">
<link rel="icon" type="image/png" href="/favicon-32x32.png" sizes="32x32">
<meta name="msapplication-TileColor" content="#00a300">
<meta name="msapplication-TileImage" content="/mstile-144x144.png">

And these files are served on this blog as favico:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
favicon.ico
favicon-16x16.png
favicon-32x32.png
favicon-96x96.png
favicon-160x160.png
favicon-196x196.png
apple-touch-icon.png
apple-touch-icon-precomposed.png
apple-touch-icon-57x57.png
apple-touch-icon-60x60.png
apple-touch-icon-72x72.png
apple-touch-icon-76x76.png
apple-touch-icon-114x114.png
apple-touch-icon-120x120.png
apple-touch-icon-144x144.png
apple-touch-icon-152x152.png
browserconfig.xml
mstile-70x70.png
mstile-144x144.png
mstile-150x150.png
mstile-310x150.png
mstile-310x310.png

As you can see, to prepare all these configurations and files is not an easy job to do. It really consumes you a lot effort.

Fortunately, we have the awesome Real Favicon Generator brought by Philippe Bernard, which will save your tons of time to have the proper fav icon configuration.

Real Favicon Generator also comes with a favicon checker, which check the favorite configuration for your website, and generates beautiful report.

At last the FAQ of the site also provides a good explanation of the issue described above in details. Hope it helps.