Auto Layout on Android, A Pure Java Implementation

If you are familiar with IOS development, Auto Layout probably is not something new to you. But for those pure android geeks and others who are interested: “Auto Layout is a system that lets you lay out your app’s user interface by creating a mathematical description of the relationships between the elements. You define these relationships in terms of constraints either on individual elements, or between sets of elements. Using Auto Layout, you can create a dynamic and versatile interface that responds appropriately to changes in screen size, device orientation, and localization.” Quoted from Apple.

By reading a verbose definition won’t help much, an example may enlighten the concept better:

autolayout

In the above screenshot, we have a layout container (which has the screen size), and 3 different objects (views). To arrange such a layout via Auto Layout on IOS, we may simply define a few constraints:

(assume <container.padding> is a constant that represents the spaces between objects)

“green.top == container.top + <container.padding>”
“green.left == container.left + <container.padding>”
“green.width == (container.width – 3 * <container.padding>)  /  2”
“green.height == (container.height – 3 * <container.padding>) / 2”
“yellow.top == green.top”
“yellow.left == green.right + <container.padding>”
“yellow.width == green.width”
“yellow.height == green.height”
“blue.top == green.bottom + <container.padding>”
“blue.left == green.left”
“blue.right == container.right – <container.padding>”
“blue.height == green.height”

After we pass this set of constraints to the layout manager, the layout engine will do the math and solve out a best result that can satisfy each of these constraints. Thus a beautiful layout is rendered based on the calculated positions of each object.

Now it’s the point of this article: this awesome layout engine is now available on Android, and you can find the source code at Github: cassowary layout. It named cassowary because that is the original name of the algorithm, which also runs behind the Auto Layout of IOS. Yes, this android version library and the Auto Layout are sharing the same algorithm, which was developed by a few computer scientists back in 1990’s. Actually, there is a whole community behind this cassowary algorithm today: overconstrained. In there developers from all over the world have contributed to different ports of the same algorithm, and some of those implementations are already in use of many applications we are using daily today.

It is worth to mention that Cassowary layout listed above includes some android elements to handle the transition from mathematical calculated results to the actual sizes and positions of different views. If you simply just want to use the pure java implementation, I would suggest you to take a look at the math engine used by this cassowary layout library: cassowary-java. Alternatively, I personally prefer this re-designed implementation of the same algorithm: kiwi-java, which is declared as faster and smaller.

All these great libraries can be found at the cassowary community’s website: overconstrained

 

Advertisements

A powerful parser for Java and Android: Jparsec

