GNU bug report logs - #50878
[PATCH] union: Resolve collisions by stable-sort'ing them.

Previous Next

Full log

Message #35 received at 50878 <at> debbugs.gnu.org (full text, mbox):

From: Liliana Marie Prikler <liliana.prikler <at> gmail.com>
To: Maxime Devos <maximedevos <at> telenet.be>, Attila Lendvai <attila <at> lendvai.name>
Cc: 50878 <at> debbugs.gnu.org
Subject: Re: [bug#50878] [PATCH] union: Resolve collisions by
 stable-sort'ing them.
Date: Thu, 30 Sep 2021 20:13:49 +0200

Am Donnerstag, den 30.09.2021, 10:42 +0200 schrieb Maxime Devos:
> Attila Lendvai schreef op do 30-09-2021 om 08:10 [+0000]:
> > > > -   (let* ((original-files (list->vector files))
> > > > -           (count (vector-length original-files))
> > > > -           (stripped-files (vector-map (lambda (_ el)
> > > > -                                         (strip-store-file-
> > > > name el))
> > > > -                                       original-files))
> > > > -           (indices (vector-unfold values count)))
> > > > 
> > > > -   (stable-sort! indices
> > > > -                    (lambda (a b)
> > > > -                      (string> (vector-ref stripped-files a)
> > > > -                               (vector-ref stripped-files
> > > > b))))
> > > > -   (vector-ref original-files (vector-ref indices 0))))
> > > 
> > > Instead of stable-sort!-ing the indices of a vector, what about
> > > stable-
> > > sort!-ing (map strip-store-file-name original-files) in more or
> > > less
> > > one go?
> > 
> > the hash also needs to be dropped from the path for sorting to be
> > useful, but the return value must be the full path, hence the
> > complexity with sorting the indices, pointing both to the full
> > paths
> > and the cut parts.
> 
> You can replace the 'less' argument of 'stable-sort'.
> Example sorting by the second character of a string:
> 
> (sort '("za" "yb" "xc") (lambda (x y)
>                           (char>? (string-ref x 1)
>                                   (string-ref y 1)))))
> 
> IIUC, you would need to replace char>? by string> and string-ref
> by strip-store-file-name.
You could also store a mapping of long file name to stripped file name
in a hash table for fast lookup, so as to not compute (strip-store-
file-name) over and over.  That way you can stable-sort! the long
names, but don't forget to list-copy them at least for functional
purity.

Greetings,
Liliana

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.