def remove_subtree(self, nid):
        """
        Return a subtree deleted from this tree. If nid is None, an
        empty tree is returned.
        For the original tree, this method is similar to
        `remove_node(self,nid)`, because given node and its children
        are removed from the original tree in both methods.
        For the returned value and performance, these two methods are
        different:

            `remove_node` returns the number of deleted nodes;
            `remove_subtree` returns a subtree of deleted nodes;

        You are always suggested to use `remove_node` if your only to
        delete nodes from a tree, as the other one need memory
        allocation to store the new tree.
        """
        st = Tree()
        if nid is None:
            return st

        if not self.contains(nid):
            raise NodeIDAbsentError("Node '%s' is not in the tree" % nid)
        st.root = nid

        parent = self[nid].bpointer
        self[nid].bpointer = None  # reset root parent for the new tree
        removed = []
        for id in self.expand_tree(nid):
            removed.append(id)
        for id in removed:
            st._nodes.update({id: self._nodes.pop(id)})
        # Update its parent info
        self.__update_fpointer(parent, nid, Node.DELETE)
        return st

class Conversation:
    def __init__(self, tweet):
        self.root_tweet = tweet
        self.conversation_tree = Tree()
        self.conversation_tree.create_node(tweet, tweet)
        self.depth = int()
        self.tweets_id = list()
        self.tweets_id.append(tweet)
        self.width = int()

    def add_replay(self, tweet, parent_tweet):
        self.conversation_tree.create_node(tweet, tweet, parent=parent_tweet)
        self.tweets_id.append(tweet)

    def set_depth(self):
        self.depth = self.conversation_tree.depth() + 1

    def find_depth(self):
        return self.depth

    def get_tweets_id(self):
        return self.tweets_id

    def set_width(self):
        self.width = len(self.tweets_id)

    def find_width(self):
        return self.width

    def get_conversation_tree(self):
        return self.conversation_tree

 def test_paste_tree(self):
     new_tree = Tree()
     new_tree.create_node("Jill", "jill")
     new_tree.create_node("Mark", "mark", parent="jill")
     self.tree.paste("jane", new_tree)
     self.assertEqual("jill" in self.tree.is_branch("jane"), True)
     self.tree.remove_node("jill")

def main():
  try:
    conf = open(args.config, 'r')
    tempConf = yaml.load_all(conf)

    for line in tempConf:
      list_path = line["ListPath"]
      write_missed = line["WriteMissed"]

    pack_list_file = open(list_path, "r+")
    pack_list = json.load(pack_list_file)

    checked = check(pack_list, write_missed)

    tree = Tree()
    tree.create_node(cur_time, "root")
    generate_tree(checked, tree, "root")

    print "\n"
    tree.show()
    print "\n"

  except KeyboardInterrupt:
    print '\nThe process was interrupted by the user'
    raise SystemExit

	def test_02_get_hierarchy_for_module_returns_single_node_when_nothing_depend_on_module(self, mock_client):
		"""
		Test that get_hierarchy_for_module returns a single node tree structure if no dependent modules are found
		:param mock_client: A mocked out version of erppeek.Client
		:return:
		"""
		# Mock Up
		mock_dp = DependencyGraph
		orig_mod_search = mock_dp.module_search
		orig_dep_search = mock_dp.dependency_search
		orig_client_search = mock_client.search
		mock_dp.module_search = MagicMock(return_value=[666])
		mock_dp.dependency_search = MagicMock(return_value=[])

		mock_dg = mock_dp('valid_module')
		test_hierarchy = Tree()
		test_hierarchy.create_node('valid_module', 'valid_module')
		self.assertEqual(mock_dg.hierarchy.to_json(), test_hierarchy.to_json(), 'get_hierarchy_for_module did not return [] when finding no dependent modules')

		# Mock Down
		mock_client.stop()
		mock_dp.module_search.stop()
		mock_client.search.stop()
		mock_client.search = orig_client_search
		mock_dp.dependency_search.stop()
		mock_dp.module_search = orig_mod_search
		mock_dp.dependency_search = orig_dep_search

 def print_prob_val(self, fname="OutTree.txt"):
     n_tree = Tree(tree=self.tree)
     for node in n_tree.nodes:
         node = n_tree.get_node(node)
         node.tag = "{tag} - {val} - {prob}".format(tag=node.tag, val=node.data[0], prob=node.data[1])
     n_tree.save2file(fname)
     self.tree =  None

 def test_show_data_property(self):
     new_tree = Tree()
     class Flower(object):
         def __init__(self, color):
             self.color = color
     new_tree.create_node("Jill", "jill", data=Flower("white"))
     new_tree.show(data_property="color")

