bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Drew Adams]

> > What this function is really about, I think, is this: a list with
> > unique elements - no duplicates.
> >
> > With your fix of this bug, "unique" will be defined by the new TEST
> > arg (predicate).  Until then, "unique" is defined by `eq'.
> 
> What on earth is a "numeric list order" of an object?  This seems to
> imply that ELEMENT should be a number.

No.  ELEMENT need not be a number.  In face, as currently
defined it needs to be something identified by `eq' (so
NOT a number, till we add an optional TEST arg).  It is
the order of ELEMENT that can (optionally) be specified
as a number.

I'm learning this too.  I never heard of this function before.

My understanding is as I said in my previous mail.  This
is about a particular kind of list: one that has no
duplicates.  (Well, you can force it to have dups by
add elements other than using `add-to-ordered-list'.)

And one where you can specify a given list order to any
of the elements.  This specified order is a number, and
elements with lower orders appear in the list before
those with higher orders.

Elements of the list can also have no specified order.
If the order of a given list element isn't specified
then its order isn't guaranteed (not controlled by you),
except that it's sorted after any elements that have a
specified order.

The order of elements is determined by sorting them by
the order values you assigned them, which are recorded
in the hash table (except for elts with no recorded order,
which are in no special order at the end of the list,
after those with specified orders - these elts are not
recorded in the hash table).

The hash table key is the element, and the key's value
is the element's recorded order.

You can assign multiple elements the same order, in which
case they appear consecutively in the list but the order
among them isn't specified.  (Well, it's deterministic,
but essentially by recording the same recorded order for
them you're saying you don't care what the order is among
them.)

Once you assign an order to an element it's retained until
you change it (by specifying a different number as ORDER)
or you remove it (by specifying a non-nil, non-number
ORDER value).  If you remove it, it's just as if it never
had a specified order - it goes after elts with specified
orders.

You specify a particular order for a given element if you
care about its position.  If you add or remove elements
without ever having specified an order for them then they
just remain after any elts that have specified orders; the
relative order among those elts with no specified order
doesn't change.

You're right, however, that the new TEST predicate arg
cannot be used only for the hash table, in place of the
hard-coded `eq'.  It needs to also be used in place of
the hard-coded `memq', to test membership in the list.

E.g., instead of this:

(unless (memq element (symbol-value list-var))
  (set list-var (cons element (symbol-value list-var))))

This:

(unless (cl-member element (symbol-value list-var) :test TEST)
  (set list-var  (cons element (symbol-value list-var))))

> > If the third optional argument ORDER is a number (integer or
> > float), set the element's list order to the given value.  If
> > ORDER is nil or omitted, do not change the numeric order of
> > ELEMENT.  If ORDER has any other value, remove the numeric order
> > of ELEMENT if it has one.
> 
> The actual ORDER bit is optional, which makes no sense for a function
> that's allegedly about an ordered list.

It makes sense if you don't care about keeping the order
of some elements.  If you care about the order of each
element then when you add it you give it a numeric ORDER.
(Once it has a recorded order you need not provide ORDER
when you call the function, in which case the function
call is a no-op for that element.)

>     > (when order
>     >   (puthash element (and (numberp order) order) ordering))
> 
> The hash table is only used to store this ORDER, and ORDER is silently
> discarded unless it's a number.

No, it's not silently discarded.  A non-nil, non-number
ORDER _removes_ the recorded order from that element.
IOW, it removes the element from the hash table, so
`gethash' returns nil for it.

>     > (unless (memq element (symbol-value list-var))
>     >   (set list-var (cons element (symbol-value list-var))))
> 
> This is the actual member check -- the hash table isn't used to keep
> track of what's already in the list or not.

Correct.  The hash table is used to keep track of the
recorded orders for list elements (and they need not
all have recorded orders, i.e., they need not all be
in the hash table).

>     > (set list-var (sort (symbol-value list-var)
> 
> The list is re-sorted upon every call, which is maximally inefficient.

Has to be done, in general.  The only case (I think)
where it could be avoided is when the ELEMENT is in
the hash table (i.e., it has a recorded order) and the
call to `add-to-order-list' for that ELEMENT uses nil
for ORDER.

>                       > (lambda (a b)
>                       >   (let ((oa (gethash a ordering))
>                       >       (ob (gethash b ordering)))
>                       >     (if (and oa ob)
>                       >       (< oa ob)
>                       >       oa)))))))
> 
> Finally, we sort based on the values stashed in the hash table, and the
> ones with a (numerical) order gets sorted first.

Yes.

> It's a strange, maximally inefficient function.  I'll fix it up a bit
> and add the test-function.

It is indeed strange.  I don't think it's inefficient,
but you may be right.

The code change should be easy.  The doc clarification
won't be so easy.