Caroline Tice | 35393b1 | 2011-06-02 23:23:47 +0000 | [diff] [blame] | 1 | """ |
| 2 | # ===-- tree_utils.py ---------------------------------------*- Python -*-===// |
| 3 | # |
| 4 | # The LLVM Compiler Infrastructure |
| 5 | # |
| 6 | # This file is distributed under the University of Illinois Open Source |
| 7 | # License. See LICENSE.TXT for details. |
| 8 | # |
| 9 | # ===---------------------------------------------------------------------===// |
| 10 | |
| 11 | tree_utils.py - A set of functions for examining binary |
| 12 | search trees, based on the example search tree defined in |
| 13 | dictionary.c. These functions contain calls to LLDB API |
| 14 | functions, and assume that the LLDB Python module has been |
| 15 | imported. |
| 16 | |
| 17 | For a thorough explanation of how the DFS function works, and |
| 18 | for more information about dictionary.c go to |
| 19 | http://lldb.llvm.org/scripting.html |
| 20 | """ |
| 21 | |
| 22 | |
| 23 | def DFS (root, word, cur_path): |
| 24 | """ |
| 25 | Recursively traverse a binary search tree containing |
| 26 | words sorted alphabetically, searching for a particular |
| 27 | word in the tree. Also maintains a string representing |
| 28 | the path from the root of the tree to the current node. |
| 29 | If the word is found in the tree, return the path string. |
| 30 | Otherwise return an empty string. |
| 31 | |
| 32 | This function assumes the binary search tree is |
| 33 | the one defined in dictionary.c It uses LLDB API |
| 34 | functions to examine and traverse the tree nodes. |
| 35 | """ |
| 36 | |
| 37 | # Get pointer field values out of node 'root' |
| 38 | |
| 39 | root_word_ptr = root.GetChildMemberWithName ("word") |
| 40 | left_child_ptr = root.GetChildMemberWithName ("left") |
| 41 | right_child_ptr = root.GetChildMemberWithName ("right") |
| 42 | |
| 43 | # Get the word out of the word pointer and strip off |
| 44 | # surrounding quotes (added by call to GetSummary). |
| 45 | |
| 46 | root_word = root_word_ptr.GetSummary() |
| 47 | end = len (root_word) - 1 |
| 48 | if root_word[0] == '"' and root_word[end] == '"': |
| 49 | root_word = root_word[1:end] |
| 50 | end = len (root_word) - 1 |
| 51 | if root_word[0] == '\'' and root_word[end] == '\'': |
| 52 | root_word = root_word[1:end] |
| 53 | |
| 54 | # Main depth first search |
| 55 | |
| 56 | if root_word == word: |
| 57 | return cur_path |
| 58 | elif word < root_word: |
| 59 | |
| 60 | # Check to see if left child is NULL |
| 61 | |
| 62 | if left_child_ptr.GetValue() == None: |
| 63 | return "" |
| 64 | else: |
| 65 | cur_path = cur_path + "L" |
| 66 | return DFS (left_child_ptr, word, cur_path) |
| 67 | else: |
| 68 | |
| 69 | # Check to see if right child is NULL |
| 70 | |
| 71 | if right_child_ptr.GetValue() == None: |
| 72 | return "" |
| 73 | else: |
| 74 | cur_path = cur_path + "R" |
| 75 | return DFS (right_child_ptr, word, cur_path) |
| 76 | |
| 77 | |
| 78 | def tree_size (root): |
| 79 | """ |
| 80 | Recursively traverse a binary search tree, counting |
| 81 | the nodes in the tree. Returns the final count. |
| 82 | |
| 83 | This function assumes the binary search tree is |
| 84 | the one defined in dictionary.c It uses LLDB API |
| 85 | functions to examine and traverse the tree nodes. |
| 86 | """ |
| 87 | if (root.GetValue == None): |
| 88 | return 0 |
| 89 | |
| 90 | if (int (root.GetValue(), 16) == 0): |
| 91 | return 0 |
| 92 | |
| 93 | left_size = tree_size (root.GetChildAtIndex(1)); |
| 94 | right_size = tree_size (root.GetChildAtIndex(2)); |
| 95 | |
| 96 | total_size = left_size + right_size + 1 |
| 97 | return total_size |
| 98 | |
| 99 | |
| 100 | def print_tree (root): |
| 101 | """ |
| 102 | Recursively traverse a binary search tree, printing out |
| 103 | the words at the nodes in alphabetical order (the |
| 104 | search order for the binary tree). |
| 105 | |
| 106 | This function assumes the binary search tree is |
| 107 | the one defined in dictionary.c It uses LLDB API |
| 108 | functions to examine and traverse the tree nodes. |
| 109 | """ |
| 110 | if (root.GetChildAtIndex(1).GetValue() != None) and (int (root.GetChildAtIndex(1).GetValue(), 16) != 0): |
| 111 | print_tree (root.GetChildAtIndex(1)) |
| 112 | |
| 113 | print root.GetChildAtIndex(0).GetSummary() |
| 114 | |
| 115 | if (root.GetChildAtIndex(2).GetValue() != None) and (int (root.GetChildAtIndex(2).GetValue(), 16) != 0): |
| 116 | print_tree (root.GetChildAtIndex(2)) |
| 117 | |
| 118 | |