« back to all changes in this revision
Viewing changes to GTG/tools/liblarch/tree.py
- browse files at revision 1058.2.14
- compare with another revision
- download diff
- download tarball
- view history from revision 1058.2.14
- Committer: Izidor Matušov
- Date: 2012-02-29 10:06:41 UTC
- mfrom: (1098 gtg)
- mto: This revision was merged to the branch mainline in revision 1103.
- Revision ID: izidor.matusov@gmail.com-20120229100641-q1uns4yqz1fem2z4
Merged with the current trunk & solved problems with offset
- files added:
- GTG/tests/test_extract_tags.py
- files removed:
- GTG/gtk/liblarch_gtk
- GTG/tools/liblarch
- files renamed:
- GTG/core/tagstore.py => GTG/core/tag.py
- files modified:
- AUTHORS
added
removed
GTG/tools/liblarch/tree.py
1
# -*- coding: utf-8 -*-
2
# -----------------------------------------------------------------------------
3
# Getting Things Gnome! - a personal organizer for the GNOME desktop
4
# Copyright (c) 2008-2011 - Lionel Dricot & Bertrand Rousseau
5
#
6
# This program is free software: you can redistribute it and/or modify it under
7
# the terms of the GNU General Public License as published by the Free Software
8
# Foundation, either version 3 of the License, or (at your option) any later
9
# version.
10
#
11
# This program is distributed in the hope that it will be useful, but WITHOUT
12
# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13
# FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14
# details.
15
#
16
# You should have received a copy of the GNU General Public License along with
17
# this program. If not, see <http://www.gnu.org/licenses/>.
18
# -----------------------------------------------------------------------------
19
20
21
import threading
22
import gobject
23
24
class SyncQueue:
25
""" Synchronized queue for processing requests"""
26
27
def __init__(self, callback):
28
""" Initialize synchronized queue.
29
30
@param callback - function for processing requests"""
31
self._queue = []
32
self._vip_queue = []
33
self._handler = None
34
self.callback = callback
35
self._lock = threading.Lock()
36
37
def push(self, *element):
38
""" Add a new element to the queue.
39
40
Schedule its processing if it is not already.
41
"""
42
self._lock.acquire()
43
self._queue.append(element)
44
45
if self._handler is None:
46
self._handler = gobject.idle_add(self.callback)
47
self._lock.release()
48
49
def priority_push(self, *element):
50
""" Add a new element to the queue.
51
52
Schedule its processing if it is not already.
53
vip element are in a priority queue. They will be processed first
54
(this comment was actually written in Berlin Airport, after having
55
to wait in an economy class queue)"""
56
self._lock.acquire()
57
self._vip_queue.append(element)
58
59
if self._handler is None:
60
self._handler = gobject.idle_add(self.callback)
61
self._lock.release()
62
63
def process(self):
64
""" Return elements to process
65
66
At the moment, it returns just one element. In the future more
67
elements may be better to return (to speed it up).
68
69
If there is no request left, disable processing. """
70
71
self._lock.acquire()
72
if len(self._vip_queue) > 0:
73
toreturn = [self._vip_queue.pop(0)]
74
elif len(self._queue) > 0:
75
toreturn = [self._queue.pop(0)]
76
else:
77
toreturn = []
78
79
if len(self._queue) == 0 and len(self._vip_queue) == 0 and\
80
self._handler is not None:
81
gobject.source_remove(self._handler)
82
self._handler = None
83
self._lock.release()
84
return toreturn
85
86
class MainTree:
87
""" Tree which stores and handle all requests """
88
89
def __init__(self):
90
""" Initialize MainTree.
91
92
@param root - the "root" node which contains all nodes
93
"""
94
95
self.nodes = {}
96
self.pending_relationships = []
97
98
self.__cllbcks = {}
99
100
self.root_id = 'root'
101
self.root = TreeNode(self.root_id)
102
self.root.set_tree(self)
103
104
self._queue = SyncQueue(self._process_queue)
105
self._origin_thread = threading.current_thread()
106
107
def __str__(self):
108
return "<Tree: root = '%s'>" % self.root
109
110
def get_root(self):
111
""" Return root node """
112
return self.root
113
114
####### INTERFACE FOR CALLBACKS ###############################################
115
def register_callback(self, event, func):
116
""" Store function and return unique key which can be used to
117
unregister the callback later """
118
119
if not self.__cllbcks.has_key(event):
120
self.__cllbcks[event] = {}
121
122
callbacks = self.__cllbcks[event]
123
key = 0
124
while callbacks.has_key(key):
125
key += 1
126
127
callbacks[key] = func
128
return key
129
130
def deregister_callback(self, event, key):
131
""" Remove the callback identifed by key (from register_cllbck) """
132
try:
133
del self.__cllbcks[event][key]
134
except KeyError:
135
pass
136
137
def _callback(self, event, node_id):
138
""" Inform others about the event """
139
#We copy the dict to not loop on it while it could be modified
140
dic = dict(self.__cllbcks.get(event, {}))
141
for func in dic.itervalues():
142
func(node_id)
143
144
####### INTERFACE FOR HANDLING REQUESTS #######################################
145
def add_node(self, node, parent_id=None, high_priority=False):
146
self._external_request(self._add_node, high_priority, node, parent_id)
147
148
def remove_node(self, node_id, recursive=False):
149
self._external_request(self._remove_node, True, node_id, recursive)
150
151
def modify_node(self, node_id):
152
self._external_request(self._modify_node, False, node_id)
153
154
def new_relationship(self, parent_id, child_id):
155
self._external_request(self._new_relationship, False, parent_id, child_id)
156
157
def break_relationship(self, parent_id, child_id):
158
self._external_request(self._break_relationship, False, parent_id, child_id)
159
160
def _external_request(self, request_type, vip, *args):
161
""" Put the reqest into queue and in the main thread handle it """
162
if vip:
163
self._queue.priority_push(request_type, *args)
164
else:
165
self._queue.push(request_type, *args)
166
167
if self._origin_thread == threading.current_thread():
168
self._process_queue()
169
170
def _process_queue(self):
171
""" Process requests from queue """
172
for action in self._queue.process():
173
func = action[0]
174
func(*action[1:])
175
176
# return True to process other requests as well
177
return True
178
179
def refresh_all(self):
180
""" Refresh all nodes """
181
for node_id in self.nodes.keys():
182
self.modify_node(node_id)
183
184
####### IMPLEMENTATION OF HANDLING REQUESTS ###################################
185
def _create_relationship(self, parent_id, child_id):
186
""" Create relationship without any checks """
187
parent = self.nodes[parent_id]
188
child = self.nodes[child_id]
189
190
if child_id not in parent.children:
191
parent.children.append(child_id)
192
193
if parent_id not in child.parents:
194
child.parents.append(parent_id)
195
196
if child_id in self.root.children:
197
self.root.children.remove(child_id)
198
199
def _destroy_relationship(self, parent_id, child_id):
200
""" Destroy relationship without any checks """
201
parent = self.nodes[parent_id]
202
child = self.nodes[child_id]
203
204
if child_id in parent.children:
205
parent.children.remove(child_id)
206
207
if parent_id in child.parents:
208
child.parents.remove(parent_id)
209
210
def _is_circular_relation(self, parent_id, child_id):
211
""" Would the new relation be circular?
212
213
Go over every possible ancestors. If one of them is child_id,
214
this would be circular relation.
215
"""
216
217
visited = []
218
ancestors = [parent_id]
219
while ancestors != []:
220
node_id = ancestors.pop(0)
221
if node_id == child_id:
222
return True
223
224
if node_id not in self.nodes:
225
continue
226
227
for ancestor_id in self.nodes[node_id].parents:
228
if ancestor_id not in visited:
229
ancestors.append(ancestor_id)
230
231
return False
232
233
def _add_node(self, node, parent_id):
234
""" Add a node to the tree
235
236
@param node - node to be added
237
@param parent_id - parent to add or it will be add to root
238
"""
239
node_id = node.get_id()
240
if node_id in self.nodes:
241
print "Error: Node '%s' already exists" % node_id
242
return False
243
244
node.set_tree(self)
245
for relationship in node.pending_relationships:
246
if relationship not in self.pending_relationships:
247
self.pending_relationships.append(relationship)
248
node.pending_relationships = []
249
250
self.nodes[node_id] = node
251
252
add_to_root = True
253
parents_to_refresh = []
254
children_to_refresh = []
255
256
# Build pending relationships
257
for rel_parent_id, rel_child_id in list(self.pending_relationships):
258
# Adding as a child
259
if rel_child_id == node_id and rel_parent_id in self.nodes:
260
if not self._is_circular_relation(rel_parent_id, node_id):
261
self._create_relationship(rel_parent_id, node_id)
262
add_to_root = False
263
parents_to_refresh.append(rel_parent_id)
264
else:
265
print "Error: Detected pending circular relationship", \
266
rel_parent_id, rel_child_id
267
self.pending_relationships.remove((rel_parent_id, rel_child_id))
268
269
# Adding as a parent
270
if rel_parent_id == node_id and rel_child_id in self.nodes:
271
if not self._is_circular_relation(node_id, rel_child_id):
272
self._create_relationship(node_id, rel_child_id)
273
children_to_refresh.append(rel_child_id)
274
else:
275
print "Error: Detected pending circular relationship", \
276
rel_parent_id, rel_child_id
277
self.pending_relationships.remove((rel_parent_id, rel_child_id))
278
279
# Build relationship with given parent
280
if parent_id is not None:
281
if self._is_circular_relation(parent_id, node_id):
282
raise Exception('Creating circular relationship between %s and %s' % \
283
(parent_id, node_id))
284
if parent_id in self.nodes:
285
self._create_relationship(parent_id, node_id)
286
add_to_root = False
287
parents_to_refresh.append(parent_id)
288
else:
289
self.pending_relationships.append((parent_id, node_id))
290
291
# Add at least to root
292
if add_to_root:
293
self.root.children.append(node_id)
294
295
# Send callbacks
296
297
#FIXME: this callback is very slow with treemodelsort
298
for parent_id in parents_to_refresh:
299
self._callback("node-modified", parent_id)
300
301
#FIXME: this callback is very slow with treemodelsort
302
self._callback("node-added", node_id)
303
304
#this callback is really fast. No problem
305
for child_id in children_to_refresh:
306
#FIXME: why parent_id? this should be a bug!
307
#removing this doesn't affect the tests. Why is it useful?
308
self._callback("node-modified", child_id)
309
310
def _remove_node(self, node_id, recursive=False):
311
""" Remove node from tree """
312
313
if node_id not in self.nodes:
314
print "*** Warning *** Trying to remove a non-existing node"
315
return
316
317
# Do not remove root node
318
if node_id is None:
319
return
320
321
# Remove pending relationships with this node
322
for relation in list(self.pending_relationships):
323
if node_id in relation:
324
self.pending_relationships.remove(relation)
325
326
node = self.nodes[node_id]
327
328
# Handle parents
329
for parent_id in node.parents:
330
self._destroy_relationship(parent_id, node_id)
331
self._callback('node-modified', parent_id)
332
333
# Handle children
334
for child_id in list(node.children):
335
if recursive:
336
self._remove_node(child_id, True)
337
else:
338
self._destroy_relationship(node_id, child_id)
339
self._callback('node-modified', child_id)
340
if self.nodes[child_id].parents == []:
341
self.root.children.append(child_id)
342
343
if node_id in self.root.children:
344
self.root.children.remove(node_id)
345
346
self.nodes.pop(node_id)
347
self._callback('node-deleted', node_id)
348
349
def _modify_node(self, node_id):
350
""" Force update of a node """
351
if node_id != self.root_id and node_id in self.nodes:
352
self._callback('node-modified', node_id)
353
354
def _new_relationship(self, parent_id, child_id):
355
""" Creates a new relationship
356
357
This method is used mainly from TreeNode"""
358
359
if (parent_id, child_id) in self.pending_relationships:
360
self.pending_relationships.remove((parent_id, child_id))
361
362
if not parent_id or not child_id or parent_id == child_id:
363
return False
364
365
if parent_id not in self.nodes or child_id not in self.nodes:
366
self.pending_relationships.append((parent_id, child_id))
367
return True
368
369
if self._is_circular_relation(parent_id, child_id):
370
self._destroy_relationship(parent_id, child_id)
371
raise Exception('Cannot build circular relationship between %s and %s' % (parent_id, child_id))
372
373
374
self._create_relationship(parent_id, child_id)
375
376
# Remove from root when having a new relationship
377
if child_id in self.root.children:
378
self.root.children.remove(child_id)
379
380
self._callback('node-modified', parent_id)
381
self._callback('node-modified', child_id)
382
383
def _break_relationship(self, parent_id, child_id):
384
""" Remove a relationship
385
386
This method is used mainly from TreeNode """
387
for rel_parent, rel_child in list(self.pending_relationships):
388
if rel_parent == parent_id and rel_child == child_id:
389
self.pending_relationships.remove((rel_parent, rel_child))
390
391
if not parent_id or not child_id or parent_id == child_id:
392
return False
393
394
if parent_id not in self.nodes or child_id not in self.nodes:
395
return False
396
397
self._destroy_relationship(parent_id, child_id)
398
399
# Move to root if beak the last parent
400
if self.nodes[child_id].get_parents() == []:
401
self.root.add_child(child_id)
402
403
self._callback('node-modified', parent_id)
404
self._callback('node-modified', child_id)
405
406
407
####### INTERFACE FOR READING STATE OF TREE ###################################
408
def has_node(self, node_id):
409
""" Is this node_id in this tree? """
410
return node_id in self.nodes
411
412
def get_node(self, node_id=None):
413
""" Return node of tree or root node of this tree """
414
if node_id in self.nodes:
415
return self.nodes[node_id]
416
elif node_id == self.root_id or node_id is None:
417
return self.root
418
else:
419
raise ValueError("Node %s is not in the tree" % node_id)
420
421
def get_node_for_path(self, path):
422
""" Convert path into node_id
423
424
@return node_id if path is valid, None otherwise
425
"""
426
if not path or path == ():
427
return None
428
node_id = path[-1]
429
if path in self.get_paths_for_node(node_id):
430
return node_id
431
else:
432
return None
433
return node_id
434
435
def get_paths_for_node(self, node_id):
436
""" Get all paths for node_id """
437
if not node_id or node_id == self.root_id:
438
return [()]
439
elif node_id in self.nodes:
440
node = self.nodes[node_id]
441
if node.has_parent():
442
paths = []
443
for parent_id in node.get_parents():
444
if parent_id not in self.nodes:
445
continue
446
for path in self.get_paths_for_node(parent_id):
447
paths.append(path + (node_id,))
448
return paths
449
else:
450
return [(node_id,)]
451
else:
452
raise ValueError("Cannot get path for non existing node %s" % node_id)
453
454
def get_all_nodes(self):
455
""" Return list of all nodes in this tree """
456
return self.nodes.keys()
457
458
def next_node(self, node_id, parent_id=None):
459
""" Return the next sibling node or None if there is none
460
461
@param node_id - we look for siblings of this node
462
@param parent_id - specify which siblings should be used,
463
if task has more parents. If None, random parent will be used
464
"""
465
if node_id is None:
466
raise ValueError('node_id should be different than None')
467
468
node = self.get_node(node_id)
469
parents_id = node.get_parents()
470
if len(parents_id) == 0:
471
parid = self.root_id
472
elif parent_id in parents_id:
473
parid = parent_id
474
else:
475
parid = parents_id[0]
476
477
parent = self.get_node(parid)
478
if not parent:
479
raise ValueError('Parent does not exist')
480
481
index = parent.get_child_index(node_id)
482
if index == None:
483
error = 'children are : %s\n' %parent.get_children()
484
error += 'node %s is not a child of %s' %(node_id,parid)
485
raise IndexError(error)
486
487
if parent.get_n_children() > index+1:
488
return parent.get_nth_child(index+1)
489
else:
490
return None
491
492
def print_tree(self, string=False):
493
output = self.root_id + "\n"
494
stack = [(" ", child_id) for child_id in reversed(self.root.children)]
495
496
while stack != []:
497
prefix, node_id = stack.pop()
498
output += prefix + node_id + "\n"
499
prefix += " "
500
for child_id in reversed(self.nodes[node_id].get_children()):
501
stack.append((prefix, child_id))
502
503
if string:
504
return output
505
else:
506
print output,
507
508
class TreeNode:
509
""" Object just for a single node in Tree """
510
# FIXME maybe add a lock which prevents changing root at the wrong moment,
511
# updating children, etc
512
513
def __init__(self, node_id, parent=None):
514
""" Initializes node
515
516
@param node_id - unique identifier of node (str)
517
@param parent - node_id of parent
518
"""
519
self.node_id = node_id
520
521
self.parents = []
522
self.children = []
523
524
self.tree = None
525
self.pending_relationships = []
526
527
if parent:
528
self.add_parent(parent)
529
530
def __str__(self):
531
return "<TreeNode: '%s'>" % (self.node_id)
532
533
def get_id(self):
534
""" Return node_id """
535
return self.node_id
536
537
def modified(self):
538
""" Force to update node (because it has changed) """
539
if self.tree:
540
self.tree.modify_node(self.node_id)
541
542
def set_tree(self, tree):
543
""" Set tree which is should contain this node.
544
545
This method should be called only from MainTree. It is not
546
part of public interface. """
547
self.tree = tree
548
549
def get_tree(self):
550
""" Return associated tree with this node """
551
return self.tree
552
553
def new_relationship(self, parent_id, child_id):
554
""" Create new relationship or save it for later if there is no tree """
555
if self.tree:
556
self.tree.new_relationship(parent_id, child_id)
557
else:
558
self.pending_relationships.append((parent_id, child_id))
559
560
####### Parents ###############################################################
561
def add_parent(self, parent_id):
562
""" Add a new parent """
563
if parent_id not in self.parents:
564
self.parents.append(parent_id)
565
self.new_relationship(parent_id, self.node_id)
566
567
def set_parent(self, parent_id):
568
""" Remove other parents and set this parent as only parent """
569
is_already_parent_flag = False
570
for node_id in self.parents:
571
if node_id != parent_id:
572
self.remove_parent(node_id)
573
else:
574
is_already_parent_flag = True
575
if parent_id and not is_already_parent_flag:
576
self.add_parent(parent_id)
577
578
def remove_parent(self, parent_id):
579
""" Remove parent """
580
if parent_id in self.parents:
581
self.parents.remove(parent_id)
582
self.tree.break_relationship(parent_id, self.node_id)
583
584
def has_parent(self, parent_id=None):
585
""" Has parent/parents?
586
587
@param parent_id - None => has any parent?
588
not None => has this parent?
589
"""
590
if parent_id:
591
return self.tree.has_node(parent_id) and parent_id in self.parents
592
else:
593
return len(self.parents) > 0
594
595
def get_parents(self):
596
""" Return parents of node """
597
parents = []
598
if self.tree:
599
for parent_id in self.parents:
600
if self.tree.has_node(parent_id):
601
parents.append(parent_id)
602
603
return parents
604
605
####### Children ##############################################################
606
def add_child(self, child_id):
607
""" Add a children to node """
608
if child_id not in self.children:
609
self.children.append(child_id)
610
self.new_relationship(self.node_id, child_id)
611
else:
612
print "%s was already in children of %s" % (child_id, self.node_id)
613
614
def has_child(self, child_id=None):
615
""" Has child/children?
616
617
@param child_id - None => has any child?
618
not None => has this child?
619
"""
620
if child_id:
621
return child_id in self.children
622
else:
623
return bool(self.children)
624
625
def get_children(self):
626
""" Return children of nodes """
627
children = []
628
if self.tree:
629
for child_id in self.children:
630
if self.tree.has_node(child_id):
631
children.append(child_id)
632
633
return children
634
635
def get_n_children(self):
636
""" Return count of children """
637
return len(self.get_children())
638
639
def get_nth_child(self, index):
640
""" Return nth child """
641
try:
642
return self.children[index]
643
except(IndexError):
644
raise ValueError("Requested non-existing child")
645
646
def get_child_index(self, node_id):
647
if node_id in self.children:
648
return self.children.index(node_id)
649
else:
650
return None
Loggerhead is a web-based interface for Breezy
Version: 2.0.1