持久化数据结构：函数式世界的基石

class FatNode:
    def __init__(self, key):
        self.key = key
        self.left_history = []   # [(version, left_child), ...]
        self.right_history = []  # [(version, right_child), ...]

    def get_left(self, version):
        """获取指定版本的左子节点"""
        result = None
        for v, child in self.left_history:
            if v <= version:
                result = child
            else:
                break
        return result

    def set_left(self, version, child):
        self.left_history.append((version, child))

;; 伪代码：查找索引 i 的元素
(defn tree-lookup [root i depth]
  (if (leaf? root)
    (aget root (bit-and i 0x1f))        ;; 取最低 5 位
    (let [slot (bit-and (unsigned-bit-shift-right i (* depth 5)) 0x1f)]
      (recur (aget root slot) i (dec depth)))))

public Object nth(int i) {
    Object[] node = root;
    for (int level = shift; level > 0; level -= 5) {
        node = (Object[]) node[(i >>> level) & 0x1f];
    }
    return node[i & 0x1f];
}

public PersistentVector assocN(int i, Object val) {
    if (i >= tailoff()) {
        // 修改在 tail 中，复制 tail 即可
        Object[] newTail = tail.clone();
        newTail[i & 0x1f] = val;
        return new PersistentVector(count, shift, root, newTail);
    }
    // 修改在主树中，需要路径复制
    Object[] newRoot = doAssoc(shift, root, i, val);
    return new PersistentVector(count, shift, newRoot, tail);
}

private Object[] doAssoc(int level, Object[] node, int i, Object val) {
    Object[] ret = node.clone();  // 复制当前节点
    if (level == 0) {
        ret[i & 0x1f] = val;
    } else {
        int subidx = (i >>> level) & 0x1f;
        ret[subidx] = doAssoc(level - 5, (Object[]) node[subidx], i, val);
    }
    return ret;
}

data Color = R | B
data RBTree a = E | T Color (RBTree a) a (RBTree a)

balance :: Color -> RBTree a -> a -> RBTree a -> RBTree a
-- 四种不平衡情况统一处理
balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance color a x b                  = T color a x b

insert :: Ord a => a -> RBTree a -> RBTree a
insert x s = makeBlack (ins s)
  where
    ins E = T R E x E
    ins (T color a y b)
      | x < y    = balance color (ins a) y b
      | x > y    = balance color a y (ins b)
      | otherwise = T color a y b
    makeBlack (T _ a y b) = T B a y b

data Color = R | B | BB  -- BB = double black

-- 删除的核心：处理双重黑色节点
bubble :: Color -> RBTree a -> a -> RBTree a -> RBTree a
bubble color left x right
  | isBB left || isBB right =
      balance (blacker color) (redder left) x (redder right)
  | otherwise = balance color left x right

# 查看一个 commit 对象的结构
$ git cat-file -p HEAD
tree 4b825dc642cb6eb9a060e54bf899d8e244f6ee8f
parent a1b2c3d4e5f6...
author ltl <ltl@example.com> 1713792000 +0800
committer ltl <ltl@example.com> 1713792000 +0800

Add persistent data structure article

# 查看 tree 对象
$ git cat-file -p 4b825dc6...
100644 blob a906cb2a...    README.md
040000 tree 9fb6e3e2...    src
100644 blob 1f7a7a47...    Makefile

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ========== 持久化 AVL 树 ========== */

typedef struct Node {
    int key;
    int height;
    struct Node *left;
    struct Node *right;
} Node;

/* 创建新节点 */
static Node *node_new(int key, Node *left, Node *right) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    n->key = key;
    n->left = left;
    n->right = right;
    int lh = left ? left->height : 0;
    int rh = right ? right->height : 0;
    n->height = 1 + (lh > rh ? lh : rh);
    return n;
}

/* 复制节点（路径复制的基本操作） */
static Node *node_copy(const Node *src) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    memcpy(n, src, sizeof(Node));
    return n;
}

static int height(const Node *n) {
    return n ? n->height : 0;
}

