Log4life

Go 编程语言入门教程（二）

刘金雨 — Mon, 07 Dec 2009 20:40:00 +0800

原文：http://golang.org
翻译：刘金雨/刘云涛 <yuntao.liu#gmail.com> http://www.log4think.com

数据类型 Types

Go有一些常见的数据类型，例如 int 和 float，其值采用机器“适用”的大小来表示。也有定义了明确大小的数据类型，例如 int8、float64 等，以及无符号整数类型，例如 uint、uint32 等。这些都是完全不同的数据类型，即使 int 和int32 都是32位整数，但它们是不同的类型。对于表示字符串元素的类型 byte 和uint8 也是同样如此。
说到字符串（ string ），这也是一个内置的数据类型。字符串的值不仅仅是一个byte 的数组，它的值是不可改变的。一旦确定了一个字符串的值，就不能再修改了。但一个字符串变量的值可以通过重新赋值来改变。下面这段来自 strings.go的代码是合法的：

11        s := "hello";
12        if s[1] != 'e' { os.Exit(1) }
13        s = "good bye";
14        var p *string = &s;
15        *p = "ciao";
然而下面这段代码是非法的，因为它试图修改一个字符串的值：

    s[0] = 'x';
    (*p)[1] = 'y';
按照C++的说法，Go的字符串有点类似带了 const 修饰符，指向字符串的指针也类似于一个 const 字符串的引用（reference）.
没错，前面看到的那些是指针，然而Go语言中的指针在用法方面有所简化，后文会提到。
数组的声明如下所示：

    var arrayOfInt [10]int;
数组同字符串一样是“值”，但是却是可变的。与C不同的是，C语言中 arrayOfInt可以当做一个指向int的指针来用。在Go中，因为数组是“值”，因此 arrayOfInt被看做（也被用做）指向数组的指针。
数组的大小是其数据类型的一部分。但是，你可以声明一个 slice 变量，然后可以用一个指向具有相同元素类型的数组指针给它赋值，更常见的是用一个形式为a[low : high]的 slice 表达式，该表达式表示下标从 low 到 high-1 的子数组。 Slice 类型类似数组，但没有显式指定大小 ([] 之于 [10])，用于表示一个隐性（通常是匿名的）数组。如果不同的 slice 都是表示同一个数组中的数据，它们可以共享该数组的内存，但不同的数组则永远不会共享内存数据。
Slice 在Go 程序中比数组更常见。它更灵活，并且具有引用的语义，效率也更高。其不足之处在于无法像数组一样精确控制存储方式，如果想在一个数据结构中保存一个具有100个元素的序列，应该采用数组。
当给函数传一个数组参数的时候，绝大多数情况下都会把参数声明为 slice 类型。当调用函数时，先取数组地址，然后Go会创建一个 slice 的引用，然后传这个引用过去。
可以用 slice 来写这个函数(来自 sum.go)：

09    func sum(a []int) int {   // 返回一个整数
10        s := 0;
11        for i := 0; i < len(a); i++ {
12            s += a[i]
13        }
14        return s
15    }
之后这样来调用：

19        s := sum(&[3]int{1,2,3}); // a slice of the array is passed to sum
注意在sum()的参数列表后面加 int 定义了其返回值类型（int）。[3]int{1,2,3} 的形式是一个数据类型后面接一个大括号括起来的表达式，整个这个表达式构造出了一个值，这里是一个包含三个整数的数组。前面的 & 表示提取这个值的地址。这个地址会被隐性的转为一个 slice 传给 sum() 。
如果想创建一个数组，但希望编译器来帮你确定数组的大小，可以用 ... 作为数组大小：

    s := sum(&[...]int{1,2,3});
实际使用中，除非非常在意数据结构的存储方式，否则 slice 本身（用[]且不带&）就足够了：

    s := sum([]int{1,2,3});
除此之外还有map，可以这样初始化：

    m := map[string]int{"one":1 , "two":2}
sum还第一次出现了内置函数 len()，用于返回元素数量。可以用于字符串、数组、slice、map、map 和 channel.
此外， for 循环中的 range 也可以用于字符串、数组、slice、map、map 和 channel。例如

    for i := 0; i < len(a); i++ { ... }
