--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/HashTree.py	Mon Apr 22 21:01:00 2013 +0200
@@ -0,0 +1,147 @@
+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 getSubtreeList(self):
+        """returns the subtree as 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).getSubtreeList())
+                
+            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.
+        """
+        #logging.debug("getNode(key=%s)"%(key))
+        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
+        
+    
+