fork download
copy 
  1. type
  2.   ElementKind = enum inner, leaf
  3.   TElement[TKey, TData] = object
  4.     case kind: ElementKind
  5.     of inner:
  6.       key: TKey
  7.       left, right: ref TElement[Tkey, TData]
  8.     of leaf:
  9.       data: TData
  10.   PElement[TKey, TData] = ref TElement[TKey, TData]
  11.  
  12. proc newElement[Tkey, TData](other: PElement[TKey, TData]): PElement[Tkey, TData] =
  13.   case other.kind:
  14.   of inner:
  15.     PElement[TKey, TData](kind: ElementKind.inner, key: other.key, left: other.left, right: other.right)
  16.   of leaf:
  17.     PElement[TKey, TData](kind: ElementKind.leaf, data: other.data)
  18.  
  19. proc newElement[TKey, TData](key: TKey, left: PElement[TKey, TData] = nil, right: PElement[TKey, TData] = nil) : PElement[TKey, TData] =
  20.   PElement[TKey, TData](kind: ElementKind.inner, key: key, left: left, right: right)
  21.  
  22. proc newElement[Tkey, TData](key: Tkey, data: TData) : PElement[Tkey, TData] =
  23.   PElement[TKey, TData](kind: ElementKind.leaf, data: data)
  24.  
  25. proc find*[TKey, TData](root: PElement[TKey, TData], key: TKey): TData {.raises: [EInvalidKey].} =
  26.   if root.left == nil:
  27.     raise newException(EInvalidKey, "key does not exist: " & key)
  28.  
  29.   var tmp_element = addr(root)
  30.  
  31.   while tmp_element.kind == inner and tmp_element.right != nil:
  32.     tmp_element = if tmp_element.key > key:
  33.                     tmp_element.left 
  34.                   else:
  35.                     tmp_element.right
  36.  
  37.   if tmp_element.key == key:
  38.     return tmp_element.left.data
  39.   else:
  40.     raise newException(EInvalidKey, "key does not exist: " & key)
  41.  
  42. proc add*[TKey, TData](root: var PElement[TKey, TData], key: TKey, data: TData) : bool =
  43.   if root.left == nil:
  44.     root.key = key
  45.     root.left = newElement[TKey, TData](key, data)
  46.     return true
  47.  
  48.   var tmp_element = addr(root)
  49.  
  50.   while tmp_element.kind == ElementKind.inner and tmp_element.right != nil:
  51.     tmp_element = if tmp_element.key > key:
  52.                     addr(tmp_element.left)
  53.                   else:
  54.                     addr(tmp_element.right)
  55.  
  56.   if tmp_element.key == key:
  57.     return false
  58.  
  59.   var old_element = newElement[TKey, TData](tmp_element)
  60.   var new_element = newElement[TKey, TData](key, data)
  61.  
  62.   tmp_element[] = if tmp_element.key < key:
  63.                     newElement(key, old_element, new_element)
  64.                   else:
  65.                     newElement(tmp_element.key, new_element, old_element)
  66.  
  67.   true
  68.  
  69. var tree = PElement[int, int](kind: ElementKind.inner, key: 0, left: nil, right: nil)
  70.  
  71. add(tree, 1, 1)
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.nim(15, 31) Error: ')' expected
stdout
copy 
Standard output is empty
https://ideone.com/o7aWq3
language:
Nim (nim 0.19.4)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!