From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?utf-8?Q?Gerd_M=C3=B6llmann?= Newsgroups: gmane.emacs.devel Subject: Re: noverlay branch Date: Fri, 07 Oct 2022 16:29:23 +0200 Message-ID: References: <1468ca31-1703-82a1-0c8c-be2c5b5674a7@gmail.com> <87r0zld0de.fsf@rfc20.org> <87edvki88a.fsf@rfc20.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="7720"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Matt Armstrong , emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Oct 07 17:57:27 2022 Return-path: Envelope-to: ged-emacs-devel@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 1ogpj5-0001ng-PW for ged-emacs-devel@m.gmane-mx.org; Fri, 07 Oct 2022 17:57:27 +0200 Original-Received: from localhost ([::1]:46980 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogpj4-0000BC-OL for ged-emacs-devel@m.gmane-mx.org; Fri, 07 Oct 2022 11:57:26 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:50968) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogoM1-0000Zb-9P for emacs-devel@gnu.org; Fri, 07 Oct 2022 10:29:33 -0400 Original-Received: from mail-ej1-x62c.google.com ([2a00:1450:4864:20::62c]:42928) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ogoLv-0005us-Ne for emacs-devel@gnu.org; Fri, 07 Oct 2022 10:29:32 -0400 Original-Received: by mail-ej1-x62c.google.com with SMTP id kg6so11676675ejc.9 for ; Fri, 07 Oct 2022 07:29:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:from:to:cc:subject:date:message-id:reply-to; bh=1xyQ36UIWFFS/twZuZ/fCA3nw+yBYN8W8p1vgqAd1yo=; b=l++AWwbGsb9K8A/QRGhqvOhJUX7xRBaso8nqVKoqduEC3MO+21c5JSwLfCWDliMg7S Q+3I+bZDI3SK2rjCWEhIP9Gbtjefpdgpx2dwn3OOOibkfAoPB3Me62IQ0P+a65ypi2lc WrXxsBOwxTLe5/3WJ8zDDbVq129vBLAnRHkjh/+JvlkWXX0EM8UlQOFtIVpvOm81Of3E /rRKh6YrovQafsYpWnzRZ7reoA9BdxIUxe7MmDPADd8pqMn+38zciJ2e2C7jiFnRx7RP j25qRoLfbYHOBtzhLFSOU0EFiA8ZCi/xdUh8ZV3airaj4CGgvqaihJyJ42J3sOEJ/NX4 LFHQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=1xyQ36UIWFFS/twZuZ/fCA3nw+yBYN8W8p1vgqAd1yo=; b=bsyAaqPGolyAd71p9n7bgSz+vejz9hsIwlffN3QWkvEwtsjXedFStvYJCGfcsvmk96 hafmwcCSCGmyovd8rtsn5cqMhKYKtvtEjFQkf5PdInqCEACPKUKBKJsnvu+uBtqNPTi0 PzIrZ8VBudbE5tOHdmHvNEhxyZZy0KWdZ0lhF5ye8gxc+T0YfXbWsl52UJo/wz0SL4tC IsKFnXLoHMNUlAbWHsOXUbiZ5dbrEnUdn8Ta1bUQe0CxMnc6Tg4V+TX1aZbXb+s2TDWN jzqSd/+0DAB2FMMVQCua5e2WAq9AT26UVfbWQWEq22t6OVmuYs3N2hi8qT6lfR91A1mE VW3w== X-Gm-Message-State: ACrzQf1aXD0/Z3K/j19Cb+2lybsG2fMKSnQFaoAzVWb4gl/DSA7ON2P/ zWB0qdXgNgpg+Not3QRZhNkC+d734+T0uQ== X-Google-Smtp-Source: AMsMyM62rE5jBzS+d7Ww5z5MHQpbQFdQjr8+duHYxALdibHjJhZSMbZEseL0xTkuuZyit3inQJQE8A== X-Received: by 2002:a17:907:62a1:b0:781:b320:90c0 with SMTP id nd33-20020a17090762a100b00781b32090c0mr4159312ejc.255.1665152965519; Fri, 07 Oct 2022 07:29:25 -0700 (PDT) Original-Received: from Mini.fritz.box (pd9e36c8d.dip0.t-ipconnect.de. [217.227.108.141]) by smtp.gmail.com with ESMTPSA id r9-20020a1709061ba900b00782cd82db09sm1297866ejg.106.2022.10.07.07.29.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 07 Oct 2022 07:29:24 -0700 (PDT) In-Reply-To: (Stefan Monnier's message of "Fri, 07 Oct 2022 09:33:47 -0400") Received-SPF: pass client-ip=2a00:1450:4864:20::62c; envelope-from=gerd.moellmann@gmail.com; helo=mail-ej1-x62c.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:297158 Archived-At: Stefan Monnier writes: >> to allow C++. With std::multimap/std::multiset, we would have a >> ready-made complete solution for the tree, tested by a gazillion of >> users. Just dreaming :-)) > > I'm not familiar with C++ libs: does this `multiset` lib offer something > similar to the lazy update of buffer positions that Andreas's code uses > (via the `offset` field together with the `interval_tree_inherit_offset` > function)? No, just the tree-part, or better said not the tree directly. These implement an abstraction of an ordered set, or multiset (containing an element more than once), or map of (key, value) pairs, or multimap (multiple (key, value) pairs with the same key. Because of the complexities that the C++ standard guarantees, libstc++ uses rb-trees for the implmentation. There are also unordered forms of these concepts, using hash-tables under the hood. https://cplusplus.com/reference/stl/ The rest would have to be built on top, using that. std::multimap::iterator for example, would be an in-order iteration over the key or (key, value) pairs. C++ iterators are modelled after pointers (++, --, *). And there are a number of algorithms defined in C++ like lower_bound, equal_range, upper_bound and so on that work on pointer-like iterators, or real C pointers for that matter. https://en.cppreference.com/w/cpp/algorithm That's probably not a good explanation, sorry :-/.