这个问题其实很简单，DFS的基础，所以我写了4个版本。第一个是递归，其实效率在4个里面算很好的，递归真的是简洁而优雅。

1
2
3
4
5
6
7
8
9

public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right) 
            return root->val == sum;

        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
	    }
	};

第二个非递归版本，用sp模拟栈，accessed记录访问过的节点。

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

class Solution2 {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;

        std::vector<TreeNode*> sp;
        unordered_map<TreeNode*, bool> accessed;

        sp.push_back(root);
        int len = 0;
        while (sp.size()) {    
            auto* np = sp.back();
            if (np->left && !accessed[np->left]) {
                len += np->val;                        
                sp.push_back(np->left);
            } else if (np->right && !accessed[np->right]) {
                len += np->val;                                        
                sp.push_back(np->right);
            } else {
                if (!np->left && !np->right)
                    if (len + np->val == sum) return true;
                accessed[np] = true;
                sp.pop_back();
                if (sp.size()) len -= sp.back()->val;
            }
        }

        return false;
    }
};

后面两个比较有意思，Solution3是一个intrusive版本，它在下降过程中修改子节点的val值，使得每个节点保存从根节点到达的路径的sum。这样，当遇到叶子节点时就知道这条路径的sum大小。

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

class Solution3 {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;

        std::vector<TreeNode*> sp;
        sp.push_back(root);
        while (sp.size()) {    
            auto* np = sp.back();
            sp.pop_back();

            if (!np->left && !np->right) {                
                if (np->val == sum) return true;
            }

            if (np->left) {
                np->left->val += np->val;                        
                sp.push_back(np->left);
            }
            if (np->right) {
                np->right->val += np->val;                                        
                sp.push_back(np->right);
            }
        }

        return false;
    }
};

第四个版本比较有意思，基础是morris遍历，所用得技巧跟第三版本比较类似，就是在下降过程中修改节点的val值，保存路径的sum大小。关键就是在哪几个地方做这个事情。看代码不如画图，画张图就清楚了。代码里的注释解释了一个问题，就是在找到一个解时不能直接return true。大概是leetcode提交环境的问题，因为morris遍历修改了每个节点的左子树的最右节点的right指向，leetcode希望树结构保持不变。

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

class Solution4 {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;

        bool ret = false;
        TreeNode* nd = root;
        while (nd) {
            if (!nd->left) {
                //NOTE: can not write `return true` here. since morris traversion modified
                //struture of tree, we need to run over to make sure all changes restored.
                //because of this, this may not as fast as primitive solution.
                if (!nd->right && nd->val == sum) ret = true;
                if (nd->right) nd->right->val += nd->val;                
                nd = nd->right;
            } else {
                auto* l = nd->left;
                while (l->right && l->right != nd) l = l->right;
                if (l->right == nd) {
                    if (!l->left && l->val == sum) ret = true;                                                                        
                    nd = nd->right;
                    l->right = nullptr;
                } else {
                    nd->left->val += nd->val;                    
                    if (nd->right) nd->right->val += nd->val;                    
                    l->right = nd;
                    nd = nd->left;
                }
            }
        }

        return ret;
    }
};

这个题基本没什么好说的了，经典回溯算法。主要问题在于如何快速剪支。我使用了三个数组来追踪每列，每条对角线以及反向对角线上是否有冲突。看了几个网上的实现，都是在放置一个皇后之后，通过计算两个坐标是否同线来判断是否（反）对角线冲突。而我是直接计算出皇后所处位置的对角线（用一个数来表示）。

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

class Solution {
public:
    std::vector<bool> cols;
    std::vector<bool> diags;
    std::vector<bool> rdiags;
    
    vector<vector<string> > solveNQueens(int n) {
        cols = std::vector<bool>(n, false);
        diags = std::vector<bool>(n, false);
        rdiags = std::vector<bool>(n, false);

        vector<vector<string>> res;
        if (n <= 0) return res;

        std::vector<string> ans(n, string(n, '.'));
        solve(res, ans, n, 0);
        return res;
    }

