From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Barry OReilly Newsgroups: gmane.emacs.devel Subject: Re: Integration of undo-tree in Emacs Date: Fri, 30 May 2014 08:00:40 -0400 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=089e011824a85b7e9e04fa9ccba9 X-Trace: ger.gmane.org 1401451264 2541 80.91.229.3 (30 May 2014 12:01:04 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 30 May 2014 12:01:04 +0000 (UTC) Cc: toby-undo-tree , emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri May 30 14:00:53 2014 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WqLUS-0003I1-Rx for ged-emacs-devel@m.gmane.org; Fri, 30 May 2014 14:00:53 +0200 Original-Received: from localhost ([::1]:53666 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WqLUS-0001kd-8O for ged-emacs-devel@m.gmane.org; Fri, 30 May 2014 08:00:52 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:38063) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WqLUO-0001kC-K0 for emacs-devel@gnu.org; Fri, 30 May 2014 08:00:49 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WqLUH-0007WB-MS for emacs-devel@gnu.org; Fri, 30 May 2014 08:00:48 -0400 Original-Received: from mail-oa0-x22e.google.com ([2607:f8b0:4003:c02::22e]:36551) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WqLUH-0007VN-GW for emacs-devel@gnu.org; Fri, 30 May 2014 08:00:41 -0400 Original-Received: by mail-oa0-f46.google.com with SMTP id g18so1717994oah.5 for ; Fri, 30 May 2014 05:00:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=THo5PfyuV8JNQC9e6XO3nEChX9Qu0RjlJlcVaLO7eXM=; b=gjq/ytexot2Btnuxp+zjdtX5up2waqTCqre8SGb9wUoQWTZY0ixvCQX/rzWRCqcOOr 5Biq1iA//v72XBKHrZhn/DftL8uITGz8TMwFe2B+qjWRzd/lS74abHt+wclHvHa7s7RH +6GFREfnksmEvTQVhdvzMfxOKuRZXVnSmUcqqOi2n8L4JKfZakWQXL95KkFbB1zpfXUZ wgMhDCfWR9YMOgq8nWBQPHRvSOXal5KnwGaA8lDxmZposoO+BPF4aC6aCg+utmbNoymf N7CSAGTgCUcrTUPIo7kA4w319mutyjg2f8FUBiW0OMByIFRXH7gDTuuR+E41vicuobqz MubA== X-Received: by 10.60.174.80 with SMTP id bq16mr16688222oec.14.1401451240453; Fri, 30 May 2014 05:00:40 -0700 (PDT) Original-Received: by 10.76.6.44 with HTTP; Fri, 30 May 2014 05:00:40 -0700 (PDT) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:4003:c02::22e X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 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.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:172192 Archived-At: --089e011824a85b7e9e04fa9ccba9 Content-Type: text/plain; charset=UTF-8 > For every branch in a tree, the undo-list keeps 2 bundles (one going > forward and the other going back), but one of the two is always > redundant, so the representation is inefficient. Yes, makes sense. So the code wouldn't trim every undo/redo pair but just those that don't lose information about the other branches that exist. So if the user goes up and down a branch twice, we only trim out one round trip. > Note that the set of reachable nodes is reduced in the same order as > in the case of undo-tree. The difference is in how these are mapped > to a tree. To a large extent the difference is in "which node is > taken to be the root". If you always take "the most recent state" > as the root of the tree (instead of the oldest), then both > techniques are "stable" and behave "identically". You lost me at "the most recent state as the root". If you mean most recently created, that is a leaf node. If you mean most recently visited, that is the user's current node and is not necessarily the root either. > So A is first in line for truncation followed by E, B, C, D. My mistake: that should have been A, D, C, B, E. (I think undo-tree's right-to-left ordering of branches threw me off.) --089e011824a85b7e9e04fa9ccba9 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
> For every branch in a tree, the undo-list keeps 2 bun= dles (one going
> forward and the other going back), but one of the t= wo is always
> redundant, so the representation is inefficient.
Yes, makes sense. So the code wouldn't trim every undo/redo pair butjust those that don't lose information about the other branches thatexist. So if the user goes up and down a branch twice, we only trim
out one round trip.

> Note that the set of reachable nodes is red= uced in the same order as
> in the case of undo-tree.=C2=A0 The diffe= rence is in how these are mapped
> to a tree.=C2=A0 To a large extent= the difference is in "which node is
> taken to be the root".=C2=A0 If you always take "the most re= cent state"
> as the root of the tree (instead of the oldest), t= hen both
> techniques are "stable" and behave "identic= ally".

You lost me at "the most recent state as the root". If you me= an most
recently created, that is a leaf node. If you mean most recently=
visited, that is the user's current node and is not necessarily the=
root either.

> So A is first in line for truncation followed by E= , B, C, D.

My mistake: that should have been A, D, C, B, E. (I think= undo-tree's
right-to-left ordering of branches threw me off.)

--089e011824a85b7e9e04fa9ccba9--