import logging
    
class HashTreeNode:
    """Node of a HashTree.
    Has a value and keeps children in a dict indexed by key."""
    key = None
    value = None
    children = None
    
    def __init__(self, key=None, value=None, children=None):
        """create node"""
        self.key = key
        self.value = value
        self.children = children


    def getNode(self, key):
        """return node under key"""
        if self.children is None:
            return None
        else:
            return self.children.get(key, None)


    def addNode(self, node):
        """add child node using key from node"""
        if self.children is None:
            self.children = {node.key : node}
        else:
            self.children[node.key] = node
            

    def getSubtreeAsList(self, depthFirst=True):
        """Return the subtree as flattened list sorted by key."""
        if depthFirst:
            return self.getSubtreeAsListDepthFirst()
        else:
            return self.getSubtreeAsListBreadthFirst()


    def getSubtreeAsListDepthFirst(self):
        """Return the subtree as flattened list, depth first, sorted by key."""
        if self.children is None:
            if self.value is None:
                return []
            else:
                return [self.value]
            
        else:
            if self.value is None:
                sub = []
            else:
                sub = [self.value]
                
            for k in sorted(self.children.keys()):
                sub.extend(self.children.get(k).getSubtreeAsListDepthFirst())
                    
        return sub


    def getSubtreeAsListBreadthFirst(self):
        """Return the subtree as flattened list, breadth first, sorted by key."""
        q = [self]
        sub = []
        while len(q) > 0:
            node = q.pop(0)
            if node.value is not None:
                sub.append(node.value)
                
            if node.children is not None:
                clist = sorted(node.children.values(), key=lambda x:x.key)
                q.extend(clist)            

        return sub


    def getSubtreeAsText(self):
        """Return whole tree as text. Depth first."""
        if self.children is None:
            return "(%s:%s)"%(self.key, self.value)
        else:
            sub = "(%s:%s):["%(self.key, self.value)
            for k in sorted(self.children.keys()):
                sub += self.children.get(k).getSubtreeAsText()
                sub += ", "
                
            return sub + "] "


class HashTree:
    """Tree using dictionaries"""
    
    # root HashTreeNode
    root = None
    # separator by which key strings are split into parts
    keySeparator = '.'
    # function applied to key parts
    keyFn = None
    
    def __init__(self, keySeparator='.', keyFn=None):
        """Create a HashTree.
        
        @param keySeparator string by which key strings are split into parts
        @param keyFn function applied to key parts (e.g. int if key parts are numbers)
        """
        self.root = HashTreeNode()
        self.keySeparator = keySeparator
        self.keyFn = keyFn
    

    def _splitkey(self, key):
        """Return a list of key parts"""
        if isinstance(key, basestring):
            # its a string - split
            keys = key.split(self.keySeparator)
            if self.keyFn is not None:
                keys = [self.keyFn(k) for k in keys]
                
        elif isinstance(key, list):
            # its a list - keep
            keys = key
            
        else:
            # not a list - wrap in list
            keys = [key]
            
        return keys


    def getNode(self, key):
        """Return node under key from the tree.
        
        key can be sequence of key string or a single string using keySeparator.
        If key is None, returns root node.
        """
        if key is None:
            return self.root

        keys = self._splitkey(key)
            
        node = self.root
        for k in keys:
            node = node.getNode(k)
            if node is None:
                return None
            
        return node


    def get(self, key):
        """Return value under key from the tree.
        
        key can be sequence of key string or a single string using keySeparator.
        """
        node = self.getNode(key)
        if node is None:
            return None
        
        return node.value

     
    def add(self, key, value):
        """Add value under key to the tree.
        
        key can be sequence of key string or a single string using keySeparator.
        """
        keys = self._splitkey(key)
        node = self.root
        for k in keys:
            nextnode = node.getNode(k)
            if nextnode is None:
                nextnode = HashTreeNode(key=k)
                node.addNode(nextnode)
            
            node = nextnode
            
        node.value = value

        
    def getChildrenOf(self, key):
        """Return the list of child (values) of the node under key."""
        node = self.getNode(key)
        if getattr(node, 'children', None) is None:
            return []
        else:
            # sort children by key
            childlist = sorted(node.children.items(), key=lambda x:x[0])
            # and return the values
            return [n.value for k, n in childlist if n.value is not None]


    def getAncestorsOf(self, key):
        """Return the list of ancestor (values) of the node under key.
        
        Order: root element first."""
        keys = self._splitkey(key)
        node = self.root
        ancestors = []
        for k in keys:
            if node.value is not None:
                ancestors.append(node.value)
                
            node = node.getNode(k)
            if node is None:
                return ancestors
            
        return ancestors