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):
        """returns the subtree as flattened list sorted by key (depth first)"""
        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]
                
            keys = self.children.keys()
            keys.sort()
            for k in keys:
                #logging.debug("getSubtreeList: k=%s sub=%s"%(k,sub))
                sub.extend(self.children.get(k).getSubtreeAsList())
                
            return sub


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


class HashTree:
    """Tree using dictionaries"""
    
    root = None
    keySeparator = '.'
    keyFn = None
    
    def __init__(self, keySeparator='.', keyFn=None):
        """creates a HashTree"""
        self.root = HashTreeNode()
        self.keySeparator = keySeparator
        self.keyFn = keyFn
    

    def getNode(self, key):
        """gets 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

        if isinstance(key, basestring):
            keys = key.split(self.keySeparator)
            if self.keyFn is not None:
                keys = [self.keyFn(k) for k in keys]
                
        elif isinstance(key, list):
            keys = key
            
        else:
            keys = [key]
            
        node = self.root
        for k in keys:
            #logging.debug("getNode node=%s k=%s"%(node, repr(k)))
            node = node.getNode(k)
            #logging.debug("getNode got:%s"%(node))
            if node is None:
                return None
            
        return node


    def get(self, key):
        """gets 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):
        """adds value under key to the tree.
        key can be sequence of key string or a single string using keySeparator.
        """
        #logging.debug("add(key=%s, value=%s)"%(repr(key), value))
        if isinstance(key, basestring):
            keys = key.split(self.keySeparator)
            if self.keyFn is not None:
                keys = [self.keyFn(k) for k in keys]
        elif isinstance(key, list):
            keys = key
        else:
            keys = [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