    void solve(vector<vector<string>>& res, vector<string>& board, int n, int row) {
        if (row == n) {
            res.push_back((board));
            return;
        }

        for (int i = 0; i < n; i++) {
            int d = row + i, rd = n - 1 - row + i;
            if (!cols[i] && !diags[d] && !rdiags[rd]) {
                board[row][i] = 'Q';
                cols[i] = diags[d] = rdiags[rd] = true;
                solve(res, board, n, row+1);
                cols[i] = diags[d] = rdiags[rd] = false;
                board[row][i] = '.';
            }
        }
    }
};

今天晚上又脑洞打开，一把年纪了，数学成了我的短处。昨天晚上一边看优酷一边解First Missing Positive，没想出来怎么在常量空间或者O(n)里处理这个问题。今天晚上突然想到一个绝妙的算法。十分钟左右搞定。

思想很简单：把每个数字A[i]挪到非递减排序后内所应在的位置上。如果数字不在(0, n]之间就跳过。比如[2, 3, 7, -1, 4]，按照排序顺序重新放置并忽略不在(0, n]范围内的数字就变成[2, 2, 3, 4, 4]了。然后就清楚了，再遍历一次新数组，第一个不满足条件A[i] != i+1的就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for (int i = 0; i < n; i++) {
            if (A[i] <= 0 || A[i] > n) {
                continue;
            } 

            int k = A[i];
            int p = A[k-1];
            while (k != p) {
                A[k-1] = k;
                k = p;
                if (p > n || p <= 0) break;
                p = A[k-1];
            }
        }

        for (int i = 0; i < n; i++) {
            if (A[i] != i+1) return i+1;
        }
        return n+1;
    }
};

我在网上看了下，这个同学跟我的思路是一样的，不知道还有没有其他好的算法。

算法思路想到之后发现其实还是很简单的，算法复杂度是O(n*m)，基本上只要扫描两遍矩阵就能得到结果。
算法分两步：

• 首先扫描一遍做预处理，生成一个新矩阵M1。M1[i][j]代表第j列上从i行到0行连续的‘1’的个数。
  比如一个这样的原矩阵

{'0', '0', '0', '1', '0'},
{'1', '0', '1', '1', '0'},
{'1', '1', '0', '1', '1'},
{'1', '1', '1', '1', '0'},
{'0', '1', '1', '1', '0'}

经过预处理变成

{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 1, 0}，
{0, 1, 0, 1, 2, 0}，
{0, 2, 1, 0, 3, 1},
{0, 3, 2, 1, 4, 0},
{0, 0, 3, 2, 5, 0}

注意我把M1矩阵增广了（augmented），第一行和第一列全空，这样的目的是方便后面的遍历算法边界条件处理更容易。

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

      int rows = matrix.size(), cols = matrix[0].size();
      vector<vector<int>> collect(rows+1, vector<int>(cols+1, 0));
      for (int i = 1; i <= rows; i++) {
          for (int j = 1; j <= cols; j++) {
              if (matrix[i-1][j-1] == '1') {
                  collect[i][j] = collect[i-1][j] + 1;
                }
            }
        }
```   

* 按行遍历M1矩阵
    
    在遍历一行的第j列时，我们要实时计算出当前最大的全1子矩阵的面积。为此，我使用一个栈来记录一些状态。这个栈的每一项是一个pair（`std::vector<pair<int, int>> sp;`）。second记录列号，first是所指列的高度。这个栈追踪从当前离j列最近的一个高度为0的列开始，到j列的所有高度低于j列的列的信息（高度大于j列的列都从栈里弹出了）。因此这个栈里的元素是按高度单调递增的（从栈底至栈顶）。这个栈的作用是用来计算包含当前行的j列的所有全1子矩阵的大小。不记录高度大于j列的列是因为它的宽度肯定为1，已经在遍历到达j列之前做为全1子矩阵计算过了。
    

```c++
    for (int i = 1; i <= rows; ++i) {
            std::vector<pair<int, int>> sp; // <high, index>
            sp.emplace_back(0, 0);
            for (int j = 1; j <= cols; j++) {
            int k = collect[i][j];
            while (sp.size() && sp.back().first >= k) {
                sp.pop_back();
            }
            sp.emplace_back(k, j);

            for (int p = 1; p < sp.size(); p++) {
                auto h = sp[p].first;
                auto w = j - sp[p-1].second;
                if (max < w * h) {
                    max = w * h;
                }
            }
        }
    }

