Alexander Medvednikov
cf16fefe55
* macos: fix CI formatting and older SDK TCC headers * crdt: format gcounter tests for CI * crdt: remove trailing blank lines caught by CI * vfmt: format files reported by macOS CI * veb.csrf: use context configuration when clearing cookies * math: provide logf in pure V builds * math: correctly round pure V square roots * transform: preserve generic elements in fixed array loops * cgen: escape bool field names for stdbool compatibility * json2: release JSON5 decoding scratch and cloned map keys * examples: use pointer recursion in the binary search tree * modulecache: preserve static macro definitions in declaration headers * macos: fix declaration test scanning and recursive tree example * test-self: isolate compiler environment flags from nested builds * cgen: preserve interface dispatch and module roots with warm caches * tests: correct backend fixtures exercised by macOS CI * transform: decode escaped bool generic arguments * tests: align GC and closure checks with native declarations * tests: match current HTML tag formatting in option output * cgen: retain mutable struct addresses in integer casts * transform: retain explicit generic method calls when ordering arguments * checker: retain nested translated array types in pointer comparisons * tests: retain type storage and canonicalize macOS temporary paths * graphql: store recursive AST edges through pointers * veb: avoid copying large request and response structs for connection checks * veb.csrf: expire cleared cookies at the configured path
147 lines
2.5 KiB
V
147 lines
2.5 KiB
V
// Binary Search Tree example by @SleepyRoy
|
|
|
|
struct Empty {}
|
|
|
|
struct Node[T] {
|
|
value T
|
|
left Tree[T]
|
|
right Tree[T]
|
|
}
|
|
|
|
type Tree[T] = Empty | &Node[T]
|
|
|
|
// return size(number of nodes) of BST
|
|
fn (tree Tree[T]) size[T]() int {
|
|
return match tree {
|
|
Empty { 0 }
|
|
&Node[T] { 1 + tree.left.size() + tree.right.size() }
|
|
}
|
|
}
|
|
|
|
// insert a value to BST
|
|
fn (tree Tree[T]) insert[T](x T) Tree[T] {
|
|
return match tree {
|
|
Empty {
|
|
&Node[T]{x, tree, tree}
|
|
}
|
|
&Node[T] {
|
|
if x == tree.value {
|
|
tree
|
|
} else if x < tree.value {
|
|
&Node[T]{
|
|
...tree
|
|
left: tree.left.insert(x)
|
|
}
|
|
} else {
|
|
&Node[T]{
|
|
...tree
|
|
right: tree.right.insert(x)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// whether able to find a value in BST
|
|
fn (tree Tree[T]) search[T](x T) bool {
|
|
return match tree {
|
|
Empty {
|
|
false
|
|
}
|
|
&Node[T] {
|
|
if x == tree.value {
|
|
true
|
|
} else if x < tree.value {
|
|
tree.left.search(x)
|
|
} else {
|
|
tree.right.search(x)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// find the minimal value of a BST
|
|
fn (tree Tree[T]) min[T]() T {
|
|
return match tree {
|
|
Empty {
|
|
T(1e9)
|
|
}
|
|
&Node[T] {
|
|
if tree.value < tree.left.min() {
|
|
tree.value
|
|
} else {
|
|
tree.left.min()
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// delete a value in BST (if nonexistent do nothing)
|
|
fn (tree Tree[T]) delete[T](x T) Tree[T] {
|
|
return match tree {
|
|
Empty {
|
|
tree
|
|
}
|
|
&Node[T] {
|
|
if tree.left !is Empty && tree.right !is Empty {
|
|
if x < tree.value {
|
|
&Node[T]{
|
|
...tree
|
|
left: tree.left.delete(x)
|
|
}
|
|
} else if x > tree.value {
|
|
&Node[T]{
|
|
...tree
|
|
right: tree.right.delete(x)
|
|
}
|
|
} else {
|
|
&Node[T]{
|
|
...tree
|
|
value: tree.right.min()
|
|
right: tree.right.delete(tree.right.min())
|
|
}
|
|
}
|
|
} else if tree.left !is Empty {
|
|
if x == tree.value {
|
|
tree.left
|
|
} else {
|
|
&Node[T]{
|
|
...tree
|
|
left: tree.left.delete(x)
|
|
}
|
|
}
|
|
} else {
|
|
if x == tree.value {
|
|
tree.right
|
|
} else {
|
|
&Node[T]{
|
|
...tree
|
|
right: tree.right.delete(x)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
mut tree := Tree[f64](Empty{})
|
|
vals := [0.2, 0.0, 0.5, 0.3, 0.6, 0.8, 0.9, 1.0, 0.1, 0.4, 0.7]
|
|
for i in vals {
|
|
tree = tree.insert(i)
|
|
}
|
|
println('[1] after insertion tree size is ${tree.size()}') // 11
|
|
del_vals := [-0.3, 0.0, 0.3, 0.6, 1.0, 1.5]
|
|
for i in del_vals {
|
|
tree = tree.delete(i)
|
|
}
|
|
print('[2] after deletion tree size is ${tree.size()}, ') // 7
|
|
print('and these elements were deleted: ') // 0.0 0.3 0.6 1.0
|
|
for i in vals {
|
|
if !tree.search(i) {
|
|
print('${i} ')
|
|
}
|
|
}
|
|
println('')
|
|
}
|