The making of circular treemap in Glamorous Toolkit
A story of moldable development
Nested data structures are ubiquitous in software. Packages, classes and methods are nested. Folders and files are nested. XML elements are nested. Treemaps are useful to highlight occurrences in such nested structures, and they should not miss from a development environment.
Glamorous Toolkit offers treemaps, too. This is a behind-the-scene story of how we constructed this algorithm. The story both sheds a light on how we approach moldable development when we develop Glamorous Toolkit, and it offers an insight on how and why we split the larger logic into smaller parts that can be used for other purposes as well.
An impatient reader might want to skim through the pictures and read the conclusion.
Let’s start from a concrete application of a circular treemap. Here is an inspector with a view highlighting some classes and packages from a Java system. The data comes from a Famix model that represents code written in various languages. The code to the right specifies the inspector view with the concrete visualization.
This treemap is implemented as an element stencil — a factory of elements — that allows us to specify several things:
- the traversal of the container nodes,
- the computation of the leaf nodes,
- the computation of the size of the leaf nodes,
- the specification of the container ellipse element, and
- the specification of the leaf ellipse element.
Furthermore, each container applies a circle packing layout. The circle packing algorithm is based on “Visualization of large hierarchical data by circle packing” by Wang etal. This is a non-trivial layout whose computation relies on several sub-algorithms. Luckily, the paper nicely describes the different parts of the algorithm. Let’s dive a little to see what’s there.
Circle packing applied on a set of elements looks like this:
To make this work, we first need to find the enclosure around given circles. We then need to identify where to add a new circle to a given enclosure. And for that, we need to compute the actual position of a new circle.
The paper comes with nice visual depictions describing the algorithm details. For example, here is a figure explaining how to calculate the outside chain of circles, called front-chain:
This algorithm is reasonably laborious and it is found inside the overall layout computation. While the paper does provide a description of the algorithm, translating it into code can still be tricky. To debug our way through the implementation, we wanted to bring the depiction from the paper into our environment. Certainly, this is what moldability should be about, and an inspector extension would be an ideal place to park this depiction.
To make this happen, we needed an explicit class. Thus, we reified the front-chain into its own dedicated class and a dozen lines later, the view materialized, too. Armed with this view, we could then step through the algorithm and see the result visually during debugging.
The two final pieces of the circle packing puzzle are finding the location of a new circle in the neighborhood of circles and determining the enclosure of given circles. Inspector extensions to the rescue! In this case, too, we first reify the neighborhood and the enclosure as first class entities.
Taking a step back, there are a couple of things to notice. The algorithm has multiple layers of abstraction: At first, we have the recursive definition of the treemap. Then is the circle packing layout which, in its turn, is based on computing the enclosure of given circles, on identifying where to add a new circle, and on actually computing the location of the new circle. All these are separate pieces that can be used independently.
Having a multi-layered algorithm is not unusual. What is less usual is that all layers are exemplified and are inspectable through custom views. When following moldable development, these custom views are natural byproducts.
The first rule of thumb is that if we need to look at the raw view of an object type more than three times, we are likely missing a custom view. So, we build one.
The second rule of thumb is that before solving a problem, we first depict it in a way that makes the solution evident.
This process is orthogonal to the typical test or example-driven development. For example, the circles enclosure is mainly a collection of circles. Yet, because we wanted to have a specific view, we ended up promoting it to a first class entity even though from a functional perspective, everything remained the same.
Thinking of custom views exercises the design in a way that testing does not. While writing tests during development builds testability into the system, guiding the design through custom views builds explainability into the system.
For example, while working on the algorithm, we had to deal with a bug when computing the enclosure of specific nodes. We noticed the issue in a larger treemap, and narrowed it down to a smaller case involving three nodes. The view below shows that the blue enclosure circle on the right is not the minimal circle we can draw.
The screenshot documented the bug report. Having the view around helped us locate the problem quickly and write a failing example for it. The solution came soon afterwards.
It is hard to convey the impact on the development experience of these custom views. It’s not unlike the testing: you have to practice it to fully appreciate it; and the more you practice it, the more pleasant the experience becomes. Like with testing, it’s counter-intuitive: building a view is a meta step that apparently distracts from the direct task at hand. Yet, building that view helps us make explicit what is important to explain and this leads to better design.
Custom views also help us tell others what is important. There is great power in being able to convey a problem about a detail deep inside a system through a single picture that requires little explanation. The pictures from the paper were deemed meaningful for communication purposes. Like the drawings on the whiteboard these picture are important in that they capture an intent. Yet, these pictures should only be drawn manually when the system does not exist. When the system does exist, the picture should never be drawn by hand. The system should draw it for us.
When a presentation is deemed meaningful by at least one person, it is the responsibility of the system to carry it forward. Only like this will our systems become explainable.