了解Objective C的都知道，Objective C在C原有的for基础上增加了一个新的语言特性fast enumeration。官方文档里提到fast enumeration要比使用NSEnumerator快，我想不是很多人知道或者想过为什么fast enumeration会更快。

首先，一个Objective C的类要支持fast enumeration就必须实现NSFastEnumeration协议。这个协议只有一个方法countByEnumeratingWithState:objects:count:，官方文档写的不太清楚，估计只看这个没人知道怎么自己实现一个支持fast enumeration的类。我们可以看看GNUStep里NSArray的实现作为参考（Cocoa框架不开源）：

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

- (NSUInteger) countByEnumeratingWithState: (NSFastEnumerationState*)state
				   objects: (__unsafe_unretained id[])stackbuf
				     count: (NSUInteger)len
{
  NSUInteger size = [self count];
  NSInteger count;

  /* This is cached in the caller at the start and compared at each
   * iteration.   If it changes during the iteration then
   * objc_enumerationMutation() will be called, throwing an exception.
   */
  state->mutationsPtr = (unsigned long *)size;
  count = MIN(len, size - state->state);
  /* If a mutation has occurred then it's possible that we are being asked to
   * get objects from after the end of the array.  Don't pass negative values
   * to memcpy.
   */
  if (count > 0)
    {
      IMP	imp = [self methodForSelector: @selector(objectAtIndex:)];
      int	p = state->state;
      int	i;

      for (i = 0; i < count; i++, p++)
	{
	  stackbuf[i] = (*imp)(self, @selector(objectAtIndex:), p);
	}
      state->state += count;
    }
  else
    {
      count = 0;
    }
  state->itemsPtr = stackbuf;
  return count;
}

代码很简单，就是从数组中取出连续的一部分，通过参数state传给调用者。这个函数会被编译器生成的代码调用。

下面一段简单的代码使用了fast enumeration：

1
2
3
4
5
6
7
8

void fastEnum()
{
    NSArray *arr = @[@"one", @"two", @"three"];
    for (id s in arr) {
        NSLog(@"val: %@", s);
    }
}

编译器生成的代码大概是这样的：

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

void fastEnum()
{
    NSArray *arr = ((NSArray *(*)(id, SEL, const id *, NSUInteger))(void *)objc_msgSend)(
            objc_getClass("NSArray"),
            sel_registerName("arrayWithObjects:count:"),
            (const id *)__NSContainer_literal(3U,
                (NSString *)&__NSConstantStringImpl__var_folders_c4_mzdkvk5n677bsntjw9d7qtzw0000gn_T_Untitled_9O7vfS_mi_0,
                (NSString *)&__NSConstantStringImpl__var_folders_c4_mzdkvk5n677bsntjw9d7qtzw0000gn_T_Untitled_9O7vfS_mi_1,
                (NSString *)&__NSConstantStringImpl__var_folders_c4_mzdkvk5n677bsntjw9d7qtzw0000gn_T_Untitled_9O7vfS_mi_2).arr,
            3U);
    
{
	id s;
	struct __objcFastEnumerationState enumState = { 0 };
	id __rw_items[16];
	id l_collection = (id) arr;
	unsigned long limit =
		((unsigned int (*) (id, SEL, struct __objcFastEnumerationState *, id *, unsigned int))(void *)objc_msgSend)
		((id)l_collection,
		sel_registerName("countByEnumeratingWithState:objects:count:"),
		&enumState, (id *)__rw_items, (unsigned int)16);
	if (limit) {
	unsigned long startMutations = *enumState.mutationsPtr;
	do {
		unsigned long counter = 0;
		do {
			if (startMutations != *enumState.mutationsPtr)
				objc_enumerationMutation(l_collection);
			s = (id)enumState.itemsPtr[counter++]; {
        NSLog((NSString *)&__NSConstantStringImpl__var_folders_c4_mzdkvk5n677bsntjw9d7qtzw0000gn_T_Untitled_9O7vfS_mi_3, s);
    };
	__continue_label_1: ;
		} while (counter < limit);
	} while (limit = ((unsigned int (*) (id, SEL, struct __objcFastEnumerationState *, id *, unsigned int))(void *)objc_msgSend)
		((id)l_collection,
		sel_registerName("countByEnumeratingWithState:objects:count:"),
		&enumState, (id *)__rw_items, (unsigned int)16));
	s = ((id)0);
	__break_label_1: ;
	}
	else
		s = ((id)0);
	}

}

