diff options
Diffstat (limited to 'lisp/gnus/nnvirtual.el')
| -rw-r--r-- | lisp/gnus/nnvirtual.el | 130 |
1 files changed, 65 insertions, 65 deletions
diff --git a/lisp/gnus/nnvirtual.el b/lisp/gnus/nnvirtual.el index c80bbf61875..25f3413fcd5 100644 --- a/lisp/gnus/nnvirtual.el +++ b/lisp/gnus/nnvirtual.el @@ -491,9 +491,9 @@ If UPDATE-P is not nil, call gnus-group-update-group on the components." -;;; This is currently O(kn^2) to merge n lists of length k. -;;; You could do it in O(knlogn), but we have a small n, and the -;;; overhead of the other approach is probably greater. +;; This is currently O(kn^2) to merge n lists of length k. +;; You could do it in O(knlogn), but we have a small n, and the +;; overhead of the other approach is probably greater. (defun nnvirtual-merge-sorted-lists (&rest lists) "Merge many sorted lists of numbers." (if (null (cdr lists)) @@ -501,68 +501,68 @@ If UPDATE-P is not nil, call gnus-group-update-group on the components." (sort (apply 'nconc lists) '<))) -;;; We map between virtual articles and real articles in a manner -;;; which keeps the size of the virtual active list the same as the -;;; sum of the component active lists. - -;;; To achieve fair mixing of the groups, the last article in each of -;;; N component groups will be in the last N articles in the virtual -;;; group. - -;;; If you have 3 components A, B and C, with articles 1-8, 1-5, and -;;; 6-7 respectively, then the virtual article numbers look like: -;;; -;;; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -;;; A1 A2 A3 A4 B1 A5 B2 A6 B3 A7 B4 C6 A8 B5 C7 - -;;; To compute these mappings we generate a couple tables and then -;;; do some fast operations on them. Tables for the example above: -;;; -;;; Offsets - [(A 0) (B -3) (C -1)] -;;; -;;; a b c d e -;;; Mapping - ([ 3 0 1 3 0 ] -;;; [ 6 3 2 9 3 ] -;;; [ 8 6 3 15 9 ]) -;;; -;;; (note column 'e' is different in real algorithm, which is slightly -;;; different than described here, but this gives you the methodology.) -;;; -;;; The basic idea is this, when going from component->virtual, apply -;;; the appropriate offset to the article number. Then search the first -;;; column of the table for a row where 'a' is less than or equal to the -;;; modified number. You can see that only group A can therefore go to -;;; the first row, groups A and B to the second, and all to the last. -;;; The third column of the table is telling us the number of groups -;;; which might be able to reach that row (it might increase by more than -;;; 1 if several groups have the same size). -;;; Then column 'b' provides an additional offset you apply when you have -;;; found the correct row. You then multiply by 'c' and add on the groups -;;; _position_ in the offset table. The basic idea here is that on -;;; any given row we are going to map back and forth using X'=X*c+Y and -;;; X=(X'/c), Y=(X' mod c). Then once you've done this transformation, -;;; you apply a final offset from column 'e' to give the virtual article. -;;; -;;; Going the other direction, you instead search on column 'd' instead -;;; of 'a', and apply everything in reverse order. - -;;; Convert component -> virtual: -;;; set num = num - Offset(group) -;;; find first row in Mapping where num <= 'a' -;;; num = (num-'b')*c + Position(group) + 'e' - -;;; Convert virtual -> component: -;;; find first row in Mapping where num <= 'd' -;;; num = num - 'e' -;;; group_pos = num mod 'c' -;;; num = (num / 'c') + 'b' + Offset(group_pos) - -;;; Easy no? :) -;;; -;;; Well actually, you need to keep column e offset smaller by the 'c' -;;; column for that line, and always add 1 more when going from -;;; component -> virtual. Otherwise you run into a problem with -;;; unique reverse mapping. +;; We map between virtual articles and real articles in a manner +;; which keeps the size of the virtual active list the same as the +;; sum of the component active lists. + +;; To achieve fair mixing of the groups, the last article in each of +;; N component groups will be in the last N articles in the virtual +;; group. + +;; If you have 3 components A, B and C, with articles 1-8, 1-5, and +;; 6-7 respectively, then the virtual article numbers look like: +;; +;; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 +;; A1 A2 A3 A4 B1 A5 B2 A6 B3 A7 B4 C6 A8 B5 C7 + +;; To compute these mappings we generate a couple tables and then +;; do some fast operations on them. Tables for the example above: +;; +;; Offsets - [(A 0) (B -3) (C -1)] +;; +;; a b c d e +;; Mapping - ([ 3 0 1 3 0 ] +;; [ 6 3 2 9 3 ] +;; [ 8 6 3 15 9 ]) +;; +;; (note column 'e' is different in real algorithm, which is slightly +;; different than described here, but this gives you the methodology.) +;; +;; The basic idea is this, when going from component->virtual, apply +;; the appropriate offset to the article number. Then search the first +;; column of the table for a row where 'a' is less than or equal to the +;; modified number. You can see that only group A can therefore go to +;; the first row, groups A and B to the second, and all to the last. +;; The third column of the table is telling us the number of groups +;; which might be able to reach that row (it might increase by more than +;; 1 if several groups have the same size). +;; Then column 'b' provides an additional offset you apply when you have +;; found the correct row. You then multiply by 'c' and add on the groups +;; _position_ in the offset table. The basic idea here is that on +;; any given row we are going to map back and forth using X'=X*c+Y and +;; X=(X'/c), Y=(X' mod c). Then once you've done this transformation, +;; you apply a final offset from column 'e' to give the virtual article. +;; +;; Going the other direction, you instead search on column 'd' instead +;; of 'a', and apply everything in reverse order. + +;; Convert component -> virtual: +;; set num = num - Offset(group) +;; find first row in Mapping where num <= 'a' +;; num = (num-'b')*c + Position(group) + 'e' + +;; Convert virtual -> component: +;; find first row in Mapping where num <= 'd' +;; num = num - 'e' +;; group_pos = num mod 'c' +;; num = (num / 'c') + 'b' + Offset(group_pos) + +;; Easy no? :) +;; +;; Well actually, you need to keep column e offset smaller by the 'c' +;; column for that line, and always add 1 more when going from +;; component -> virtual. Otherwise you run into a problem with +;; unique reverse mapping. (defun nnvirtual-map-article (article) "Return a cons of the component group and article corresponding to the given virtual ARTICLE." |