class Scansion(object):
    """
        .src    : list of strings
    """

    #///////////////////////////////////////////////////////////////////////////
    def __init__(self, source_file):
        """
                Scansion.__init__

                source_file     : (src) source file's name.
        """
        self.htree = Tree()
        self.src = []

        # creating root node (level 0) :
        self.htree.create_node(tag           = "root",
                               identifier    = "root",
                               data          = Hypothesis(htree = self.htree,
                                                          level=0,
                                                          language=None,
                                                          src=source_file))

        # calling root node :
        msg(0, "Calling the root node.")
        stop = False
        while not stop:
            leaves_to_be_extended = [leave for leave in self.htree.leaves() if not leave.data.dead]

            for leave in leaves_to_be_extended:
                leave.data.go_on()

            if len(leaves_to_be_extended)==0:
                stop = True

class TreePipeline(object):

    def open_spider(self, spider):
        self.tree = Tree()
        self.tree.create_node("root", "root")

    def process_item(self, item, spider):
        lst = item['text']
        lst = [x.strip() for x in [y.replace('...', '') for y in lst]]
        item['pagetitle'] = item['pagetitle'].replace('...', '')
        lst[-1] = item['pagetitle']
        for idx, elem in enumerate(lst):
            if idx == 0:
                previous = "root"
            else:
                previous = "|".join(lst[:idx])
            elem = "|".join(lst[:idx + 1])
            # elem = elem.replace('...', '')
            elem = elem.encode('utf-8').decode('utf-8')
            if not self.tree.contains(elem):
                print "Adding node %s" % elem
                self.tree.create_node(elem, elem, parent=previous)
                # self.tree.show()
        return item

    def close_spider(self, spider):
        self.tree.show()
        with open(makepath('data/cats/tree.json'), 'w') as outfile:
            outfile.write(self.tree.to_json())
        self.tree.save2file(makepath('data/cats/tree.tree'))

def parse_xml(path):
    tree = ET.parse(path)
    bill_list = []
    destination = "console"

    # eg:       (cox, "[email protected]")                  (rent, 2000)
    #          /                                 \            &    /            \
    #      (Evan, 0.5)                        (Jason, 0.5)       (Evan, 0.45)   (Jason, 0.55)
    for bill in tree.findall("bill"):
        billname = bill.get("name")
        bill_tree = Tree()
        bill_value = bill.get("fixed")
        if bill_value is None:
            bill_value = bill.get("from_email")
        bill_tree.create_node(tag=billname, identifier=billname, data=bill_value)

        for user in bill.findall("user"):
            username = user.get("name")
            ratio = user.get("ratio")
            bill_tree.create_node(tag=username, identifier=username, parent=billname, data=ratio)
        bill_list.append(bill_tree)

    # Get the location to dump our results
    for d in tree.findall("output"):
        destination = d.get("destination")

    return (bill_list, destination)

 def visit_root(self, node, tree=None):
     tree = Tree()
     root = repr(node)
     tree.create_node(root, root)
     for child in node.children:
         tree = self.visit(child, tree=tree)
     return tree