遍历一个序列的每个元素，可以写成

    for i, v := range a { ... }
其中， i 会赋值为下标， v 会赋值为 a 中对应的值，Effective Go 中包含了更多的用法演示。

新的blog地址

刘金雨 — Sat, 05 Dec 2009 14:12:00 +0800

新的blog，独立域名、独立管理、随便加widget，基于GAE和micolog的 http://www.log4think.com

Go 编程语言入门教程（一）

刘金雨 — Tue, 24 Nov 2009 17:43:00 +0800

Go 编程语言入门教程

原文：http://golang.org
翻译：刘金雨/刘云涛 <yuntao.liu#gmail.com> http://www.log4think.com

介绍

本文档是关于Go编程语言基础的一个介绍性的入门教程，偏向于熟悉C或C++的读者。本文并非一份语言的完整指南，如果需要的话，你应该去看看“语言规范”（language specification）。当读完本教程之后，你可能会希望继续看看“Effective Go”，这份文档更深入的挖掘如何使用Go语言。此外还有一份《三日入门》的教程可供参考: 第一日,第二日, 第三日.
本文将会以一系列适当的程序来说明语言的一些关键特性。所有的示例程序都是可运行的（在撰写本文时），并且这些程序都会提交到版本库的/doc/progs/目录下。
程序片段都会标注上在源文件中的行号，为了清晰起见，空行前面的行号留空。

Hello, World

让我们以最常见的方式开始吧:
05 package main

07 import fmt "fmt" // 本包实现了格式化输入输出

09    func main() {
10        fmt.Printf("Hello, world; or Καλημέρα κόσμε; or こんにちは世界\n");
11    }
每份Go的源文件都会使用 package 语句声明它的包名。同时也可以通过导入其它包来使用其中定义的功能。这段代码导入了包 fmt 来调用我们的老朋友——现在它的开头字母是大写的，并且前面带有包名限定——fmt.Printf。
函数的声明使用关键字func ，整个程序将会从为main 包中的main 函数开始（经过初始化之后）。
字符串常量可以包含Unicode字符，采用UTF-8编码。（事实上，所有Go程序的源文件都是使用UTF-8编码的）
注释的方式同C++一样：
    /* ... */
    // ...
稍后，我们会继续谈到print。

编译

Go是一个编译型语言。目前有两个编译器，其中gccgo编译器采用了GCC作为后端，此外还有一系列根据其所适用的架构命名的编译器，例如6g 适用于64位的x86结构，8g 适用于32位的x86结构，等等。这些编译器比gccgo运行的更快、生成的代码更加有效率。在撰写本文的时候（2009年底），他们还具有一个更加健壮的运行期系统，但是gccgo 也正在迎头赶上。
下面来看看如何编译和运行程序。采用 6g 是这样的
    $ 6g helloworld.go # 编译; 中间代码位于 helloworld.6 中
    $ 6l helloworld.6   # 链接; 输出至 6.out
    $ 6.out
    Hello, world; or Καλημέρα κόσμε; or こんにちは世界
    $
gccgo 的方式看起来更加传统一些。
    $ gccgo helloworld.go
    $ a.out
    Hello, world; or Καλημέρα κόσμε; or こんにちは世界
    $

Echo

下一步，是来实现一个Unix的传统命令Echo：
05 package main

07    import (
08        "os";
09        "flag"; // command line option parser
10    )

12 var omitNewline = flag.Bool("n", false, "don't print final newline")

14    const (
15        Space = " ";
16        Newline = "\n";
17    )

19    func main() {
20        flag.Parse();   // Scans the arg list and sets up flags
21        var s string = "";
22        for i := 0; i < flag.NArg(); i++ {
23            if i > 0 {
24                s += Space
25            }
26            s += flag.Arg(i);
27        }
28        if !*omitNewline {
29            s += Newline
30        }
31        os.Stdout.WriteString(s);
32    }
这段程序很小，但是却有几个特别之处。前面这个例子中，我们看到可以使用func 来声明一个函数，同时关键字 var、const和type （目前还没有用到）也可以用于声明，就好像 import 一样。注意，我们可以将同一类的声明放到括号中，以分号分隔，例如第7-10行和第14-17行。但也并非一定要如此，例如可以这样写

    const Space = " "
    const Newline = "\n"
