diff corebio/seq_io/_nexus/Nodes.py @ 4:4d47ab2b7bcc

Uploaded

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/corebio/seq_io/_nexus/Nodes.py	Fri Jan 13 07:18:19 2012 -0500
@@ -0,0 +1,172 @@
+# Copyright 2005 by Frank Kauff & Cymon J. Cox. All rights reserved.
+# This code is part of the Biopython distribution and governed by its
+# license. Please see the LICENSE file that should have been included
+# as part of this package.
+#
+# Nodes.py
+# 
+# Provides functionality of a linked list.
+# Each node has one (or none) predecessor, and an arbitrary number of successors.
+# Nodes can store arbitrary data in a NodeData class.
+#
+# Subclassed by Nexus.Trees to store phylogenetic trees.
+#
+# Bug reports to Frank Kauff ([e-mail])
+#
+
+class ChainException(Exception):
+    pass
+
+class NodeException(Exception):
+    pass
+
+class Chain:
+    """Stores a list of nodes that are linked together."""
+    
+    def __init__(self):
+        """Initiates a node chain: (self)."""
+        self.chain={}
+        self.id=-1
+
+    def _get_id(self):
+        """Gets a new id for a node in the chain."""
+        self.id+=1
+        return self.id 
+   
+    def all_ids(self):
+        """Return a list of all node ids."""
+        return self.chain.keys()
+
+    def add(self,node,prev=None):
+        """Attaches node to another: (self, node, prev)."""
+        if prev is not None and prev not in self.chain:
+            raise ChainException('Unknow predecessor: '+str(prev))
+        else:
+            id=self._get_id()
+            node.set_id(id)
+            node.set_prev(prev)
+            if prev is not None:
+                self.chain[prev].add_succ(id)
+            self.chain[id]=node
+        return id
+
+    def collapse(self,id):
+        """Deletes node from chain and relinks successors to predecessor: collapse(self, id)."""
+        if id not in self.chain:
+            raise ChainException('Unknown ID: '+str(id))
+        prev_id=self.chain[id].get_prev()
+        self.chain[prev_id].remove_succ(id)
+        succ_ids=self.chain[id].get_succ()
+        for i in succ_ids:
+            self.chain[i].set_prev(prev_id)
+        self.chain[prev_id].add_succ(succ_ids)
+        node=self.chain[id]
+        self.kill(id)
+        return node
+
+    def kill(self,id):
+        """Kills a node from chain without caring to what it is connected: kill(self,id)."""
+        if id not in self.chain:
+            raise ChainException('Unknown ID: '+str(id))
+        else:
+            del self.chain[id]
+
+    def unlink(self,id):
+        """Disconnects node from his predecessor: unlink(self,id)."""
+        if id not in self.chain:
+            raise ChainException('Unknown ID: '+str(id))
+        else:
+            prev_id=self.chain[id].prev
+            if prev_id is not None:
+                self.chain[prev_id].succ.pop(self.chain[prev_id].succ.index(id))
+            self.chain[id].prev=None
+            return prev_id
+
+    def link(self, parent,child):
+        """Connects son to parent: link(self,son,parent)."""
+        if child not in self.chain:
+            raise ChainException('Unknown ID: '+str(child))
+        elif parent not in self.chain:
+            raise ChainException('Unknown ID: '+str(parent))
+        else:
+            self.unlink(child)
+            self.chain[parent].succ.append(child)
+            self.chain[child].set_prev(parent)
+
+    def is_parent_of(self,parent,grandchild):
+        """Check if grandchild is a subnode of parent: is_parent_of(self,parent,grandchild)."""
+        if grandchild==parent or grandchild in self.chain[parent].get_succ():
+            return True
+        else:
+            for sn in self.chain[parent].get_succ():
+                if self.is_parent_of(sn,grandchild):
+                    return True
+            else:
+                return False
+
+    def trace(self,start,finish):
+        """Returns a list of all node_ids between two nodes (excluding start, including end): trace(start,end)."""
+        if start not in self.chain or finish not in self.chain:
+            raise NodeException('Unknown node.')
+        if not self.is_parent_of(start,finish) or start==finish:
+            return []
+        for sn in self.chain[start].get_succ():
+            if self.is_parent_of(sn,finish):
+                return [sn]+self.trace(sn,finish)
+                
+class Node:
+    """A single node."""
+
+    def __init__(self,data=None):
+        """Represents a node with one predecessor and multiple successors: (self, data=None)."""
+        self.id=None
+        self.data=data
+        self.prev=None
+        self.succ=[]
+
+    def set_id(self,id):
+        """Sets the id of a node, if not set yet: (self,id)."""
+        if self.id is not None:
+            raise NodeException, 'Node id cannot be changed.'
+        self.id=id
+
+    def get_id(self):
+        """Returns the node's id: (self)."""
+        return self.id
+
+    def get_succ(self):
+        """Returns a list of the node's successors: (self)."""
+        return self.succ
+
+    def get_prev(self):
+        """Returns the id of the node's predecessor: (self)."""
+        return self.prev
+
+    def add_succ(self,id):
+        """Adds a node id to the node's successors: (self,id)."""
+        if isinstance(id,type([])):
+            self.succ.extend(id)
+        else:
+            self.succ.append(id)
+
+    def remove_succ(self,id):
+        """Removes a node id from the node's successors: (self,id)."""
+        self.succ.remove(id)
+
+    def set_succ(self,new_succ):
+        """Sets the node's successors: (self,new_succ)."""
+        if not isinstance(new_succ,type([])):
+            raise NodeException, 'Node successor must be of list type.'
+        self.succ=new_succ
+
+    def set_prev(self,id):
+        """Sets the node's predecessor: (self,id)."""
+        self.prev=id
+    
+    def get_data(self):
+        """Returns a node's data: (self)."""
+        return self.data
+
+    def set_data(self,data):
+        """Sets a node's data: (self,data)."""
+        self.data=data