Re: Ranges

[Ted Zlatanov <tzz@lifelogs.com>]

On Tue, 06 Jan 2004, prj@po.cwru.edu wrote:

> AIUI, It would be another way to represent a list of article
> numbers.  For example, if the last article number in a group is 8
> (or maybe even if not): 

> Inversion list Range list  Full list 
> (2 5 7 8)      ((2 . 4) 7) (2 3 4 7)

Right.  Inversion lists are as compact as ranges, but have some nicer
features - insertion and deletion of items from the inversion list is,
I think, simpler and faster code than ranges.  There's no
consolidation or splitting of ranges needed - you just eliminate any
duplicate numbers if they happen after an insertion or a deletion.
Also, for a range you have to examine the beginning and the end of the
range if you're searching.  With an inversion list you know it's
sorted, so you can step through the list in linear time (or O(log2(n))
if you can access elements randomly, but I don't think that's possible
with the regular single-linked lists in Emacs).

> I think an inversion list would use 1-2 times as many conses as the
> corresponding range list.

Also, more garbage collection would probably happen when the list gets
rebuilt.  It may not be the optimal solution, but I think some
benchmarking would be good.  I'll look at gnus-range.el, time
permitting.

Ted