static int balance_factor(const Node *n) {
    if (!n) return 0;
    return height(n->left) - height(n->right);
}

static void update_height(Node *n) {
    int lh = height(n->left);
    int rh = height(n->right);
    n->height = 1 + (lh > rh ? lh : rh);
}

/* 持久化右旋：返回新子树根，不修改原节点 */
static Node *rotate_right(const Node *y) {
    const Node *x = y->left;
    Node *new_x = node_copy(x);
    Node *new_y = node_copy(y);
    new_y->left = new_x->right;
    update_height(new_y);
    new_x->right = new_y;
    update_height(new_x);
    return new_x;
}

/* 持久化左旋 */
static Node *rotate_left(const Node *x) {
    const Node *y = x->right;
    Node *new_y = node_copy(y);
    Node *new_x = node_copy(x);
    new_x->right = new_y->left;
    update_height(new_x);
    new_y->left = new_x;
    update_height(new_y);
    return new_y;
}

/* 平衡操作：对路径复制后的新节点进行平衡 */
static Node *do_balance(Node *n) {
    update_height(n);
    int bf = balance_factor(n);

    if (bf > 1) {
        if (balance_factor(n->left) < 0) {
            n->left = rotate_left(n->left);
        }
        return rotate_right(n);
    }
    if (bf < -1) {
        if (balance_factor(n->right) > 0) {
            n->right = rotate_right(n->right);
        }
        return rotate_left(n);
    }
    return n;
}

/* 持久化插入：返回新树的根，原树不变 */
Node *persistent_insert(const Node *root, int key) {
    if (!root) {
        return node_new(key, NULL, NULL);
    }

    Node *new_node = node_copy(root);

    if (key < root->key) {
        new_node->left = persistent_insert(root->left, key);
    } else if (key > root->key) {
        new_node->right = persistent_insert(root->right, key);
    } else {
        return new_node;  /* 键已存在，返回副本 */
    }

    return do_balance(new_node);
}

/* 查找最小节点 */
static const Node *find_min(const Node *n) {
    while (n->left) n = n->left;
    return n;
}

/* 持久化删除：返回新树的根，原树不变 */
Node *persistent_delete(const Node *root, int key) {
    if (!root) return NULL;

    Node *new_node = node_copy(root);

    if (key < root->key) {
        new_node->left = persistent_delete(root->left, key);
    } else if (key > root->key) {
        new_node->right = persistent_delete(root->right, key);
    } else {
        /* 找到要删除的节点 */
        if (!root->left) {
            free(new_node);
            return root->right ? node_copy(root->right) : NULL;
        }
        if (!root->right) {
            free(new_node);
            return node_copy(root->left);
        }
        /* 双子节点：用右子树最小值替换 */
        const Node *successor = find_min(root->right);
        new_node->key = successor->key;
        new_node->right = persistent_delete(root->right, successor->key);
    }

    return do_balance(new_node);
}

/* 查找 */
int persistent_search(const Node *root, int key) {
    while (root) {
        if (key < root->key) root = root->left;
        else if (key > root->key) root = root->right;
        else return 1;
    }
    return 0;
}

/* 中序遍历 */
void inorder(const Node *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}

/* 统计节点数 */
int count_nodes(const Node *root) {
    if (!root) return 0;
    return 1 + count_nodes(root->left) + count_nodes(root->right);
}

