Steven Engelhardt

Victorian novelist Edward George Earl Bulwer-Lytton (1803-1873) opened his 1830 novel Paul Clifford with this infamous sentence:

It was a dark and stormy night; the rain fell in torrents–except at occasional intervals, when it was checked by a violent gust of wind which swept up the streets (for it is in London that our scene lies), rattling along the housetops, and fiercely agitating the scanty flame of the lamps that struggled against the darkness.

To honor this noxious piece of writing, the San Jose State University invented the annual Bulwer-Lytton Fiction Contest in which contestants must “compose the opening sentence to the worst of all possible novels.” Here are some of my favorite entries from the 2006 contest results:

She looked at her hands and saw the desiccated skin hanging in Shar-Pei wrinkles, confetti-like freckles, and those dry, dry cuticles–even her “Fatale Crimson” nail color had faded in the relentless sun to the color of old sirloin–and she vowed if she ever got out of the Sahara alive, she’d never buy polish on sale at Walgreen’s again.

Christin Keck, Kent, OH

The cold, cynical wind molested the auburn tresses of the fair damsel clinging to the steel of the rail trestle, from which vantage point she could see that it was a long way down to where she would land if she fell, which, given the velocity she would attain and the unfriendly pavement leering up at her, added to soft tissue’s low tolerance for sudden impacts, would be a very bad thing.

Pat Hricko, Nicholson, PA

“Send a message back to Command Central on Earth and ask for their advice, which we will be able receive immediately even at this great distance, thanks to the ingenious manipulation of coherent radiation through a Bose-Einstein condensate and the bizarre influence of the Aspect effect, which enables us to impart identical properties to remotely separated photons,” Captain Buzz told the feathered Vjorkog at the comms desk, “and tell them our life-pod is going to explode in eight seconds.”

Christopher Backeberg, KwaZulu-Natal, South Africa

As Johann looked out across the verdant Iowa River valley, and beyond to the low hills capped by the massive refrigerator manufacturing plant, he reminisced on the history of the great enterprise from its early days, when he and three other young men, all of differing backgrounds, had only their dream of bringing refrigeration to America’s heartland to sustain them, to the present day, where they had become the Midwest’s foremost group of refrigerator magnates.

Dick Davis, Circle Pines, MN

For concurrent programming to become mainstream, we must discard threads as a programming model. Nondeterminism should be judiciously and carefully introduced where needed, and it should be explicit in programs.

Lee, Edward A. “The Problem With Threads.” Computer May 2006.

Per request, I have made the Python script which generates my weight graph available here: graph-weight.py.

Consider, once again, the XML file from yesterday’s post Selecting A Maximum Value Using XPath:

<Prices>
  <Price>
    <Date>2006-09-01</Date>
    <Open>25.89</Open>
    <High>25.97</High>
    <Low>25.64</Low>
    <Close>25.84</Close>
    <Volume>31594600</Volume>
    <AdjClose>25.84</AdjClose>
  </Price>
  <Price>
    <Date>2006-08-31</Date>
    <Open>25.87</Open>
    <High>25.98</High>
    <Low>25.68</Low>
    <Close>25.70</Close>
    <Volume>26380500</Volume>
    <AdjClose>25.70</AdjClose>
  </Price>
  ...
</Prices>

If you cannot assume the data are sorted, the types of XPath 1.0 expressions you can write are deeply limited; as we saw last time, we couldn’t even write an expression which selects the Price element with the latest Date. However, if you can assume the data are sorted in latest-first order, you can write some fairly useful expressions:

Select the Price element with the latest Date:

This is the first Price element, so the expression is:

Prices/Price[1]

Select the Price element with the earliest Date:

This is (obviously) the last Price element, so the expression is:

/Prices/Price[last()]

Select all Price elements from the last trading day of the month:

Normally this is fairly complicated because stock markets aren’t usually open on weekdays or holidays. However, because the Price elements are assumed to be in latest-first order, we can simply look for the (physically) first Price element for a month. While this may not work for all XPath parsers, the following expression works on my machine:

/Prices/Price[substring(preceding-sibling::Price[1]/Date, 1, 7) != substring(Date, 1, 7)]

This reads “Select all Price elements whose Date element have a different year and month from the previous Price element’s Date.”

This expression may not work on all XPath parsers because it assumes that the first Price element in the preceding-sibling axis is the immediate predecessor — in other words, the preceding-sibling axis iterates backwards. I do not know if this is guaranteed by the standard, but I can see that it might commonly be implemented this way.

Furthermore, while this expression correctly selects the <Date>2006-09-01</Date> element as part of the result, it does so for subtle reasons. It might be clearer to explicitly test for the number of elements in the preceding-sibling axis using count().

Let’s say you have an XML file which contains daily stock prices, such as the following:

<Prices>
  <Price>
    <Date>2006-09-01</Date>
    <Open>25.89</Open>
    <High>25.97</High>
    <Low>25.64</Low>
    <Close>25.84</Close>
    <Volume>31594600</Volume>
    <AdjClose>25.84</AdjClose>
  </Price>
  <Price>
    <Date>2006-08-31</Date>
    <Open>25.87</Open>
    <High>25.98</High>
    <Low>25.68</Low>
    <Close>25.70</Close>
    <Volume>26380500</Volume>
    <AdjClose>25.70</AdjClose>
  </Price>
  ...
</Prices>

Excerpt from MSFT.xml generated on 2006-09-05 from Yahoo Finance’s MSFT Historical Prices and YahooCsvToXml.py

Now let’s write an XSLT fragment which displays the Price element with the latest Date:

<xsl:for-each select="/Prices/Price">
  <xsl:sort select="Date" order="descending" />

  <xsl:if test="position() = 1">
    <xsl:copy-of select="." />
  </xsl:if>
</xsl:for-each>

What if you wanted to do this in pure XPath 1.0? Well, normally one would use something akin to Jeni Tennison’s XPath maximum ‘trick’ and write the following XPath expression:

/Prices/Price[not(preceding-sibling::Price/Date > Date or
                  following-sibling::Price/Date > Date)]

This expression reads “Select the Price element that doesn’t have a sibling Price element with a Date greater than this one.” (By the way, you should be careful with this XPath expression and large node sets — it is highly likely it runs in O(n²) time.)

Unfortunately the above expression doesn’t work for dates because XPath’s comparison operators only work on numbers, not strings. I tried writing the equivalent expression using Microsoft’s ms:string-compare XPath extension function but it didn’t work — I believe because it only compares two strings whereas the expression requires a function that compares a node-set to a string and returns a node-set.

As far as I can tell, the only way to perform this selection in pure XPath 1.0 is to change the original XML by converting the Date values to numbers (by removing the dashes). Hopefully XPath 2.0 will have a more palatable solution.