Dynamic Accordion Drawing

This page is for noting the significant differences between the static versions of Accordion Drawing applications (and base generic code) and dynamic versions. Also should include new application requirements that were not satisfiable by the original code which prompted the change to dynamic Accordion Drawing.

Original applications versus new changes

Generic code

• Red-black tree for storing split lines instead of array
  • Indexing split lines not possible directly
    • store subtree sizes at each split line, compute index in log N
  • Array of length N no longer needed
• Hooks for static version (just for TJ at the moment)
  • A static split line object type created, with an index value

TreeJuxtaposer

TreeJuxtaposer was not to be changed to use a dynamic Accordion Drawing infrastructure as it was not a priority to support tree editing, due to complexity involved with user-controlled modifications of the topology (more info needed here?). Simple editing of labels will be supported to provide renaming nodes (add/delete/rename node names through their labels) and these changes will be saved back to a new tree file. These changes are not what we consider dynamic.

Where new dynamic code uses

• Store leaves in split line hierarchy
  • Do not keep an array of leaves indexed (this may have to change) as we can index them from the split line hierarchy with index lookups of split lines
    • Might have issues with range lookups during descent drawing
  • right-most leaf of entire tree not in the hierarchy (one more leaf than we have split lines, arbitrary choice either left-most or right-most)
  • Nodes in topology still store reference to left- and right-most leaves

• Nodes still keyed (integers) the same as original method (depth-first/left-to-right (top-down) numbering)
  • If node with key K is a right-most leaf of any internal node N, then K+1 is next internal node that is not in the subtree under N, or an ancestor of N (is either a sibling or ancestor of N's sibling)

• Descent drawing issue (indexing)
  • Checking ranges in static versions with array indices was easy with [0,N] indexed split lines, descent into a particular section of leaves was trivial (N = number of split lines). With changes to the range structure (now stores first and last geom objects, TreeNodes in TJ) and removal of the leaf array (leaves now stored in split line objects, CullingObject; originally, differently used in SJ to store aggregated columns), we lost reference methods:
    • from a given TreeNode to a corresponding SplitLine
    • from an index to a TreeNode. This reference is possible with our dynamic infrastructure, but requires an index lookup for each split line (uncached, log N).
  • With a TreeNode key, we may be able to determine if a leaf TreeNode is within a given range of TreeNode leaves.
    • If a node's rightmost leaf key is less than the range's leftmost leaf, that node does not descend into the range (similar argument for node's leftmost and range's rightmost leaves).

SequenceJuxtaposer