分号在此处并不是必须的。事实上，任何顶层声明后面都不需要分号。但如果要是在一个括号内进行一系列的声明，就需要用分号来分割了。
你可以像在C、C++或Java中那样去使用分号，但如果你喜欢的话，在很多情况下都可以省略掉分号。分号是用于表示语句间的分隔，而非表示其中止。因此对于一个代码块中的最后一条语句来说，有无分号皆可。大括号之后的分号也是可选的，就像C语言中的一样。比对一下echo的源代码，只有第8、15和21行必须要加分号，当然第22行中的 for 语句中为了分隔三个表达式也需要加分号。第9、16、26和31行的分号都不是必须的，加上分号只是为了以后再增加语句的时候方便而已。
这个程序导入了os包以访问 Stdout 变量，Stdout的类型是 *os.File 。import 语句实际上是个声明：通常情况下（如hello world程序中那样），它命名了一个标识符fmt用于访问导入的包的成员变量，而包是从当前目录或标准库下的"fmt"文件中导入的。在这个程序中，我们为导入的包显式的指定了一个名字，默认情况下，包名是采用在导入的包里面已经定义好的名字，通常会与文件名一致。因此在这个“hello world”程序中，可以只写 import "fmt" 。

你可以任意为包指定一个导入名，但通常只有在解决名字冲突的情况下才有必要这样做。
有了 os.Stdout，我们就可以用它的 WriteString 方法打印字符串了。
导入了 flag 包之后，第12行创建了一个全局变量来保存 echo 的 -n 选项标志。omitNewline 变量的类型是 *bool ——指向bool值的指针。

在 main.main中进行了参数解析，并创建了一个本地字符串类型的变量用于构造输出的内容。声明语句如下

    var s string = "";
这里用到了关键字 var ，后面跟变量名和数据类型，之后可以继续接=来赋初值。
Go 试图尽量保持简洁，这个声明也可以用更短的形式。因为初值是一个字符串类型的常量，没有必要再声明数据类型了，因此这个声明可以写成这样：

    var s = "";

或者也可以直接用更短的形式：

s := "";

操作符 := 在 Go 语言里经常会用在赋初值的声明中，比如下面这个 for 语句的声明：

