diff options
Diffstat (limited to 'examples/scripting/tree_utils.py')
| -rwxr-xr-x | examples/scripting/tree_utils.py | 118 |
1 files changed, 0 insertions, 118 deletions
diff --git a/examples/scripting/tree_utils.py b/examples/scripting/tree_utils.py deleted file mode 100755 index a4d1645d7350..000000000000 --- a/examples/scripting/tree_utils.py +++ /dev/null @@ -1,118 +0,0 @@ -""" -# ===-- 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. - """ - - # Get pointer field values out of node 'root' - - root_word_ptr = root.GetChildMemberWithName("word") - left_child_ptr = root.GetChildMemberWithName("left") - right_child_ptr = root.GetChildMemberWithName("right") - - # Get the word out of the word pointer and strip off - # surrounding quotes (added by call to GetSummary). - - 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] - - # Main depth first search - - if root_word == word: - return cur_path - elif word < root_word: - - # Check to see if left child is NULL - - if left_child_ptr.GetValue() is None: - return "" - else: - cur_path = cur_path + "L" - return DFS(left_child_ptr, word, cur_path) - else: - - # Check to see if right child is NULL - - if right_child_ptr.GetValue() is 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 is 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() is not None) and ( - int(root.GetChildAtIndex(1).GetValue(), 16) != 0): - print_tree(root.GetChildAtIndex(1)) - - print root.GetChildAtIndex(0).GetSummary() - - if (root.GetChildAtIndex(2).GetValue() is not None) and ( - int(root.GetChildAtIndex(2).GetValue(), 16) != 0): - print_tree(root.GetChildAtIndex(2)) |