12 O Libro de Ridgun
A lib btree — Árbores AVL Persistentes $O(\log N)$, Conxuntos e Montículos
12.1. Por que existe a lib btree? (O problema real e a filosofía Ridgun)
«Por que necesito unha lib
btreeescrita dende cero en Ridgun puro en vez de enlazar unha librería de C de toda a vida?»
Esa é a primeira pregunta que se fai calquera enxeñeiro de sistemas ao chegar a btree. E a resposta resume toda a filosofía de ridgun-libs:
Sexamos sinceros: as táboas hash mutables sofren ataques de colisión de chaves (HashDoS), non manteñen as chaves ordenadas para consultas por rango e non se poden compartir entre actores sen copialas enteiras ou meter un cadeado.
A lib btree implementa tres estruturas de datos funcionais persistentes en $O(\log N)$ con compartición estrutural: BTreeMap (árbore AVL autobalanceada), BTreeSet (álxebra de conxuntos ordenada) e MinHeap (fila de prioridade leftist heap).
Nun ecosistema tradicional, resolver as tarefas do dominio BTREE implica arrastrar dependencias externas en C, loitar con punteiros crus, conversións opacas de tipos, excepcións non verificadas ou pausas impredicibles do colector de lixo. En Ridgun, a lib btree (src/main/ridgun/lib/btree.rg) aborda o problema con catro principios innegociables:
- Declara
import btree(ouimport btree as alias) ao inicio do ficheiro: cada lib define o seu espazo de nomesmodule :: btreee en modo--strictas funcións multi-palabra invócanse sempre con espazos naturais. - Encadea as túas tubaxes de esquerda a dereita con
->: escribeentrada paso un -> paso dous -> resultado, usa máscaras(+ _ _ +)para desestruturar secuencias e omite_ =en sentenzas secuenciais (ou descarta con-> ()). - Recursión de cola con TCO (Tail-Call Optimization): todos os percorridos internos de
btreecompílanse a bucles nativos en espazo de pila $O(1)$. - Memoria determinista (
RMM1/RMM2): cada estrutura intermedia libérase no instante exacto en que remata a súa última lectura, sen Garbage Collector.
12.2. Artefactos nativos, importación e catálogo completo da API de btree
En ridgun-libs, btree é unha lib de primeira clase situada en src/main/ridgun/lib/btree.rg (dominio BTREE). Ao compilar con stable bundle, empaquétase en tres formatos nativos:
| Artefacto | Ruta | Propósito |
|---|---|---|
| Bundle Ridgun | target/bundles/btree.rglib | Distribución e importación directa con import btree |
| Ficheiro compilado | target/btree.rgc | Artefacto intermedio verificado por ridgunc |
| Obxecto compartido ELF64 | target/libbtree.so | Biblioteca dinámica nativa sen dependencias de C nin libc |
Cada lib declara o seu propio espazo de nomes con
module :: btree: abonda con escribirimport btree(ouimport btree as alias) na cabeceira e chamar ás súas funcións con espazos naturais (mina funcion x) e tubaxes->(x mina funcion -> resultado).
12.2.1. Resumo de familias funcionais de btree
| Sinatura / Función / Tipo | Que fai e cando usala |
|---|---|
btree empty / btree insert / btree get / btree remove | Busca, inserción e borrado persistente en dicionario AVL en $O(\log N)$ |
btree min key / btree max key / btree range | Extremos ordenados e consulta por rango [lo, hi] |
bset from list / bset union / bset intersect / bset diff | Álxebra de conxuntos ordenados (BTreeSet) e predicado de subconxunto |
heap empty / heap push / heap peek / heap pop / heap sort | Fila de prioridade MinHeap (leftist heap) con fusión en $O(\log N)$ |
12.2.2. Catálogo exhaustivo de tipos e sinaturas en src/main/ridgun/lib/btree.rg
A continuación tes o inventario completo de tipos alxébricos (type), operadores (op ::) e sinaturas de funcións (fn ::) definidos en src/main/ridgun/lib/btree.rg (3 tipos, 0 operadores e 54 funcións):
Tipos alxébricos e rexistros (type) de btree:
type BTreeMap = BMapEmpty | BMapNode String String Int BTreeMap BTreeMap
type BTreeSet = BSetEmpty | BSetNode String Int BTreeSet BTreeSet
type MinHeap = HeapEmpty | HeapNode Int String Int MinHeap MinHeap| # | Función / Sinatura (fn ::) | Tipo de Retorno |
|---|---|---|
1 | fn :: bt max Int Int | Int |
2 | fn :: bt str cmp loop String String Int Int Int | Int |
3 | fn :: bt str cmp String String | Int |
4 | fn :: btree empty | BTreeMap |
5 | fn :: btree height BTreeMap | Int |
6 | fn :: bt mk String String BTreeMap BTreeMap | BTreeMap |
7 | fn :: bt bf BTreeMap | Int |
8 | fn :: bt rot right BTreeMap | BTreeMap |
9 | fn :: bt rot left BTreeMap | BTreeMap |
10 | fn :: bt rebalance String String BTreeMap BTreeMap | BTreeMap |
11 | fn :: btree put BTreeMap String String | BTreeMap |
12 | fn :: btree get or BTreeMap String String | String |
13 | fn :: btree get BTreeMap String | String |
14 | fn :: btree has BTreeMap String | Bool |
15 | fn :: bt min pair BTreeMap | (String String) |
16 | fn :: bt pair k (String String) | String |
17 | fn :: bt pair v (String String) | String |
18 | fn :: bt delete root BTreeMap BTreeMap | BTreeMap |
19 | fn :: btree remove BTreeMap String | BTreeMap |
20 | fn :: btree size BTreeMap | Int |
21 | fn :: btree keys BTreeMap | [String] |
22 | fn :: btree values BTreeMap | [String] |
23 | fn :: btree to list BTreeMap | [String String] |
24 | fn :: bt from pairs [String String] BTreeMap | BTreeMap |
25 | fn :: btree from list [String String] | BTreeMap |
26 | fn :: bset empty | BTreeSet |
27 | fn :: bs height BTreeSet | Int |
28 | fn :: bs mk String BTreeSet BTreeSet | BTreeSet |
29 | fn :: bs bf BTreeSet | Int |
30 | fn :: bs rot right BTreeSet | BTreeSet |
31 | fn :: bs rot left BTreeSet | BTreeSet |
32 | fn :: bs rebalance String BTreeSet BTreeSet | BTreeSet |
33 | fn :: bset add BTreeSet String | BTreeSet |
34 | fn :: bset has BTreeSet String | Bool |
35 | fn :: bs min key BTreeSet | String |
36 | fn :: bs delete root BTreeSet BTreeSet | BTreeSet |
37 | fn :: bset remove BTreeSet String | BTreeSet |
38 | fn :: bset size BTreeSet | Int |
39 | fn :: bset to list BTreeSet | [String] |
40 | fn :: bs from strs [String] BTreeSet | BTreeSet |
41 | fn :: bset from list [String] | BTreeSet |
42 | fn :: bset union BTreeSet BTreeSet | BTreeSet |
43 | fn :: bs inter loop [String] BTreeSet BTreeSet | BTreeSet |
44 | fn :: bset intersect BTreeSet BTreeSet | BTreeSet |
45 | fn :: bs diff loop [String] BTreeSet | BTreeSet |
46 | fn :: bset diff BTreeSet BTreeSet | BTreeSet |
47 | fn :: heap empty | MinHeap |
48 | fn :: hp rank MinHeap | Int |
49 | fn :: hp mk Int String MinHeap MinHeap | MinHeap |
50 | fn :: hp merge MinHeap MinHeap | MinHeap |
51 | fn :: heap push MinHeap Int String | MinHeap |
52 | fn :: heap peek MinHeap | (Int String) |
53 | fn :: heap pop MinHeap | (Int String MinHeap) |
54 | fn :: heap size MinHeap | Int |
12.3. Explorando btree a fondo: Exemplos paso a paso de cada funcionalidade
Non abonda con ver a táboa de sinaturas: imos explorar cada unha das funcionalidades da lib btree mediante exemplos progresivos e executables en Ridgun. Comezaremos polas dúas receitas tabulares de uso cotián e despois percorreremos en detalle todos os escenarios funcionais, transformacións e casos límite verificados en src/test/ridgun/test btree.rg.
12.3.1. Exemplo 1: Fluxo principal en estilo tabular con btree
Observa como en Ridgun os signos = e os pasos de transformación con btree quedan aliñados coma unha táboa limpa, sen variables mutables innecesarias nin efectos laterais ocultos:
import btree
fn :: consultar rango precios => [String String]
consultar rango precios =
btree empty -> t0
btree insert t0 "item:10" "Teclado" -> t1
btree insert t1 "item:20" "Monitor" -> t2
btree insert t2 "item:30" "Raton" -> t3
btree range t3 "item:10" "item:25"12.3.2. Exemplo 2: Composición segura e manexo de casos de bordo
Toda función da lib btree está deseñada para compoñerse con gardas booleanas | e co resto das 32 libs de ridgun-libs:
import btree
fn :: despachar urgente => Int String
despachar urgente =
heap empty -> h0
heap push h0 50 "backup-nocturno" -> h1
heap push h1 10 "alerta-seguridad" -> h2
heap push h2 30 "rotar-logs" -> h3
h3 heap peek12.3.3. Exemplo 3: Árbores AVL BTreeMap: inserción con auto-balanceo, busca $O(\log N)$, borrado, percorrido en orde e extremos (min key, max key)
Neste exemplo práctico exploramos de forma exhaustiva como se comporta btree neste bloque funcional, incluíndo entradas estándar, combinacións de parámetros e valores fronteira:
fn :: test btree map avl balance and crud => ()
test btree map avl balance and crud =
m0 = btree empty
assert int equals (btree size m0) 0 "AC1: empty map size 0"
assert int equals (btree height m0) 0 "AC1: empty map height 0"
m1 = btree put m0 "k01" "v1"
m2 = btree put m1 "k02" "v2"
m3 = btree put m2 "k03" "v3"
m4 = btree put m3 "k04" "v4"
m5 = btree put m4 "k05" "v5"
m6 = btree put m5 "k06" "v6"
m7 = btree put m6 "k07" "v7"
m8 = btree put m7 "k08" "v8"
m9 = btree put m8 "k09" "v9"
m10 = btree put m9 "k10" "v10"
m11 = btree put m10 "k11" "v11"
m12 = btree put m11 "k12" "v12"
m13 = btree put m12 "k13" "v13"
m14 = btree put m13 "k14" "v14"
m15 = btree put m14 "k15" "v15"
assert int equals (btree size m15) 15 "AC1: btree size after 15 ascending puts"
assert true ((btree height m15) <= 5) "AC1: AVL tree height <= 5 on 15 sequential ascending keys"
assert str eq (btree get m15 "k08") "v8" "AC1: btree get k08"
assert str eq (btree get or m15 "k99" "def") "def" "AC1: btree get or fallback"
assert true (btree has m15 "k15") "AC1: btree has k15"
assert false (btree has m15 "k00") "AC1: btree has k00 false"
-- Descending insertion order (triggers right-rotations) + RL/LR double rotations
d0 = btree from list [("z", "26"), ("x", "24"), ("v", "22"), ("t", "20"), ("r", "18"), ("u", "21"), ("y", "25")]
assert int equals (btree size d0) 7 "AC1: descending + RL/LR size 7"
assert true ((btree height d0) <= 4) "AC1: descending + RL/LR height <= 4"
assert str eq (bt join strs (btree keys d0)) "r,t,u,v,x,y,z" "AC1: keys in-order after RL/LR rotations"
assert str eq (bt join strs (btree values d0)) "18,20,21,22,24,25,26" "AC1: values in key order"
-- Overwrite existing key preserves size
d_upd = btree put d0 "v" "22_new"
assert int equals (btree size d_upd) 7 "AC1: update existing key preserves size"
assert str eq (btree get d_upd "v") "22_new" "AC1: updated value retrieved"
-- Remove root/two-child node, single-child node, leaf node, and non-existent key
d_rem1 = btree remove d_upd "v"
d_rem2 = btree remove d_rem1 "r"
d_rem3 = btree remove d_rem2 "nonexistent"
assert int equals (btree size d_rem3) 5 "AC1: size after removing 2 existing keys and 1 missing key"
assert false (btree has d_rem3 "v") "AC1: removed two-child node 'v' absent"
assert false (btree has d_rem3 "r") "AC1: removed leaf node 'r' absent"
assert str eq (bt join strs (btree keys d_rem3)) "t,u,x,y,z" "AC1: keys remain strictly sorted after removals"
pairs = btree to list d_rem3
m_rt = btree from list pairs
assert int equals (btree size m_rt) 5 "AC1: btree to/from list round-trip size"
assert str eq (btree get m_rt "y") "25" "AC1: btree to/from list round-trip lookup"
()12.3.4. Exemplo 4: Conxuntos ordenados BTreeSet: álxebra de conxuntos (union, intersect, diff, is subset) e conversión ordenada a lista
Neste exemplo práctico exploramos de forma exhaustiva como se comporta btree neste bloque funcional, incluíndo entradas estándar, combinacións de parámetros e valores fronteira:
fn :: test btree set operations => ()
test btree set operations =
s1 = bset from list ["charlie", "alpha", "bravo", "alpha", "charlie"]
s2 = bset from list ["bravo", "delta", "echo"]
s_empty = bset empty
assert int equals (bset size s1) 3 "AC2: bset deduplicates items"
assert true (bset has s1 "bravo") "AC2: bset has bravo"
assert false (bset has s1 "delta") "AC2: bset has delta false"
assert str eq (bt join strs (bset to list s1)) "alpha,bravo,charlie" "AC2: bset sorted order"
s1_rem = bset remove s1 "bravo"
assert int equals (bset size s1_rem) 2 "AC2: bset remove size"
assert false (bset has s1_rem "bravo") "AC2: bset remove membership"
u = bset union s1 s2
assert str eq (bt join strs (bset to list u)) "alpha,bravo,charlie,delta,echo" "AC2: bset union"
assert int equals (bset size (bset union s1 s1)) 3 "AC2: union idempotence A U A = A"
assert int equals (bset size (bset union s1 s_empty)) 3 "AC2: union identity A U empty = A"
inter = bset intersect s1 s2
assert str eq (bt join strs (bset to list inter)) "bravo" "AC2: bset intersect"
assert int equals (bset size (bset intersect s1 s_empty)) 0 "AC2: intersect with empty is empty"
df = bset diff s1 s2
assert str eq (bt join strs (bset to list df)) "alpha,charlie" "AC2: bset diff A \\ B"
assert int equals (bset size (bset diff s1 s1)) 0 "AC2: self difference A \\ A is empty"
()12.3.5. Exemplo 5: Colas de prioridade MinHeap (montículo esquerdista): heap push, heap peek, heap pop e planificación por prioridade en $O(\log N)$
Neste exemplo práctico exploramos de forma exhaustiva como se comporta btree neste bloque funcional, incluíndo entradas estándar, combinacións de parámetros e valores fronteira:
fn :: test min heap priority queue => ()
test min heap priority queue =
h0 = heap empty
assert int equals (heap size h0) 0 "AC3: empty heap size 0"
h1 = heap push h0 50 "low"
h2 = heap push h1 10 "urgent-1"
h3 = heap push h2 30 "normal"
h4 = heap push h3 20 "high"
h5 = heap push h4 10 "urgent-2"
h6 = heap push h5 (-5) "critical"
assert int equals (heap size h6) 6 "AC3: heap size 6"
pk = heap peek h6
assert int equals (hp peek prio pk) (-5) "AC3: heap peek negative priority (-5)"
assert str eq (hp peek val pk) "critical" "AC3: heap peek critical value"
p0 = heap pop h6
assert int equals (hp pop prio p0) (-5) "AC3: pop 0 (-5)"
p1 = heap pop (hp pop rest p0)
assert int equals (hp pop prio p1) 10 "AC3: pop 1 (10)"
p2 = heap pop (hp pop rest p1)
assert int equals (hp pop prio p2) 10 "AC3: pop 2 duplicate priority (10)"
-- Interleaved push after partial pop
h_mid = heap push (hp pop rest p2) 15 "medium-high"
p3 = heap pop h_mid
assert int equals (hp pop prio p3) 15 "AC3: interleaved push 15 popped before 20"
p4 = heap pop (hp pop rest p3)
assert int equals (hp pop prio p4) 20 "AC3: pop 20"
p5 = heap pop (hp pop rest p4)
assert int equals (hp pop prio p5) 30 "AC3: pop 30"
p6 = heap pop (hp pop rest p5)
assert int equals (hp pop prio p6) 50 "AC3: pop 50"
assert int equals (heap size (hp pop rest p6)) 0 "AC3: heap empty after popping all"
()12.4. Baixo o capó: como está construída btree en Ridgun puro (src/main/ridgun/lib/btree.rg)
Unha das maiores vantaxes de ridgun-libs é que non hai caixas negras en C. Podes abrir src/main/ridgun/lib/btree.rg e ler exactamente como está implementada cada operación usando pattern matching, árbores de gardas | / |. e recursión de cola (TCO). Vexamos as pezas clave da súa implementación real:
12.4.1. Implementación interna: Lexicographical String Comparison & Int Helpers
Fíxate en como btree.rg estrutura as sinaturas fn :: ... => ... primeiro e resolve cada caso mediante ecuacións aliñadas e chamadas de cola:
module :: btree
fn :: bt max Int Int => Int
bt max a b =
| a >= b = a
| otherwise = b
fn :: bt str cmp loop String String Int Int Int => Int
bt str cmp loop a b idx la lb =
| idx >= la and idx >= lb = 0
| idx >= la = (0 - 1)
| idx >= lb = 1
| (str char at a idx) < (str char at b idx) = (0 - 1)
| (str char at a idx) > (str char at b idx) = 1
| otherwise = bt str cmp loop a b (idx + 1) la lb
fn :: bt str cmp String String => Int
bt str cmp a b = bt str cmp loop a b 0 (str len a) (str len b)12.4.2. Implementación interna: AVL-Balanced Ordered Map (BTreeMap)
Fíxate en como btree.rg estrutura as sinaturas fn :: ... => ... primeiro e resolve cada caso mediante ecuacións aliñadas e chamadas de cola:
fn :: btree empty => BTreeMap
btree empty = BMapEmpty
fn :: btree height BTreeMap => Int
btree height BMapEmpty = 0
btree height (BMapNode _ _ h _ _) = h
fn :: bt mk String String BTreeMap BTreeMap => BTreeMap
bt mk k v l r = BMapNode k v (1 + (bt max (btree height l) (btree height r))) l r
fn :: bt bf BTreeMap => Int
bt bf BMapEmpty = 0
bt bf (BMapNode _ _ _ l r) = (btree height l) - (btree height r)
fn :: bt rot right BTreeMap => BTreeMap
bt rot right (BMapNode y yv _ (BMapNode x xv _ t1 t2) t3) = bt mk x xv t1 (bt mk y yv t2 t3)
bt rot right node = node
fn :: bt rot left BTreeMap => BTreeMap
bt rot left (BMapNode x xv _ t1 (BMapNode y yv _ t2 t3)) = bt mk y yv (bt mk x xv t1 t2) t3
bt rot left node = node
fn :: bt rebalance String String BTreeMap BTreeMap => BTreeMap
bt rebalance k v l r =
| ((btree height l) - (btree height r)) > 1 and (bt bf l) >= 0 = bt rot right (bt mk k v l r)
| ((btree height l) - (btree height r)) > 1 = bt rot right (bt mk k v (bt rot left l) r)
| ((btree height l) - (btree height r)) < (0 - 1) and (bt bf r) <= 0 = bt rot left (bt mk k v l r)
| ((btree height l) - (btree height r)) < (0 - 1) = bt rot left (bt mk k v l (bt rot right r))
| otherwise = bt mk k v l r
fn :: btree put BTreeMap String String => BTreeMap
btree put BMapEmpty key val = BMapNode key val 1 BMapEmpty BMapEmpty
btree put (BMapNode k v _ l r) key val =
| (bt str cmp key k) < 0 = bt rebalance k v (btree put l key val) r
| (bt str cmp key k) > 0 = bt rebalance k v l (btree put r key val)
| otherwise = bt mk key val l r
fn :: btree get or BTreeMap String String => String
btree get or BMapEmpty _ fallback = fallback
btree get or (BMapNode k v _ l r) key fallback =
| (bt str cmp key k) < 0 = btree get or l key fallback
| (bt str cmp key k) > 0 = btree get or r key fallback
| otherwise = v
fn :: btree get BTreeMap String => String
btree get t key = btree get or t key ""
fn :: btree has BTreeMap String => Bool
btree has BMapEmpty _ = False
btree has (BMapNode k _ _ l r) key =
| (bt str cmp key k) < 0 = btree has l key
| (bt str cmp key k) > 0 = btree has r key
| otherwise = True
fn :: bt min pair BTreeMap => String String
bt min pair BMapEmpty = ("", "")
bt min pair (BMapNode k v _ BMapEmpty _) = (k, v)
bt min pair (BMapNode _ _ _ l _) = bt min pair l
fn :: bt pair k (String String) => String
bt pair k (k, _) = k
fn :: bt pair v (String String) => String
bt pair v (_, v) = v
fn :: bt delete root BTreeMap BTreeMap => BTreeMap
bt delete root BMapEmpty r = r
bt delete root l BMapEmpty = l
bt delete root l r =
r bt min pair -> succ
succ bt pair k -> sk
succ bt pair v -> sv
bt rebalance sk sv l (btree remove r sk)
fn :: btree remove BTreeMap String => BTreeMap
btree remove BMapEmpty _ = BMapEmpty
btree remove (BMapNode k v _ l r) key =
| (bt str cmp key k) < 0 = bt rebalance k v (btree remove l key) r
| (bt str cmp key k) > 0 = bt rebalance k v l (btree remove r key)
| otherwise = bt delete root l r
fn :: btree size BTreeMap => Int
btree size BMapEmpty = 0
btree size (BMapNode _ _ _ l r) = 1 + (btree size l) + (btree size r)
fn :: btree keys BTreeMap => [String]
btree keys BMapEmpty = []
btree keys (BMapNode k _ _ l r) = ((btree keys l) :: [k]) :: (btree keys r)
fn :: btree values BTreeMap => [String]
btree values BMapEmpty = []
btree values (BMapNode _ v _ l r) = ((btree values l) :: [v]) :: (btree values r)
fn :: btree to list BTreeMap => [String String]
btree to list BMapEmpty = []
btree to list (BMapNode k v _ l r) = ((btree to list l) :: [(k, v)]) :: (btree to list r)
fn :: bt from pairs [String String] BTreeMap => BTreeMap
bt from pairs [] acc = acc
bt from pairs (p:rest) acc = bt from pairs rest (btree put acc (bt pair k p) (bt pair v p))
fn :: btree from list [String String] => BTreeMap
btree from list pairs = bt from pairs pairs BMapEmpty12.4.3. Implementación interna: AVL-Balanced Ordered Set (BTreeSet)
Fíxate en como btree.rg estrutura as sinaturas fn :: ... => ... primeiro e resolve cada caso mediante ecuacións aliñadas e chamadas de cola:
fn :: bset empty => BTreeSet
bset empty = BSetEmpty
fn :: bs height BTreeSet => Int
bs height BSetEmpty = 0
bs height (BSetNode _ h _ _) = h
fn :: bs mk String BTreeSet BTreeSet => BTreeSet
bs mk k l r = BSetNode k (1 + (bt max (bs height l) (bs height r))) l r
fn :: bs bf BTreeSet => Int
bs bf BSetEmpty = 0
bs bf (BSetNode _ _ l r) = (bs height l) - (bs height r)
fn :: bs rot right BTreeSet => BTreeSet
bs rot right (BSetNode y _ (BSetNode x _ t1 t2) t3) = bs mk x t1 (bs mk y t2 t3)
bs rot right node = node
fn :: bs rot left BTreeSet => BTreeSet
bs rot left (BSetNode x _ t1 (BSetNode y _ t2 t3)) = bs mk y (bs mk x t1 t2) t3
bs rot left node = node
fn :: bs rebalance String BTreeSet BTreeSet => BTreeSet
bs rebalance k l r =
| ((bs height l) - (bs height r)) > 1 and (bs bf l) >= 0 = bs rot right (bs mk k l r)
| ((bs height l) - (bs height r)) > 1 = bs rot right (bs mk k (bs rot left l) r)
| ((bs height l) - (bs height r)) < (0 - 1) and (bs bf r) <= 0 = bs rot left (bs mk k l r)
| ((bs height l) - (bs height r)) < (0 - 1) = bs rot left (bs mk k l (bs rot right r))
| otherwise = bs mk k l r
fn :: bset add BTreeSet String => BTreeSet
bset add BSetEmpty key = BSetNode key 1 BSetEmpty BSetEmpty
bset add (BSetNode k _ l r) key =
| (bt str cmp key k) < 0 = bs rebalance k (bset add l key) r
| (bt str cmp key k) > 0 = bs rebalance k l (bset add r key)
| otherwise = bs mk k l r
fn :: bset has BTreeSet String => Bool
bset has BSetEmpty _ = False
bset has (BSetNode k _ l r) key =
| (bt str cmp key k) < 0 = bset has l key
| (bt str cmp key k) > 0 = bset has r key
| otherwise = True
fn :: bs min key BTreeSet => String
bs min key BSetEmpty = ""
bs min key (BSetNode k _ BSetEmpty _) = k
bs min key (BSetNode _ _ l _) = bs min key l
fn :: bs delete root BTreeSet BTreeSet => BTreeSet
bs delete root BSetEmpty r = r
bs delete root l BSetEmpty = l
bs delete root l r =
sk = bs min key r
bs rebalance sk l (bset remove r sk)
fn :: bset remove BTreeSet String => BTreeSet
bset remove BSetEmpty _ = BSetEmpty
bset remove (BSetNode k _ l r) key =
| (bt str cmp key k) < 0 = bs rebalance k (bset remove l key) r
| (bt str cmp key k) > 0 = bs rebalance k l (bset remove r key)
| otherwise = bs delete root l r
fn :: bset size BTreeSet => Int
bset size BSetEmpty = 0
bset size (BSetNode _ _ l r) = 1 + (bset size l) + (bset size r)
fn :: bset to list BTreeSet => [String]
bset to list BSetEmpty = []
bset to list (BSetNode k _ l r) = ((bset to list l) :: [k]) :: (bset to list r)
fn :: bs from strs [String] BTreeSet => BTreeSet
bs from strs [] acc = acc
bs from strs (k:rest) acc = bs from strs rest (bset add acc k)
fn :: bset from list [String] => BTreeSet
bset from list keys = bs from strs keys BSetEmpty
fn :: bset union BTreeSet BTreeSet => BTreeSet
bset union a b = bs from strs (bset to list b) a
fn :: bs inter loop [String] BTreeSet BTreeSet => BTreeSet
bs inter loop [] _ acc = acc
bs inter loop (k:rest) b acc =
| bset has b k = bs inter loop rest b (bset add acc k)
| otherwise = bs inter loop rest b acc
fn :: bset intersect BTreeSet BTreeSet => BTreeSet
bset intersect a b = bs inter loop (bset to list a) b BSetEmpty
fn :: bs diff loop [String] BTreeSet => BTreeSet
bs diff loop [] acc = acc
bs diff loop (k:rest) acc = bs diff loop rest (bset remove acc k)
fn :: bset diff BTreeSet BTreeSet => BTreeSet
bset diff a b = bs diff loop (bset to list b) a12.4.4. Implementación interna: Leftist MinHeap Priority Queue (MinHeap)
Fíxate en como btree.rg estrutura as sinaturas fn :: ... => ... primeiro e resolve cada caso mediante ecuacións aliñadas e chamadas de cola:
fn :: heap empty => MinHeap
heap empty = HeapEmpty
fn :: hp rank MinHeap => Int
hp rank HeapEmpty = 0
hp rank (HeapNode _ _ r _ _) = r
fn :: hp mk Int String MinHeap MinHeap => MinHeap
hp mk p v a b =
| (hp rank a) >= (hp rank b) = HeapNode p v ((hp rank b) + 1) a b
| otherwise = HeapNode p v ((hp rank a) + 1) b a
fn :: hp merge MinHeap MinHeap => MinHeap
hp merge HeapEmpty h2 = h2
hp merge h1 HeapEmpty = h1
hp merge (HeapNode p1 v1 r1 l1 rt1) (HeapNode p2 v2 r2 l2 rt2) =
| p1 <= p2 = hp mk p1 v1 l1 (hp merge rt1 (HeapNode p2 v2 r2 l2 rt2))
| otherwise = hp mk p2 v2 l2 (hp merge (HeapNode p1 v1 r1 l1 rt1) rt2)
fn :: heap push MinHeap Int String => MinHeap
heap push h prio val = hp merge h (HeapNode prio val 1 HeapEmpty HeapEmpty)
fn :: heap peek MinHeap => Int String
heap peek HeapEmpty = (0, "")
heap peek (HeapNode p v _ _ _) = (p, v)
fn :: heap pop MinHeap => Int String MinHeap
heap pop HeapEmpty = (0, "", HeapEmpty)
heap pop (HeapNode p v _ l r) = (p, v, hp merge l r)
fn :: heap size MinHeap => Int
heap size HeapEmpty = 0
heap size (HeapNode _ _ _ l r) = 1 + (heap size l) + (heap size r)12.5. Garantías algorítmicas, memoria RMM1/RMM2 e as 5 Regras de Ouro de btree
- Garantía algorítmica e de seguridade: Rotacións AVL estritas (
height diff <= 1), inmunidade total a HashDoS, consultas por rango en $O(\log N + K)$ e fusión de montículos en $O(\log N)$. - Complexidade de pila $O(1)$ con TCO: Todos os bucles recursivos en
src/main/ridgun/lib/btree.rgestán en posición de cola, polo queridguncos compila a saltos nativos sen crecemento de pila. - Memoria determinista (
RMM1/RMM2): Cero pausas de colector de lixo; todas as estruturas intermedias libéranse de forma determinista ao saír do ámbito. - Verificación continua: Probada exhaustivamente con
stable checke a suite automatizadasrc/test/ridgun/test btree.rg.
As 5 Regras de Ouro ao programar con btree
- Declara
import btreeao inicio do ficheiro e aproveita a equivalencia entre espazos e guións baixos para que o teu código se lea coma prosa. - Aliña as túas tubaxes de datos con
=: encadea as chamadas abtreeen pasos con nome propio e deixa questable formataliñe as columnas. - Aproveita as funcións totais de
btreenas túas gardas|: comproba os valores de retorno ou desenvolve os ADTs con pattern matching en vez de asumir que a entrada externa sempre é válida. - Evita copiar grandes estruturas se só necesitas consultar un campo: lembra que en
RMM2os argumentos de entrada non incrementan nin decrementan contadores (+0/-0). - Combina
btreecontest(import test): escribe sempre asercións conassert equalsouassert truepara fixar os invariantes do teu dominio.
No Capítulo 13 pasaremos a explorar en profundidade a lib tensor (A lib tensor — Tensores Multidimensionais, Vistas e Contracción de Einstein).