diff options
Diffstat (limited to 'tests/run/tbintree.nim')
-rw-r--r-- | tests/run/tbintree.nim | 107 |
1 files changed, 0 insertions, 107 deletions
diff --git a/tests/run/tbintree.nim b/tests/run/tbintree.nim deleted file mode 100644 index 8cc8acb82..000000000 --- a/tests/run/tbintree.nim +++ /dev/null @@ -1,107 +0,0 @@ -discard """ - file: "tbintree.nim" - output: "helloworld99110223" -""" -type - TBinaryTree[T] = object # TBinaryTree is a generic type with - # with generic param ``T`` - le, ri: ref TBinaryTree[T] # left and right subtrees; may be nil - data: T # the data stored in a node - PBinaryTree*[A] = ref TBinaryTree[A] # type that is exported - -proc newNode*[T](data: T): PBinaryTree[T] = - # constructor for a node - new(result) - result.data = data - -proc add*[Ty](root: var PBinaryTree[Ty], n: PBinaryTree[Ty]) = - # insert a node into the tree - if root == nil: - root = n - else: - var it = root - while it != nil: - # compare the data items; uses the generic ``cmp`` proc that works for - # any type that has a ``==`` and ``<`` operator - var c = cmp(n.data, it.data) - if c < 0: - if it.le == nil: - it.le = n - return - it = it.le - else: - if it.ri == nil: - it.ri = n - return - it = it.ri - -proc add*[Ty](root: var PBinaryTree[Ty], data: Ty) = - # convenience proc: - add(root, newNode(data)) - -proc find*[Ty2](b: PBinaryTree[Ty2], data: Ty2): bool = - # for testing this needs to be recursive, so that the - # instantiated type is checked for proper tyGenericInst envelopes - if b == nil: - result = false - else: - var c = cmp(data, b.data) - if c < 0: result = find(b.le, data) - elif c > 0: result = find(b.ri, data) - else: result = true - -iterator preorder*[T](root: PBinaryTree[T]): T = - # Preorder traversal of a binary tree. - # Since recursive iterators are not yet implemented, - # this uses an explicit stack: - var stack: seq[PBinaryTree[T]] = @[root] - while stack.len > 0: - var n = stack.pop() - while n != nil: - yield n.data - add(stack, n.ri) # push right subtree onto the stack - n = n.le # and follow the left pointer - -iterator items*[T](root: PBinaryTree[T]): T = - ## Inorder traversal of the binary tree. - var stack: seq[PBinaryTree[T]] = @[] - var n = root - while true: - while n != nil: - add(stack, n) - n = n.le - if stack.len > 0: - n = stack.pop() - yield n.data - n = n.ri - if stack.len == 0 and n == nil: break - -proc debug[T](a: PBinaryTree[T]) = - if a != nil: - debug(a.le) - echo a.data - debug(a.ri) - -when isMainModule: - var - root: PBinaryTree[string] - x = newNode("hello") - add(root, x) - add(root, "world") - if find(root, "world"): - for str in items(root): - stdout.write(str) - else: - stdout.writeln("BUG") - - var - r2: PBinaryTree[int] - add(r2, newNode(110)) - add(r2, 223) - add(r2, 99) - for y in items(r2): - stdout.write(y) - -#OUT helloworld99110223 - - |