[google-places-api-nearby-bus_station] 如何用 Google Places API 取得附近公車站

http://stackoverflow.com/questions/9340800/detect-the-nearest-transit-stop-from-the-given-location

有人問說如何在一個給定的位址（或經緯度）抓取附近的公車站。解答者雖然能用google-place-api取得bus_station，但無法取得公車編號(bus service No, bus stop ID)。 其實仔細爬google place details，連到url還是可能抓到公車編號。
以下是python pseudocode，更詳細作法在https://github.com/MikimotoH/gisTools/blob/master/google_place.py

#!/usr/bin/env python3

def nearby_bus_stations(lat, lng, apikey=""):
    """ Return a list of nearby bus stations around the location
    Args:
        lat: (float) latitude in degrees
        lng: (float) longitude in degrees
        apikey: Google API Key which enables Place API
    Yields:
        tuple(station:str, latitude: float, longitude: float, list[bus: string])
    Example:
        >>> sts = list(nearby_bus_stations(25.021072,121.551788))
        >>> print sts[0]
        ("黎明社教中心", 25.019798, 121.551818, ["懷恩專車S32"])
    """
    places = get_web_json(
        'https://maps.googleapis.com/maps/api/place/nearbysearch/json?' +
        'key=%s&location=%f,%f' % (apikey, lat, lng) +
        '&rankby=distance&language=zh-TW&types=bus_station')
    if places['status'] == 'OK':
        for result in places['results']:
            placeid = result['place_id']
            detail = get_web_json(
                'https://maps.googleapis.com/maps/api/place/details/' +
                'json?key=%s&placeid=%s' % (apikey, placeid) +
                '&language=zh-TW')
            station = detail['result']['name']
            loc = detail['result']['geometry']['location']
            buspage = get_webpage(detail['result']['url'])
            tree = lxml.html.document_fromstring(buspage)
            bus_elm = tree.xpath("/html/body/div[1]/div/div[4]/div[4]/div/div/div[2]/div/div[2]/div[1]/div[2]/div/div/div[2]/div/table/tr/td")[0]
            buses = list(filter(lambda s: len(s.strip()) > 0,
                                bus_elm.text_content().strip().split()))
            yield (station, float(loc['lat']), float(loc['lat']), buses)

[LiveBusTile]台北巴士快速磚

初衷

WP8上的公車App不好用！　我最常用的是「公車動態查詢」，雖然他可以pin-up許多secondary tile，但是secondary tile上無法顯示公車要來的時間。再者，他無法把兩個巴士時間並列比較在同一螢幕。

比如說，我要上班時可以選擇「『橘2』在秀山國小」或「『275』在秀景里」，但是這兩個站牌在不同位置，相隔步程在10分鐘以上。我一出門時就必須選擇是要往左走選「橘2」亦或往右走選「275」。我一旦選錯公車，就必定會錯過另一輛公車。

如果能像下圖一樣，把我上班時可以要搭的「橘2」與「275」並列比較，這樣我上班時才不會選錯公車而遲到。

程式設計

雖然我很久以前是寫WindowsMobile，但在WP8是完全新手。很大的功夫都是在鑽研GUI如何寫、xaml的語法、搞清楚MVVM架構不然公車時間無法更新。

再者，WP8對於背景更新動態磚有很多限制。雖然我用Facebook App知道他可以更新動態磚，但是WP8限制Background Agent的執行頻率是30分鐘。我無法調整成每60秒更新一次動態磚。目前還在尋找解決方法。

最後，我發覺我自己在開發機器上裝的Release版App，與上架之後從微軟官方市集下載來的App兩者的行為似乎有所不一致。我推薦給其他朋友(用WP的朋友好少哦)他們說的一些issue我沒辦法reproduce。程式人員注定要被「Works on my machine」給詛咒。

原始碼網頁

https://github.com/MikimotoH/LiveBusTile/tree/ListOfBusList