22 for i := 0; i < flag.NArg(); i++ {

flag 包会解析命令行参数，并将参数值保存在一个列表中。
Go语言中的 for 语句和C语言中的有几个不同之处。首先，for是唯一的循环语句，没有 while 语句或 do 语句。其次，for 语句后面的三个子句不需要圆括号，但大括号是必须的。这一条对 if 和 switch 语句同样适用。稍后还会有几个例子演示for 语句的其它用法。
循环体中通过追加（+=）标志和空格构造字符串 s 。循环之后，如果没有设置 -n 标志，程序追加一个空行，最后输出结果。
注意，函数 main.main 没有返回值。它就是这样定义的，如果到达了main.main 的末尾就表示“成功”，如果想表明出错并返回，可以调用

os.Exit(1)
os 包还包含一些其他的常用功能，例如 os.Args 会被 flag 包用于访问命令行参数。

（未完待续）

打车抬表费用图

刘金雨 — Sun, 05 Jul 2009 05:35:00 +0800

<mce:script type="text/javascript" src="wz_jsgraphics.js" mce_src="wz_jsgraphics.js"></mce:script> <mce:script type="text/javascript"></mce:script>

android path relative macro

刘金雨 — Wed, 13 May 2009 18:15:00 +0800

defined in build/core/envsetup.mk

BUILD_FINGERPRINT := $(PRODUCT_BRAND)/$(TARGET_PRODUCT)/$(TARGET_DEVICE)/$(TARGET_BOOTLOADER_BOARD_NAME):$(PLATFORM_VERSION)/$(BUILD_ID)/$(BUILD_NUMBER):$(TARGET_BUILD_VARIANT)/$(BUILD_VERSION_TAGS)

TARGET_SIMULATOR = { true <null> }
TARGET_BUILD_TYPE = { release debug }
TARGET_PRODUCT := sim generic cdma_sholes umts_sholes
TARGET_BUILD_VARIANT := user eng develop test
TARGET_ARCH := arm x86
TARGET_OS := linux

ifeq ($(TARGET_SIMULATOR),true)
TARGET_PREBUILT_TAG := $(TARGET_OS)-$(TARGET_ARCH)
TARGET_PREBUILT_TAG := android-$(TARGET_ARCH)
TARGET_OUT_ROOT_release := $(OUT_DIR)/target
TARGET_OUT_ROOT_debug := $(DEBUG_OUT_DIR)/target
TARGET_OUT_ROOT := $(TARGET_OUT_ROOT_$(TARGET_BUILD_TYPE))

ifeq ($(TARGET_SIMULATOR),true)
TARGET_PRODUCT_OUT_ROOT := $(HOST_OUT_$(TARGET_BUILD_TYPE))/product
TARGET_PRODUCT_OUT_ROOT := $(TARGET_OUT_ROOT)/product

TARGET_COMMON_OUT_ROOT := $(TARGET_OUT_ROOT)/common
PRODUCT_OUT := $(TARGET_PRODUCT_OUT_ROOT)/$(TARGET_DEVICE)
OUT_DOCS := $(TARGET_COMMON_OUT_ROOT)/docs

TARGET_OUT_INTERMEDIATES := $(PRODUCT_OUT)/obj
TARGET_OUT_HEADERS:= $(TARGET_OUT_INTERMEDIATES)/include
TARGET_OUT_INTERMEDIATE_LIBRARIES := $(TARGET_OUT_INTERMEDIATES)/lib
TARGET_OUT_COMMON_INTERMEDIATES := $(TARGET_COMMON_OUT_ROOT)/obj
TARGET_OUT := $(PRODUCT_OUT)/system
TARGET_OUT_EXECUTABLES:= $(TARGET_OUT)/bin
TARGET_OUT_OPTIONAL_EXECUTABLES:= $(TARGET_OUT)/xbin
TARGET_OUT_SHARED_LIBRARIES:= $(TARGET_OUT)/lib
TARGET_OUT_JAVA_LIBRARIES:= $(TARGET_OUT)/framework
TARGET_OUT_APPS:= $(TARGET_OUT)/app
TARGET_OUT_KEYLAYOUT := $(TARGET_OUT)/usr/keylayout
TARGET_OUT_KEYCHARS := $(TARGET_OUT)/usr/keychars
TARGET_OUT_ETC := $(TARGET_OUT)/etc
TARGET_OUT_STATIC_LIBRARIES:= $(TARGET_OUT_INTERMEDIATES)/lib
TARGET_OUT_NOTICE_FILES:=$(TARGET_OUT_INTERMEDIATES)/NOTICE_FILES
TARGET_OUT_DATA := $(PRODUCT_OUT)/data
TARGET_OUT_DATA_EXECUTABLES:= $(TARGET_OUT_EXECUTABLES)
TARGET_OUT_DATA_SHARED_LIBRARIES:= $(TARGET_OUT_SHARED_LIBRARIES)
TARGET_OUT_DATA_JAVA_LIBRARIES:= $(TARGET_OUT_JAVA_LIBRARIES)
TARGET_OUT_DATA_APPS:= $(TARGET_OUT_DATA)/app
TARGET_OUT_DATA_KEYLAYOUT := $(TARGET_OUT_KEYLAYOUT)
TARGET_OUT_DATA_KEYCHARS := $(TARGET_OUT_KEYCHARS)
TARGET_OUT_DATA_ETC := $(TARGET_OUT_ETC)
TARGET_OUT_DATA_STATIC_LIBRARIES:= $(TARGET_OUT_STATIC_LIBRARIES)
TARGET_OUT_UNSTRIPPED := $(PRODUCT_OUT)/symbols
TARGET_OUT_EXECUTABLES_UNSTRIPPED := $(TARGET_OUT_UNSTRIPPED)/system/bin
TARGET_OUT_SHARED_LIBRARIES_UNSTRIPPED := $(TARGET_OUT_UNSTRIPPED)/system/lib
TARGET_ROOT_OUT_UNSTRIPPED := $(TARGET_OUT_UNSTRIPPED)
TARGET_ROOT_OUT_SBIN_UNSTRIPPED := $(TARGET_OUT_UNSTRIPPED)/sbin
TARGET_ROOT_OUT_BIN_UNSTRIPPED := $(TARGET_OUT_UNSTRIPPED)/bin
TARGET_ROOT_OUT := $(PRODUCT_OUT)/root
TARGET_ROOT_OUT_BIN := $(TARGET_ROOT_OUT)/bin
TARGET_ROOT_OUT_SBIN := $(TARGET_ROOT_OUT)/sbin
TARGET_ROOT_OUT_ETC := $(TARGET_ROOT_OUT)/etc
TARGET_ROOT_OUT_USR := $(TARGET_ROOT_OUT)/usr
TARGET_RECOVERY_OUT := $(PRODUCT_OUT)/recovery
TARGET_RECOVERY_ROOT_OUT := $(TARGET_RECOVERY_OUT)/root
TARGET_SYSLOADER_OUT := $(PRODUCT_OUT)/sysloade

android transform macro

刘金雨 — Wed, 13 May 2009 18:13:00 +0800

defined in build/core/definitions.mk

transform-aidl-to-java
transform-classes.jar-to-dex
transform-classes.jar-to-emma
transform-c-or-s-to-o-no-deps
transform-cpp-to-o
transform-c-to-o
transform-c-to-o-no-deps
transform-d-to-p
transform-generated-source
transform-host-c-or-s-to-o-no-deps
transform-host-cpp-to-o
transform-host-c-to-o
transform-host-c-to-o-no-deps
transform-host-java-to-package
transform-host-o-to-executable
transform-host-o-to-executable-inner
transform-host-o-to-package
transform-host-o-to-shared-lib
transform-host-o-to-shared-lib-inner
transform-host-o-to-static-lib
transform-host-ranlib-copy-hack
transform-host-s-to-o
transform-host-s-to-o-no-deps
transform-java-to-classes.jar
transform-l-to-cpp
transform-o-to-executable
transform-o-to-executable-inner
transform-o-to-package
transform-o-to-shared-lib
transform-o-to-shared-lib-inner
transform-o-to-static-executable
transform-o-to-static-executable-inner
transform-o-to-static-lib
transform-prebuilt-to-target
transform-ranlib-copy-hack
transform-s-to-o
transform-s-to-o-no-deps
transform-to-prelinked
transform-to-stripped
transform-variables
transform-y-to-cpp

copy-file-to-new-target
copy-file-to-new-target-with-cp
copy-file-to-target
copy-file-to-target-with-cp

为什么cpio要比tar好

刘金雨 — Tue, 10 Feb 2009 08:07:00 +0800

为什么cpio比tar好？有这样几个原因。
1、cpio会保留硬连接（hard link），备份的时候这个很重要
2、cpio没有文件名长度的限制。确实，guntar在这一点上做过改进，允许使用长文件名（实际上是创建了一个临时文件用来保存实际的文件名），但是在非gnu的tar工具上仍然存在这个问题。
3、默认情况下，cpio保留时间戳
4、在编写脚本的时候，cpio可以更好的控制要操作哪些文件。因为cpio需要显式的制定要操作的文件列表，例如下面哪个更加容易理解？
find . -type f -name '*.sh' -print | cpio -o | gzip >sh.cpio.gz

或者在Solaris上：
find . -type f -name '*.sh' -print >/tmp/includeme tar -cf - . -I /tmp/includeme | gzip >sh.tar.gz

或者用gnutar：
find . -type f -name '*.sh' -print >/tmp/includeme tar -cf - . --files-from=/tmp/includeme | gzip >sh.tar.gz

这儿有一个需要特别注意的：对于包含大量文件的列表，不能将find放在反引号（`）内，因为命令行长度会超出长度限制，因此必须使用中间文件。find和tar分开跑很明显会使得速度减慢。

下面这个例子更加复杂，将一部分文件打包到一个文件中，其它部分打包到另外一个文件中：

find . -depth -print >/tmp/files egrep '\.sh$' /tmp/files | cpio -o | gzip >with.cpio.gz egrep -v '\.sh$' /tmp/files | cpio -o | gzip >without.cpio.gz

在 Solaris 下:
find . -depth -print >/tmp/files egrep '\.sh$' /tmp/files >/tmp/with tar -cf - . -I /tmp/with | gzip >with.tar.gz tar -cf - . /tmp/without | gzip >without.tar.gz

使用 gnutar:
find . -depth -print >/tmp/files egrep '\.sh$' /tmp/files >/tmp/with tar -cf - . -I /tmp/with | gzip >with.tar.gz tar -cf - . -X /tmp/without | gzip >without.tar.gz

同样的，find和tar分开跑会使得速度变慢。创建多个中间文件也搞出了更多的混乱。gnutar稍好些，但是它的命令行参数却是不兼容的。

5、如果有很多文件需要通过网络在两台机器之间复制，则可以并行的跑几个cpio。例如：

find . -depth -print >/tmp/files split /tmp/files for F in /tmp/files?? ; do cat $F | cpio -o | ssh destination "cd /target && cpio -idum" & done

注意，如果能够将输入平均分成几个部分来进行并行处理会更好。

ThoughtWorks 的一道笔试题

古月春秋 — Thu, 11 Dec 2008 15:30:00 +0800

PROBLEM ONE: TRAINS

Problem: The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!

The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.

Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.

Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).

1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
7. The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
8. The length of the shortest route (in terms of distance to travel) from A to C.
9. The length of the shortest route (in terms of distance to travel) from B to B.
10. The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.

Test Input:

For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.

Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

Expected Output:

Output #1: 9
Output #2: 5
Output #3: 13
Output #4: 22
Output #5: NO SUCH ROUTE
Output #6: 2
Output #7: 3
Output #8: 9
Output #9: 9
Output #10: 7
==========

简单来说，就是一个图的搜索问题。用数组来表示图，简化之后大致的解决方案都差不多。

public class Graphmain {
    public int[][] map = { 
            {-1, 5, -1, 5, 7}, 
            {-1, -1, 4, -1, -1},
            {-1, -1, -1, 8, 2},
            {-1, -1, 8, -1, 6},
            {-1, 3, -1, -1, -1},
    };
    
    public void dfs(String end, String path, int maxLength)
    {
        if (path.length() - 1 > maxLength) return;
        
        if ( path.length() > 1 && path.endsWith(end) ) {
            System.out.println(path + ", " + path.length());
        }
        
        char lastChar = path.charAt(path.length()-1);
        int lastNodeIndex = lastChar - 'A';
        
        for ( int i=0; i<map[lastNodeIndex].length; i++ )
        {
            char newChar = (char)(i + 'A');
            if ( map[lastNodeIndex][i] > 0) {
                dfs(end, path + newChar, maxLength);
            }
        }
    }
    
    public static void main(String[] args) {
        Graphmain g = new Graphmain();
        
        g.dfs("C", "C", 3);
    }
}

public class Graphmain {
    public int[][] map = { 
            { -1, 5, -1, 5, 7 }, 
            { -1, -1, 4, -1, -1 },
            { -1, -1, -1, 8, 2 }, 
            { -1, -1, 8, -1, 6 }, 
            { -1, 3, -1, -1, -1 }
    };
    public void bfs(String start, String end, int hops) {
        String lastRoute = start;
        for (int hop = 0; hop < hops; hop++) {
            String route = "";
            for (int i = 0; i < lastRoute.length(); i++) {
                char c = lastRoute.charAt(i);
                int id = c - 'A';
                for (int j = 0; j < map[id].length; j++) {
                    if (map[id][j] > 0)
                        route = route + (char) (j + 'A');
                }
            }
//          System.out.println(lastRoute); 
            lastRoute = route;
        }
//      System.out.println(lastRoute); 
        System.out.println(lastRoute.split(end).length - 1);
    }
    public static void main(String[] args) {
        Graphmain g = new Graphmain();
        g.bfs("A", "C", 4);
    }
}

8/9:

public class Graphmain {
    public int[][] map = { 
            {-1, 5, -1, 5, 7}, 
            {-1, -1, 4, -1, -1},
            {-1, -1, -1, 8, 2},
            {-1, -1, 8, -1, 6},
            {-1, 3, -1, -1, -1},
    };
    
    public void dfs(String end, String path, int cost) {
        if (path.endsWith(end) && cost < bestCost && cost > 0) {
            bestPath = path;
            bestCost = cost;
            return;
        }
        char lastChar = path.charAt(path.length() - 1);
        int lastNodeIndex = lastChar - 'A';
        for (int i = 0; i < map[lastNodeIndex].length; i++) {
            char newChar = (char) (i + 'A');
            int newCost = map[lastNodeIndex][i];
            if (newCost > 0) {
                if (path.indexOf(newChar) > 0)
                    continue;
                dfs(end, path + newChar, cost + newCost);
            }
        }
    }
    public String bestPath = "";
    public int bestCost = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Graphmain g = new Graphmain();
        g.dfs("C", "A", 0); // 8  
//      g.dfs("B", "B", 0); // 9 
        System.out.println("Best Path: " + g.bestPath + "\nCost: " + g.bestCost);
    }
}

10:

public class Graphmain {
    public int[][] map = { 
            {-1, 5, -1, 5, 7}, 
            {-1, -1, 4, -1, -1},
            {-1, -1, -1, 8, 2},
            {-1, -1, 8, -1, 6},
            {-1, 3, -1, -1, -1},
    };
    
    public void dfs(String end, String path, int cost) {
        if (cost >= 30)
            return;
        if (cost > 0 && path.endsWith(end)) {
            System.out.println(path + ", " + cost);
        }
        char lastChar = path.charAt(path.length() - 1);
        int lastNodeIndex = lastChar - 'A';
        for (int i = 0; i < map[lastNodeIndex].length; i++) {
            char newChar = (char) (i + 'A');
            int newCost = map[lastNodeIndex][i];
            if (newCost > 0) {
                dfs(end, path + newChar, cost + newCost);
            }
        }
    }
    public static void main(String[] args) {
        Graphmain g = new Graphmain();
        g.dfs("C", "C", 0);
    }
}

Android源码构建工具速览（二）—— 清单文件

古月春秋 — Sat, 25 Oct 2008 15:11:00 +0800

上回已经简单的在本地构造了一个Android的源码库，这回来看看这个源码库是如何构造出来的。

这一切其实都是基于那个名为repo的构造工具。回到最开始的命令 $ curl http://android.git.kernel.org/repo > ~/bin/repo
这个命令从网站上下载了一个名为repo的脚本，它实际上是段python的代码，这个代码仔细看看还是有点意思的。它其实是整个构建工具的一小部分代码，而这一小部分的代码的功能主要就是去下载自身其它的代码，并初始化构建环境。

在运行这个工具的时候，它首先会去检查当前目录下的.repo目录，然后从脚本内置的（或命令行指定的）一个地址 git://android.kernel.org/tools/repo.git 去使用git clone一份最新的repo工具的完整的版本库放置到 .repo/repo 目录下，之后checkout出最新的代码。这些代码就是repo的其它部分的代码。这其中的 main.py 就是repo构建工具的主干入口代码。

而在之前的构造过程中的调用命令 $ repo init -u git://android.git.kernel.org/platform/manifest.git 中，repo首先完成了前面所说的对自身的更新和初始化，然后通过调用后面补充进来的代码完成init的操作。在这个操作中， repo从 git://android.git.kernel.org/platform/manifest.git 这个地址下载了一份整个源码仓库的清单的版本库，并checkout出一份最新的清单，即 .repo/manifests/default.xml 文件。该文件是一个xml文件，在这个文件中描述了获取代码的远程版本库地址、其中所涉及到的每个项目的地址等等。下面是其中一部分：

<manifest branch="master">
  <remote  name="korg"
           fetch="git://android.git.kernel.org/"
           review="review.source.android.com" />
     
  <project path="bionic" name="platform/bionic" />
  
  <project path="external/clearsilver" name="platform/external/clearsilver">
    <import>
      <remap strip="clearsilver-%version%/" />
      <mirror url="http://android.git.kernel.org/pub/clearsilver-%version%.tar.gz" />
      <snapshot version="0.10.5" check="ec5fff5d7367ddd29a619cf81ae264687fde94c8" />
    </import>
  </project>
  
  ... ...
  
</manifest>

这里只是截取了其中一小部分的片段用来说明问题。

remote节点的fetch属性描述了远程的版本库的基本地址，之后是一系列的project节点。每一个project节点都有一个path和name属性，path是该项目在本地的存储地址，如bionic则是存储在本地的 ./repo/projects/bionic 下面，而name属性是远程版本库中的路径，与remote的fetch的地址结合起来即可得到该项目的版本库地址，如bionic的版本库是在 git://android.git.kernel.org/platform/bionic

而有的project定义中有import节点，该import节点中定义的一般都是该项目所依赖的第三方的独立项目，这些项目是没有历史版本信息的，因此只是一个tar.gz的包。repo在同步的过程中会将其下载下来，解压、加入到该项目的版本库中，并打上一个tag标记。

通过这个清单文件，repo可以实现整个源码库的随时更新和同步，这也是基于git的版本控制的特性所带来的独特的优势。

Android源码构建工具速览（一）——构造源码库

古月春秋 — Sat, 25 Oct 2008 14:18:00 +0800

随着第一款Android的手机上市，Google也终于发布了其Android的源码。通常情况下，一个开源项目的发布都是伴随着一个巨大的完整的xxx-src.tar.gz的源码包，然后解压、configure/make即可。而Android是基于传说中的Git来管理的，在发布方面自然也有所不同，它基于Git构造了一个可以随时同步更新的源码库。

从 http://source.android.com/download 可以找到一段简单的下载源码的介绍。大致情况是，首先要在Linux或者MacO的系统下操作，其次要保证Git的版本在1.5.4之上，Python的版本在2.4之上。

先做一个小准备，在个人home目录下建立一个bin目录，并加入到PATH环境变量中
$ mkdir ~/bin
$ export PATH=$HOME/bin:$PATH

要下载其源码，先要安装一个Android的构建工具 repo。
$ curl http://android.git.kernel.org/repo > ~/bin/repo
$ chmod a+x ~/bin/repo

然后再建立一个存放源码的目录
$ mkdir ~/android ; cd ~/android

之后使用这个repo工具，来初始化这个源码仓库：
$ repo init -u git://android.git.kernel.org/platform/manifest.git

片刻等待之后，仓库初始化完成。此时，这个仓库只是更新了repo这个构建工具本身，并下载了整个Android源码仓库的一个清单的版本库，在~/android/.repo下面能够看到这些文件。其中 ~/android/.repo/repo 目录是构建工具的全部代码，基于Python写成，稍后再看。其次是 ~/android/.repo/manifests/default.xml文件，这个是整个Android源码库的清单文件，之后repo这个工具会根据这个清单依次下载所有的代码。而~/android/.repo/manifest.git则是这个清单文件的版本库 :) 。

Git有一个有意思的特性，就是可以制定存放版本库版本信息的目录的位置，因而可以将存放版本信息的目录和实际的项目文件放置于不同的目录下，而不是像以前的cvs或者Subversion一样在每一个目录下都有一个讨厌的.xxx隐藏目录。这也从某种程度上减少了冗余信息。

经过上述步骤之后，可以开始进行源码仓库的下载了，对于repo来说，称之为“同步”——sync。

$ repo sync

下载过程中随时可以终断，中断后重新执行同步即可更新到最新的源码仓库。