福建省科學(xué)技術(shù)信息研究所 劉懷北

?

關(guān)于Google日歷中事件排列算法的實(shí)現(xiàn)

福建省科學(xué)技術(shù)信息研究所 劉懷北

Google Calendar作為一款基于事件的日歷系統(tǒng)，以友好的操作界面和實(shí)用的功能而著稱(chēng)。在事件的顯示方面，通過(guò)自適應(yīng)調(diào)整事件寬度的方式進(jìn)行排列，避免事件之間的重疊，直觀地反映事件的時(shí)間與分布。該文對(duì)Google Calendar中事件排列顯示的方式進(jìn)行了解析，對(duì)其中的概念進(jìn)行了抽象與定義，并提出了一種相應(yīng)的算法實(shí)現(xiàn)。

Google Calendar 功能 事件排列算法

0 引言

Google Calendar[1]作為Google在線服務(wù)的一個(gè)重要組成部分，以其簡(jiǎn)潔易用的操作界面、全面實(shí)用的功能以及豐富而強(qiáng)大的插件，贏得了廣大用戶(hù)的青睞。在顯示事件的方式上，Google Calendar通過(guò)自適應(yīng)調(diào)整事件寬度進(jìn)行排列的方式來(lái)處理時(shí)間上存在重疊的事件，從而使得用戶(hù)能夠一目了然地查看事件的時(shí)間與分布。

本文通過(guò)對(duì)該事件顯示方式進(jìn)行一系列的解析，闡述自適應(yīng)調(diào)整寬度進(jìn)行排列的目的與方法，構(gòu)造并提出一種相應(yīng)的算法實(shí)現(xiàn)。

1 事件的排列顯示

如下圖1所示，不同情況下事件的顯示方式可以歸納為以3種：

● 自然排列：每個(gè)事件都完整的顯示，并占據(jù)整列；

● 重疊排列：每個(gè)事件都占據(jù)整列顯示，后面的事件會(huì)遮蓋前面的事件；

● 自適應(yīng)寬度排列：每個(gè)事件各占據(jù)約整列寬的一半，并且完整顯示。

圖1 事件的3種排列顯示方式

顯然，當(dāng)2個(gè)事件之間存在重疊的情況下，第3種排列顯示方法要比第2種方法更有效，用戶(hù)能夠直觀地看到2個(gè)事件的時(shí)間跨度，而第2種重疊排列的顯示方式則無(wú)法反映出第1個(gè)事件在何時(shí)結(jié)束，用戶(hù)必須借助文字信息才能做出判斷。不能想象，在更多事件之間存在更多重疊的情況下，第2種排列顯示方式對(duì)于用戶(hù)來(lái)說(shuō)是毫無(wú)意義的。

2 自適應(yīng)寬度排列算法

自適應(yīng)寬度排列方式的優(yōu)點(diǎn)在于能夠通過(guò)調(diào)整事件在列表中的顯示寬度和水平位置來(lái)降低或避免事件顯示時(shí)的重疊。為此，可以通過(guò)2個(gè)步驟來(lái)實(shí)現(xiàn)：(1)查找在時(shí)間上存在重疊的事件，建立連續(xù)重疊事件集合；(2)根據(jù)重疊的情況安排事件顯示的寬度和水平位置。

2.1 連續(xù)重疊事件集合

如果事件A與事件B之間存在時(shí)間重疊，稱(chēng)A與B直接重疊；如果事件B與事件C也直接重疊，則事件A重疊可達(dá)C；如果事件C重疊可達(dá)事件E，則事件A也重疊可達(dá)E。

圖2 連續(xù)重疊事件集合示例

連續(xù)重疊事件集合（以下簡(jiǎn)稱(chēng)為COE集合）是指在連續(xù)時(shí)間區(qū)域上，所有能夠通過(guò)重疊連接的事件所組成的集合。任意2個(gè)屬于該集合的事件A和B，至少滿足以下2個(gè)條件之一：①A和B直接重疊；②A重疊可達(dá)B。

如圖2所示，事件ABCDE形成了COE集合1，事件FH形成了COE集合2。值得指出的是，任何集合1中的事件都無(wú)法重疊達(dá)到任何集合2中的事件。

2.2 建立COE集合

定義COE集合類(lèi)，該類(lèi)維護(hù)一個(gè)事件數(shù)組evtList，存儲(chǔ)所有屬于該集合的事件，并按照事件發(fā)生時(shí)間順序排列。

建立COE集合的過(guò)程可以通過(guò)按照時(shí)間順序遍歷所有事件一次完成，其具體算法如下（JavaScript[2]偽代碼）：

其中sortByTime方法將evts數(shù)組按事件起始先后排序；belongWhichCOE方法在coes數(shù)組中查找，返回傳入事件所屬的COE集合，如果未找到，則返回null；insert方法則將事件插入到COE集合中適當(dāng)位置。

2.3 自適應(yīng)寬度排列

建立COE集合數(shù)組后，需要為每個(gè)COE集合中的事件計(jì)算寬度和水平位置，為此需要根據(jù)各事件間的重疊情況對(duì)事件進(jìn)行分列顯示，其具體算法如下（JavaScript偽代碼）：

上述COE類(lèi)的insert方法將完成事件的插入和列的建立與更新；findColumn方法用于尋找空隙的列來(lái)插入事件；而isOverlap方法則負(fù)責(zé)判斷列中是否有空隙能夠容納傳入的事件；最后layout算法完成對(duì)COE集合中事件的排列。

因此，最終整個(gè)算法可以歸納為如下過(guò)程。

[1] Google日歷在線系統(tǒng)，https://www.google.com/calendar/render?tab=mc

[2] John Resig. Versions of JavaScript. Ejohn.org, 2009