Drawing of a constrained tree by means of XSLT – how to use XSLT and XPath rationally

One of the things I like about XML and technologies connected with it is the opportunity to keep learning something new. I have been using XML for more than three years and nearly every week I discover something new to do by its means or even a simpler way to do something which I’ve already learnt

Recently one of such discoveries happened in connection with drawing of hierarchies of ‘constrained tree’ type. Constrained tree is a tree in which nodes are connected with their children and parents with lines as it is frequently shown in the file managers and titles (see example on the picture #1). Application over which I’m working at the moment uses such type of displaying for different purposes which makes it realization for different data type more complicated. However all the hierarchy types are available like DOM-trees. This made me think that if I can realize drawing of constrained trees by means of XSLT only, I will be able to get rid of great code number for tree building by replacing it with one XSLT-template which makes our code much easier.

As a result some hundreds of error liable Java code strings (spread over some classes) have been replaced with some dozens of XSL-strings within a single template which increased safety and simplified support and changes entries. In this article I’m going to tell you how it was done.

I’m sure that most of the readers already know that XSL and XSLT are two interconnected standards describing conversion of the same data from XML into some other format demanded. XSL-template is something like instruction for data search within initial XML, their conversion and converted version output. This technology has got many applying variants but probably the mostly spread of them is conversion of XML into HTML which is suitable for human overview.

Another specification which is called XPath is widely used in XSLT. XPath is a functional language for information search within a XML-tree. In XSLT it performs the role of a filter according to the template for search of data which should be converted within a document.

As for me, XPath is the part of XSLT-tools which is the most difficult to understand. One of the sides of XPath which has annoyed me a lot is usage of ‘axes’ to make XSLT-processor ‘run’ over the document in different ‘directions’. The techniques described here are based on three different axes usage and I hope it will be a useful example of axes power for those who haven’t handled them exactly like me.

A tree of four sticks

If you look at Picture #1 attentively, you’ll notice that you need only four figures to draw a tree. Firstly, each element is connected with the tree by a horizontal line going from the center to the right. If an element isn’t the last child of its parent it is connected with the tree by means of a figure which is similar to 90 degrees converted letter ‘T’. The last child is connected to the tree by means of a figure which looks like ‘L’.

If the element is paced in the tree deeper than the first hierarchy level, one of two other will appear from the left of connectors described before, one for each element’s parent. If an ancestor isn’t the last child of its parent a vertical line is drawn which together with other similar lines connects the element with the following one on this level. If the element is the last one by its parent, a blank ‘cross-piece’ picture will be displayed.

For this article I’ve drawn four pictures: tree_tee, tree_corner, tree_bar, and tree_spacer (see Picture #2; they can also be downloaded on address www.sys-con.com/xml/sourcec.cfm). All of them correspond with these descriptions; I’ve just added a dot in the middle of blank separator to see when it is used.

Now, having analyzed the problem we can write an approximate algorithm of a tree drawing:

1) We draw a blank separator for each level from the beginning of a tree up to the parent of the current element if it is the last element of its parent and a vertical line if not.

2) We draw an ‘L’-connector if the current element is the last by its parent and a ‘T’-connector if not.

3) Display the current element’s name.

One of my colleagues expressively called the picture succession which is made up on the 1st and 2nd steps a ‘fence’ what displays the reality well enough – you are building something like a fence which pickets are your pictures; one picket for each level beginning from the root. The very right picture will always be either ‘T’ or ‘L’ connector and pictures situated from the left are either vertical lines or blank separators. We also use the term ‘set transformation’ to designate of what is drawn from the right of the ‘fence’ – in our case it will be simply an element’s name formatted according to the element’s type. Thus we can describe the algorithm like this: “We draw a ‘fence’ for each element within a tree and then transform the element”.

But as it usually occurs all the difficulties are concluded in the details. So let’s examine ways for XSLT realization.

Details

Primary document shown on the Picture #1 is called "book.xml" and you’ll be able to find it in the Listing 1. It’s a very simple document containing title of a book. Following elements are included into the root element of the book – chapters and into them sections are included which may contain other sections. Each element possesses attribute ‘title’ but conversion principles work with far more complicated documents as well.