/* 释放整棵树（注意：有结构共享时需要引用计数或 GC） */
void free_tree(Node *root) {
    if (!root) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

/* ========== 版本管理 ========== */

#define MAX_VERSIONS 1024

typedef struct VersionStore {
    Node *roots[MAX_VERSIONS];
    int count;
} VersionStore;

void vs_init(VersionStore *vs) {
    vs->count = 0;
    memset(vs->roots, 0, sizeof(vs->roots));
}

int vs_save(VersionStore *vs, Node *root) {
    if (vs->count >= MAX_VERSIONS) {
        fprintf(stderr, "version store full\n");
        return -1;
    }
    int ver = vs->count;
    vs->roots[vs->count++] = root;
    return ver;
}

Node *vs_get(const VersionStore *vs, int version) {
    if (version < 0 || version >= vs->count) return NULL;
    return vs->roots[version];
}

/* ========== 测试程序 ========== */

int main(void) {
    VersionStore vs;
    vs_init(&vs);

    /* 版本 0：空树 */
    Node *tree = NULL;
    vs_save(&vs, tree);

    /* 版本 1：插入 10, 20, 5, 15, 30 */
    int keys[] = {10, 20, 5, 15, 30, 3, 7, 25, 35, 12};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        tree = persistent_insert(tree, keys[i]);
    }
    int v1 = vs_save(&vs, tree);

    printf("Version %d: ", v1);
    inorder(vs_get(&vs, v1));
    printf(" (%d nodes)\n", count_nodes(vs_get(&vs, v1)));

    /* 版本 2：删除 20 */
    Node *tree2 = persistent_delete(tree, 20);
    int v2 = vs_save(&vs, tree2);

    printf("Version %d: ", v2);
    inorder(vs_get(&vs, v2));
    printf(" (%d nodes)\n", count_nodes(vs_get(&vs, v2)));

    /* 版本 3：在版本 1 的基础上插入 100 */
    Node *tree3 = persistent_insert(vs_get(&vs, v1), 100);
    int v3 = vs_save(&vs, tree3);

    printf("Version %d: ", v3);
    inorder(vs_get(&vs, v3));
    printf(" (%d nodes)\n", count_nodes(vs_get(&vs, v3)));

    /* 验证版本 1 未被修改 */
    printf("Version %d (unchanged): ", v1);
    inorder(vs_get(&vs, v1));
    printf(" (%d nodes)\n", count_nodes(vs_get(&vs, v1)));

    /* 搜索测试 */
    printf("\nSearch 20 in v1: %s\n", persistent_search(vs_get(&vs, v1), 20) ? "found" : "not found");
    printf("Search 20 in v2: %s\n", persistent_search(vs_get(&vs, v2), 20) ? "found" : "not found");
    printf("Search 100 in v1: %s\n", persistent_search(vs_get(&vs, v1), 100) ? "found" : "not found");
    printf("Search 100 in v3: %s\n", persistent_search(vs_get(&vs, v3), 100) ? "found" : "not found");

    return 0;
}

gcc -O2 -Wall -o persistent_avl persistent_avl.c
./persistent_avl

data Queue a = Queue [a] [a]

-- 入队：追加到后端列表
enqueue :: a -> Queue a -> Queue a
enqueue x (Queue front rear) = check (Queue front (x:rear))

-- 出队：从前端列表取
dequeue :: Queue a -> (a, Queue a)
dequeue (Queue (x:front) rear) = (x, check (Queue front rear))

-- 当前端为空时，翻转后端
check :: Queue a -> Queue a
check (Queue [] rear) = Queue (reverse rear) []
check q = q

-- 攻击性使用模式
let q = enqueue_many n empty  -- 构造 n 个元素的队列
-- q 的前端为空，下一次 dequeue 会触发 reverse
let (x1, q1) = dequeue q     -- O(n) reverse
let (x2, q2) = dequeue q     -- 又是 O(n) reverse！同一个 q！
let (x3, q3) = dequeue q     -- 再一次 O(n)！

-- 使用惰性列表的队列（Banker's Queue）
data Queue a = Queue Int [a] Int [a]
  -- 维护不变量: |front| >= |rear|
  -- [a] 是惰性列表（Haskell 默认惰性）

check :: Queue a -> Queue a
check (Queue flen front rlen rear)
  | rlen <= flen = Queue flen front rlen rear
  | otherwise    = Queue (flen + rlen) (front ++ reverse rear) 0 []
  -- front ++ reverse rear 是惰性的，不会立即执行

data Queue a = Queue [a] [a] [a]
  -- Queue front rear schedule
  -- schedule 是 front 的一个旋转副本，用于驱动增量求值

