As I am a hobbyist developer who is still exploring the depths of JavaScript, and who had never written or published a package before, I am certainly in no position to teach anything to anyone. What I can do, though, is to share my experience in writing what is essentially still an imperfect package, but that I had a lot of fun coming up with.

It all started with a problem that I was surprised to see had not been tackled all that much online, and that I found out could be neatly solved in a bit of an unexpected way: that is, using recursion.

The problem with league tables

Those of you who like soccer (or sports in general, or any competitive environment where rankings are needed) are certainly familiar with the concept of a league table: a certain number of teams compete against one another in a sequence of matches, after which each team earns a certain number of points depending on whether they won, drew or lost; a league table collects all teams in descending order of points, thus making it clear which team is crowned as the winner.

In terms of programming, this is a situation that poses no issues whatsoever: checking which team won a match is trivial (in soccer, it's as easy as seeing which of the two teams scored more goals), and computing the total number of points across all the matches boils down to a simple addition. The sorting step is not complicated either, as JavaScript even comes with default sorting methods for arrays.

One would imagine that things become a little less trivial when two or more teams finish level on points, in which case a tiebreaker is needed. Turning our heads to soccer once more, common tiebreakers usually include goal difference (the number of goals scored minus the number of goals conceded), the number of goals scored itself, the number of wins and so on. And this would, once again, suggest that the problem is not all that difficult to solve: in case of a tie in points, just switch to sorting the teams in question under a different criterion. Even allowing the user to choose which tiebreakers to apply, or in what order, is not tough to implement so long as the pool of choices is finite and hard-coded.

And this is the extent to which most online solutions address the problem. However, the matter is a little subtler and goes deeper than one might initially expect.

Head-to-head v. overall style

The truth is, any kind of criterion (goal difference, goals scored, and so on—but even the number of points themselves) can be checked in two different ways: in a global sense (the so-called overall check), which is the standard type of check where one looks at the full table, as it appears from all the matches that have been played by all teams, and compares teams based on that; or in a restricted sense (the so-called head-to-head check), where if two or more teams are tied in points then any subsequent tiebreaker is checked only within the matches played between the teams in question.

An example will make this difference clear. Take Group E at the UEFA Euro 2016, where the final table ended up looking like this

GF = Goals For (goals scored), GA = Goals Against (goals conceded), GD = Goal Difference.

Italy and Belgium are tied on points, and the first tiebreaker at the Euros is goal difference (where Italy and Belgium are still tied, with 2 each), followed by the number of goals scored—at which point one would expect Belgium to triumph over Italy, with 4 goals scored against 3.

However, the Euros are a competition where a head-to-head style is used to sort teams that are even on points. This means that, as soon as we recognize that Italy and Belgium need to have their tie broken, we immediately calculate a new sub-table made only of the teams concerned in the tie. And as they played a single match that ended 0-2 for Italy in the very first matchday, this sub-table looks like this (soccer assigns three points for a win, one for a draw and none for a loss)

GF = Goals For (goals scored), GA = Goals Against (goals conceded), GD = Goal Difference.

meaning that Italy is sorted above Belgium immediately, on account of head-to-head points (three to zero).

Different competitions will usually employ different styles (the Euros use the head-to-head style as we just saw, while for example the FIFA World Cup is famous for employing overall checks instead), though they will both switch to the other style should the first run of criteria be inconclusive in breaking a given tie.

This means that, potentially, head-to-head checks are bound to happen sooner or later (either immediately in a competition like the Euros, or as a potential second tiebreaking run at the FIFA World Cup). So my takeaway here was that the table we look at may potentially change during the sorting process, as the head-to-head style (whether it comes immediately or not) hinges on this fact.

But this was not my only takeaway, as the following example shows.

More intricacies: head-to-head reapplication

Belgium is once again the protagonist in the famous Group E at the UEFA Euro 2024, where every single team finished their group with 4 points

GF = Goals For (goals scored), GA = Goals Against (goals conceded), GD = Goal Difference.

As all teams are tied in points, the sub-table of head-to-head results is still the full table anyway. Slovakia and Ukraine are sorted on goal difference to the bottom of the table, and then Romania is put above Belgium due to their superior number of goals scored (Romania 4, Belgium 2). Indeed, this is what the final table ended up looking like.

But one might think this odd: there was exactly one game played between Belgium and Romania, which Belgium won 2-0 in the second matchday. So why did Belgium not rank above Romania? Does this not matter? Why was a sub-table not recalculated for them after Slovakia and Ukraine were separated from the rest, like we did before?

The truth of the matter is that, according to the UEFA Euro regulations (§20.01-d.), a recomputation of the head-to-head results does not happen at every step, but only once the full list of tiebreakers has run out. Since after the tie in points and goal difference there is still the number of goals scored to be checked, we look at that and this is why Romania ends up triumphing. Had that been tied as well, only at that point would we actually start considering a sub-table based on the single match played between the still-tied teams (Belgium and Romania), where Belgium would in fact come out on top due to their win.

So here is the second takeaway: there is a concept of depth involved in the sorting process, as depending on how far you are into it you have to take different decisions—such as whether to proceed with a sub-table recalculation or not. In this case, you would not proceed with it just yet as the list of criteria is still going on.

These are the main points that lead to my decision for the form of my sorting function.

A recursive approach

The sorting algorithm, accessing via the .standings() method of the class that my package implements, relies on a recursive function

const sortAndDivideTable = (table, iteration, criteria) => {
    // ...
}

where at any given step table is the table holding the data of the teams that are currently to be sorted, iteration keeps track of the iteration number and other related information (e.g. if this is a head-to-head or overall type of check), and criteria is an array representing the ordered list of criteria to be applied (e.g. points, goal difference, number of goals scored).

The recursion starts with a table that is computed from all the matches played by all teams, and which is still potentially unordered. Notice that the first iteration of the algorithm is always of type overall (and is therefore initialized as such when the recursion starts), as by definition the first check is always the number of points obtained across all matches; again by definition, the first element in the criteria array is always "points".

This starting table is also safely kept tucked away: at any given step its entries are not modified, but its rows will be sorted little by little. For reference purposes, we can call it the ‘original standings’ from now on.

A real-world example from the UEFA Champions League

Having this in mind, it is possible to make sense of the algorithm with an example that is provided by Group D at the 2013-14 UEFA Champions League, which ended up looking like this

GF = Goals For (goals scored), GA = Goals Against (goals conceded), GD = Goal Difference.

As we noted, at the first step of our algorithm the sorting criterion is "points". The first job of sortAndDivideTable is to chop up the table according to it, and we employ the standard .reduce() JavaScript array method for doing so.

In this case we produce two sub-tables of two teams each, as there are two groups of tied teams (Bayern Munich/Manchester City and Viktoria Plzeň/CSKA Moscow, at 15 and 3 points respectively). The original standings are then partially sorted: some of these teams will definitely be above others (e.g. Manchester City certainly lives above Viktoria Plzeň), but the teams that are level on points are still left undecided.

As this first recursive step nears its end, we decide where to go next: we know the UEFA Champions League employs a head-to-head style, and thus we write that as the type for the next iteration; and as the chopped-up groups are of length greater than one (there are two teams in each of them), meaning that we still have some work to do in terms of sorting, we feed each of them back into sortAndDivideTable as the new table.

Let us follow the history of the first set of tied teams. We have entered a head-to-head run of criteria, so first things first we compute the sub-table of their matches: we see that Bayern Munich lost at home (Bayern Munich 2-3 Manchester City) but then won away from home by a larger margin (Manchester City 1-3 Bayern Munich), thus giving rise to the sub-table

GF = Goals For (goals scored), GA = Goals Against (goals conceded), GD = Goal Difference.

Now, they are tied in (head-to-head) points: the grouping step therefore leaves this table unchanged, the sorting step has nothing to do, and we reach the end of the recursive iteration without much accomplished; therefore we move onto the next criterion (goal difference), keep the head-to-head type, and we feed the table it back into the function.

As we are in the middle of a head-to-head run, we skip the table recomputing step (as noted in the second takeaway section, that is something we only do when the head-to-head process starts, or when it ends after all criteria have been applied without reaching a decision); but this time the criterion is goal difference, so the grouping step succeeds in chopping the table up into two sub-tables (of length one each) as one team has a goal difference of 1, while the other has a goal difference of -1. This allows the sorting step to look at the original standings once more, and now definitely say that Bayern Munich ranks above Manchester City.

And as the resulting chopped-up sets from the grouping step are of length exactly one (meaning there are no remaining ties), we exit the recursion on this branch by not calling the function anymore.

On the other side of things, for the history of the second set, we have that Viktoria Plzeň likewise won at home (Viktoria Plzeň 2-1 CSKA Moscow) but then lost away from home by the same margin (CSKA Moscow 3-2 Viktoria Plzeň), thus yielding

GF = Goals For (goals scored), GA = Goals Against (goals conceded), GD = Goal Difference.

where both teams are tied on head-to-head goal difference and head-to-head goals scored, and so they require an additional criterion (and therefore an additional recursion step) to be sorted unlike their counterparts. In the case of the UEFA Champions League, this next criterion would be the number of goals scored away from home—here 2 for Viktoria Plzeň and 1 for CSKA Moscow in their head-to-head record.

Once again, the recursion ends at this step and the original standings are now fully sorted.

What's good about it

This examples showcases some of the positive aspects of the recursive approach: the two branches need not ‘talk’ to one another—in fact, one of them even needs an additional tiebreaker to be sorted but this is of no concern to the other. Any matter regarding the recursion depth that we have reached, such as whether or not we have to go for head-to-head reapplication (as explained in the section by the same name above) can be sorted out by each branch independently.

Additionally, as the intersection of any two branches is always empty (since they are created in the grouping step via .reduce(), which always splits an array in non-intersecting equivalence classes), each branch can independently sort their own teams in the original standings without stepping on each other's feet. This means that a branch of extremely tied teams could even run out the entire head-to-head criteria, and thus revert back to overall checks with the hope to break the tie, without this affecting the comparisons of any other teams—as no branch ever influences any other.

Notice also how the recursion has to end: whenever two teams are sorted according to the current criterion, .reduce() will produce sub-arrays whose length is strictly smaller than that of the present table, so that the next step in the recursion will be closer to reaching an array of length one (at which point the function is not called anymore); and if the tie persists all the way to the end, the final criterion is always either a drawing of random lots or alphabetical sorting, which is bound to produce a result either way (team identifiers are required to be unique at input time).

Final considerations

There is a lot more to be said about tiebreaking styles, as well as in terms of the functionalities of this package and all the customization options that the user has access to in defining the rules of the tournament.

I may write more about this in the future, especially for what concerns the .ties() method that provides a text description of which teams were sorted, including how and at what step, that the final user may want to print for clarity's sake.

But in the meantime, feel free to check the repository on GitHub if you want to...

...and naturally, this is an opportunity for me to learn as well. If you see any points of concern or margins for improvement, do not be shy and tell me in the comments!

The above is the detailed content of My first JavaScript package (with recursion for the win). For more information, please follow other related articles on the PHP Chinese website!