W3C home > Mailing lists > Public > xproc-dev@w3.org > November 2010

QuickSort in XProc

From: mozer <xmlizer@gmail.com>
Date: Wed, 17 Nov 2010 18:32:06 +0000
Message-ID: <AANLkTinRv-VtQTKSdXSTv5oR11=MQo3yVtd4YAsfUmQM@mail.gmail.com>
To: XProc Dev <xproc-dev@w3.org>
Hi,

During a training on XProc I had today, I proposed to work on a
QuickSort implementation
Here is the signature of the ix:sort step
  <p:declare-step type="ix:sort" name="sort">
    <p:input port="source" sequence="true"/>
    <p:output port="result" sequence="true"/>
    <p:option name="key" required="true"/> <!-- XPathExpression -->
  </p:declare-step>

You provide as input a sequence of document
You provide as a key the XPath expression to select an ELEMENT on
which the fn:string() function will get the key
And you're done

Here you can find a working example that sorts the doc elements under the root

<p:declare-step xmlns:p="http://www.w3.org/ns/xproc"
xmlns:c="http://www.w3.org/ns/xproc-step"
xmlns:ix="http://www.innovimax.fr/ns" version="1.0">
  <p:input port="source">
    <p:inline exclude-inline-prefixes="#all">
      <root>
        <doc>03</doc>
        <doc>04</doc>
        <doc>07</doc>
        <doc>06</doc>
        <doc>02</doc>
        <doc>01</doc>
        <doc>08</doc>
        <doc>10</doc>
        <doc>09</doc>
        <doc>05</doc>
        <doc>03</doc>
        <doc>04</doc>
        <doc>07</doc>
        <doc>06</doc>
        <doc>02</doc>
        <doc>01</doc>
        <doc>08</doc>
        <doc>10</doc>
        <doc>09</doc>
        <doc>05</doc>
        <doc>03</doc>
        <doc>04</doc>
        <doc>07</doc>
        <doc>06</doc>
        <doc>02</doc>
        <doc>01</doc>
        <doc>08</doc>
        <doc>10</doc>
        <doc>09</doc>
        <doc>05</doc>
        <doc>03</doc>
        <doc>04</doc>
        <doc>07</doc>
        <doc>06</doc>
        <doc>02</doc>
        <doc>01</doc>
        <doc>08</doc>
        <doc>10</doc>
        <doc>09</doc>
        <doc>05</doc>
        <doc>03</doc>
        <doc>04</doc>
        <doc>07</doc>
        <doc>06</doc>
        <doc>02</doc>
        <doc>01</doc>
        <doc>08</doc>
        <doc>10</doc>
        <doc>09</doc>
        <doc>05</doc>
        <doc>03</doc>
        <doc>04</doc>
        <doc>07</doc>
        <doc>06</doc>
        <doc>02</doc>
        <doc>01</doc>
        <doc>08</doc>
        <doc>10</doc>
        <doc>09</doc>
        <doc>05</doc>
      </root>
    </p:inline>
  </p:input>
  <p:output port="result"/>
  <p:declare-step type="ix:sort" name="sort">
   <p:documentation>
      <p>XProc QuickSort implementation</p>
      <p>Copyright (C) 2010  Mohamed ZERGAOUI Innovimax</p>

      <p>This program is free software: you can redistribute it and/or modify
          it under the terms of the GNU General Public License as published by
          the Free Software Foundation, either version 3 of the License, or
          (at your option) any later version.</p>

      <p>This program is distributed in the hope that it will be useful,
          but WITHOUT ANY WARRANTY; without even the implied warranty of
          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
          GNU General Public License for more details.</p>

      <p>You should have received a copy of the GNU General Public License
          along with this program.  If not, see
http://www.gnu.org/licenses/.</p>
    </p:documentation>
    <p:input port="source" sequence="true"/>
    <p:output port="result" sequence="true"/>
    <p:option name="key" required="true"/>
    <p:count/>
    <p:choose>
      <p:when test="number(.) le 1">
        <p:identity>
          <p:input port="source">
            <p:pipe port="source" step="sort"/>
          </p:input>
        </p:identity>
      </p:when>
      <p:otherwise>
        <p:split-sequence test="position() = 1" name="split">
          <p:input port="source">
            <p:pipe port="source" step="sort"/>
          </p:input>
        </p:split-sequence>
        <p:filter name="filter">
          <p:with-option name="select" select="$key">
            <p:empty/>
          </p:with-option>
        </p:filter>
        <p:group>
          <p:variable name="pivot-key" select=".">
            <p:pipe port="result" step="filter"/>
          </p:variable>
          <p:split-sequence name="split-pivot">
            <p:input port="source">
              <p:pipe port="not-matched" step="split"/>
            </p:input>
            <p:with-option name="test" select="concat($key, ' &lt;= ',
$pivot-key)"/>
          </p:split-sequence>
          <ix:sort name="less">
            <p:with-option name="key" select="$key">
              <p:empty/>
            </p:with-option>
            <p:input port="source">
              <p:pipe port="matched" step="split-pivot"/>
            </p:input>
          </ix:sort>
          <ix:sort name="greater">
            <p:with-option name="key" select="$key">
              <p:empty/>
            </p:with-option>
            <p:input port="source">
              <p:pipe port="not-matched" step="split-pivot"/>
            </p:input>
          </ix:sort>
          <p:identity>
            <p:input port="source">
              <p:pipe port="result" step="less"/>
              <p:pipe port="matched" step="split"/>
              <p:pipe port="result" step="greater"/>
            </p:input>
          </p:identity>
        </p:group>
      </p:otherwise>
    </p:choose>
  </p:declare-step>
  <p:for-each>
    <p:iteration-source select="/root/doc"/>
    <p:identity/>
  </p:for-each>
  <ix:sort key="/doc"/>
  <p:wrap-sequence wrapper="root"/>
</p:declare-step>
Received on Wednesday, 17 November 2010 18:32:39 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Wednesday, 17 November 2010 18:32:40 GMT