XSLT 2.0 and XPath 2.0 Programmer's Reference, 4th Edition (734 page)

I've taken a bit of a short cut here. There's no guarantee that a GEDCOM file will contain an individual with this identifier. A more carefully constructed application would display the first individual in the file, or an index of people.

Jaqueline Lee Bouvier

 xmlns:xsl=“http://www.w3.org/1999/XSL/Transform”

 version=“1.0”

>

    ‘

          select=“concat(‘Javascript:refresh(‘, $apos, ../@Id, $apos, ‘)’)”/>

Summary

I hope this little excursion into the strange world of genealogical data models has given you some flavor of the power of XSLT as a manipulation and reporting tool for complex structured data. We've covered a lot of ground:

• Using XSLT to transform structured data that wasn't originally in XML format
  
• How to navigate your way around complex linked data within an XML document
  
• Several different ways of generating an interactive view of a large XML data set:
  
  • Generating lots of static HTML pages in one go at publication time
    
  • Generating HTML pages dynamically using either a Java servlet or a Microsoft ASP.NET page
    
  • Generating HTML incrementally within the browser
    

The worked example in the next chapter will venture into even stranger territory, using XSLT to solve a chess problem. While genealogy has demonstrated how XSLT can be used to process complex data, the chess example will show something of the computational power of the language.

Chapter 20

Case Study: Knight's Tour

This chapter contains the third (and last) of the XSLT case studies. It shows how XSLT can be used to calculate a knight's tour of the chessboard, in which the knight visits every square without ever landing on the same square twice.

Readers of previous editions of this book have reacted differently to this case study. Some have suggested that I should be less frivolous, and stick to examples that involve the processing of invoices and purchase orders, and the formatting of product catalogs. Others have welcomed the example as light relief from the comparatively boring programming tasks they are asked to do in their day job. A third group has told me that this example is absolutely typical of the challenges they face in building real Web sites. The Web, after all, does not exist only (or even primarily) to oil the wheels of big business. It is also there to provide entertainment.

Whatever your feelings about the choice of problem, I hope that by showing that it can be done I will convince you that XSLT has the computational power and flexibility to tackle any XML formatting and transformation challenge, and that as you study it, you will discover ideas that you can use a wide range of tasks that are more typical of your own programming assignments.

The Problem

The purpose of the stylesheet is to produce a knight's tour of the chessboard, in which each square is visited exactly once, as shown in the illustration overleaf. A knight can move to any square that is at the opposite corner of a 3 × 2 rectangle (see
Figure 20-1
).

Figure 20-1

The only input to the stylesheet is an indication of the starting square: in modern chess notation, the columns are denoted by the letters a–h starting from the left, and the rows by the numbers 1–8, starting at the bottom. We'll supply the starting square as a parameter to the stylesheet. The stylesheet doesn't need to get anything from the source document. In fact, with XSLT 2.0, there doesn't need to be a source document: the entry point to the stylesheet can be specified as a named template.

We'll build up the stylesheet piece by piece: you can find the complete stylesheet,
tour.xsl
, on the Wrox Web site.

The Algorithm

The strategy for getting the knight round the board is based on the observation that if a square hasn't been visited yet, and if it isn't the knight's final destination, then it had better have at least two unvisited squares that are a knight's move away from it, because there needs to be a way of getting in and another way of getting out. That means that if we can get to a square that's only got one exit left, we'd better go there now or we never will.

This suggests an approach where at each move, we look at all the squares we can jump to next, and choose the one that has fewest possible exits. It turns out that this strategy works, and always gets the knight round the board.

It's possible that this could lead the knight into a blind alley, especially in the case where two of the possible moves look equally good. In this case, the knight might need to retrace its steps and try a different route. In the version of the stylesheet that I published in the previous edition of this book, I included code to do this backtracking, but made the assertion that it was never actually used (though I couldn't prove why). Recently, one of my readers reported that if the knight starts on square f8, it does indeed take a wrong turning at move 58, and needs to retrace its steps. Moreover, this appears to be the only case where this happens.

The place I usually start design is with the data structures. Here the main data structure we need is the board itself. We need to know which squares the knight has visited, and so that we can print out the board at the end, we need to know the sequence in which they were visited. In XSLT 2.0 the obvious choice is to represent the board as a sequence of 64 integers: the value will be zero for a square that has not been visited, or a value in the range 1 to 64 representing the number of the move on which the knight arrived at this square.

In a conventional program this data structure would probably be held in a global variable and updated every time the knight moves. We can't do this in XSLT, because variables can't be updated. Instead, every time a function is called, it passes the current state of the board as a parameter, and when the knight moves, a new copy of the board is created, that differs from the previous one only in the details of one square.

It doesn't really matter which way the squares are numbered, but for the sake of convention we'll number them as shown in
Figure 20-2
.

Figure 20-2

So if we number the rows 0–7, and the columns 0–7, the square number is given as
row * 8 + column
, and then we add one if indexing into the sequence representing the board.

Having decided on the principal data structure, we can decide the broad structure of the program. There are three stages:

Calculating the tour involves 63 steps, each one taking the form:

We're ready to start coding. The tricky bit, as you've probably already guessed, is that all the loops have to be coded using recursion. That takes a bit of getting used to at first, but it quickly becomes a habit.

The Initial Template

Let's start with the framework of top-level elements:

All I'm doing here is declaring the global parameter,
start
, which defines the starting square, and deriving from it two global variables: a row number and column number.

Some observations:

• The parameter
  start
  has the default value
  a1
  . As this is a string-value, it needs to be in quotes; these quotes are additional to the quotes that surround the XML attribute. If I had written
  select=“a1”
  , the default value would be the string-value of the
  
  element child of the document root.
  
• The simplest way of converting the alphabetic column identifier (a–h) into a number (0–7) is to use the
  translate()
  function, which is described in Chapter 13.
  
• The row number is subtracted from 8 so that the lowest-numbered row is at the top, and so that row numbers start from zero. Numbering from zero makes it easier to convert between row and column numbers and a number for each square on the board in the range 0–63.
  
• I haven't yet checked that the supplied start square is valid. I'll do that in the initial template.