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
|
discard """
output: '''true'''
"""
#bug #592
type
ElementKind = enum inner, leaf
TElement[TKey, TData] = object
case kind: ElementKind
of inner:
key: TKey
left, right: ref TElement[Tkey, TData]
of leaf:
data: TData
PElement[TKey, TData] = ref TElement[TKey, TData]
proc newElement[Tkey, TData](other: PElement[TKey, TData]): PElement[Tkey, TData] =
case other.kind:
of inner:
PElement[TKey, TData](kind: ElementKind.inner, key: other.key, left: other.left, right: other.right)
of leaf:
PElement[TKey, TData](kind: ElementKind.leaf, data: other.data)
proc newElement[TKey, TData](key: TKey, left: PElement[TKey, TData] = nil, right: PElement[TKey, TData] = nil) : PElement[TKey, TData] =
PElement[TKey, TData](kind: ElementKind.inner, key: key, left: left, right: right)
proc newElement[Tkey, TData](key: Tkey, data: TData) : PElement[Tkey, TData] =
PElement[TKey, TData](kind: ElementKind.leaf, data: data)
proc find*[TKey, TData](root: PElement[TKey, TData], key: TKey): TData {.raises: [KeyError].} =
if root.left == nil:
raise newException(KeyError, "key does not exist: " & key)
var tmp_element = addr(root)
while tmp_element.kind == inner and tmp_element.right != nil:
tmp_element = if tmp_element.key > key:
addr(tmp_element.left)
else:
addr(tmp_element.right)
if tmp_element.key == key:
return tmp_element.left.data
else:
raise newException(KeyError, "key does not exist: " & key)
proc add*[TKey, TData](root: var PElement[TKey, TData], key: TKey, data: TData) : bool =
if root.left == nil:
root.key = key
root.left = newElement[TKey, TData](key, data)
return true
var tmp_element = addr(root)
while tmp_element.kind == ElementKind.inner and tmp_element.right != nil:
tmp_element = if tmp_element.key > key:
addr(tmp_element.left)
else:
addr(tmp_element.right)
if tmp_element.key == key:
return false
var old_element = newElement[TKey, TData](tmp_element[])
var new_element = newElement[TKey, TData](key, data)
tmp_element[] = if tmp_element.key < key:
newElement(key, old_element, new_element)
else:
newElement(tmp_element.key, new_element, old_element)
return true
var tree = PElement[int, int](kind: ElementKind.inner, key: 0, left: nil, right: nil)
let result = add(tree, 1, 1)
echo(result)
|