[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Grouping with second choice

Subject: Re: Grouping with second choice
From: Jeni Tennison <mail@xxxxxxxxxxxxxxxx>
Date: Fri, 17 Aug 2001 15:35:39 +0100
first choice second choice
Hi Thorsten,

> You are right, of course. And you might be right, that I should
> write or use an optimizing tool rather than a xslt processor. Even
> though, it is a fascinating thought using our campus Web interface
> in that way (register and divide students and automatically present
> the results). The algorithm I want to use is simple indeed:
>         // supposing the students are sorted by their <RegistrationDate>
>         // (first come first serve)
>         for-each <Student>
>         if ( sum(students in group of <FirstChoice>) < max )
>                 put <Student> in <FirstChoice> group
>         else
>                 if( sum(students in group of <SecondChoice> < max )
>                         put <Student> in <SecondChoice> group
>                 else
>                         ?? use a arbitrary free group ?? (optional)

Just 'cos you optimise doesn't mean you can't use XSLT to do it,
although I admit it's probably not the best tool for the job.

Every technique that you could use here would benefit a great deal
from having the Student elements in RegistrationDate order to start
with, so I'd recommend at least a two-stage process, using sequential
processing or a node-set() extension.

They also benefit from having a list of the groups that you want to
split the students into. You could get that with:

<xsl:key name="groups" match="FirstChoice | SecondChoice" use="." />

<xsl:variable name="groups"
                         [count(.|key('groups', .)[1]) = 1] |
                         [count(.|key('groups', .)[1]) = 1]" />

To follow your algorithm as it's expressed, you need to hold
assignment information in an XML structure. Since you're updating the
assignment information, you need a recursive template, and since you
want to look at the existing assignments in order to tell what the
next set of assignments should look like, you need to use the
node-set() extension function to convert the XML into a node set. The
recursive template would be in the form:

<xsl:template name="assignStudents">
  <xsl:param name="assignments" />
  <xsl:param name="remaining-students" />
  <xsl:variable name="new-assignments">
    ... generate new assignment RTF based on the old assignments and
        the first student in $remaining-students ...
    <xsl:when test="$remaining-students[2]">
      <xsl:call-template name="assignStudents">
        <xsl:with-param name="assignments"
                        select="exsl:node-set($new-assignments)" />
        <xsl:with-param name="remaining-students"
                        select="$remaining-students[position() > 1]" />
      <xsl:copy-of select="$new-assignments" />

Alternatively, you could take a more declarative approach and iterate
over the groups trying to find the students that should be in it. I've
got it working on sorted students with the following:

<xsl:template match="Course">
    <!-- apply templates to the unique groups -->
    <xsl:apply-templates select="$groups" />

<!-- key to retrieve students by their first choice -->
<xsl:key name="first-choice-students" match="Student"
         use="FirstChoice" />
<!-- key to retrieve students by their second choice -->
<xsl:key name="second-choice-students" match="Student"
         use="SecondChoice" />

<!-- template called once per group -->
<xsl:template match="FirstChoice | SecondChoice">
  <!-- creates an element for the group -->
  <xsl:element name="{.}">
    <!-- finds the students that have it as their first choice -->
    <xsl:variable name="first-choice-students"
                  select="key('first-choice-students', .)" />
    <!-- counts them -->
    <xsl:variable name="nfirst-choice"
                  select="count($first-choice-students)" />
      <!-- if there are more first-choice students than there
           are places, copy the requisite number -->
      <xsl:when test="$nfirst-choice > $group-size">
        <xsl:copy-of select="$first-choice-students
                               [position() &lt;= $group-size]" />
        <!-- copy all the first choice students -->
        <xsl:copy-of select="$first-choice-students" />
        <!-- call the AddSecondChoiceStudents to add more students
             to the group, if there are any -->
        <xsl:call-template name="AddSecondChoiceStudents">
          <xsl:with-param name="group" select="." />
          <xsl:with-param name="count"
                          select="$group-size - $nfirst-choice" />

<!-- recursive template for adding more students -->
<xsl:template name="AddSecondChoiceStudents">
  <!-- group holds the name of the group -->
  <xsl:param name="group" />
  <!-- count holds how many students we need -->
  <xsl:param name="count" />
  <!-- students holds the students that we've yet to look at -->
  <xsl:param name="students"
             select="key('second-choice-students', $group)" />
    <!-- stop recursing when we've found as many as we need -->
    <xsl:when test="$count = 0" />
      <!-- change the current node to the first student -->
      <xsl:for-each select="$students[1]">
          <!-- if there wasn't enough room in this student's first
               choice group -->
          <xsl:when test="count(preceding-sibling::Student
                                 [FirstChoice =
                                  current()/FirstChoice]) >=
            <!-- copy this student -->
            <xsl:copy-of select="." />
            <!-- call this template recursively on the remaining
                 students, with count - 1 -->
            <xsl:call-template name="AddSecondChoiceStudents">
              <xsl:with-param name="group" select="$group" />
              <xsl:with-param name="count" select="$count - 1" />
              <xsl:with-param name="students"
                              select="$students[position() > 1]" />
            <!-- otherwise just call the template on the remaining
                 students -->
            <xsl:call-template name="AddSecondChoiceStudents">
              <xsl:with-param name="group" select="$group" />
              <xsl:with-param name="count" select="$count" />
              <xsl:with-param name="students"
                              select="$students[position() > 1]" />

This template loses the students that don't manage to get into their
first or second choice, which isn't ideal.

I hope that gives you some ideas,


Jeni Tennison

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list

Current Thread


Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
First Name
Last Name
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.