def build_directory_tree(service):
    print colored("*** Building directory tree ***", 'blue')
    
    # initialize a new directory structure
    directory = Tree()
    directory.create_node("Root", "root")
    page_token = None
    while True:
        try:
            param = {}
            if page_token:
                param['pageToken'] = page_token
            
            # Get children of folderID
            children = service.children().list(folderId='root', **param).execute()

            # For each child in folder, get ID, name and Type
            # and write to the directory tree
            for child in children.get('items', []):
                try:
                    file__ = service.files().get(fileId=child['id']).execute()
                    directory.create_node(file__['title'], child['id'], parent = 'root', data=node('root', child['id'], file__['title'], file__['mimeType']))
                except errors.HttpError, error:
                    print 'An error occurred: %s' % error
            
            # Get next page token for current folderID
            page_token = children.get('nextPageToken')
            if not page_token:
                break
        except errors.HttpError, error:
            print colored('An error occurred: %s', 'red') % error
            break

 def _get_random_tree(self, start, max_depth=999):
     """
     Returns a random tree from PCFG starting with symbol 'start'
     depth: the maximum depth of tree
     """
     t = Tree()
     t.create_node(ParseNode(start,''))
     
     # get ids of not expanded nonterminals in tree
     nodes_to_expand, depth = self.__get_nodes_to_expand_and_depth(t)
     
     while len(nodes_to_expand) > 0:
         # for each non terminal, choose a random rule and apply it
         for node in nodes_to_expand:
             symbol = t[node].tag.symbol
             
             # if tree exceeded the allowed depth, expand nonterminals
             # using rules from terminating_rule_ids
             if depth >= (max_depth-1):
                 # choose from rules for nonterminal from terminating_rule_ids
                 rhsix = np.random.choice(self.grammar.terminating_rule_ids[symbol], size=1)
             else:
                 # choose from rules for nonterminal according to production probabilities
                 rhsix = np.random.choice(len(self.grammar.rules[symbol]), p=self.grammar.prod_probabilities[symbol], size=1)
             
             t[node].tag.rule = rhsix[0] # index of production rule used when expanding this node
             rhs = self.grammar.rules[symbol][rhsix[0]]
             for s in rhs:
                 t.create_node(tag=ParseNode(s,''), parent=node)
         
         nodes_to_expand, depth = self.__get_nodes_to_expand_and_depth(t)
     
     return t

    def __init__(self, id, opcode, op_array, context):
        """ Create a tree representaiton of an Opcode

            Arguments :
                id : The id representing the new OPcode
                opcode : An OPcode struct
                op_array : The op_array of the OPcode
                context : An OPcacheParser instance
        """

        Tree.__init__(self)

        # Identifier to be used by the tree and nodes
        id_with_hash = str(hash(str(op_array))) + "_" + id

        # OP name
        op = OPcodeParser.get_opcode_name(opcode['opcode'])

        # Parser
        context = OPcodeParser(context)

        # Parse operands and result
        (op1, op2, result) = context.parse_operands(opcode, op_array)

        # Create nodes
        op1_node = Node("Operand 1: " + op1, id_with_hash + "_op1")
        op2_node = Node("Operand 2: " + op2, id_with_hash + "_op2")
        result_node = Node("Result: " + result, id_with_hash + "_result")

        # Link nodes to tree
        self.create_node(id + ": " + op, id_with_hash + "_opcode")
        self.add_node(op1_node, parent=id_with_hash + "_opcode")
        self.add_node(op2_node, parent=id_with_hash + "_opcode")
        self.add_node(result_node, parent=id_with_hash + "_opcode")

def create_trees(BP, Roots, NT, n):

    for bp in BP[n-1,0]:
        if bp.name in Roots:
            print '\nTree'
            t = Tree()
            create_tree(t, bp, 0, 1)
            t.show(key=lambda x: x.identifier)

def merge_trees(t1, t2, tick):
  t = Tree()
  identifier = -tick # using negative numbers as identifiers, positive numbers are ids for the leaf nodes
  name = "new_cluster_%s" % tick
  t.create_node(name, identifier)
  t.paste(identifier, t1)
  t.paste(identifier, t2)
  return t, name

def create_tree(indexed_titles, root, children=None):
  t = Tree()
  identifier = indexed_titles[root]
  t.create_node(root, identifier)
  if children:
    for sub_tree in children:
      t.paste(identifier, sub_tree)
  return t

def build_conversation(cursor):
    conversation_roots = postgres_queries.find_conversations_root(cursor)
    conversation_list = list()
    for root in conversation_roots:
        conversation_tree = Tree()
        conversation_tree.create_node(root[0], root[0])
        search_children(root[0], conversation_tree, cursor)
        conversation_list.append(conversation_tree)
    return conversation_list

 def compare_actual_folder_with_tree(self, root: path, tree: Tree):
     root_name = tree.root
     root_path = root.joinpath(root_name)
     print(root_path)
     self.assertTrue(root_path.exists(), "The path {} should exist, but doesn't".format(root_path))
     children = tree.children(root_name)
     for children in children:
         subtree = tree.subtree(children.identifier)
         self.compare_actual_folder_with_tree(root_path, subtree)

 def create_powerset_tree(self):
     tree = Tree(None)
     for idx, s in enumerate(self.object_sets):
         if idx == 0:
             tree.create_node((s, self.get_max_timeset(s)), s)
         else:
             parent_index = frozenset(sorted(list(s)[0:-1]))
             tree.create_node((s, self.get_max_timeset(s)), s, parent_index)
     return tree