From: "Gerd Möllmann" <gerd.moellmann@gmail.com>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: Eli Zaretskii <eliz@gnu.org>,
Andreas Politz <mail@andreas-politz.de>,
58158@debbugs.gnu.org
Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful
Date: Sun, 02 Oct 2022 10:22:21 +0200 [thread overview]
Message-ID: <m27d1i1vpe.fsf@Mini.fritz.box> (raw)
In-Reply-To: <jwva66fll9a.fsf-monnier+emacs@gnu.org> (Stefan Monnier's message of "Sat, 01 Oct 2022 09:54:36 -0400")
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> Phew. I'm not sure but I get the feeling that makes implementing a
>> successor function, let's say, challenging.
>
> I don't think it makes any difference in that respect, no.
The reason I find it challenging, and I'm sure now, is that I've written
the following code, and failed :-).
/* FIXME: This assumption is wrong. Nodes on the left of P are <=,
and nodes on the right are >=. */
/* Value is the successor of interval node X in ascending order. It
is assumed that the tree is organized so that nodes < X are in
X->left and nodes in X->right are >= X. */
static struct interval_node *
in_order_successor (struct interval_node *x)
{
if (x->right != ITREE_NULL)
{
/* X has a right child, which means X's right subtree has
elements >= X. Proceed to the left-most child in the right
subtree, which is the smallest in that subtree. */
x = x->right;
while (x->left != 0)
x = x->left;
}
else
{
/* X's left subtree is uninteresting, because everything there
is < X. Therefore follow the parent chain. If X is the
parent's right child, this means the parent is < X, We are
looking for a parent that is >=. */
struct interval_node *y = x->parent;
while (x == y->right)
{
x = y;
y = y->parent;
}
/* If we found a parent that's >=, the parent is what we sought.
Otherwise, X has arrived at the null node, whose right child
is the sentinel node itself. */
if (x->right != y)
x = y;
}
return x;
}
I tried to change the comments and/or modify the code for a tree like we
have (left subtree <=, right >=), and couldn't explain why it works,
but I also couldn't produce a counter-example that the existing tree
code actually can produce. IOW, I couldn't prove anything.
P.S.
With the "all over the place" I indented to hint at the fact that the
tree is not a "normal" BST. I should probably have said that directly,
sorry.
next prev parent reply other threads:[~2022-10-02 8:22 UTC|newest]
Thread overview: 68+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-29 5:29 bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Gerd Möllmann
2022-09-29 6:28 ` Eli Zaretskii
2022-09-29 7:03 ` Gerd Möllmann
2022-09-29 8:08 ` Eli Zaretskii
2022-09-29 9:09 ` Gerd Möllmann
2022-09-29 9:37 ` Eli Zaretskii
2022-09-29 10:05 ` Gerd Möllmann
2022-09-29 10:43 ` Eli Zaretskii
2022-09-29 11:33 ` Gerd Möllmann
2022-09-29 13:10 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 13:23 ` Eli Zaretskii
2022-09-29 16:48 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 13:40 ` Eli Zaretskii
2022-09-29 14:15 ` Gerd Möllmann
2022-09-29 14:37 ` Gerd Möllmann
2022-09-29 22:09 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30 5:28 ` Gerd Möllmann
2022-09-30 6:11 ` Eli Zaretskii
2022-09-30 11:31 ` Gerd Möllmann
2022-09-30 18:29 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-02 8:06 ` Gerd Möllmann
2022-10-06 22:36 ` Dmitry Gutov
2022-10-07 19:47 ` Eli Zaretskii
2022-10-08 18:50 ` Dmitry Gutov
2022-10-10 8:10 ` Eli Zaretskii
2022-10-11 2:12 ` Dmitry Gutov
2022-10-11 6:37 ` Eli Zaretskii
2022-10-11 11:36 ` xref-query-replace-in-results error message after xref-find-definitions, was: " Dmitry Gutov
2022-10-11 11:51 ` Eli Zaretskii
2022-10-11 12:10 ` Dmitry Gutov
2022-10-11 12:17 ` Eli Zaretskii
2022-10-11 12:44 ` Dmitry Gutov
2022-10-11 12:55 ` Eli Zaretskii
2022-10-11 14:55 ` Dmitry Gutov
2022-10-11 16:01 ` Eli Zaretskii
2022-10-11 16:41 ` Dmitry Gutov
2022-10-11 16:50 ` Eli Zaretskii
2022-10-11 20:31 ` Dmitry Gutov
2022-10-12 5:17 ` Eli Zaretskii
2022-10-12 10:06 ` John Yates
2022-10-12 10:17 ` Eli Zaretskii
[not found] ` <CAJnXXogKsM=gMTFi2NivDMHW4A3EBtBtsNDBV3o5vcu2xXfuvw@mail.gmail.com>
2022-10-12 13:21 ` Eli Zaretskii
2022-10-12 16:12 ` John Yates
2022-10-12 13:47 ` Dmitry Gutov
2022-10-12 14:05 ` Eli Zaretskii
2022-10-11 14:04 ` Stefan Monnier
2022-10-11 14:07 ` Stefan Monnier
2022-10-11 15:07 ` Dmitry Gutov
2022-10-11 15:37 ` Eli Zaretskii
2022-09-30 13:25 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30 14:08 ` Gerd Möllmann
2022-09-30 15:25 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-30 16:04 ` Eli Zaretskii
2022-09-30 17:11 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-01 5:06 ` Gerd Möllmann
2022-10-01 13:54 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-02 8:22 ` Gerd Möllmann [this message]
2022-10-02 16:32 ` Andreas Politz
2022-10-03 4:35 ` Gerd Möllmann
2022-10-04 10:50 ` Andreas Politz
2022-10-01 7:25 ` Gerd Möllmann
2022-10-01 10:55 ` Gerd Möllmann
2022-10-01 14:01 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-09-29 16:40 ` Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors
2022-10-01 1:57 ` Richard Stallman
2022-10-01 7:00 ` Eli Zaretskii
2022-10-06 22:26 ` Matt Armstrong
2023-10-06 13:14 ` Gerd Möllmann
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=m27d1i1vpe.fsf@Mini.fritz.box \
--to=gerd.moellmann@gmail.com \
--cc=58158@debbugs.gnu.org \
--cc=eliz@gnu.org \
--cc=mail@andreas-politz.de \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.