- From: mozer <xmlizer@gmail.com>
- Date: Wed, 17 Nov 2010 18:32:06 +0000
- 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, ' <= ',
$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 UTC