GNU bug report logs - #5012
avl-tree.el enhancements

Previous Next

Full log

View this message in rfc822 format

From: Toby Cubitt <tsc25 <at> cantab.net>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>, bug-gnu-emacs <at> gnu.org
Subject: bug#5012: avl-tree.el enhancements
Date: Mon, 23 Nov 2009 00:01:23 +0000

[Message part 1 (text/plain, inline)]

Attached is a sequence of two patches for avl-tree.el, implementing the
enhancements to that library that I posted a while ago to the
gnu-emacs-sources list.

The first patch, avl-tree.el.1.diff, simplifies some of the avl-tree.el
functions, reducing code redundancy. These changes also make it natural
to add an optional argument to `avl-tree-map' specifying the order in
which to map over the tree.

The second patch, avl-tree.el.2.diff, contains the feature
enhancements. It adds optional arguments to a number of functions, and
adds a number of new functions. The new optional argument to
`avl-tree-member' allows it to distinguish a non-existence element from
an element of the tree with null data. The new optional argument to
`avl-tree-enter' allows data in the tree to be updated without having to
first search for it and then enter the new data (a factor of 2 difference
in efficiency). Similarly, the new optional argument to `avl-tree-delete'
allows data to be deleted if it satisfies some predicate (another factor
of 2 in efficiency). The patch also adds new mapping functions, and new
functions for accessing the tree elements as though they were a stack
(which for some purposes can be more efficient than mapping over the tree
of flattening it).

Note that, as the only changes to the existing function interfaces are
additional optional arguments, any code using avl-tree.el will remain
compatible with the modified version.

I've initiated the copyright paperwork process, so hopefully you should
have everything you need soon.

Toby Cubitt

[avl-tree.el.1.diff (text/plain, attachment)]

[avl-tree.el.2.diff (text/plain, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.