这段代码是通过clang -x objective-c -fobjc-arc -rewrite-objc test.m生成的，去掉其他框架代码，只留下fastEnum的实现。
对比一下，可以看到，编译器生成了两层while循环，外层循环每次调用countByEnumeratingWithState:objects:count:读取16个连续的对象，内层循环逐个访问对象并检查集合是否发生了修改（如果发生了修改，则调用objc_enumerationMutation抛出异常）。fast enumeration性能的关键是countByEnumeratingWithState:objects:count:如何快速批量读取连续的对象。但是如果是像GNUStep里的实现，在性能上就不会有太大的优势。因为使用了objectAtIndex逐个取出对象，这跟NSEnumerator取出对象的方法类似。所以我估计苹果在自己的实现中使用了一些技巧，能够直接访问到NSArray的内部数据，而不是通过objactAtIndex逐个读取。

这里有一个性能测试，可以看到当集合里的对象数量足够多的时候，fast enumeration的优势还是很明显的。

PS: 这里有一个如何在自定义类中实现MSFastEnumeration的说明，可以对如何合理的实现countByEnumeratingWithState:objects:count:有一个认识。

最近看了Russ Cox大神关于正则的文章。深深的被打动了。仔细看完文章之后，一时兴起，自己鼓捣了一个实现，然后再看他的代码，还是不得不佩服大神对C指针的运用。

Russ Cox在实现时用到的一些指针技巧

• 在nfa的实现中，最有意思的地方就是PtrList的定义。一般我们在定义一个单项链表时都会定义成一个结构struct，但是在这里它被定义成union。在C中，一个union中的所有成员是共享一个地址的，怎么能表示一个链表结构呢？仔细分析后，一切就很清楚了。这里之所以可以用union的前提是基于这样一个事实，即：一个Frag中的PtrList成员所指向的是State结构中out或者out1指针的地址，在调用patch之前它的值是NULL。list1中在根据一个outp指针构造一个PtrList时是直接将其强制转换为一个PtrList。因为这个outp是某个State的out或out1的地址，还没有跟其他State连接起来（通过patch操作连接），所以这么做不会影响任何现有State对象。这个非常trick的设计需要对PtrList的作用和使用方式（在post2nfa函数中）有很深的理解。我在自己实现的时候没有使用这样的方式，目的主要是为了清晰可读。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/*
 * Since the out pointers in the list are always 
 * uninitialized, we use the pointers themselves
 * as storage for the Ptrlists.
 */
union Ptrlist
{
	Ptrlist *next;
	State *s;
};

/* Create singleton list containing just outp. */
Ptrlist*
list1(State **outp)
{
	Ptrlist *l;
	
	l = (Ptrlist*)outp;
	l->next = NULL;
	return l;
}

• 在dfa的dstate函数实现中，当分配一个DState的内存空间时，不仅分配了DState结构体本身的内存，同时还分配了List结构中State列表的内存。这么做减少了内存分配的碎片。

