Re: [PATCH v3 3/3] gitweb: Optional grouping of projects by category

From: Jakub Narebski <jnareb@gmail.com>
Date: Dec 12, 2008, 02:03 UTC
Message-ID: <200812120303.56997.jnareb@gmail.com>
In-Reply-To: <87zlj2xm35.wl%seb@cine7.net>

On Fri, 12 Dec 2008, Sébastien Cevey wrote:

Show 17 quoted lines

> At Fri, 12 Dec 2008 01:13:45 +0100, Jakub Narebski wrote:
> 
> > I just tried, it works but we first need to sort @projects by
> > category.
> > 
> > I don't understand.
> > [...]
> > I propose to change it to:
> 
> Well in my previous iteration of the patch (v3), the printing of
> projects with categories is done using:
> 
>   foreach my $cat (sort keys %categories) {
> 
> So everything was already sorted by category (and then by whichever
> property you picked inside each category).  You seemed okay with it,
> but requested that I documented that behaviour in the commit log.

But this does not mean that sorting by categories is necessary, or
even wanted (see below). This foreach _sorts_ by categories as primary
key using kind of bucket sort algorithm.

Show 5 quoted lines

> To maintain the same result with your proposed change (which is what I
> submitted in my patch), we need to sort by categories first (AFAIK
> Perl sort retains the original order inside equivalence classes of
> comparison key?), otherwise splice(projlist, from, to) doesn't return 
> the expected subset.

Perl requires "use sort 'stable';" pragma to ensure stable sort.

And no, we don't need to sort by categories first. Let me explain in more detail a bit.

Let us assume that $from and $to is actually used to divide projects list into categories (which goal is incompatible with searching projects, limiting to given tag/tagset and hiding forked as it is done now, at the display time; it has to be done _before_ pagination). They are used to display first page, i.e. repositories numbered 1..N in current ordering, or N..2*N, or 2*N..3*N to show next pages. Let us have the following project list:

  Project       Category
  ---------------------------
  1             a
  2             b
  3             b
  4             a

If categories are not shown, and page limit is 2, then project would be displayed like this:

  page 1          page 2
  ------          ------
  1               3
  2               4

Now _without_ sorting by category upfront, those pages would look like the following if grouping by category is enabled:

A.page 1          page 2
  ------          ------
  [a]             [a]
  1               4
  [b]             [b]
  2               3

What is not visible in this example is that projects inside category would be sorted by given order.

Now if you would sort by categories _before_ pagination, like you (from what I understand) proposed, you would have (assuming that you used "use sort 'stable'" inside block):

  Project       Category
  ---------------------------
  1             a
  4             a
  2             b
  3             b

Pagination would then look like the following:

B.page 1          page 2
  ------          ------
  [a]             [b]
  1               2
  4               3

Now which result you consider correct depends on the point of view. First is sort, paginate, sort; second is sort, sort, paginate. First have first N repositories in given order on first page, perhaps reordered a bit by categories, second doesn't have this feature. I think that the case A is more correct, but you might disagree.

Let us change example a bit:

  Project       Category
  ---------------------------
  1             b
  2             a
  3             a
  4             b

A.page 1          page 2
  ------          ------
  [a]             [a]
  2               3
  [b]             [b]
  1               4

B.page 1          page 2
  ------          ------
  [a]             [b]
  2               1
  3               4

P.S. It is IMHO better to use

 	for (my $i = $from; $i <= $to; $i++) {

than the style which is not used elsewhere in gitweb, from what I remember

 	foreach my $i ($from..$to) {

I might also be inefficient as it generates temporary array which might be quite big; I don't know if Perl 5.8.x, the oldest version one can sensibly use with gitweb I think, has this bug or not.

-- 
Jakub Narebski
Poland