0.0.9 docs





    Nov 1, 2013

    Michał Marczyk


    Index of all namespaces

    « Project + dependencies

    Persistent sorted maps and sets with log-time rank queries

    An implementation of persistent sorted maps and sets based on AVL
    trees with API mimicking that of Clojure's sorted maps and
    sets (based on Red-Black Trees). Additionally, the provided map and
    set types support the transients API and logarithmic time rank
    queries via clojure.core/nth (select element by rank) and
    avl.clj/rank-of (discover rank of element).
    The README below is fetched from the published project artifact. Some relative links may be broken.


    Persistent sorted maps and sets with support for transients and logarithmic time rank queries (via clojure.core/nth and avl.clj/rank-of), using AVL trees as the underlying data structure.


    avl.clj supports Clojure and ClojureScript. It exports a single namespace with five public functions, four of which are drop-in replacements for clojure.core / cljs.core functions of the same names:

    (require '[avl.clj :as avl])
    (doc avl/sorted-map)
    (doc avl/sorted-map-by)
    (doc avl/sorted-set)
    (doc avl/sorted-set-by)

    The fifth function finds the rank of the given element in an AVL map or set (-1 if not found):

    (doc avl/rank-of)

    The maps and sets returned by these functions behave like the core Clojure variants, with two differences:

    1. they have transient counterparts:

      (persistent! (assoc! (transient (avl/sorted-map) 0 0)))
      ;= {0 0}

    and use transients during construction:

        (apply avl/sorted-map (interleave (range 32) (range 32)))
        ;; ^- uses transients
    1. they support logarithmic time rank queries via clojure.core/nth and avl.clj/rank-of:

      (nth (avl/sorted-map 0 0 1 1 2 2) 1)
      ;= [1 1]
      (nth (avl/sorted-set 0 1 2) 1)
      ;= 1
      (avl/rank-of (avl/sorted-map-by > 0 0 1 1 2 2) 0)
      (avl/rank-of (avl/sorted-set-by > 0 1 2) 0)

    Releases and dependency information

    avl.clj releases are available from Clojars. Please follow the link to discover the current release number.

    Leiningen dependency information:

    [avl.clj "${version}"]

    Maven dependency information:


    Developer information

    Please note that patches will only be accepted from developers who have submitted the Clojure CA and would be happy with the code they submit to avl.clj becoming part of the Clojure project.

    Clojure(Script) code reuse

    avl.clj sorted maps and sets support the same basic functionality regular Clojure’s sorted maps and sets do (with the additions listed above). Some of the code supporting various Clojure(Script) interfaces and protocols is adapted from the ClojureScript implementations of the red-black-tree-based sorted collections, which themselves are ports of Clojure’s implementations written in Java. The Clojure(Script) source files containing the relevant code carry the following copyright notice:

    Copyright (c) Rich Hickey. All rights reserved.
    The use and distribution terms for this software are covered by the
    Eclipse Public License 1.0 (
    which can be found in the file epl-v10.html at the root of this distribution.
    By using this software in any fashion, you are agreeing to be bound by
      the terms of this license.
    You must not remove this notice, or any other, from this software.


    Copyright © 2013 Michał Marczyk

    Distributed under the Eclipse Public License, the same as Clojure.