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

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

At Fri, 12 Dec 2008 01:13:45 +0100, Jakub Narebski wrote:

quoted

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