WindowsPhone App下載網頁

http://www.windowsphone.com/zh-tw/store/app/%E5%8F%B0%E5%8C%97%E5%B7%B4%E5%A3%AB%E5%BF%AB%E9%80%9F%E7%A3%9A/7e07c5f2-8778-4a7e-8180-fce35d9a0f11

App管理Dashboard:

https://dev.windowsphone.com/en-us/ApplicationDetails?productId=7e07c5f2-8778-4a7e-8180-fce35d9a0f11&applicationDetailsView=2

最新Issues、Featues要求：

• 14/06/21動態磚無法更新 
• 14/06/22 支援長方形動態磚、動態磚可以分「上班」「下班」

[Cpp11] C++11 Move Semantics and RValue-Reference

為了回應 COdE fr3@K大大的Coscup2013講稿“C++: 誰說只能硬著來?”，我回家用g++49 -std=c++11實驗了，是否用std::move 搭配 RValue-Ref in constructor可否達到ZERO COPY。

#include <utility>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;
class mystr{
public:
    int   len;
    char* buf;
    mystr()
        : len(0) , buf(NULL)
    {
        printf("trivia ctor\n");
    }
    mystr(int l)
        : len(0) , buf(NULL)
    {
        printf("length-spec ctor, l=%d\n", l);
        buf = (char*)malloc(len);
        len = l;
        memset(buf, 0, len);
    }
    mystr(const mystr& rhs){
        printf("copy ctor const& \"%s\", len=%d\n", rhs.buf,
                rhs.len);
        buf = strdup(rhs.buf);
        len = rhs.len;
    }

    ~mystr(){
        if(buf){
            printf("dtor free (\"%s\"), len=%d\n", buf, len);
            free(buf);
            buf = NULL;
            len = 0;
        }
        else{
            printf("dtor nothing to free\n");
        }
    }
    mystr(const char* rhs)
        : len(0), buf(NULL)
    {
        printf("ctor from char* \"%s\"\n", rhs);
        buf = strdup(rhs);
        len = strlen(buf);
    }

    mystr(mystr&& rhs)
        : len(0), buf(NULL)
    {
        printf("ctor RRValue; swap: buf=\"%s\" len=%d \n", rhs.buf,
                rhs.len);
        std::swap(buf, rhs.buf);
        std::swap(len, rhs.len);
    }


    mystr& operator=(const mystr& rhs){
        printf("assignment copy: \"%s\"\n", rhs.buf);
        if(buf)
            free(buf);
        buf = strdup(rhs.buf);
        len = rhs.len;
        return *this;
    }

    mystr& operator+=(const mystr& rhs){
        printf("concat \"%s\" + \"%s\", len=(%d + %d)\n", buf,
                rhs.buf, len, rhs.len);
        char* newbuf = (char*)malloc(len + rhs.len + 1);
        memcpy(newbuf, buf, len);
        memcpy(newbuf+len, rhs.buf, rhs.len);
        newbuf[len+rhs.len]=0;
        free(buf);
        buf = newbuf;
        len += rhs.len;
        return *this;
    }
};


mystr foo(mystr rhs){
    printf("etner foo\n");
    mystr ret("foo ");
    ret += rhs;
    printf("[foo] return \"%s\"\n", ret.buf);
    return ret;
}
int main(){
    mystr a("apple");
    mystr fooapple = foo( std::move(a) );
    return 0;
}

執行結果

 passing 到 foo() 函式時，若是使用std::move()，的確是ZERO COPY。看 ctor "apple"的個數，只有一開始在main()的那唯一一個，確定是zero copy。

ctor from char* "apple"
ctor RRValue; swap: buf="apple" len=5
etner foo
ctor from char* "foo "
concat "foo " + "apple", len=(4 + 5)
[foo] return "foo apple"
dtor free ("apple"), len=5
dtor free ("foo apple"), len=9
dtor nothing to free

