Download A Partitioned Rendering Infrastructure for Stable Accordion Navigation

3.3.2
Marked ranges in TJ2
There were several changes made to improve on the performance of the implementation of marked ranges in TJ1, most notably using a binary tree to sort and store
RangeInT ree objects. TJ2 no longer caches results for each node, since color lookup
for ranges of nodes is sufficiently fast; we improve scalability by not caching colors
for each tree node. The efficiency issues mentioned in Section 3.3.1 are dealt with in
the following topics: RangeLists combining adjacent or overlapping RangeInT ree
objects; storing RangeInT ree objects in binary trees; and RangeList storing nodes
for implicitly user-marked nodes.
Combining adjacent RangeInT ree objects
Automated marking from operations like computed differences and search results
often return several adjacent, non-unique, or overlapping RangeInT ree objects, all
of which we refer to as overlapping ranges. TJ2 combines RangeInT ree objects by
searching the RangeList binary tree for overlapping ranges, combining any overlapping ranges with the RangeInT ree, repeating the process until no more overlapping
ranges are found, and finally adding the new non-overlapping RangeInT ree to the
RangeList. This repeated searching is necessary with the data structures we use
for our binary tree implementation, namely the Java T reeSet, which cannot return
the entire set of overlapping ranges in a single function call.
RangeList collections as binary trees
We sort the RangeInT ree objects in a binary tree by their minimum node key
values; the sorting criteria could actually use any node key in the range since there
are no overlapping ranges in RangeList binary trees. Since each RangeInT ree
is accessible in time logarithmic to the number of marked items, the performance
improvement is a dramatic improvement for large numbers of marked items, often
resulting from hundreds of either differences or search results.
50