1
2
3
4
5
6

/* allocate, initialize new DState */
d = malloc(sizeof *d + l->n*sizeof l->s[0]);
memset(d, 0, sizeof *d);
d->l.s = (State**)(d+1);
memmove(d->l.s, l->s, l->n*sizeof l->s[0]);
d->l.n = l->n;

• dfa1的实现加入了受控的内存使用，即只缓存特定数量的DFA状态，如果超出限制将回收当前分配的所以DState对象，回收的方法很有技巧，核心如下面的两个函数所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/* Free the tree of states rooted at d. */
void
freestates(DState *d)
{
	if(d == NULL)
		return;
	freestates(d->left);
	freestates(d->right);
	d->left = freelist;
	freelist = d;
}


/* Throw away the cache and start over. */
void
freecache(void)
{
	freestates(alldstates);
	alldstates = NULL;
	nstates = 0;
}

也即回收之后并没用free掉之前分配的内存，而是转而将所有DState构造成一个单项链表（复用了DState的left指针）。这个链表的头是freelist。于是在分配一个DState空间时会优先检查freelist是否有项可用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/* Allocate DStates from a cached list. */
DState*
allocdstate(void)
{
	DState *d;
	
	if((d = freelist) != NULL)
		freelist = d->left;
	else{
		d = malloc(sizeof *d + nstate*sizeof(State*));
		d->l.s = (State**)(d+1);
	}
	d->left = NULL;
	d->right = NULL;
	memset(d->next, 0, sizeof d->next);
	return d;
}

这个技巧充分复用了已经分配的数据结构，聪明的降低了内存释放的开销。

• nfa-posix.y的实现也很有意思，他的主要目的是为了实现submatch extraction。也就是这里提到的：

  There are two possible ways to avoid the seemingly unbounded tracking of space implied by POSIX submatching semantics. First, it turns out that matching the regular expression backward bounds the bookkeeping to being linear in the size of the regular expression. This program demonstrates the technique.

nfa-posix.y采用的是逆向匹配正则，主要体现在两个地方：

1
2
3
4
5
6
7
8
9
10
11
12

Frag
paren(Frag f, int n)
{
    State *s1, *s2;

    if(n > MPAREN)
        return f;
    s1 = state(RParen, n, f.start, NULL);
    s2 = state(LParen, n, NULL, NULL);
    patch(f.out, s2);
    return frag(s1, list1(&s2->out));
}

注意这里构造的Frag的顺序，右括号指向f，f的出口指向左括号。

1
2
3
4
5
6
7
8

concat:
    repeat
|   concat repeat
    {
        patch($2.out, $1.start);
        $$ = frag($2.start, $1.out);
    }
;

可以对比下nfa里的实现，正好是反向的。$2的出口指向$1的开始。要是不细心，可能会忽略这两个微小而重要的区别。

因此，通过文中的parser构造的NFA是逆向的，所以match函数也是从字符串的尾部开始匹配。

我的实现

我根据文章中的描述，重写了一个实现。主要是去掉了一个静态的分配，正则的解析改用递归下降解析。并且将所有自动机内部的状态信息都封装到一个结构体中，加强了内存管理，可以释放内部创建的所有资源。我用Xcode自带的Instruments测试没有内存泄露，还算不错。我的实现放在github上了。

PS: 我将文章中相关的几个实现一起放在仓库里了，方便自己研究用。

PPS：顺便还发现了一个nfa-posix.y中的bug，我要不要告诉他呢。。。。纠结啊，应该是个笔误。

上次看到一段JS的代码觉得很酷，今天偶尔看到另一篇文章，讲的是原C版的Duff’s Device。自认为对C很有认识了，没想到这种诡异的写法还是难倒我了。现在才知道原来C的语法可以这么灵活。原文里给出了一个链接，是一个C的yacc语法文件。根据这个文件里switch和statement的描述可以很清楚的看出来，在switch中可以嵌入任何复杂的statement，而不仅仅是迭代语句。那到底生成的代码时怎么样的呢，它的工作原理在文章里已经进行了描述，但是想要知道到底是怎么样的，还是得看汇编，于是我将下面一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <stdio.h>