Style which we apply to XML-document is called "connected_tree.xsl" and it is shown in the Listing 2. And this template is also artificially simplified by using ideas illustrated in it you can do far more complicated transformations.

Strings 1-13 of an XSL-template contain standard headings which follow before any transformation in HTML.

More interesting things begin from the 17th string in which a template for XML-document root element handling is created. We create static HTML within this template. One of such components is integrated CSS in which we set up indentions and boarders for pictures in order to interconnect them without any gaps and also level the text vertically to make it seem natural prolongation of the very right picture.

In the 28th string we put out the title of the book (meaning of attribute ‘title’ of element ‘book’) concluded into tags <b>…</b> in order to mark it in bold. After that we apply suitable templates to its child elements using mode ‘line’. In this and all the rest of the cases of templates applying to the child elements they will be handled in the succession order within a document. Firstly handling of an element will be done then that of its child elements and so on until we get the tree needed.

Modes enable us to handle the same element in different ways depending on the circumstances that, as you will see, is the key to this task’s solution. Mode ‘line’ works with drawing of the whole line including ‘fence’ and set transformation. Other modes – ‘item’ and ‘tree’ – will be examined further.

All the elements are worked through in the ‘line’ mode in a similar way and so we have only one template with ‘line’ mode which handles all elements; it begins in the line 36. Inside of this template we draw completely one horizontal ‘line’ of our tree. We include our output into <div> of corresponding class in order to remove borders and level the text vertically. Inside of <div> two blocks are situated. The first one in the string 38 is called ‘graft’ and it is namely the block which builds a ‘fence’; further we’ll discuss how it occurs. The second one in the string 39 and calls again apply-templates for the current node but this time in the mode ‘item’ not ‘line’ as before. Outside of <div> in the end of the template we call it for children elements by keeping doing the complete being on beat of the tree.

‘Item’ mode is used for the object reflection mentioned before. This occurs in a different way for each elements’ type. In this example for each of the two elements’ types mentioned in this book (‘chapter’ and ‘section’) its own template for the ‘item’ mode is set (strings 46-52). As I’ve already said we simply put out title of objects with different formatting for each of the type.

So we’ve come to the most interesting things. I’ve mentioned before that template ‘graft’ which begins from string 57 builds a ‘fence’ for the calling it element. How does it do this? To realize it you are to start thinking backwards – from the right to the left. So now you are to cross immediately to the string 62 on which we draw a connector connecting the element with the rest of the tree. As we’ve mentioned before it will be either ‘L’-connector in case it is the last child element of its parent or ‘T’-connector. This way the code functions and it’s very important to understand how do we define that the element given is the last child of its parent.

To do this we are to use another XPath-axe. Usually we use axe ‘child’ when working which extracts child nodes of the current node. However there are many other axes beside it which enable moving through the document in various ‘directions’. The first axe to be discussed is ‘following-sibling’ which enables extracting all the child nodes of the same parent that the current element has placed in the document after it. This axe is used within condition in the line 63. If "following-sibling::*" returns non-blank selection, condition will return meaning ‘true’ and we use ‘T’-connector otherwise if the selection is empty we use ‘L’-connector. Axe ‘following-subling’ (and its pair ‘preceding-sibling’) are rather convenient if you need to do something with the rest of the elements of this level.

So we’ve drawn the first element of our ‘fence’. And what about the rest? As you remember we should draw one graphic element for each chapter or unit which are parents for the given one at this it’ll be either a vertical line or a blank picture depending on that if this parent element is followed by other elements on the same level. Half of solution should be obvious from the formulation itself but how should we visit our parents to make a decision?

The answer is simple: by means of another axe – ‘ancestor’. In the string 59 you’ll see that we apply templates in the ‘tree’ mode to the nodes extracted on the axe "ancestor::*". This means “to extract all the ancestors of the current node to generate the rest of the tree as we do it in the last two templates which are marked for usage in the ‘tree’ mode.

