图1. universe
背景
最近因为项目需要，用到了DirectUI开源库SOUI，在使用listview控件时，觉得该控件挺好用，效率也不错(在此感谢启程软件，为作者点个赞)，就分析了一下其实现原理， 方便以后查阅。
对于列表控件，行高一般都是固定的，但在实际项目中，的确会有可变行高的情况。传统列表控件很难满足这个需求，SOUI却可以很容易实现该需求。
算法原理
在重绘列表控件时，只需要绘制可视区域就行了。但在绘制项的时候，需要在控件内部维护列表项的位置(postion)和列表项的索引(index)关系。对于固定行高的列表来讲比较简单：position = index * height。
但对于可变高列表项来说，就不好办了，一个简单的办法就是每次都遍历一下所有项，直到找到一个项使得position处于该项内，可知这种方法的时间复杂度是O(n)，这种方法对于数据量比较少的列表来讲是可行的，但数据量比较大时，就会出现性能瓶颈。
SOUI对listview列表控件采用不断分组的方式构建出一棵索引树，查找和修改的时间复杂度都是O(log(n))，举个例子：
现在有14个列表项，每个项的高度分别为[1,2,3,1,2,3,1,2,3,1,2,3,4,5],
如果按照3个列表项为一组构成一个结点（该结点的值为3个列表项的高度和）。
第一次分组：[6,6,6,6,9]
第二次分组：[18,15]
第三次分组：[33]
最后得到的索引树为（虚线部分只是为了说明，不在索引树中）：
图2. 索引树
构建出上述索引树，在此索引树中会进行四个最重要操作：
-
通过位置计算列表项索引（Position2Item）
给定一个位置，计算出该位置所在列表项的索引，计算方法：
1.从根节点开始查找，对非叶子结点运用2，3策略。
2.如果结点高度大于等于给定位置，查找其子结点。
3.如果结点高度小于给定位置，给定位置减去结点高度并继续查找右边兄弟结点。
4.在找到的叶子结点中，遍历分组列表项，直到找到满足条件的索引。
例如给定位置position=22, 要计算出该位置所在列表项的索引，如下图：
图3. Position2Item
其计算步骤为：
1. 从根结点开始，22小于33，运用策略2，查找其子结点。
2. 22大于18，运用策略3，查找右边兄弟结点，并减去已查找到的高度22 - 18 = 4，
根据分治法，也就是我们只需要在右边兄弟结点中再次按照相同的策略查找符合条件的叶子结点。
3. 4小于15，运用策略2，查找其子结点。
4. 红色结点6为叶子结点，符合条件。
5. 遍历图中红色结点的分组，找到第三个项(高度为3)满足条件，由于前面分了3组，
计算出position=22所在列表项的index为11。
- 通过列表项索引计算位置（Item2Position）
图4. Item2Position
给定一个索引计算其位置，是上面的逆过程，但相对来说要简单些，计算方法是：
通过索引，可以计算出列表数项所在的分组及在分组中的子索引:
分组索引 = 列表项索引 / 分组大小
分组子索引 = 列表项索引 % 分组大小
由分组索引可以定位到分组叶子结点，可以计算数该分组叶子结点的位置，算法如下：
1.累加该叶子结点左兄弟结点高度
2.如果该叶子结点有父结点，对其父结点运用策略1
3.运用1，2策略所得的结点高度和即为该分组叶子结点的位置
计算一个分组叶子结点的位置也可理解成累加其所有左边的非直系结点的高度和, 如图4绿色部分。
分组叶子结点的位置再加上分组内索引的位置即可求得列表项索引的位置了。
例如，要计算列表项索引index=11的项的位置：
1. 分组索引 = 11 / 3 = 3
2. 分组子索引 = 11 % 3 = 2
3. 第三个分组叶子结点为上图红色结点，应用上述算法可得该结点的高度为18，
然后再累加分组内子索引的高度为1 + 2 = 3, 可计算出索引为11列表项位置为18 + 3 = 21.
- 设置列表项的高度（SetItemHeight）
通过索引，可以计算出列表数项所在的分组及在分组中的子索引:
分组索引 = 列表项索引 / 分组大小
分组子索引 = 列表项索引 % 分组大小
通过分组索引和分组内子索引可以设置一个项的高度，叶子结点高度的改变需要更新其直系父结点的高度，
时间复杂度同样是O(log(n))
- 获取列表项的高度（GetItemHeight）
通过索引，可以计算出列表数项所在的分组及在分组中的子索引:
分组索引 = 列表项索引 / 分组大小
分组子索引 = 列表项索引 % 分组大小
由分组索引和分组内子索引可以获得列表项的高。
数据结构
通过上面分析，需要用一个树型结构维护分组；另外，为了能够通过列表项索引定位到叶子结点，还需要一个分组的列表存储分组索引到叶子结点的映射。如下：
图5. 数据结构
网友评论