On 25 March 2014, Bram Moolenaar <b...@moolenaar.net> wrote:
>
> lcd wrote:
>
> > > > On 21 March 2014, Cade Forester <ahx2...@gmail.com> wrote:
> > > > > > How about separating it from sort()? That is, an uniq()
> > > > > > function that would remove duplicates from an already sorted
> > > > > > list (results would be undefined if the input list is not
> > > > > > sorted). That would be consistent with how uniq(1) works on
> > > > > > UNIX.
> > > > >
> > > > > This patch add uniq() function. uniq(list) will remove copies
> > > > > of repeated adjacent items
> > > >
> > > > There is a problem with this patch: it removes the
> > > > duplicates on the fly, so if the comparison function fails on
> > > > the second or subsequent call the list is still modified. In
> > > > contrast, sort() restores the list to the initial state if the
> > > > comparison fails at some point.
> > > >
> > > > I'm attaching bellow my attempt to a fix. I also merged
> > > > f_sort() and f_uniq() in a single function, and made some minor
> > > > optimisations.
> > > >
> > > > On a related topic: adding an efficient "stable unique"
> > > > would be relatively straightforward too, using plain red-black
> > > > trees. Now, red-black trees are implemented as a header (namely
> > > > sys/tree.h) on *BSD, but not on other systems. Any comment
> > > > on the preferred way to handle this? I'd suggest testing for
> > > > the existence of sys/tree.h in autoconf, and also including a
> > > > stripped down copy of it from, say, OpenBSD, for the systems
> > > > that don't have it.
> > >
> > > There are a few problems with this implementation.
> > >
> > > The li_prev pointer is not updated.
> >
> > Right: this comes from the initial patch. I should have checked
> > what is actually going on.
> >
> > > When the first item is not a list the error is for sort(), even
> > > when uniq() is used.
> >
> > Updated patch below.
>
> Thanks. There are a few remaining issues but it's easier to fix them
> than to explain the problems.
Thanks. Any comment about the red-black trees? The resulting
uniq() function should be about as fast as sort(), but having the tree
operations implemented as macros would make the code a little awkward.
On the other hand, the same trees (or perhaps splays, implemented in
the same header file) might also be useful for speeding up operations
involving hash keys.
/lcd
--
--
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php
---
You received this message because you are subscribed to the Google Groups
"vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to vim_dev+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
