awkrs 0.4.13

Awk implementation in Rust with broad CLI compatibility, parallel records, and experimental Cranelift JIT
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

# AVL self-balancing binary search tree.
# Input lines:
#   "INSERT <k>"     insert key k (deduped)
#   "INORDER"        print sorted keys: "INORDER: k1 k2 ..."
#   "HEIGHT"         print height of the root: "HEIGHT: h"
#   "BALANCED"       verify every node satisfies |bf| <= 1: prints YES/NO
#
# Node arrays:
#   key[i] left[i] right[i] h[i]   (0 = nil)

function ht(n) { return (n == 0) ? 0 : h[n] }
function bf(n) { return (n == 0) ? 0 : ht(left[n]) - ht(right[n]) }
function update_h(n) {
  if (n == 0) return
  h[n] = 1 + ((ht(left[n]) > ht(right[n])) ? ht(left[n]) : ht(right[n]))
}

function rot_right(y,   x) {
  x = left[y]
  left[y] = right[x]
  right[x] = y
  update_h(y)
  update_h(x)
  return x
}

function rot_left(x,   y) {
  y = right[x]
  right[x] = left[y]
  left[y] = x
  update_h(x)
  update_h(y)
  return y
}

function rebalance(n,   b) {
  update_h(n)
  b = bf(n)
  if (b > 1 && bf(left[n]) >= 0) return rot_right(n)
  if (b > 1 && bf(left[n]) <  0) { left[n] = rot_left(left[n]); return rot_right(n) }
  if (b < -1 && bf(right[n]) <= 0) return rot_left(n)
  if (b < -1 && bf(right[n]) >  0) { right[n] = rot_right(right[n]); return rot_left(n) }
  return n
}

function insert(n, k) {
  if (n == 0) {
    cnt++
    key[cnt] = k; left[cnt] = 0; right[cnt] = 0; h[cnt] = 1
    return cnt
  }
  if (k < key[n])      left[n]  = insert(left[n], k)
  else if (k > key[n]) right[n] = insert(right[n], k)
  else return n
  return rebalance(n)
}

function inorder(n) {
  if (n == 0) return
  inorder(left[n])
  inorder_out = inorder_out " " key[n]
  inorder(right[n])
}

function check_balanced(n,   b) {
  if (n == 0) return 1
  b = bf(n)
  if (b < -1 || b > 1) return 0
  if (!check_balanced(left[n])) return 0
  return check_balanced(right[n])
}

BEGIN { root = 0; cnt = 0 }

$1 == "INSERT" { root = insert(root, $2 + 0); next }
$1 == "INORDER" {
  inorder_out = ""
  inorder(root)
  sub(/^ /, "", inorder_out)
  print "INORDER: " inorder_out
  next
}
$1 == "HEIGHT" { print "HEIGHT: " ht(root); next }
$1 == "BALANCED" { print "BALANCED: " (check_balanced(root) ? "YES" : "NO"); next }