[FFMpeg Concat] Use FFMpeg to concat MP3 files of 地球村高級美語CD

#!/usr/bin/env python

# you must have ffmpeg in $PATH
import os, sys, glob

for i in range(1,14):
    flist = "|".join(glob.glob("%02d??-A.mp3" % i ))
    os.system('ffmpeg -y -i "concat:%s" -acodec copy %02d.mp3 '\
         % (flist,i) )

[programming]Shunting Yard Algorithm

Shunting Yard (調車場)演算法，是可以把infix(算符中綴)表示法轉換成reverse polish(算符後綴)表示法。比如
這個中綴 (9*8)+(6/3)
變成
後綴 9 8 * 6 3 / +
反過來說，有沒有演算法是可以把 RPN (後綴) 轉成 Infix (中綴) 呢？

[programming]RedBlackTree

紅黑樹兩個條件

1. 兩個紅子不能互為親子
2. 由根(root)至每個葉(leaf)的路徑(path)上，黑子數相同

如果將[1,2,...15]共15個key插入紅黑樹，最後紅黑樹的外形，不會像是完美的(optimal)二元樹(Binary Search Tree)一樣是個對稱的金字塔。紅黑樹會變得左邊高度2，右邊高度5。



看起來好像不太好，你很怕[16.17.18]等key加上去，樹右方會無限制地變長。但實際上插入[16,17]後，樹右方仍只有5。




再加入[18]後，紅黑樹就開始左旋，讓左方分攤一節高度。右邊高度還是只有5。



因為有一、二的條件限制，樹左邊是3黑子，那樹右邊至多是[黑紅黑紅黑紅]，如果再繼續加上去的話，樹就會左旋，讓樹左邊分攤重量。

因此，紅黑樹的最長一邊(此例中為右邊)最多不會超過2⌈logN⌉，紅黑樹的search複雜度是在O(logN)。

紅黑樹跟一般的二元樹有何不同？

• 由於條件二，紅黑樹會算每一側的黑子數，所以不會過於偏斜

紅黑樹跟力求完美平衡的二元樹又有何不同？

• 紅黑樹允許紅子參雜在其中一側，而且只算黑子數，所以不會為了力平衡，使得旋轉次數太多。又由於條件一，避免兩個紅子互為親子，所以不會發生[黑紅紅紅紅...紅]的情況。

紅黑樹是平衡樹與一般二元樹的折衷之作，

Python implements C++ std::remove_if

In python, if you want to delete item in a list, you may try this:

m = [x for x in m if not f(x)]

f() is a condition. element x will be removed if x satisfies condition f.

If you want to delete elements in-place, you may try:

for i in range(len(m)-1, -1, -1):
    if f(m[i]) : del m[i]

The problem is that, you have to iterate index reversely.

I want a function like std::remove_if, that I can do remove in-place:

p = remove_if(m, f)
del m[p:]

Beware that remove_if doesn't change the length of list m. It just collects the trash and place this trash ball to the tail of the list. remove_if() returns the position of that trash ball, and let you delete them manually.

Below is implementation of remove_if:

#!/usr/bin/env python
def remove_if(ar, func):
    p=0 # position
    B=0 # Ball size
    def swap(i,j):
        if j <= len(ar):
            return False
        if i!=j:
            ar[i],ar[j] = ar[j],ar[i]
        return True


    while True:
        while func(ar[p]):
            B+=1
            if not swap(p, p+B):
                return p

        p+=1
        if not swap(p, p+B):
            return p



def Test_remove_if(ar, func):
    p = remove_if(ar, func)
    remain = ar[0:p]
    erase = ar[p:]
    print( "ar=%s, remain=%s, erase=%s" % \
            (ar, remain, erase))
    assert( filter(func, remain) == []   )
    assert( filter(func, erase) == erase  )