int main(int argc, char *argv[])
{
    int key = 2;
    switch(key)
        for (int i = 0; i < 10; ++i) {
            key = i;
        case 2: printf("case 2: key is %d\n", key);
        case 4: printf("case 4: key is %d\n", key);
        }
    return 0;
}

用clang -S -emit-llvm反汇编了出来，核心的部分如下：

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

  %key = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %1
  store i32 %argc, i32* %2, align 4
  store i8** %argv, i8*** %3, align 8
  store i32 2, i32* %key, align 4
  %4 = load i32* %key, align 4
  switch i32 %4, label %19 [
    i32 2, label %11
    i32 4, label %13
  ]
                                                  ; No predecessors!
  store i32 0, i32* %i, align 4
  br label %6

; <label>:6                                       ; preds = %15, %5
  %7 = load i32* %i, align 4
  %8 = icmp slt i32 %7, 10
  br i1 %8, label %9, label %18

; <label>:9                                       ; preds = %6
  %10 = load i32* %i, align 4
  store i32 %10, i32* %key, align 4
  br label %11

; <label>:11                                      ; preds = %0, %9
  %12 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([10 x i8]* @.str, i32 0, i32 0))
  br label %13

; <label>:13                                      ; preds = %0, %11
  %14 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([10 x i8]* @.str1, i32 0, i32 0))
  br label %15

; <label>:15                                      ; preds = %13
  %16 = load i32* %i, align 4
  %17 = add nsw i32 %16, 1
  store i32 %17, i32* %i, align 4
  br label %6

; <label>:18                                      ; preds = %6
  br label %19

; <label>:19                                      ; preds = %18, %0
  ret i32 0

这个可读性还是很强的，基本上就是switch块和嵌入switch的循环被拆成两个独立的代码块，并且switch的分支语句会跳转到for循环体中带有相应label的部分。这个跳转只会影响for的第一次迭代，之后就是正常的循环了。另外，如果switch分支没有任何匹配的case，就会跳过整个循环（代码中switch的默认label是%19，对应函数的结尾处）。

这个技巧有什么用我也不知道，说不定什么时候能派上用场呢。

因为有了一个苹果本，感觉不学点Objective C，不搞点iOS开发有点浪费。最近在学习Objective C的时候遇到一个坑，经过一点实验，终于想明白是怎么回事了。记下来算是个学习笔记。

长话短说，下面的代码会运行时崩溃。

#include <Foundation/Foundation.h>

@interface Command: NSObject
@property (nonatomic, copy) NSMutableString *name;
@end

@implementation Command
@end

int main(int argc, char** argv) {
    Command *c1 = [[Command alloc] init];
    c1.name = [NSMutableString stringWithUTF8String:"list-panes"];

    NSMutableString *n = c1.name;
    [n appendString:@"(target)"];
    return 0;
}    

原因是因为name属性设置了copy标志。这个copy告诉编译器生成类似下面的setter

- (void) setName: (NSMutableString *)data {
    name = [data copy] ;
}

虽然NSString遵循了NSMutableCopying协议，但是由于赋值时得到的是copy返回的对象而不是mutableCopy，所以虽然c1.name返回的是一个NSMutableString，但是无法修改。这个解释听起来还算合理。

但是为什么一个NSMutableString实例是无法修改的呢？ 难道c1.name返回的其实不是一个NSMutableString？于是我打印出它的类型：

NSLog(@"class: %@", [c1.name class]);
NSLog(@"class: %@", [NSMutableString class]);

输出的结果是

2013-05-24 00:04:24.395 a.out[58754:707] class: __NSCFString
2013-05-24 00:04:24.396 a.out[58754:707] class: NSMutableString

这个完全出乎我的意料，对于刚刚接触Objective C的我来说，这太诡异了。于是我仔细查看了NSString的参考手册。里面有这么一段：