The first template in the string 74 simply forbids a picture substitution for the root node (in our case it is ‘book’). We’ve already dealt with this element in the template "/book" before so there is no sense in treating it once more.

The second template uses for choice between a picture with a vertical line and a blank picture logic which is based on usage of axe ‘following-sibling’ which we’ve discussed before.

Traveling in XSLT goes on

That’s all! Now having applied XSLT-sample to initial XML we’ll get a HTML-tree which is shown on Picture #1. There are many ways to do it; I usually use Apache Xalan from the command line for experiments like this. This works like following (of course, if you’ve already downloaded, installed and inserted into CLASSPATH):

Don’t forget that only one of the methods for constrained tree drawing is described here and there are many other ways to adopt it for you, to extend, to improve and to treat somehow. According to my own experience the best way to examine XSLT is to do as many experiments as possible and so I urge you to ‘play’ with code connected_tree.xsl and book.xml and see what you’ll get. Many things in XSLT and XPath may seem to you too complicated and difficult to understand at the beginning but later you’ll find out that in fact these approaches are quite rational. And after that you will be able to share your interesting discoveries with others.

Picture 1

Picture 2

Sources

Listing 1

<?xml version="1.0"?>
<book title="XML For Fun and Profit">
<chapter title="A Day at the Beach with XML">
<section title="XML Surfing">
<section title="The "Cowabunga" entity"/>
<section title="Gremmies and XPath"/>
</section>
<section title="XML Sandcastles">
<section title="How Wet is the Sand?">
<section title="The Seashell Environment"/>
<section title="Getting Kelp"/>
</section>
<section title="The Tide and Long Term Stability Issues"/>
</section>
</chapter>
<chapter title="The XML Circus">
<section title="Lions and Tigers and Parsers!"/>
<section title="The W3C Standards Clown Car">
<section title="Loose and Strict Clown Compliance"/>
</section>
</chapter>
</book> 


Listing 2


<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output 
method="html"
encoding="UTF-8"
indent="yes"
version="1.0"
omit-xml-declaration="yes"
media-type="text/html"
standalone="yes"
/>

<!—Templates for text content generation -->

<xsl:template match="/book">
<html>
<head>
<title>XML Book Outline</title>
<style type="text/css">
body { font-size: smaller }
div, img { border: 0px; margin: 0px; padding: 0px }
div.Node * { vertical-align: middle }
</style>
</head>
<body>
<b><xsl:value-of select="@title"/></b>
<xsl:apply-templates mode="line"/>
</body>
</html>
</xsl:template>

<!—Draw each tree string -->

<xsl:template match="*" mode="line">
<div class="Node">
<xsl:call-template name="graft"/>
<xsl:apply-templates select="." mode="item"/>
</div>
<xsl:apply-templates mode="line"/>
</xsl:template>

<!—Represent different elements’ types -->

<xsl:template match="chapter" mode="item">
<i><xsl:value-of select="@title"/></i>
</xsl:template>

<xsl:template match="section" mode="item">
<xsl:value-of select="@title"/>
</xsl:template>

<!—Templates used for ‘fence’ generation of different connectors -->

<xsl:template name="graft">
<!—Draw connector pictures for all the ancestors -->
<xsl:apply-templates select="ancestor::*" mode="tree"/>

<!—Draw a connector for the current node -->
<xsl:choose>
<xsl:when test="following-sibling::*">
<img src="tree_tee.gif"/>
</xsl:when>
<xsl:otherwise>
<img src="tree_corner.gif"/>
</xsl:otherwise>
</xsl:choose>
</xsl:template>

<!—Forbid connector drawing for the root node -->

<xsl:template match="book" mode="tree"/>

<!—Draw connectors for the rest of the nodes -->

<xsl:template match="*" mode="tree">
<xsl:choose>
<xsl:when test="following-sibling::*">
<img src="tree_bar.gif"/>
</xsl:when>
<xsl:otherwise>
<img src="tree_spacer.gif"/>
</xsl:otherwise>
</xsl:choose>
</xsl:template>

</xsl:stylesheet>