关于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