Because of the nature of class clusters, string objects aren’t actual
instances of the NSString or NSMutableString classes but of one of their
private subclasses. Although a string object’s class is private, its interface
is public, as declared by these abstract superclasses, NSString and
NSMutableString. The string classes adopt the NSCopying and NSMutableCopying
protocols, making it convenient to convert a string of one type to the other.

基本意思就是说其实由NSString或NSMutableString构造出来的对象是某私有子类的类型。可以用类型检查来证实：

NSString* s = [NSString stringWithUTF8String: "wor"];
NSLog(@"kind of NSMutableString: %u", [s isKindOfClass: [NSMutableString class]]);
NSLog(@"kind of NSString: %u", [s isKindOfClass: [NSString class]]);

NSMutableString* ms = [NSMutableString stringWithUTF8String: "helo"];
NSLog(@"kind of NSMutableString: %u", [ms isKindOfClass: [NSMutableString class]]);
NSLog(@"kind of NSString: %u", [ms isKindOfClass: [NSString class]]);

输出结果是：

2013-05-24 00:28:33.995 a.out[58996:707] kind of NSMutableString: 1
2013-05-24 00:28:33.996 a.out[58996:707] kind of NSString: 1
2013-05-24 00:28:33.997 a.out[58996:707] kind of NSMutableString: 1
2013-05-24 00:28:33.998 a.out[58996:707] kind of NSString: 1

这说明两个string类型其实都是某个类型的子类型。

于是我仔细翻查了官方文档，发现在Foundation框架中有一个叫类簇(class cluster)的技术。在Foundation框架中有很多类簇，比如NSNumber，目的是减少暴露出来的公共类的数量，用私有子类来实现，这样使得外部接口简洁易用。具体信息可以参考苹果的文档。所以表面上你得到的是一个NSMutableString的指针，但是由于使用了immutable copy，系统进行了优化，返回给你的其实是一个不可修改的string object。要更深入的理解最好去看官方文档。

iterm2 is a great terminal in Mac OS X. It has a lot of features
go beyond what you thought a terminal might be. here is a tip I
learned recently.

Turns out you can select text without mouse in iterm2. just by
press CMD-f to activate find. Enter some initial text you wish to
copy, you’ll find that the last matching highlighted with selected state. use CMD-G or CMD-Shift-G to switch selected text as you want and then press tab to advanced the selected text by words. To advance the beginning of the selection to the left, press Shift-tab. At most one line of text can be selected this way.

It’s up to you to say if this is useful or not.

今天遇到一个问题，百度android sdk扫不出离线地图包，后来发现主要问题是官方文档说明没有及时更新。

说实话，感觉百度的地图sdk有不少问题，官方api文档语焉不详，给出的demo有问题，说明更新也不及时。最可恶的是按照说明下载的离线数据包在程序里面扫不出来，几度让人怀疑自己的智商。期间试过多种方法，比如安装百度地图app，从百度地图里先下载离线地图，然后再回到自己的app，发现无法加载。从官方下载的离线数据包，根据
说明导入（当然，取决于你使用的sdk版本，说明可能是错的）sd卡后同样无法加载。

最后发现导入数据包的正确方法是解压zip包，将里面的vmp目录拷贝到SD卡根目录的BaiduMapSDK目录下（没有就创建一个）。MKOfflineMap的scan函数返回值
一直都是0，所以不要理会它。这里关于离线包在SD卡上的存储未知的说明是正确的，而下载页面给出的说明是错的。

另外一种可以成功的方法是把sd卡里面所有的离线包删除，然后使用MKOfflineMap的searchCity搜索城市地图，并用start函数手动下载离线数据包（比如北京），然后scan会正确加载离线数据（虽然这个时候scan函数返回值还是0）。

bonus: 另外，官网上的sdk包有bug，所以你可能需要联系百度地图团队（比如百度hi）获取一个更新的版本。遇到问题，去问百度客服吧，你的智商没问题。