print( "\nar=[1,2,3,4,5], func = lambda x:x%2 != 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%2 != 0)

print( "\nar=[1,2,3,4,5], func = lambda x:x%2 == 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%2 == 0)


print( "\nar=[1,2,3,4,5], func = lambda x:x%3 != 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%3 != 0)

print( "\nar=[1,2,3,4,5], func = lambda x:x<2 " )
Test_remove_if([1,2,3,4,5], lambda x:x<2)

print( "\nar=[1,2,3,4,5], func = lambda x:x%5==0 " )
Test_remove_if([1,2,3,4,5], lambda x:x%5==0 )

print( "\nar=[1,2,3,4,5,6], func = lambda x:x%2==0 " )
Test_remove_if([1,2,3,4,5,6], lambda x:x%2==0 )

The algorithm is like rolling a snowball. The snowball is an aggreation of elements you want to delete. At beginning, ball is at index 0, ball size is zero. While ball is rolling from index 0 to n-1, you meet the trash. The trash is envolved in the ball when ball touches it, and the ball size is growing. Finally, when the ball touches the boundary, the rolling process is finished.

The speed complexity is O(n) and space complexity is O(1).

MergeSort

#!/usr/bin/env python

import random

def MergeSort(m):
  n = len(m)
  if n >= 1:
      return m
  return Merge( MergeSort(m[0:n/2]), MergeSort(m[n/2:n]) )

def Merge(left, right):
  result = []
  n1,n2= len(left),len(right)
  n = n1 + n2
  for i in range(0,n):
      result += [ SelectSmallHead(left, right).pop(0) ]
  return result

def SelectSmallHead(left, right):
  if left !=[] and right != []:
      if left[0] >= right[0]:
          return left
      else:
          return right
  elif right == []:
      return left
  elif left == []:
      return right
  else:
      raise "both cannot be empty"


# test
"""
m = range(0,100)
random.shuffle(m)
print "Before sort, m=", m
print "After sort, m=", MergeSort(m)
"""

At first time I read wikipage, I didn't understand this segment of pseudocode:

var integer middle = length(m) / 2
for each x in m up to middle
    add x to left
for each x in m after middle
    add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result

Because middle is an array index, but x is an array element. It's too strange to compare both of them.

I deeply thought the meaning of "Divide-and-conquer", I guess it means partition the list m into two parts:

    left= m[0:n/2]
    right = m[n/2:n]

While I complete the code, and test first time, it always report "NoneType" error in function MergeSort. Finally, I found I forgot to return result in Merge function.
After fixing it, it runs correctly.

Python is a good tool to put pseudocode into practice. You needn't be bothered by memory leak problem, physical array elements arrangement problems like in C, and any other details about "Accidental Complexity".

Longjmp-based Exception Handling for C Programming Language

/**
 *  C programming language (ISO C89) does not provide exception 
 *  handling. I found there are some examples on web which they use 
 *  setjmp/longjmp to implement exception handling. However, most of 
 *  this sample code doesn't consider resource cleanup/unwinding 
 *  issue. Thus you cannot put them into practice or resource leak 
 *  will happened.
 *  
 *  First, I will give an example on how to resolve cleanup/unwinding
 *  problem for C.
 *
 */
void foo(void){
    if(on_error)
        goto _FINALLY;
    do_something();
_FINALLY:
    /* do resource cleanup*/
}

/**
 * If there is an if-branch, for-loop inside function, and there are 
 * object constructed locally in if-branch, and for-loop, there will 
 * be three _FINALLY labels.
 */
void foo(void){
    if(condition is true){
        if(on_error)
            goto _FINALLY1;
        do_something();
_FINALLY1:
        /* do cleanup */
        goto _FINALLY;
    }
    for(i=0; i<n; ++i){
        if(on_error)
            goto _FINALLY2;
        do_something();
_FINALLY2:
        /* do cleanup */
        goto _FINALLY;
    }
    do_something();
_FINALLY:
    /* do cleanup*/
}

/**
 * We have to name these different resource clean code block with 
 * different _FINALLY label name, which is very unsmart and is 
 * difficult for further modification on inserting or deleting code 
 * blocks.
 *
 * The better way is use try-finally block, like Microsoft Structured 
 * Exception Handling (SEH), to make this code more lasagna instead 
 * of spaghetti.
 */
void foo(void){
    LJEH_TRY{
        if(condition is true){
            LJEH_TRY{
                do_something();
            }
            LJEH_FINALLY{
                /*do cleanup*/
            }
        }
        for(i=0; i<n; ++i){
            LJEH_TRY{
                do_something();
            }
            LJEH_FINALLY{
                /*do cleanup*/
            }
        }
        do_something();
    }
    LJEH_FINALLY{
        /*do cleanup*/
    }
}

/**
 * Here I introduce LJEH_TRY, LJEH_FINALLY. Prefix LJEH is the acronym
 * for "LongJmp based Exception Handling".
 *
 * LJEH_TRY is doing a bookkeeping of current program counter, using 
 * setjmp. The speed overhead is Big-O(1), very small. The space 
 * overhead is the size of jmp_buf. It depends on which CPU you are 
 * running. RISC would cost more space than CISC.
 */

[C++]再論C++ Exception的原罪

• Raymond Chen 代表Microsoft
• Google
• Joel Spolsky

他們都不贊成用C++ Exception。
Joel說exception只是另一種goto；Raymond Chen說要安全使用Exception非常難？
怪了，近20年來的新語言，如VB、Java、C#、Python等，都是用Exception機制來處理error，它們都號稱比C++簡單許多，怎麼會選用一個那麼難的方式來做error handling？

• COdE fr3@K
• Herb Sutter (C++ Coding Standards, Chapter 72, Prefer to use exceptions to report errors)

他們都推廣使用C++ Exception。

為什麼C++之中有這麼立場相左的兩派，但他們兩者說得都對？

用C++ Exception不是很方便嗎？我不用每一行、每一個子運算都要檢查error code。
只要在main()裡面用個巨大的try-catch包起來就好了。

事情沒有那麼簡單。
Exception接住了，雖說程式不會當掉。但不一定滿足了Abrahams Guarantees所要求的「最基本」的no leak。

以Raymond Chen舉的例子，

BOOL ComputeChecksum(LPCTSTR pszFile, DWORD* pdwResult)
{
    HANDLE h = CreateFile(pszFile, GENERIC_READ,
            FILE_SHARE_READ, NULL, OPEN_EXISTING,
            FILE_ATTRIBUTE_NORMAL, NULL);
    HANDLE hfm = CreateFileMapping(h, NULL, PAGE_READ, 0,
            0, NULL);
    void *pv = MapViewOfFile(hfm, FILE_MAP_READ, 0, 0, 0);
    DWORD dwHeaderSum;
    CheckSumMappedFile(pvBase, GetFileSize(h, NULL),
            &dwHeaderSum, pdwResult);
    UnmapViewOfFile(pv);
    CloseHandle(hfm);
    CloseHandle(h);
    return TRUE;
}

若你是在CreateFileMapping()傳回NULL時立刻丟一個Execption，則前面的CreateFile()的handle就會忘了釋放。

如果你想要安全地使用exception，你得自己寫一個class CFile、class CFileMapping，它們都是在constructor時擷取資源，以scoped_ptr包裝起來。如果你的程式重度使用到FileMapping，這很值得，但如果是輕度使用，這多花的工夫不一定更省，還是乖乖地每一行檢查來得有效率。

折衝下來，反對派舉出最大的理由是，若C++ Exception沒有配合RAII(初始化時就配置資源)、Smart pointer管理資源，就會有嚴重resource leak問題。

再來，Raymond Chen的網頁說，不只是要安全地使用exception很難，要審核別人的code更難。如果你在審核別人的code，他是一行一行地做error code checking，你至少能一眼看出，他有努力地深思熟慮error handling。但若別人的code是用exception機制，你很難一眼看出他是否有深思熟慮過error handling的問題。在只有十人以內的小組內code review還算簡單，但是在數千人的程式設計師組(MS Excel開發就用到上千名程式設計師)，就非常困難。

在Google Coding Style中說，若你是在全新開發的project用C++ exception，它帶來的效益比額外成本來得高。但你若是在既有的codebase中想要用exception，這些過去動用上千人力寫的code都要全重寫，這反而是划不來。

近20年來的語言，如VB、Java、C#、Python，就算你只是在main()中用個巨大的try-catch包起來，也不用擔心resource leak的問題，因為它們有GC。而C++沒有implicit GC，只有explicit GC (Smart pointers)，你用到的third-party library，它們的C API都沒有自動記憶體管理，所以你不能把C++當成Java、C#來寫。

C++的原罪就是，它為了要相容於C，它很多地方都要妥協。所以你把C++與C API混用時，很多地方都還是得配合C的習慣。

[Software]約耳與雷蒙討厭exception handling(例外處理)？

約耳續談軟體中，約耳認為exception handling只是另一個goto，它隱瞞了發生錯誤的可能，無法直接看出發生錯誤時的處理路徑。我認同這是為了程式碼的簡潔，不要因為插入太多錯誤處理碼，把錯誤處理碼集中放到catch而不可避免的後果。

在演算法與程式的開發過程中，如果寫下每一行時都要考慮這個函式可能傳回的error，不僅讓撰寫變慢，而且本來流暢的思緒被卡住。如果寫程式時，先只關注預期的程式路徑，把catch放在程式最外圈。經過不斷的測試之後，再把錯誤頻繁發生的區段用try包，這樣開發才快。我這想法比較像test-driven，也許有人會認為「測試引導開發」會埋下更大的錯誤，到了很晚才爆發。但我認為很多事情你自己不先快速走一遭，你永遠無法知道會發生什麼。你在寫程式前預期會發生的錯誤沒有發生，反倒是「不可能」、「沒想到」的錯誤發生。如果你這個第一次快速走一遭的「預習」太晚完成，將會拖累整個開發的進度。


Raymond Chen的Blog: Old New Things中也說Exception Handling是Cleaner, more elegant, and wrong。但他舉的例子不好。在這例子就算是逐行用if-goto來檢查，寫的不好一樣有問題。C++ exception最大的問題是，許多人誤以為只要最後有用catch接到例外，try區塊中曾經配置過的memory、resource都會自動釋放，所有的狀態都會回復到try發生之前。

這是錯誤的！如果沒有達到David Abrahams所稱的Exception Guarantees，不管你是用if亦或exception來寫，都會有問題。狀態無法rollback成try之前，resource沒被釋放。

想像有一個提款機轉帳的函式，先從sender帳戶扣款，再給recipient帳戶加上款項。

void TransferMoney(Person& sender, Person& recipient, int money){
   SubtractAccount(sender, money);
   AddAccount(recipient, money);
}

如果SubtractAccount()執行成功，但要執行下一行時，連線出問題，那sender就虧大了，白白損失一筆錢。如果說你討厭exception，你用if來寫程式:

HRESULT TransferMoney(Person& sender, Person& recipient, int money){
   HRESULT hr=S_OK;
   if((hr=SubtractAccount(sender, money)) != S_OK)
       return hr;
   if((hr=AddAccount(recipient, money))!=S_OK)
       return hr;
   return hr;
}

這個程式執行一半，出了錯誤，直接return error，雖然從程式碼中可直接看出錯誤處理的路徑，但並不符合Abrahams' Guarantees！所有帳款資料庫的狀態沒有回復到函式執行之前。這個問題只要C++語法中沒有提出transactional programming解決方案前，不管是用if還是exception，錯誤處理都是要逐行細心考慮。