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:

  1. A small aspect ratio—ideally close to one. Regions with a small aspect ratio (i.e., fat objects) are easier to perceive.

  2. Preserve some sense of the ordering in the input data (ordered).

  3. 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