1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
19
22
24 """Stores a list of nodes that are linked together."""
25
27 """Initiates a node chain: (self)."""
28 self.chain={}
29 self.id=-1
30
32 """Gets a new id for a node in the chain."""
33 self.id+=1
34 return self.id
35
37 """Return a list of all node ids."""
38 return self.chain.keys()
39
40 - def add(self,node,prev=None):
41 """Attaches node to another: (self, node, prev)."""
42 if prev is not None and prev not in self.chain:
43 raise ChainException('Unknow predecessor: '+str(prev))
44 else:
45 id=self._get_id()
46 node.set_id(id)
47 node.set_prev(prev)
48 if prev is not None:
49 self.chain[prev].add_succ(id)
50 self.chain[id]=node
51 return id
52
54 """Deletes node from chain and relinks successors to predecessor: collapse(self, id)."""
55 if id not in self.chain:
56 raise ChainException('Unknown ID: '+str(id))
57 prev_id=self.chain[id].get_prev()
58 self.chain[prev_id].remove_succ(id)
59 succ_ids=self.chain[id].get_succ()
60 for i in succ_ids:
61 self.chain[i].set_prev(prev_id)
62 self.chain[prev_id].add_succ(succ_ids)
63 node=self.chain[id]
64 self.kill(id)
65 return node
66
68 """Kills a node from chain without caring to what it is connected: kill(self,id)."""
69 if id not in self.chain:
70 raise ChainException('Unknown ID: '+str(id))
71 else:
72 del self.chain[id]
73
75 """Disconnects node from his predecessor: unlink(self,id)."""
76 if id not in self.chain:
77 raise ChainException('Unknown ID: '+str(id))
78 else:
79 prev_id=self.chain[id].prev
80 if prev_id is not None:
81 self.chain[prev_id].succ.pop(self.chain[prev_id].succ.index(id))
82 self.chain[id].prev=None
83 return prev_id
84
85 - def link(self, parent,child):
86 """Connects son to parent: link(self,son,parent)."""
87 if child not in self.chain:
88 raise ChainException('Unknown ID: '+str(child))
89 elif parent not in self.chain:
90 raise ChainException('Unknown ID: '+str(parent))
91 else:
92 self.unlink(child)
93 self.chain[parent].succ.append(child)
94 self.chain[child].set_prev(parent)
95
97 """Check if grandchild is a subnode of parent: is_parent_of(self,parent,grandchild)."""
98 if grandchild==parent or grandchild in self.chain[parent].get_succ():
99 return True
100 else:
101 for sn in self.chain[parent].get_succ():
102 if self.is_parent_of(sn,grandchild):
103 return True
104 else:
105 return False
106
107 - def trace(self,start,finish):
108 """Returns a list of all node_ids between two nodes (excluding start, including end): trace(start,end)."""
109 if start not in self.chain or finish not in self.chain:
110 raise NodeException('Unknown node.')
111 if not self.is_parent_of(start,finish) or start==finish:
112 return []
113 for sn in self.chain[start].get_succ():
114 if self.is_parent_of(sn,finish):
115 return [sn]+self.trace(sn,finish)
116
118 """A single node."""
119
121 """Represents a node with one predecessor and multiple successors: (self, data=None)."""
122 self.id=None
123 self.data=data
124 self.prev=None
125 self.succ=[]
126
128 """Sets the id of a node, if not set yet: (self,id)."""
129 if self.id is not None:
130 raise NodeException, 'Node id cannot be changed.'
131 self.id=id
132
134 """Returns the node's id: (self)."""
135 return self.id
136
138 """Returns a list of the node's successors: (self)."""
139 return self.succ
140
142 """Returns the id of the node's predecessor: (self)."""
143 return self.prev
144
146 """Adds a node id to the node's successors: (self,id)."""
147 if isinstance(id,type([])):
148 self.succ.extend(id)
149 else:
150 self.succ.append(id)
151
153 """Removes a node id from the node's successors: (self,id)."""
154 self.succ.remove(id)
155
157 """Sets the node's successors: (self,new_succ)."""
158 if not isinstance(new_succ,type([])):
159 raise NodeException, 'Node successor must be of list type.'
160 self.succ=new_succ
161
163 """Sets the node's predecessor: (self,id)."""
164 self.prev=id
165
167 """Returns a node's data: (self)."""
168 return self.data
169
171 """Sets a node's data: (self,data)."""
172 self.data=data
173