Hi,
I am pleased to announce the 0.0.12 release of data.avl, a Clojure
Contrib library providing drop-in replacements for Clojure(Script)'s
built-in sorted maps and sets with additional functionality:
1. real (non-view) logarithmic-time slicing and splits;
2. logarithmic-time nearest neighbour lookups and rank queries;
3. support for transients.
This release is identical to 0.0.12-alpha1 except for the fact that
the Vars clojure.data.avl/empty-{set,map}-hash{eq,code} are now marked
private, as they should be.
Changes since 0.0.11 include an important fix to the rebalancing
algorithm, so I would strongly advise all users of 0.0.11 to upgrade
as soon as possible. There are also several new additions to the API,
on which more below.
[org.clojure/data.avl "0.0.12"]
<dependency>
<groupId>org.clojure</groupId>
<artifactId>data.avl</artifactId>
<version>0.0.12</version>
</dependency>
org.clojure:data.avl:0.0.12
The following transcript of a REPL session includes calls to each of
the new public functions:
(require '[clojure.data.avl :as avl])
(avl/nearest (avl/sorted-set 0 1 2) < 2)
;= 1
(avl/subrange (avl/sorted-set 0 1 2 3 4 5) >= 1 < 4)
;= #{1 2 3}
(avl/split-at 2 (avl/sorted-set 0 1 2 3 4 5))
;= [#{0 1} #{2 3 4 5}]
(avl/split-key 3 (avl/sorted-set 0 2 4 6))
;= [#{0 2} nil #{4 6}]
All of these functions operate in time logarithmic in the size of
their inputs. avl/subrange returns a data.avl collection of the same
type as its input and completely independent from it -- that is, it
shares structure with the input where possible, but does not hold on
to any parts of the tree containing keys that should not be present in
the output. avl/split-at and avl/split-key return similarly
independent data.avl collections; the middle element of the vector
returned by split-key is the element at the split key if present in
the input, nil otherwise.
"split" is the name usually applied in the literature to the operation
that splits a tree into a "left" tree, a middle element and a "right"
tree. "subrange" could also be called "slice". The split-* functions
take their collection argument last to be consistent with
clojure.core's split-at and split-with. Arguments accepted by subrange
are analogous to those taken by subseq/rsubseq.
Many thanks to the two new contributors to this release (listed here
in chronological order of ticket creation): Pepijn de Vos, who
prompted me to develop the above-mentioned new features by creating
the ticket asking for what is now avl/nearest and mentioning
java.util.Navigable{Map,Set}, and who provided new tests for
avl/nearest; and Andy Fingerhut, who kept on top of the hashing
changes and provided the initial implementation of new-style hasheq
for data.avl with further tests.
Cheers,
Michał
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
