關于Google日歷中事件排列算法的實現

福建省科學技術信息研究所 劉懷北

?

關于Google日歷中事件排列算法的實現

福建省科學技術信息研究所 劉懷北

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

Google Calendar 功能 事件排列算法

0 引言

Google Calendar[1]作為Google在線服務的一個重要組成部分，以其簡潔易用的操作界面、全面實用的功能以及豐富而強大的插件，贏得了廣大用戶的青睞。在顯示事件的方式上，Google Calendar通過自適應調整事件寬度進行排列的方式來處理時間上存在重疊的事件，從而使得用戶能夠一目了然地查看事件的時間與分布。

本文通過對該事件顯示方式進行一系列的解析，闡述自適應調整寬度進行排列的目的與方法，構造并提出一種相應的算法實現。

1 事件的排列顯示

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

● 自然排列：每個事件都完整的顯示，并占據整列；

● 重疊排列：每個事件都占據整列顯示，后面的事件會遮蓋前面的事件；

● 自適應寬度排列：每個事件各占據約整列寬的一半，并且完整顯示。

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

顯然，當2個事件之間存在重疊的情況下，第3種排列顯示方法要比第2種方法更有效，用戶能夠直觀地看到2個事件的時間跨度，而第2種重疊排列的顯示方式則無法反映出第1個事件在何時結束，用戶必須借助文字信息才能做出判斷。不能想象，在更多事件之間存在更多重疊的情況下，第2種排列顯示方式對于用戶來說是毫無意義的。

2 自適應寬度排列算法

自適應寬度排列方式的優點在于能夠通過調整事件在列表中的顯示寬度和水平位置來降低或避免事件顯示時的重疊。為此，可以通過2個步驟來實現：(1)查找在時間上存在重疊的事件，建立連續重疊事件集合；(2)根據重疊的情況安排事件顯示的寬度和水平位置。

2.1 連續重疊事件集合

如果事件A與事件B之間存在時間重疊，稱A與B直接重疊；如果事件B與事件C也直接重疊，則事件A重疊可達C；如果事件C重疊可達事件E，則事件A也重疊可達E。

圖2 連續重疊事件集合示例

連續重疊事件集合（以下簡稱為COE集合）是指在連續時間區域上，所有能夠通過重疊連接的事件所組成的集合。任意2個屬于該集合的事件A和B，至少滿足以下2個條件之一：①A和B直接重疊；②A重疊可達B。

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

2.2 建立COE集合

定義COE集合類，該類維護一個事件數組evtList，存儲所有屬于該集合的事件，并按照事件發生時間順序排列。

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

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

2.3 自適應寬度排列

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

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

因此，最終整個算法可以歸納為如下過程。

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

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