# `gno.land/p/moul/cow`

A copy-on-write AVL tree: a fork of
[`p/nt/avl`](https://github.com/gnolang/gno/tree/master/examples/gno.land/p/nt/avl)
with the same API, plus **O(1) cloning**.

```go
t := cow.NewTree()
t.Set("a", 1)

snapshot := t.Clone()   // O(1): shares every node with t
t.Set("b", 2)           // only the root-to-"b" path is copied
```

`Clone` copies a pointer. Both trees then present as full independent copies,
but they share structure until one of them is written to, and a write only
copies the nodes along the path from the root to the modified node: O(log n)
new nodes, not O(n).

## What it is for

On chain, the storage bill follows what changed. A snapshot taken by copying an
avl tree writes the whole tree; a snapshot taken by `Clone` writes nothing.
That makes cheap versioning practical: a proposal that must be evaluated
against the state at submission time, an undo point before a batch, a
before/after diff, a speculative apply you might throw away.

## The one thing to get right

Structural sharing is automatic. **Value copying is not.**

- Simple values (`int`, `string`, ...) are copied by value. Nothing to do.
- Structs and pointers are copied by reference. Mutating the pointed-to value
  through one tree mutates what the other tree sees, which is exactly the bug
  copy-on-write was supposed to prevent.

If your values are mutable, store an immutable representation or deep-copy on
write yourself. The tree cannot do it for you.

## API

Same as `p/nt/avl`. On `Tree`: `Set`, `Get`, `Has`, `Remove`, `Size`,
`GetByIndex`, `Iterate`, `ReverseIterate`, `IterateByOffset`,
`ReverseIterateByOffset`, plus `Clone`. `Node` additionally exposes
`TraverseInRange` and `TraverseByOffset` for walking inner nodes.

`Equal` (on either type) is a full recursive structural comparison. It is there
for tests: do not call it from realm code.

<!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) -->

---

Part of **[moul/gno-contracts](https://github.com/moul/gno-contracts)** — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

> ⚠️ **Disclaimer:** provided as-is, without warranty; not security-audited. Full disclaimer: [DISCLAIMER](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md).

<!-- END GNOCONTRACTS FOOTER -->