
An Introduction to Treemaps
We live in a data-driven world. But understanding data in numbers is
not always quick and easy. Visualizations like charts and treemaps (or
treemapping, tree maps) help us present data in a way that is quick and
easy to digest.
Treemaps display hierarchical (tree-structured) data as a set of
nested rectangles. Each branch of the tree is given a rectangle, which
is then tiled with smaller rectangles representing sub-branches. A leaf
node’s rectangle has an area proportional to a specified dimension of
the data. Often the leaf nodes are colored to show a separate dimension
of the data.
When the color and size dimensions are correlated in some way with
the tree structure, one can often easily see patterns that would be
difficult to spot in other ways, such as whether a certain color is
particularly relevant. A second advantage of treemaps is that, by
construction, they make efficient use of space. As a result, they can
legibly display thousands of items on the screen simultaneously.
History of Treemaps
Area-based visualizations have existed for decades. For example,
mosaic plots (also known as Marimekko diagrams) use rectangular tilings
to show joint distributions (i.e., most commonly they are essentially
stacked column plots where the columns are of different widths). The
main distinguishing feature of a treemap, however, is the recursive
construction that allows it to be extended to hierarchical data with any
number of levels. This idea was invented by professor Ben Shneiderman at
the University of Maryland Human – Computer Interaction Lab in the early
1990s. Shneiderman and
his collaborators then deepened the idea by introducing a variety of
interactive techniques for filtering and adjusting treemaps.
These early treemaps all used the simple “slice-and-dice” tiling
algorithm. Despite many desirable properties (it is stable, preserves
ordering, and is easy to implement), the slice-and-dice method often
produces tilings with many long, skinny rectangles. In 1994 Mountaz Hascoet and Michel
Beaudouin-Lafon invented a “squarifying” algorithm, later
popularized by Jarke van Wijk,
that created tilings whose rectangles were closer to square. In 1999 Martin
Wattenberg used a variation of the “squarifying” algorithm that he
called “pivot and slice” to create the first Web-based treemap, the
SmartMoney Map of the Market, which displayed data on hundreds of
companies in the U.S. stock market. Following its launch, treemaps
enjoyed a surge of interest, especially in financial contexts.
A third wave of treemap innovation came around 2004, after Marcos
Weskamp created the Newsmap, a treemap that displayed news headlines.
This example of a non-analytical treemap inspired many imitators, and
introduced treemaps to a new, broad audience.[citation needed] In recent
years, treemaps have made their way into the mainstream media, including
usage by the New York Times. The Treemap Art Project produced 12 framed
images for the National Academies (United States), shown the Every
AlgoRiThm has ART in It exhibit in Washington, DC and another set for
the collection of Museum of Modern Art in New York.
Tiling Algorithms for Treemaps
To create a treemap, one must define a tiling algorithm, that is, a
way to divide a region into sub-regions of specified areas. Ideally, a
treemap algorithm would create regions that satisfy the following
criteria:
A small aspect ratio—ideally close to one. Regions with a small
aspect ratio (i.e., fat objects) are easier to perceive.
Preserve some sense of the ordering in the input data
(ordered).
Change to reflect changes in the underlying data (high
stability).
These properties have an inverse relationship. As the aspect ratio is
optimized, the order of placement becomes less predictable. As the order
becomes more stable, the aspect ratio is degraded.
Advantages of Treemaps
Here are some advantages of tree maps over bar (or pie) charts:
Efficient Space Utilization. Treemaps are excellent
for displaying hierarchical (tree-structured) data and for efficiently
using space. Unlike bar or pie charts that may require more space to
display many items distinctly, tree maps can show hundreds or even
thousands of items in a compact space.
Effective for Large Data Sets. Tree maps can handle
large datasets much better than pie charts and, to a certain extent, bar
charts. They can display a vast number of items at once, making it
easier to compare different segments without flipping through multiple
charts.
Hierarchical Representation. Tree maps can show
parts of a whole and how those parts are subdivided into smaller parts,
which is something pie charts cannot do and bar charts struggle with.
This makes tree maps ideal for visualizing nested data in a way that
immediately reveals the structure of the data.
Color Coding and Size Dimensions. Tree maps use both
size and color to represent different dimensions of data, offering a
multifaceted view of the dataset. For example, the size of each box can
represent a quantity, while the color indicates a category or metric,
providing a dense and rich informational summary at a glance.
Better for Comparing Proportions. While pie charts
can show proportions, they can be misleading or hard to interpret when
there are many small slices. Tree maps can more accurately represent
proportions, especially for categories that make up a smaller percentage
of the whole, because the size of each rectangle can be more precisely
compared than the angles or areas of pie slices.
Readability of Small Categories. In bar and pie
charts, small categories can become indistinguishable or require
additional labeling that clutters the chart. In a tree map, even small
categories can be more easily identified and analyzed without
overwhelming the visual presentation.
Intuitive for Certain Types of Data. For datasets
where the hierarchical structure or categorization is significant, tree
maps provide an intuitive and immediate understanding of the data’s
structure and composition. This makes them especially useful for certain
types of financial, organizational, or categorical data.
While tree maps have these advantages, the choice between using a
tree map or bar chart should be based on the specific goals of the data
visualization, the nature of the data, and the audience’s familiarity
with these tools. Each type of chart has its place in data presentation,
and understanding the strengths of each can help in selecting the most
effective way to communicate data insights.
A Real-world Application
Below are the R codes to create the Treemap as seen above:
#--------------------------------------------
# Stage 0: Load R packages and select font
#--------------------------------------------
# Load R packages:
library(rvest)
library(ggplot2)
library(dplyr)
library(stringr)
library(DescTools) # For capitalizing the first letter of a string.
library(treemapify) # For ploting tree map chart.
library(viridis) # For using Viridis Color Scales.
library(showtext) # For using Google fonts.
# Select Open Sans font:
my_font <- "Open Sans"
font_add_google(name = my_font, family = my_font)
showtext_auto()
# Extract GDP data by country:
url <- "https://www.worldometers.info/gdp/gdp-by-country/"
url %>%
read_html() %>%
html_nodes(xpath = '//*[@id="example2"]') %>%
html_table() %>%
.[[1]] -> gdpData
#-------------------------------
# Stage 1: Data pro-processing
#-------------------------------
gdpData %>%
select(2, 3, 4) %>%
rename(gdp = `GDP (nominal, 2022)`, gdpAbb = `GDP (abbrev.)`) -> gdpData
gdpData %>%
mutate(gdp = str_replace_all(gdp, pattern = "\\$|\\,", replacement = ""),
gdpAbb = str_replace_all(gdpAbb, pattern = "\\$", replacement = "")) %>%
mutate(unit = str_replace_all(gdpAbb, pattern = "[0-9]|\\.| ", replacement = "")) %>%
mutate(unit = str_sub(unit, start = 1, end = 3)) %>%
mutate(unit = StrCap(unit)) %>%
mutate(gdpAbb = str_replace_all(gdpAbb, pattern = "[a-z]| ", replacement = "")) %>%
mutate(gdp = as.numeric(gdp)) -> gdpData
gdpData %>%
mutate(shareGdp = 100*gdp / sum(gdp)) %>%
mutate(shareGdp = round(shareGdp, 1)) %>%
mutate(shareGdp = as.character(shareGdp)) %>%
mutate(shareGdp = case_when(!str_detect(shareGdp, "\\.") ~ str_c(shareGdp, ".0"), TRUE ~ shareGdp)) %>%
mutate(shareGdp = str_c(shareGdp, "%")) -> gdpData
gdpData %>%
mutate(label = str_c(Country, "\n", gdpAbb, " ", unit, " (", shareGdp, ")")) -> gdpData
#-------------------------------
# Stage 2: Plot Tree Map
#-------------------------------
gdpData %>%
ggplot(aes(area = gdp, fill = gdp, label = label)) +
geom_treemap(show.legend = FALSE) +
geom_treemap_text(colour = "white",
place = "centre",
family = my_font,
size = 13) +
scale_fill_viridis(option = "H", direction = -1) +
theme(legend.title = element_blank()) +
labs(title = "Nominal GDP Ranked by Country 2022",
subtitle = "Gross Domestic Product (GDP) is the monetary market value of all final goods and services made within a country during a specific period.\nAs of 2022, the United States and China would occupy the first two places. The US is ahead of China by $7 trillion in 2022 but the margin\nis coming down in nominal ranking as China's GDP growth rate of 2023 (5.01%) is higher than the US's 2.09%.",
caption = "Source: https://www.worldometers.info/gdp/gdp-by-country/") +
theme(plot.margin = unit(c(0.5, 0.5, 0.5, 0.5), "cm")) +
theme(text = element_text(family = my_font)) +
theme(plot.title = element_text(size = 18, color = "grey10"),
plot.subtitle = element_text(size = 10, color = "grey30"),
plot.caption = element_text(color = "grey30", size = 8))
LS0tDQp0aXRsZTogIldoeSBBcmUgVHJlZW1hcHMgQmV0dGVyIFRoYW4gQmFyIENoYXJ0cz8iDQphdXRob3I6ICJBdXRob3I6IE5ndXllbiBDaGkgRHVuZyINCnN1YnRpdGxlOiAiUiBEYXRhIFZpc3VhbGl6YXRpb24gU2VyaWVzIg0Kb3V0cHV0Og0KICBodG1sX2RvY3VtZW50Og0KICAgIGNvZGVfZG93bmxvYWQ6IHllcw0KICAgIGhpZ2hsaWdodDogemVuYnVybg0KICAgIHRoZW1lOiBmbGF0bHkNCiAgICB0b2M6IHllcw0KICAgIHRvY19mbG9hdDogeWVzDQogIHdvcmRfZG9jdW1lbnQ6DQogICAgdG9jOiB5ZXMNCiAgcGRmX2RvY3VtZW50Og0KICAgIHRvYzogeWVzDQotLS0NCg0KYGBge3Igc2V0dXAsaW5jbHVkZT1GQUxTRX0NCmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UsIGNhY2hlID0gVFJVRSwgZXZhbCA9IEZBTFNFKQ0KDQpgYGANCg0KIVtdKEQ6L3JlcG9ydFRoYW5nMy9mMTYuanBnKQ0KDQojIEFuIEludHJvZHVjdGlvbiB0byBUcmVlbWFwcw0KDQpXZSBsaXZlIGluIGEgZGF0YS1kcml2ZW4gd29ybGQuIEJ1dCB1bmRlcnN0YW5kaW5nIGRhdGEgaW4gbnVtYmVycyBpcyBub3QgYWx3YXlzIHF1aWNrIGFuZCBlYXN5LiBWaXN1YWxpemF0aW9ucyBsaWtlIGNoYXJ0cyBhbmQgdHJlZW1hcHMgKG9yIHRyZWVtYXBwaW5nLCB0cmVlIG1hcHMpIGhlbHAgdXMgcHJlc2VudCBkYXRhIGluIGEgd2F5IHRoYXQgaXMgcXVpY2sgYW5kIGVhc3kgdG8gZGlnZXN0Lg0KDQpUcmVlbWFwcyBkaXNwbGF5IGhpZXJhcmNoaWNhbCAodHJlZS1zdHJ1Y3R1cmVkKSBkYXRhIGFzIGEgc2V0IG9mIG5lc3RlZCByZWN0YW5nbGVzLiBFYWNoIGJyYW5jaCBvZiB0aGUgdHJlZSBpcyBnaXZlbiBhIHJlY3RhbmdsZSwgd2hpY2ggaXMgdGhlbiB0aWxlZCB3aXRoIHNtYWxsZXIgcmVjdGFuZ2xlcyByZXByZXNlbnRpbmcgc3ViLWJyYW5jaGVzLiBBIGxlYWYgbm9kZSdzIHJlY3RhbmdsZSBoYXMgYW4gYXJlYSBwcm9wb3J0aW9uYWwgdG8gYSBzcGVjaWZpZWQgZGltZW5zaW9uIG9mIHRoZSBkYXRhLiBPZnRlbiB0aGUgbGVhZiBub2RlcyBhcmUgY29sb3JlZCB0byBzaG93IGEgc2VwYXJhdGUgZGltZW5zaW9uIG9mIHRoZSBkYXRhLg0KDQpXaGVuIHRoZSBjb2xvciBhbmQgc2l6ZSBkaW1lbnNpb25zIGFyZSBjb3JyZWxhdGVkIGluIHNvbWUgd2F5IHdpdGggdGhlIHRyZWUgc3RydWN0dXJlLCBvbmUgY2FuIG9mdGVuIGVhc2lseSBzZWUgcGF0dGVybnMgdGhhdCB3b3VsZCBiZSBkaWZmaWN1bHQgdG8gc3BvdCBpbiBvdGhlciB3YXlzLCBzdWNoIGFzIHdoZXRoZXIgYSBjZXJ0YWluIGNvbG9yIGlzIHBhcnRpY3VsYXJseSByZWxldmFudC4gQSBzZWNvbmQgYWR2YW50YWdlIG9mIHRyZWVtYXBzIGlzIHRoYXQsIGJ5IGNvbnN0cnVjdGlvbiwgdGhleSBtYWtlIGVmZmljaWVudCB1c2Ugb2Ygc3BhY2UuIEFzIGEgcmVzdWx0LCB0aGV5IGNhbiBsZWdpYmx5IGRpc3BsYXkgdGhvdXNhbmRzIG9mIGl0ZW1zIG9uIHRoZSBzY3JlZW4gc2ltdWx0YW5lb3VzbHkuDQoNCiMgSGlzdG9yeSBvZiBUcmVlbWFwcw0KDQpBcmVhLWJhc2VkIHZpc3VhbGl6YXRpb25zIGhhdmUgZXhpc3RlZCBmb3IgZGVjYWRlcy4gRm9yIGV4YW1wbGUsIG1vc2FpYyBwbG90cyAoYWxzbyBrbm93biBhcyBNYXJpbWVra28gZGlhZ3JhbXMpIHVzZSByZWN0YW5ndWxhciB0aWxpbmdzIHRvIHNob3cgam9pbnQgZGlzdHJpYnV0aW9ucyAoaS5lLiwgbW9zdCBjb21tb25seSB0aGV5IGFyZSBlc3NlbnRpYWxseSBzdGFja2VkIGNvbHVtbiBwbG90cyB3aGVyZSB0aGUgY29sdW1ucyBhcmUgb2YgZGlmZmVyZW50IHdpZHRocykuIFRoZSBtYWluIGRpc3Rpbmd1aXNoaW5nIGZlYXR1cmUgb2YgYSB0cmVlbWFwLCBob3dldmVyLCBpcyB0aGUgcmVjdXJzaXZlIGNvbnN0cnVjdGlvbiB0aGF0IGFsbG93cyBpdCB0byBiZSBleHRlbmRlZCB0byBoaWVyYXJjaGljYWwgZGF0YSB3aXRoIGFueSBudW1iZXIgb2YgbGV2ZWxzLiBUaGlzIGlkZWEgd2FzIGludmVudGVkIGJ5IHByb2Zlc3NvciBCZW4gU2huZWlkZXJtYW4gYXQgdGhlIFVuaXZlcnNpdHkgb2YgTWFyeWxhbmQgSHVtYW4g4oCTIENvbXB1dGVyIEludGVyYWN0aW9uIExhYiBpbiB0aGUgZWFybHkgMTk5MHMuIFtTaG5laWRlcm1hbl0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvQmVuX1NobmVpZGVybWFuKSBhbmQgaGlzIGNvbGxhYm9yYXRvcnMgdGhlbiBkZWVwZW5lZCB0aGUgaWRlYSBieSBpbnRyb2R1Y2luZyBhIHZhcmlldHkgb2YgaW50ZXJhY3RpdmUgdGVjaG5pcXVlcyBmb3IgZmlsdGVyaW5nIGFuZCBhZGp1c3RpbmcgdHJlZW1hcHMuDQoNClRoZXNlIGVhcmx5IHRyZWVtYXBzIGFsbCB1c2VkIHRoZSBzaW1wbGUgInNsaWNlLWFuZC1kaWNlIiB0aWxpbmcgYWxnb3JpdGhtLiBEZXNwaXRlIG1hbnkgZGVzaXJhYmxlIHByb3BlcnRpZXMgKGl0IGlzIHN0YWJsZSwgcHJlc2VydmVzIG9yZGVyaW5nLCBhbmQgaXMgZWFzeSB0byBpbXBsZW1lbnQpLCB0aGUgc2xpY2UtYW5kLWRpY2UgbWV0aG9kIG9mdGVuIHByb2R1Y2VzIHRpbGluZ3Mgd2l0aCBtYW55IGxvbmcsIHNraW5ueSByZWN0YW5nbGVzLiBJbiAxOTk0IFtNb3VudGF6IEhhc2NvZXRdKGh0dHBzOi8vZGwuYWNtLm9yZy9wcm9maWxlLzgxMTAwMzAwNTI5KSBhbmQgW01pY2hlbCBCZWF1ZG91aW4tTGFmb25dKGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL01pY2hlbF9CZWF1ZG91aW4tTGFmb24pIGludmVudGVkIGEgInNxdWFyaWZ5aW5nIiBhbGdvcml0aG0sIGxhdGVyIHBvcHVsYXJpemVkIGJ5IFtKYXJrZSB2YW4gV2lqa10oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvSmFja192YW5fV2lqayksIHRoYXQgY3JlYXRlZCB0aWxpbmdzIHdob3NlIHJlY3RhbmdsZXMgd2VyZSBjbG9zZXIgdG8gc3F1YXJlLiBJbiAxOTk5IFtNYXJ0aW4gV2F0dGVuYmVyZ10oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTWFydGluX00uX1dhdHRlbmJlcmcpIHVzZWQgYSB2YXJpYXRpb24gb2YgdGhlICJzcXVhcmlmeWluZyIgYWxnb3JpdGhtIHRoYXQgaGUgY2FsbGVkICJwaXZvdCBhbmQgc2xpY2UiIHRvIGNyZWF0ZSB0aGUgZmlyc3QgV2ViLWJhc2VkIHRyZWVtYXAsIHRoZSBTbWFydE1vbmV5IE1hcCBvZiB0aGUgTWFya2V0LCB3aGljaCBkaXNwbGF5ZWQgZGF0YSBvbiBodW5kcmVkcyBvZiBjb21wYW5pZXMgaW4gdGhlIFUuUy4gc3RvY2sgbWFya2V0LiBGb2xsb3dpbmcgaXRzIGxhdW5jaCwgdHJlZW1hcHMgZW5qb3llZCBhIHN1cmdlIG9mIGludGVyZXN0LCBlc3BlY2lhbGx5IGluIGZpbmFuY2lhbCBjb250ZXh0cy4NCg0KQSB0aGlyZCB3YXZlIG9mIHRyZWVtYXAgaW5ub3ZhdGlvbiBjYW1lIGFyb3VuZCAyMDA0LCBhZnRlciBNYXJjb3MgV2Vza2FtcCBjcmVhdGVkIHRoZSBOZXdzbWFwLCBhIHRyZWVtYXAgdGhhdCBkaXNwbGF5ZWQgbmV3cyBoZWFkbGluZXMuIFRoaXMgZXhhbXBsZSBvZiBhIG5vbi1hbmFseXRpY2FsIHRyZWVtYXAgaW5zcGlyZWQgbWFueSBpbWl0YXRvcnMsIGFuZCBpbnRyb2R1Y2VkIHRyZWVtYXBzIHRvIGEgbmV3LCBicm9hZCBhdWRpZW5jZS5bY2l0YXRpb24gbmVlZGVkXSBJbiByZWNlbnQgeWVhcnMsIHRyZWVtYXBzIGhhdmUgbWFkZSB0aGVpciB3YXkgaW50byB0aGUgbWFpbnN0cmVhbSBtZWRpYSwgaW5jbHVkaW5nIHVzYWdlIGJ5IHRoZSBOZXcgWW9yayBUaW1lcy4gVGhlIFRyZWVtYXAgQXJ0IFByb2plY3QgcHJvZHVjZWQgMTIgZnJhbWVkIGltYWdlcyBmb3IgdGhlIE5hdGlvbmFsIEFjYWRlbWllcyAoVW5pdGVkIFN0YXRlcyksIHNob3duIHRoZSBFdmVyeSBBbGdvUmlUaG0gaGFzIEFSVCBpbiBJdCBleGhpYml0IGluIFdhc2hpbmd0b24sIERDIGFuZCBhbm90aGVyIHNldCBmb3IgdGhlIGNvbGxlY3Rpb24gb2YgTXVzZXVtIG9mIE1vZGVybiBBcnQgaW4gTmV3IFlvcmsuDQoNCg0KIyBUaWxpbmcgQWxnb3JpdGhtcyBmb3IgVHJlZW1hcHMNCg0KVG8gY3JlYXRlIGEgdHJlZW1hcCwgb25lIG11c3QgZGVmaW5lIGEgdGlsaW5nIGFsZ29yaXRobSwgdGhhdCBpcywgYSB3YXkgdG8gZGl2aWRlIGEgcmVnaW9uIGludG8gc3ViLXJlZ2lvbnMgb2Ygc3BlY2lmaWVkIGFyZWFzLiBJZGVhbGx5LCBhIHRyZWVtYXAgYWxnb3JpdGhtIHdvdWxkIGNyZWF0ZSByZWdpb25zIHRoYXQgc2F0aXNmeSB0aGUgZm9sbG93aW5nIGNyaXRlcmlhOg0KDQoxLiBBIHNtYWxsIGFzcGVjdCByYXRpb+KAlGlkZWFsbHkgY2xvc2UgdG8gb25lLiBSZWdpb25zIHdpdGggYSBzbWFsbCBhc3BlY3QgcmF0aW8gKGkuZS4sIGZhdCBvYmplY3RzKSBhcmUgZWFzaWVyIHRvIHBlcmNlaXZlLg0KDQoyLiBQcmVzZXJ2ZSBzb21lIHNlbnNlIG9mIHRoZSBvcmRlcmluZyBpbiB0aGUgaW5wdXQgZGF0YSAob3JkZXJlZCkuDQoNCjMuIENoYW5nZSB0byByZWZsZWN0IGNoYW5nZXMgaW4gdGhlIHVuZGVybHlpbmcgZGF0YSAoaGlnaCBzdGFiaWxpdHkpLg0KDQpUaGVzZSBwcm9wZXJ0aWVzIGhhdmUgYW4gaW52ZXJzZSByZWxhdGlvbnNoaXAuIEFzIHRoZSBhc3BlY3QgcmF0aW8gaXMgb3B0aW1pemVkLCB0aGUgb3JkZXIgb2YgcGxhY2VtZW50IGJlY29tZXMgbGVzcyBwcmVkaWN0YWJsZS4gQXMgdGhlIG9yZGVyIGJlY29tZXMgbW9yZSBzdGFibGUsIHRoZSBhc3BlY3QgcmF0aW8gaXMgZGVncmFkZWQuDQoNCiMgQWR2YW50YWdlcyBvZiBUcmVlbWFwcw0KDQpIZXJlIGFyZSBzb21lIGFkdmFudGFnZXMgb2YgdHJlZSBtYXBzIG92ZXIgYmFyIChvciBwaWUpIGNoYXJ0czoNCg0KKipFZmZpY2llbnQgU3BhY2UgVXRpbGl6YXRpb24qKi4gVHJlZW1hcHMgYXJlIGV4Y2VsbGVudCBmb3IgZGlzcGxheWluZyBoaWVyYXJjaGljYWwgKHRyZWUtc3RydWN0dXJlZCkgZGF0YSBhbmQgZm9yIGVmZmljaWVudGx5IHVzaW5nIHNwYWNlLiBVbmxpa2UgYmFyIG9yIHBpZSBjaGFydHMgdGhhdCBtYXkgcmVxdWlyZSBtb3JlIHNwYWNlIHRvIGRpc3BsYXkgbWFueSBpdGVtcyBkaXN0aW5jdGx5LCB0cmVlIG1hcHMgY2FuIHNob3cgaHVuZHJlZHMgb3IgZXZlbiB0aG91c2FuZHMgb2YgaXRlbXMgaW4gYSBjb21wYWN0IHNwYWNlLg0KDQoqKkVmZmVjdGl2ZSBmb3IgTGFyZ2UgRGF0YSBTZXRzKiouIFRyZWUgbWFwcyBjYW4gaGFuZGxlIGxhcmdlIGRhdGFzZXRzIG11Y2ggYmV0dGVyIHRoYW4gcGllIGNoYXJ0cyBhbmQsIHRvIGEgY2VydGFpbiBleHRlbnQsIGJhciBjaGFydHMuIFRoZXkgY2FuIGRpc3BsYXkgYSB2YXN0IG51bWJlciBvZiBpdGVtcyBhdCBvbmNlLCBtYWtpbmcgaXQgZWFzaWVyIHRvIGNvbXBhcmUgZGlmZmVyZW50IHNlZ21lbnRzIHdpdGhvdXQgZmxpcHBpbmcgdGhyb3VnaCBtdWx0aXBsZSBjaGFydHMuDQoNCioqSGllcmFyY2hpY2FsIFJlcHJlc2VudGF0aW9uKiouIFRyZWUgbWFwcyBjYW4gc2hvdyBwYXJ0cyBvZiBhIHdob2xlIGFuZCBob3cgdGhvc2UgcGFydHMgYXJlIHN1YmRpdmlkZWQgaW50byBzbWFsbGVyIHBhcnRzLCB3aGljaCBpcyBzb21ldGhpbmcgcGllIGNoYXJ0cyBjYW5ub3QgZG8gYW5kIGJhciBjaGFydHMgc3RydWdnbGUgd2l0aC4gVGhpcyBtYWtlcyB0cmVlIG1hcHMgaWRlYWwgZm9yIHZpc3VhbGl6aW5nIG5lc3RlZCBkYXRhIGluIGEgd2F5IHRoYXQgaW1tZWRpYXRlbHkgcmV2ZWFscyB0aGUgc3RydWN0dXJlIG9mIHRoZSBkYXRhLg0KDQoqKkNvbG9yIENvZGluZyBhbmQgU2l6ZSBEaW1lbnNpb25zKiouIFRyZWUgbWFwcyB1c2UgYm90aCBzaXplIGFuZCBjb2xvciB0byByZXByZXNlbnQgZGlmZmVyZW50IGRpbWVuc2lvbnMgb2YgZGF0YSwgb2ZmZXJpbmcgYSBtdWx0aWZhY2V0ZWQgdmlldyBvZiB0aGUgZGF0YXNldC4gRm9yIGV4YW1wbGUsIHRoZSBzaXplIG9mIGVhY2ggYm94IGNhbiByZXByZXNlbnQgYSBxdWFudGl0eSwgd2hpbGUgdGhlIGNvbG9yIGluZGljYXRlcyBhIGNhdGVnb3J5IG9yIG1ldHJpYywgcHJvdmlkaW5nIGEgZGVuc2UgYW5kIHJpY2ggaW5mb3JtYXRpb25hbCBzdW1tYXJ5IGF0IGEgZ2xhbmNlLg0KDQoqKkJldHRlciBmb3IgQ29tcGFyaW5nIFByb3BvcnRpb25zKiouIFdoaWxlIHBpZSBjaGFydHMgY2FuIHNob3cgcHJvcG9ydGlvbnMsIHRoZXkgY2FuIGJlIG1pc2xlYWRpbmcgb3IgaGFyZCB0byBpbnRlcnByZXQgd2hlbiB0aGVyZSBhcmUgbWFueSBzbWFsbCBzbGljZXMuIFRyZWUgbWFwcyBjYW4gbW9yZSBhY2N1cmF0ZWx5IHJlcHJlc2VudCBwcm9wb3J0aW9ucywgZXNwZWNpYWxseSBmb3IgY2F0ZWdvcmllcyB0aGF0IG1ha2UgdXAgYSBzbWFsbGVyIHBlcmNlbnRhZ2Ugb2YgdGhlIHdob2xlLCBiZWNhdXNlIHRoZSBzaXplIG9mIGVhY2ggcmVjdGFuZ2xlIGNhbiBiZSBtb3JlIHByZWNpc2VseSBjb21wYXJlZCB0aGFuIHRoZSBhbmdsZXMgb3IgYXJlYXMgb2YgcGllIHNsaWNlcy4NCg0KKipSZWFkYWJpbGl0eSBvZiBTbWFsbCBDYXRlZ29yaWVzKiouIEluIGJhciBhbmQgcGllIGNoYXJ0cywgc21hbGwgY2F0ZWdvcmllcyBjYW4gYmVjb21lIGluZGlzdGluZ3Vpc2hhYmxlIG9yIHJlcXVpcmUgYWRkaXRpb25hbCBsYWJlbGluZyB0aGF0IGNsdXR0ZXJzIHRoZSBjaGFydC4gSW4gYSB0cmVlIG1hcCwgZXZlbiBzbWFsbCBjYXRlZ29yaWVzIGNhbiBiZSBtb3JlIGVhc2lseSBpZGVudGlmaWVkIGFuZCBhbmFseXplZCB3aXRob3V0IG92ZXJ3aGVsbWluZyB0aGUgdmlzdWFsIHByZXNlbnRhdGlvbi4NCg0KKipJbnR1aXRpdmUgZm9yIENlcnRhaW4gVHlwZXMgb2YgRGF0YSoqLiBGb3IgZGF0YXNldHMgd2hlcmUgdGhlIGhpZXJhcmNoaWNhbCBzdHJ1Y3R1cmUgb3IgY2F0ZWdvcml6YXRpb24gaXMgc2lnbmlmaWNhbnQsIHRyZWUgbWFwcyBwcm92aWRlIGFuIGludHVpdGl2ZSBhbmQgaW1tZWRpYXRlIHVuZGVyc3RhbmRpbmcgb2YgdGhlIGRhdGEncyBzdHJ1Y3R1cmUgYW5kIGNvbXBvc2l0aW9uLiBUaGlzIG1ha2VzIHRoZW0gZXNwZWNpYWxseSB1c2VmdWwgZm9yIGNlcnRhaW4gdHlwZXMgb2YgZmluYW5jaWFsLCBvcmdhbml6YXRpb25hbCwgb3IgY2F0ZWdvcmljYWwgZGF0YS4NCg0KV2hpbGUgdHJlZSBtYXBzIGhhdmUgdGhlc2UgYWR2YW50YWdlcywgdGhlIGNob2ljZSBiZXR3ZWVuIHVzaW5nIGEgdHJlZSBtYXAgb3IgYmFyIGNoYXJ0IHNob3VsZCBiZSBiYXNlZCBvbiB0aGUgc3BlY2lmaWMgZ29hbHMgb2YgdGhlIGRhdGEgdmlzdWFsaXphdGlvbiwgdGhlIG5hdHVyZSBvZiB0aGUgZGF0YSwgYW5kIHRoZSBhdWRpZW5jZSdzIGZhbWlsaWFyaXR5IHdpdGggdGhlc2UgdG9vbHMuIEVhY2ggdHlwZSBvZiBjaGFydCBoYXMgaXRzIHBsYWNlIGluIGRhdGEgcHJlc2VudGF0aW9uLCBhbmQgdW5kZXJzdGFuZGluZyB0aGUgc3RyZW5ndGhzIG9mIGVhY2ggY2FuIGhlbHAgaW4gc2VsZWN0aW5nIHRoZSBtb3N0IGVmZmVjdGl2ZSB3YXkgdG8gY29tbXVuaWNhdGUgZGF0YSBpbnNpZ2h0cy4NCg0KIyBBIFJlYWwtd29ybGQgQXBwbGljYXRpb24NCg0KQmVsb3cgYXJlIHRoZSBSIGNvZGVzIHRvIGNyZWF0ZSB0aGUgVHJlZW1hcCBhcyBzZWVuIGFib3ZlOiANCg0KYGBge3J9DQoNCg0KIy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tDQojICBTdGFnZSAwOiBMb2FkIFIgcGFja2FnZXMgYW5kIHNlbGVjdCBmb250DQojLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0NCg0KIyBMb2FkIFIgcGFja2FnZXM6IA0KDQpsaWJyYXJ5KHJ2ZXN0KQ0KbGlicmFyeShnZ3Bsb3QyKQ0KbGlicmFyeShkcGx5cikNCmxpYnJhcnkoc3RyaW5ncikNCmxpYnJhcnkoRGVzY1Rvb2xzKSAjIEZvciBjYXBpdGFsaXppbmcgdGhlIGZpcnN0IGxldHRlciBvZiBhIHN0cmluZy4gDQpsaWJyYXJ5KHRyZWVtYXBpZnkpICMgRm9yIHBsb3RpbmcgdHJlZSBtYXAgY2hhcnQuIA0KbGlicmFyeSh2aXJpZGlzKSAjIEZvciB1c2luZyBWaXJpZGlzIENvbG9yIFNjYWxlcy4gDQpsaWJyYXJ5KHNob3d0ZXh0KSAjIEZvciB1c2luZyBHb29nbGUgZm9udHMuIA0KDQojIFNlbGVjdCBPcGVuIFNhbnMgZm9udDogDQoNCm15X2ZvbnQgPC0gIk9wZW4gU2FucyINCg0KZm9udF9hZGRfZ29vZ2xlKG5hbWUgPSBteV9mb250LCBmYW1pbHkgPSBteV9mb250KQ0KDQpzaG93dGV4dF9hdXRvKCkNCg0KIyBFeHRyYWN0IEdEUCBkYXRhIGJ5IGNvdW50cnk6IA0KDQp1cmwgPC0gImh0dHBzOi8vd3d3Lndvcmxkb21ldGVycy5pbmZvL2dkcC9nZHAtYnktY291bnRyeS8iDQoNCnVybCAlPiUgDQogIHJlYWRfaHRtbCgpICU+JSANCiAgaHRtbF9ub2Rlcyh4cGF0aCA9ICcvLypbQGlkPSJleGFtcGxlMiJdJykgJT4lIA0KICBodG1sX3RhYmxlKCkgJT4lIA0KICAuW1sxXV0gLT4gZ2RwRGF0YQ0KDQojLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQ0KIyBTdGFnZSAxOiBEYXRhIHByby1wcm9jZXNzaW5nDQojLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQ0KDQpnZHBEYXRhICU+JSANCiAgc2VsZWN0KDIsIDMsIDQpICU+JSANCiAgcmVuYW1lKGdkcCA9IGBHRFAgKG5vbWluYWwsIDIwMjIpYCwgZ2RwQWJiID0gYEdEUCAoYWJicmV2LilgKSAtPiBnZHBEYXRhDQoNCmdkcERhdGEgJT4lIA0KICBtdXRhdGUoZ2RwID0gc3RyX3JlcGxhY2VfYWxsKGdkcCwgcGF0dGVybiA9ICJcXCR8XFwsIiwgcmVwbGFjZW1lbnQgPSAiIiksIA0KICAgICAgICAgZ2RwQWJiID0gc3RyX3JlcGxhY2VfYWxsKGdkcEFiYiwgcGF0dGVybiA9ICJcXCQiLCByZXBsYWNlbWVudCA9ICIiKSkgJT4lIA0KICBtdXRhdGUodW5pdCA9IHN0cl9yZXBsYWNlX2FsbChnZHBBYmIsIHBhdHRlcm4gPSAiWzAtOV18XFwufCAiLCByZXBsYWNlbWVudCA9ICIiKSkgJT4lIA0KICBtdXRhdGUodW5pdCA9IHN0cl9zdWIodW5pdCwgc3RhcnQgPSAxLCBlbmQgPSAzKSkgJT4lIA0KICBtdXRhdGUodW5pdCA9IFN0ckNhcCh1bml0KSkgJT4lIA0KICBtdXRhdGUoZ2RwQWJiID0gc3RyX3JlcGxhY2VfYWxsKGdkcEFiYiwgcGF0dGVybiA9ICJbYS16XXwgIiwgcmVwbGFjZW1lbnQgPSAiIikpICU+JSANCiAgbXV0YXRlKGdkcCA9IGFzLm51bWVyaWMoZ2RwKSkgLT4gZ2RwRGF0YQ0KDQpnZHBEYXRhICU+JSANCiAgbXV0YXRlKHNoYXJlR2RwID0gMTAwKmdkcCAvIHN1bShnZHApKSAlPiUgDQogIG11dGF0ZShzaGFyZUdkcCA9IHJvdW5kKHNoYXJlR2RwLCAxKSkgJT4lIA0KICBtdXRhdGUoc2hhcmVHZHAgPSBhcy5jaGFyYWN0ZXIoc2hhcmVHZHApKSAlPiUgDQogIG11dGF0ZShzaGFyZUdkcCA9IGNhc2Vfd2hlbighc3RyX2RldGVjdChzaGFyZUdkcCwgIlxcLiIpIH4gc3RyX2Moc2hhcmVHZHAsICIuMCIpLCBUUlVFIH4gc2hhcmVHZHApKSAlPiUgDQogIG11dGF0ZShzaGFyZUdkcCA9IHN0cl9jKHNoYXJlR2RwLCAiJSIpKSAtPiBnZHBEYXRhDQoNCmdkcERhdGEgJT4lIA0KICBtdXRhdGUobGFiZWwgPSBzdHJfYyhDb3VudHJ5LCAiXG4iLCBnZHBBYmIsICIgIiwgdW5pdCwgIiAoIiwgc2hhcmVHZHAsICIpIikpIC0+IGdkcERhdGENCg0KDQojLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQ0KIyAgICBTdGFnZSAyOiBQbG90IFRyZWUgTWFwIA0KIy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0NCg0KZ2RwRGF0YSAlPiUgDQogIGdncGxvdChhZXMoYXJlYSA9IGdkcCwgZmlsbCA9IGdkcCwgbGFiZWwgPSBsYWJlbCkpICsgDQogIGdlb21fdHJlZW1hcChzaG93LmxlZ2VuZCA9IEZBTFNFKSArDQogIGdlb21fdHJlZW1hcF90ZXh0KGNvbG91ciA9ICJ3aGl0ZSIsDQogICAgICAgICAgICAgICAgICAgIHBsYWNlID0gImNlbnRyZSIsDQogICAgICAgICAgICAgICAgICAgIGZhbWlseSA9IG15X2ZvbnQsIA0KICAgICAgICAgICAgICAgICAgICBzaXplID0gMTMpICsgDQogIHNjYWxlX2ZpbGxfdmlyaWRpcyhvcHRpb24gPSAiSCIsIGRpcmVjdGlvbiA9IC0xKSArIA0KICB0aGVtZShsZWdlbmQudGl0bGUgPSBlbGVtZW50X2JsYW5rKCkpICsgDQogIGxhYnModGl0bGUgPSAiTm9taW5hbCBHRFAgUmFua2VkIGJ5IENvdW50cnkgMjAyMiIsIA0KICAgICAgIHN1YnRpdGxlID0gIkdyb3NzIERvbWVzdGljIFByb2R1Y3QgKEdEUCkgaXMgdGhlIG1vbmV0YXJ5IG1hcmtldCB2YWx1ZSBvZiBhbGwgZmluYWwgZ29vZHMgYW5kIHNlcnZpY2VzIG1hZGUgd2l0aGluIGEgY291bnRyeSBkdXJpbmcgYSBzcGVjaWZpYyBwZXJpb2QuXG5BcyBvZiAyMDIyLCB0aGUgVW5pdGVkIFN0YXRlcyBhbmQgQ2hpbmEgd291bGQgb2NjdXB5IHRoZSBmaXJzdCB0d28gcGxhY2VzLiBUaGUgVVMgaXMgYWhlYWQgb2YgQ2hpbmEgYnkgJDcgdHJpbGxpb24gaW4gMjAyMiBidXQgdGhlIG1hcmdpblxuaXMgY29taW5nIGRvd24gaW4gbm9taW5hbCByYW5raW5nIGFzIENoaW5hJ3MgR0RQIGdyb3d0aCByYXRlIG9mIDIwMjMgKDUuMDElKSBpcyBoaWdoZXIgdGhhbiB0aGUgVVMncyAyLjA5JS4iLCANCiAgICAgICBjYXB0aW9uID0gIlNvdXJjZTogaHR0cHM6Ly93d3cud29ybGRvbWV0ZXJzLmluZm8vZ2RwL2dkcC1ieS1jb3VudHJ5LyIpICsgDQogIHRoZW1lKHBsb3QubWFyZ2luID0gdW5pdChjKDAuNSwgMC41LCAwLjUsIDAuNSksICJjbSIpKSArIA0KICB0aGVtZSh0ZXh0ID0gZWxlbWVudF90ZXh0KGZhbWlseSA9IG15X2ZvbnQpKSArICANCiAgdGhlbWUocGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChzaXplID0gMTgsIGNvbG9yID0gImdyZXkxMCIpLCANCiAgICAgICAgcGxvdC5zdWJ0aXRsZSA9IGVsZW1lbnRfdGV4dChzaXplID0gMTAsIGNvbG9yID0gImdyZXkzMCIpLCANCiAgICAgICAgcGxvdC5jYXB0aW9uID0gZWxlbWVudF90ZXh0KGNvbG9yID0gImdyZXkzMCIsIHNpemUgPSA4KSkgDQoNCmBgYA0KDQoNCg0KIyBSZWZlcmVuY2VzDQoNCjEuIFtUcmVlIHZpc3VhbGl6YXRpb24gd2l0aCB0cmVlLW1hcHM6IDItZCBzcGFjZS1maWxsaW5nIGFwcHJvYWNoXShodHRwczovL2RsLmFjbS5vcmcvZG9pLzEwLjExNDUvMTAyMzc3LjExNTc2OCkNCjIuIFtUcmVlbWFwcyBmb3Igc3BhY2UtY29uc3RyYWluZWQgdmlzdWFsaXphdGlvbiBvZiBoaWVyYXJjaGllczogSW5jbHVkaW5nIHRoZSBIaXN0b3J5IG9mIFRyZWVtYXAgUmVzZWFyY2ggYXQgdGhlIFVuaXZlcnNpdHkgb2YgTWFyeWxhbmRdKGh0dHBzOi8vd3d3LmNzLnVtZC5lZHUvaGNpbC90cmVlbWFwLWhpc3RvcnkvaW5kZXguc2h0bWwpDQozLiBbVGhlIGhlYWx0aCBvZiB0aGUgY2FyLCB2YW4sIFNVViwgYW5kIHRydWNrIG1hcmtldCwgVGhlIE5ldyBZb3JrIFRpbWVzXShodHRwczovL2FyY2hpdmUubnl0aW1lcy5jb20vd3d3Lm55dGltZXMuY29tL2ltYWdlcGFnZXMvMjAwNy8wMi8yNS9idXNpbmVzcy8yMDA3MDIyNV9DSFJZU0xFUl9HUkFQSElDLmh0bWwpDQo0LiBbVHJlZW1hcCBBcnRdKGh0dHBzOi8vdHJlZW1hcGFydC53b3JkcHJlc3MuY29tLykNCjUuIFtQZXJjZXB0dWFsIEd1aWRlbGluZXMgZm9yIENyZWF0aW5nIFJlY3Rhbmd1bGFyIFRyZWVtYXBzXShodHRwczovL2hvbWVzLmNzLndhc2hpbmd0b24uZWR1L35qaGVlci9maWxlcy90cmVlbWFwcy5wZGYpDQo2LiBbT3JkZXJlZCBUcmVlbWFwIExheW91dHNdKGh0dHBzOi8vd3d3LmNzLnVtZC5lZHUvfmJlbi9wYXBlcnMvU2huZWlkZXJtYW4yMDAxT3JkZXJlZC5wZGYpDQo3LiBbVmlzdWFsaXppbmcgY2hhbmdlcyBvZiBoaWVyYXJjaGljYWwgZGF0YSB1c2luZyB0cmVlbWFwc10oaHR0cHM6Ly93ZWIuY3NlLm9oaW8tc3RhdGUuZWR1L35zaGVuLjk0L1Jlc2VhcmNoL0hpZ2hsaWdodF9QYXBlcnMvSDZfZmlsZXMvVHUyMDA3LnBkZikNCjguIFtWaXN1YWxpemluZyBCdXNpbmVzcyBEYXRhIHdpdGggR2VuZXJhbGl6ZWQgVHJlZW1hcHNdKGh0dHBzOi8vd2ViLmFyY2hpdmUub3JnL3dlYi8yMDExMDcyNDE2MDU0Ny9odHRwOi8vd3d3Lm1hZ25hdmlldy5ubC9kb2N1bWVudHMvVmlzdWFsaXppbmdfQnVzaW5lc3NfRGF0YV93aXRoX0dlbmVyYWxpemVkX1RyZWVtYXBzLnBkZikNCg0K