rotate :: [a] -> [a] -> [a] -> [a]
rotate []     [y]    acc = y : acc
rotate (x:xs) (y:ys) acc = x : rotate xs ys (y : acc)

exec :: Queue a -> Queue a
exec (Queue front rear (_:schedule)) = Queue front rear schedule
exec (Queue front rear []) = let f' = rotate front rear []
                             in Queue f' [] f'

enqueue :: a -> Queue a -> Queue a
enqueue x (Queue front rear schedule) = exec (Queue front (x:rear) schedule)

dequeue :: Queue a -> (a, Queue a)
dequeue (Queue (x:front) rear schedule) = (x, exec (Queue front rear schedule))

;; 查询数据库在特定时间点的状态
(let [db-yesterday (d/as-of (d/db conn) #inst "2026-04-21")]
  (d/q '[:find ?name
          :where [?e :user/name ?name]]
        db-yesterday))

(def state (atom {:users [] :count 0}))

;; swap! 使用 CAS 循环，持久化数据结构保证了无锁更新
(swap! state (fn [s]
  (-> s
      (update :users conj "Alice")
      (update :count inc))))

;; 旧的 state 快照仍然可用——不会有 ABA 问题

val v1 = Vector(1, 2, 3, 4, 5)
val v2 = v1 :+ 6          // O(~1)，结构共享
val v3 = v1.updated(2, 99) // O(~1)，路径复制

// v1 仍然是 (1, 2, 3, 4, 5)
assert(v1(2) == 3)
assert(v3(2) == 99)

import qualified Data.Map.Strict as Map

let m1 = Map.fromList [("a", 1), ("b", 2), ("c", 3)]
let m2 = Map.insert "d" 4 m1
let m3 = Map.delete "b" m1

-- m1 不变: fromList [("a",1),("b",2),("c",3)]
-- m2: fromList [("a",1),("b",2),("c",3),("d",4)]
-- m3: fromList [("a",1),("c",3)]

// 一个简单的 G-Counter CRDT
interface GCounter {
    readonly nodeId: string;
    readonly counts: ReadonlyMap<string, number>;  // 不可变！
}

function increment(counter: GCounter): GCounter {
    const newCounts = new Map(counter.counts);  // 结构共享的 Map
    newCounts.set(counter.nodeId,
        (counter.counts.get(counter.nodeId) || 0) + 1);
    return { nodeId: counter.nodeId, counts: newCounts };
}

function merge(a: GCounter, b: GCounter): GCounter {
    const merged = new Map(a.counts);
    for (const [node, count] of b.counts) {
        merged.set(node, Math.max(merged.get(node) || 0, count));
    }
    return { nodeId: a.nodeId, counts: merged };
}

// 方案一：引用计数
typedef struct RCNode {
    int refcount;
    int key;
    struct RCNode *left, *right;
} RCNode;

void rc_retain(RCNode *n) {
    if (n) n->refcount++;
}

void rc_release(RCNode *n) {
    if (!n) return;
    if (--n->refcount == 0) {
        rc_release(n->left);
        rc_release(n->right);
        free(n);
    }
}

// 方案二：Arena 分配器（适合版本生命周期明确的场景）
typedef struct Arena {
    char *base;
    size_t offset;
    size_t capacity;
} Arena;

void *arena_alloc(Arena *a, size_t size) {
    if (a->offset + size > a->capacity) return NULL;
    void *ptr = a->base + a->offset;
    a->offset += size;
    return ptr;
}

// 当某个版本不再需要时，可以整体释放 arena
void arena_reset(Arena *a) {
    a->offset = 0;
}

use std::rc::Rc;

#[derive(Clone)]
enum PList<T: Clone> {
    Nil,
    Cons(T, Rc<PList<T>>),
}

impl<T: Clone> PList<T> {
    fn prepend(&self, val: T) -> PList<T> {
        PList::Cons(val, Rc::new(self.clone()))
    }
}