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

[Jakub Narebski <jnareb@gmail.com>]

On Fri, 12 Dec 2008, Sébastien Cevey wrote:
> 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.
 
> 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