cowtreedict

An immutable, copy-on-write (COW) sorted dictionary for Python with O(log n) order-statistic operations.

Why This Exists

No Python package on PyPI provides all four of these properties together:

COWTreeDict fills this gap. If you need a sorted dict that is also immutable, hashable, and supports positional access — this is it.

Motivation

• sortedcontainers gives you sorted + order statistics, but it's mutable. Sharing state across versions requires explicit deep copies — O(n) per snapshot.
• pyrsistent gives you persistence + hashability, but it's hash-based and unordered. No sorted iteration, no "what's the k-th smallest key?".
• immutables (from the EdgeDB team) gives you a fast persistent mapping, but again unsorted and not even hashable.

If you want persistent + sorted + positional access + hashable in Python, you had to roll your own. Now you don't.

Languages like Clojure (sorted-map), Scala (TreeMap), and Haskell (Data.Map) have had this in their standard libraries for years. Python didn't — until now.

Installation

pip install cowtreedict

Example Usage

from cowtreedict import COWTreeDict

# Construction (same interface as frozen_odict() plus lt)
d = COWTreeDict({'c': 3, 'a': 1, 'b': 2})

# Keys are always sorted
list(d)  # ['a', 'b', 'c']

# Mutations return new instances — the original is never modified
d2 = d.set('d', 4)
d3 = d2.delete('a')
list(d)   # ['a', 'b', 'c']     — unchanged
list(d3)  # ['b', 'c', 'd']

# Order-statistic operations in O(log n)
d.select(0)       # 'a' — smallest key
d.select(-1)      # 'c' — largest key
d.rank('b')       # 1   — number of keys < 'b'
d.peekitem(0)     # ('a', 1) — item at position 0
d.peekitem(-1)    # ('c', 3) — last item

# Range iteration in O(log n + k)
list(d.irange('a', 'b'))                            # ['a', 'b']
list(d.irange('a', 'c', inclusive=(False, False)))  # ['b']

# Hashable — can be used as dict keys or in sets
cache = {d: 'result'}
cache[COWTreeDict({'a': 1, 'b': 2, 'c': 3})]  # 'result'

# Structural sharing minimizes memory
# d and d2 share all nodes except those on the path to 'd'

Use Cases

• Functional-style programming — chain transformations without defensive copying.
• Undo/redo — keep a stack of previous versions at near-zero cost.
• Event sourcing / temporal versioning — each event produces a new version; all versions are queryable.
• Concurrent reads — no locks needed since instances are immutable.
• Sorted dicts as dict keys or set elements — because COWTreeDict is hashable.
• Competitive programming — O(log n) rank and select without pulling in C extensions.

API Reference

Construction

COW-Mutating Methods

All return a new instance. The original is never modified.

Mapping (Read) Methods

Order-Statistic Operations

Range Operations

How It Works

COWTreeDict is backed by an AVL tree augmented with subtree sizes for O(log n) positional access.

Path copying provides persistence: when a key is inserted or deleted, only the nodes on the path from the root to the affected leaf are copied (O(log n) nodes). All other nodes are shared between the old and new tree.

Original:           After d.set('f', 6):

      c                    c'
     / \                  / \
    a   e     →         a   e'       (only c, e, f are new nodes)
       / \                 / \
      d   (nil)           d   f      (a and d are shared)

This means:

• Each mutation allocates only O(log n) new node objects.
• Old versions remain valid and accessible with zero overhead.
• Memory usage grows linearly with the number of distinct mutations, not with the total number of versions.

Part of the COW Family

COWTreeDict is designed alongside cowlist to form a coherent family of persistent Python collections:

Both are immutable, hashable, and share the same conventions (__new__-only construction, cached tuplehash, COW mutation methods returning new instances).

Dependencies

• tuplehash — Pure Python reimplementation of CPython's tuplehash for computing hash values without materializing intermediate tuples.

Contributing

Contributions are welcome! Please submit pull requests or open issues on the GitHub repository.

License

This project is licensed under the Apache License 2.0.