Today I want to talk about a powerful Java parser: Jparsec (http://jparsec.codehaus.org/). I recently used it for one of my projects and found it really helpful. This article is mainly for students, who are still at school and have no industry experience. If you are already in Java development career for years, then you might already a user of this tool or at least met it before.

Back in school, whenever I needed to parse strings to capture inputs for my projects, I usually took the shortcut to make the development faster, by using the easiest way: str.split(). Normally a str.contains() command would be enough to help me judge whether the input string is the format my code required, then splitting the string to an array of words by defining delimiters finished the job.

This is an efficient approach when the project is small enough and while the input string format is rigidly controlled. If I ever encountered a more complex case, constructing a regex would be my final weapon to launch. I had never been to a circumstance that these methods failed on me, since all the projects was not at the engineering level yet.

However, these approaches became unacceptable for my first job. str.split() can only handle cases when delimiters are not complex, and if you can’t control the input format, things get worse because you never know what the string from user input looks like. Regex is hard to write at the first place and it’s even harder to maintain because it’s not human readable when it gets long and complicated. A experienced team member recommended Jparsec to me and it becomes my daily solution for parsing at these days.

Accurately speaking, Jparsec is a parser building tool. It helps you build mini java parsers quickly. The standout of Jparsec is its combinator nature. You can start building simple parsers such as whitespace parser, and then combine these simple parsers to a more complex parser. The way it works is just like the evolution of functional programming: Taking advantage of simple functions to generate the most powerful function!

Let’s see some codes:

/*
    ** fundamental parsers
     */


    // zero or more whitespace
    private static final Parser<String> whiteSpace() {
        return Scanners.string(" ").many().source();
    }

    //left parentheses
    private static final Parser<String> leftParen() {
        return whiteSpace().followedBy(Scanners.string("(")).followedBy(whiteSpace());
    }

    //right parentheses
    private static final Parser<String> rightParen() {
        return whiteSpace().followedBy(Scanners.string(")")).followedBy(whiteSpace());
    }

    //comma
    private static final Parser<String> comma() {
        return whiteSpace().followedBy(Scanners.string(",")).followedBy(whiteSpace());
    }

    //dot
    private static final Parser<String> dot() {
        return whiteSpace().followedBy(Scanners.string(".")).followedBy(whiteSpace());
    }

    //negative sign
    private static final Parser<String> negativeSign() {
        return whiteSpace().next(Scanners.string("-").source()).optional().followedBy(whiteSpace());
    }

As seen in the code, we first built a whitespace parser, it scans for ” ” zero or many times, and returns the scanned whitespace(s) as a string(by using source()). I won’t talk much on the syntax and APIs since they are basically human readable and you can find pretty much you need in the documentation listed at the beginning of this article.

Later on, we used the similar way to generate more fundamental parsers such as parentheses, comma, and dot. Note how we generate these parsers by taking advantage of the whitespace parser we built earlier: each parentheses, comma and dot can comes after whitespace, and followed by more whitespace. We are now in the evolution!

Let’s together see a more complex case:

//decimal number with possible negative sign
    private static final Parser<Integer> integer() {
        return Parsers.sequence(negativeSign(), Scanners.INTEGER, new Map2<String, String, Integer>() {
            public Integer map(String neg, String value) {
                if (neg != null) {
                    return -Integer.parseInt(value);
                } else {
                    return Integer.parseInt(value);
                }
            }
        });
    }

In the above code, we generated a parser that parses negative integers. Whenever we see a negative sign followed by an integer, we create a map to translate these inputs to the result we want(in this case a negative integer). The map defines three parameter types, the first two comes from the parsers in the sequence. and the last parameter type is the result(return) type. Inside the map method, we can do whatever we want to generate the ideal result. In this case, if we see a negative sign, we return the negative value of the value we got from the second parser in the sequence, otherwise we return this value directly.

In the end, if we want to parse a string “-5”, we write:

int result = integer().parse("-5"); 

We got result = -5.

Here I’m only showing a basic example, but you can already see the power of Jparsec. You can use it to define your own gramma and parse whatever value you want from any kind of string input format. It’s much more human readable than regex, and it’s much more reliable than str.split().

Have fun with Jparsec!

关于二分查找(Binary Search)及其变种形式的总结

二分查找是基本算法,但是据统计只有10%的程序员可以写出没有bug的代码。出错的原因主要集中在对边界值得选择和判定条件上,一不小心就可能导致超出边界或者死循环的情况。这里作如下总结:

标准版二分查找:
在有序(非降序)数组中查找一个target值,数组中元素没有重复,找到target则返回该元素对应的index,找不到则返回-1。

注意1:如果是start < end,那么当target等于num[num.length-1]时,会找不到该值。 注意2:因为num[mid] > target, 所以如果有num[index] == target, index一定小于mid,能不能写成end = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成end = mid,当循环到start = 0, end = 0时(即num[start] = 1, num[end] = 1时),mid将永远等于0,此时end也将永远等于0,陷入死循环。也就是说寻找target = -2时,程序将死循环。

注意3:因为num[mid] < target, 所以如果有num[index] == target, index一定大于mid,能不能写成start = mid呢?举例来说:num = {1, 2, 5, 7, 9}; 如果写成start = mid,当循环到start = 3, end = 4时(即num[start] = 7, num[end] = 9时),mid将永远等于3,此时start也将永远等于3,陷入死循环。也就是说寻找target = 9时,程序将死循环。

public int binarySearchStandard(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start <= end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] == target)
            return mid;
        else if(num[mid] > target){
            end = mid - 1; //注意2
        }
        else{
            start = mid + 1; //注意3
        }
    }
    return -1;
}

二分查找变形一:
在有序(非降序)数组中查找一个target值,数组中元素可能有重复,找到target在数组中对应的index的最小值,找不到则返回-1。

注意1:为了对左右相邻的两个数进行对比,循环结束的时候,start和end应该相隔1。

注意2:a). 当num[mid] == target时,此时并不能直接返回mid,因为有可能num[mid-1]或者num[mid-2]…也等于target,所以此时应该将end  = mid,然后继续循环。b). 当num[mid] > target时,如果有num[index] == target,那么index一定小于mid,本来按此道理应该令end = mid – 1,但是为什么此处可以end = mid呢?回头去看上一题(标准版)的注意2,只有当start = end时,才会出现死循环的情况。这里因为while循环的限制条件使得start和end永远不可能相等,所以end = mid也是正确的。由此,我们可将a) 和 b) 两种情况合并。

注意3:这里与上题一致,不用有变化。但是在这里写成start = mid也是成立的,为啥呢?回头看上题的注意3,同样的例子num = {1, 2, 5, 7, 9}; 在上题中,如果写成start = mid,当循环到start = 3, end = 4时(即num[start] = 7, num[end] = 9时),mid将永远等于3,此时start也将永远等于3,陷入死循环。但在此题中由于while中的限制条件的变化,避免了这种死循环的发生。

注意4:此处为什么要分别检验num[start]和num[end]是否等于target呢?因为这两个值都有可能等于target,取决于中间二分时start和end的更新过程。这里随便用几个简单的例子即可验证。如果循环结束时num[start] == num[end] == target,根据题意应该返回start,所以我们先验证start。如果两个值都不是target,则target不存在,返回-1。

public int binarySearchMinimumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] >= target){ //注意2
            end = mid;
        }
        else{
            start = mid + 1; //注意3
        }
    }
    if(num[start] == target) //注意4
        return start;
    else if(num[end] == target)
        return end;
    else
        return -1;
}

