git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Jakub Narebski <jnareb@gmail.com>
To: "Sébastien Cevey" <seb@cine7.net>
Cc: git@vger.kernel.org, Junio C Hamano <gitster@pobox.com>,
	Petr Baudis <pasky@suse.cz>,
	Gustavo Sverzut Barbieri <barbieri@profusion.mobi>
Subject: Re: [PATCH v3 3/3] gitweb: Optional grouping of projects by category
Date: Fri, 12 Dec 2008 03:03:55 +0100	[thread overview]
Message-ID: <200812120303.56997.jnareb@gmail.com> (raw)
In-Reply-To: <87zlj2xm35.wl%seb@cine7.net>

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

  reply	other threads:[~2008-12-12  2:05 UTC|newest]

Thread overview: 24+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2008-12-02 15:04 [PATCH] gitweb: Optional grouping of projects by category Sebastien Cevey
2008-12-02 23:36 ` Jakub Narebski
2008-12-03 14:22   ` [PATCH v2] " Sébastien Cevey
2008-12-03 22:51     ` Junio C Hamano
2008-12-03 23:12       ` Jakub Narebski
2008-12-04  0:39       ` [PATCH v3 0/3] " Sébastien Cevey
2008-12-04  0:43         ` Junio C Hamano
2008-12-04  0:42       ` [PATCH v3 1/3] gitweb: Modularized git_get_project_description to be more generic Sébastien Cevey
2008-12-04  0:44         ` [PATCH v3 2/3] gitweb: Split git_project_list_body in two functions Sébastien Cevey
2008-12-04  0:46           ` [PATCH v3 3/3] gitweb: Optional grouping of projects by category Sébastien Cevey
2008-12-04 19:37             ` Junio C Hamano
2008-12-05  2:08             ` Jakub Narebski
2008-12-05  2:32               ` Sébastien Cevey
2008-12-05 10:45                 ` Jakub Narebski
2008-12-11 23:34                   ` Sébastien Cevey
2008-12-12  0:13                     ` Jakub Narebski
2008-12-12  0:40                       ` Sébastien Cevey
2008-12-12  2:03                         ` Jakub Narebski [this message]
2008-12-12  3:10                           ` Sébastien Cevey
2008-12-12  9:26                             ` Jakub Narebski
2008-12-05  1:52           ` [PATCH v3 2/3] gitweb: Split git_project_list_body in two functions Jakub Narebski
2008-12-05  1:38         ` [PATCH v3 1/3] gitweb: Modularized git_get_project_description to be more generic Jakub Narebski
2008-12-03 14:29   ` [PATCH] gitweb: Optional grouping of projects by category Sébastien Cevey
2008-12-03 21:14   ` Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=200812120303.56997.jnareb@gmail.com \
    --to=jnareb@gmail.com \
    --cc=barbieri@profusion.mobi \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=pasky@suse.cz \
    --cc=seb@cine7.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).