"""
# ===-- tree_utils.py ---------------------------------------*- Python -*-===//
#
# The LLVM Compiler Infrastructure
#
# This file is distributed under the University of Illinois Open Source
# License. See LICENSE.TXT for details.
#
# ===---------------------------------------------------------------------===//
tree_utils.py - A set of functions for examining binary
search trees, based on the example search tree defined in
dictionary.c. These functions contain calls to LLDB API
functions, and assume that the LLDB Python module has been
imported.
For a thorough explanation of how the DFS function works, and
for more information about dictionary.c go to
http://lldb.llvm.org/scripting.html
"""
def DFS (root, word, cur_path):
"""
Recursively traverse a binary search tree containing
words sorted alphabetically, searching for a particular
word in the tree. Also maintains a string representing
the path from the root of the tree to the current node.
If the word is found in the tree, return the path string.
Otherwise return an empty string.
This function assumes the binary search tree is
the one defined in dictionary.c It uses LLDB API
functions to examine and traverse the tree nodes.
"""
root_word_ptr = root.GetChildMemberWithName ("word")
left_child_ptr = root.GetChildMemberWithName ("left")
right_child_ptr = root.GetChildMemberWithName ("right")
root_word = root_word_ptr.GetSummary()
end = len (root_word) - 1
if root_word[0] == '"' and root_word[end] == '"':
root_word = root_word[1:end]
end = len (root_word) - 1
if root_word[0] == '\'' and root_word[end] == '\'':
root_word = root_word[1:end]
if root_word == word:
return cur_path
elif word < root_word:
if left_child_ptr.GetValue() == None:
return ""
else:
cur_path = cur_path + "L"
return DFS (left_child_ptr, word, cur_path)
else:
if right_child_ptr.GetValue() == None:
return ""
else:
cur_path = cur_path + "R"
return DFS (right_child_ptr, word, cur_path)
def tree_size (root):
"""
Recursively traverse a binary search tree, counting
the nodes in the tree. Returns the final count.
This function assumes the binary search tree is
the one defined in dictionary.c It uses LLDB API
functions to examine and traverse the tree nodes.
"""
if (root.GetValue == None):
return 0
if (int (root.GetValue(), 16) == 0):
return 0
left_size = tree_size (root.GetChildAtIndex(1));
right_size = tree_size (root.GetChildAtIndex(2));
total_size = left_size + right_size + 1
return total_size
def print_tree (root):
"""
Recursively traverse a binary search tree, printing out
the words at the nodes in alphabetical order (the
search order for the binary tree).
This function assumes the binary search tree is
the one defined in dictionary.c It uses LLDB API
functions to examine and traverse the tree nodes.
"""
if (root.GetChildAtIndex(1).GetValue() != None) and (int (root.GetChildAtIndex(1).GetValue(), 16) != 0):
print_tree (root.GetChildAtIndex(1))
print root.GetChildAtIndex(0).GetSummary()
if (root.GetChildAtIndex(2).GetValue() != None) and (int (root.GetChildAtIndex(2).GetValue(), 16) != 0):
print_tree (root.GetChildAtIndex(2))