From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Drew Adams Newsgroups: gmane.emacs.bugs Subject: bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table Date: Wed, 30 Dec 2020 21:34:12 -0800 (PST) Message-ID: References: <1af7f2ac-0e6c-4c8a-860b-22148265d8aa@default> <87y2hgosxo.fsf@gnus.org> <64015d41-a84f-4ff6-a5a1-ab5d92aa20e5@default> <87k0szpyaj.fsf@gnus.org> <87v9ciociu.fsf@gnus.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="28072"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 45539@debbugs.gnu.org To: Lars Ingebrigtsen Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Thu Dec 31 06:35:11 2020 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1kuqcA-00079E-Se for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 31 Dec 2020 06:35:11 +0100 Original-Received: from localhost ([::1]:39404 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kuqc9-0005P9-GI for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 31 Dec 2020 00:35:09 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:55342) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kuqc2-0005P2-G1 for bug-gnu-emacs@gnu.org; Thu, 31 Dec 2020 00:35:02 -0500 Original-Received: from debbugs.gnu.org ([209.51.188.43]:40162) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kuqc2-0005HA-8q for bug-gnu-emacs@gnu.org; Thu, 31 Dec 2020 00:35:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1kuqc2-0000P9-4U for bug-gnu-emacs@gnu.org; Thu, 31 Dec 2020 00:35:02 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Drew Adams Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 31 Dec 2020 05:35:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 45539 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: fixed Original-Received: via spool by 45539-submit@debbugs.gnu.org id=B45539.16093928651505 (code B ref 45539); Thu, 31 Dec 2020 05:35:02 +0000 Original-Received: (at 45539) by debbugs.gnu.org; 31 Dec 2020 05:34:25 +0000 Original-Received: from localhost ([127.0.0.1]:51708 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kuqbR-0000OD-CR for submit@debbugs.gnu.org; Thu, 31 Dec 2020 00:34:25 -0500 Original-Received: from userp2130.oracle.com ([156.151.31.86]:46940) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kuqbO-0000Ny-L5 for 45539@debbugs.gnu.org; Thu, 31 Dec 2020 00:34:23 -0500 Original-Received: from pps.filterd (userp2130.oracle.com [127.0.0.1]) by userp2130.oracle.com (8.16.0.42/8.16.0.42) with SMTP id 0BV5TA7H060229; Thu, 31 Dec 2020 05:34:15 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=mime-version : message-id : date : from : sender : to : cc : subject : references : in-reply-to : content-type : content-transfer-encoding; s=corp-2020-01-29; bh=mR70SExPQSdtVDEM11OjJaUeFYAEOOf90Qnfr8SOGNY=; b=CfojuI+UpSqZqmG6vBUkiDvquJ876YePHXrBHcospbbaIf5PxsF1Hdvwxvx9JZQ2kn21 wbJXC8PRxdURWZ9vjS1wNZM+Utvezem2MVkv8kZ3u2DUdyx63JBA66e+xsLjw4h/Cyb+ 8YOYuQiT+auuU3UzlXh4aU2H+m1hQoaedF1TjZNNro58DbcAqfkbN61bd1vYIYcCHDvB 5/kHQzDHcoVMle+nXshfrznTL44nzx7ScxwXYBEcDBicltv/a/r2uKg8KvMv7ROm7+1y KQ7CJJnqnioArADgewpYsMSG7rd1I8eVqZ4xPRxhmRAbDOghHOI9NryvvINpzZegSFQB sg== Original-Received: from userp3020.oracle.com (userp3020.oracle.com [156.151.31.79]) by userp2130.oracle.com with ESMTP id 35nvkqt5mx-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Thu, 31 Dec 2020 05:34:15 +0000 Original-Received: from pps.filterd (userp3020.oracle.com [127.0.0.1]) by userp3020.oracle.com (8.16.0.42/8.16.0.42) with SMTP id 0BV5U46T011903; Thu, 31 Dec 2020 05:34:15 GMT Original-Received: from aserv0122.oracle.com (aserv0122.oracle.com [141.146.126.236]) by userp3020.oracle.com with ESMTP id 35pextjku0-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 31 Dec 2020 05:34:15 +0000 Original-Received: from abhmp0002.oracle.com (abhmp0002.oracle.com [141.146.116.8]) by aserv0122.oracle.com (8.14.4/8.14.4) with ESMTP id 0BV5YECA018703; Thu, 31 Dec 2020 05:34:14 GMT In-Reply-To: <87v9ciociu.fsf@gnus.org> X-Priority: 3 X-Mailer: Oracle Beehive Extensions for Outlook 2.0.1.9.1 (1003210) [OL 16.0.5095.0 (x86)] X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9850 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 adultscore=0 spamscore=0 malwarescore=0 mlxscore=0 mlxlogscore=999 bulkscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2009150000 definitions=main-2012310029 X-Proofpoint-Virus-Version: vendor=nai engine=6000 definitions=9850 signatures=668683 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 spamscore=0 clxscore=1015 lowpriorityscore=0 bulkscore=0 adultscore=0 priorityscore=1501 malwarescore=0 impostorscore=0 suspectscore=0 mlxlogscore=999 mlxscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2009150000 definitions=main-2012310029 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:197068 Archived-At: > > 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'. >=20 > 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. >=20 > 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)) >=20 > 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)))) >=20 > 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) >=20 > 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. > =09=09=09> (lambda (a b) > =09=09=09> (let ((oa (gethash a ordering)) > =09=09=09> =09(ob (gethash b ordering))) > =09=09=09> (if (and oa ob) > =09=09=09> =09(< oa ob) > =09=09=09> oa))))))) >=20 > 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.