二分查找变形二:
在有序(非降序)数组中查找一个target值,数组中元素可能有重复,找到target在数组中对应的index的最大值,找不到则返回-1。

道理与上一题相同,只要在注意2和注意3处与上题反过来就行了,原理不重复了,拿不准的时候可以用几个简单的test case测试一下。

public int binarySearchMaximumIndex(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] <= target){ //注意2
            start = mid;
        }
        else{
            end = mid - 1; //注意3
        }
    }
    if(num[end] == target)
        return end;
    else if(num[start] == target) //注意4
        return start;
    else
        return -1;
}

二分查找变形三:
在有序(非降序)数组中查找一个可能的”最大”index,使得num[index] < target,数组中元素可能有重复,找不到则返回-1。

注意1:我们可以对此步分开考虑,当num[mid] == target时,因为我们要求num[index] < target,所以index必须在mid左边。当num[mid] > target时,target肯定在num[mid]的左边,所以index肯定也要在mid的左边。那么再多想一步,假如num[mid] >= target时,我们进行了end = mid的操作,会产生什么后果呢?经我的有限测试,好像并没有什么问题,因为while中的限制条件导致了每当start + 1 == end的时候,循环就结束了,所以标准版二分查找中出现的死循环的情况并不存在。

注意2:当num[mid] < target时,为什么此处用start = mid而不是start = mid + 1?因为有可能num[mid+1] == target,此时如果start = mid + 1, 则num[start] == target,明显错过了正解。

public int binarySearchClosestFromLeft(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);
        if(num[mid] >= target){ //注意1
            end = mid - 1;
        }
        else{ //注意2
            start = mid;
        }
    }
    if(num[end] < target){
        return end;
    }
    else if(num[start] < target){
        return start;
    }
    else{
        return -1;
    }
}

二分查找变形四:
在有序(非降序)数组中查找一个可能的”最小”index,使得num[index] > target,数组中元素可能有重复,找不到则返回-1。
道理与上题完全相同,稍作调整即可。

注意1:此处同上题注意1原理相同,写成start = mid也应该没有问题。

public int binarySearchClosestFromRight(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start + 1 < end){
        int mid = start + ((end - start) >> 1);
        if(num[mid] <= target){
            start = mid + 1; //注意1
        }
        else{
            end = mid;
        }
    }
    if(num[start] > target){
        return start;
    }
    else if(num[end] > target){
        return end;
    }
    else{
        return -1;
    }
}

综上所述,总结规律:
1. 当数组中没有重复元素时:while循环判定条件是(start <= end),每次start更新为mid + 1,end更新为mid – 1。
2. 当数组中含有重复元素时或者要找的值是target的相邻数时,判定条件是(start + 1 < end),当num[mid] == target时,并不返回mid,而是根据情况跟新start或者end。每次start更新为mid,end也更新为mid即可。

在命令行快速切换目录

原文链接:http://blogread.cn/it/article/6648?f=wb
今天在微博上看到一个用命令行快速切换目录的文章,比之前自己的解决方案好了非常多,必须记录下来分享下。

每天在命令行下,一大部分的工作都是一遍又一遍的输入 cd ~/some/very/deep/often-used/directory这样来切换目录,现在利用一个简单的配置可以实现如下效果:

首先进入我的日常工作目录,标记一个书签mark sanguo

cd /Users/kimi/work/123guo/sanguo
mark sanguo
以后我再进入这个目录只需要g sanguo即可
g sanguo

通过输入gs指令来浏览所有的标签
gs
#app -> /Applications
#sanguo -> /Users/kimi/work/123guo/sanguo
#web -> /Library/WebServer/Documents

实现原理如下

sudo vim /etc/profile

编辑/etc/profile文件并在尾部添加以下内容后强制保存 wq!

# mark
export MARKPATH=$HOME/.marks
export MARKDEFAULT=sanguo#设置你的默认书签,可以直接输入g跳转

function g {
local m=$1
if [ “$m” = “” ]; then m=$MARKDEFAULT; fi
cd -P “$MARKPATH/$m” 2>/dev/null || echo “No such mark: $m”
}
function mark {
mkdir -p “$MARKPATH”
local m=$1
if [ “$m” = “” ]; then m=$MARKDEFAULT; fi
rm -f “$MARKPATH/$m”
ln -s “$(pwd)” “$MARKPATH/$m”
}
function unmark {
local m=$1
if [ “$m” = “” ]; then m=$MARKDEFAULT; fi
rm -i “$MARKPATH/$m”
}
function gs {
ls -l “$MARKPATH” | grep ^l | cut -d ‘ ‘ -f 13-
}

_completemarks() {
local curw=${COMP_WORDS[COMP_CWORD]}
local wordlist=$(ls -l “$MARKPATH” | grep ^l | cut -d ‘ ‘ -f 13)
COMPREPLY=($(compgen -W ‘${wordlist[@]}’ — “$curw”))
return 0
}

complete -F _completemarks g unmark