~bryce/gtg/dbus-service-name : revision 821.1.10

1

# -*- coding: utf-8 -*-

2

# -----------------------------------------------------------------------------

3

# Gettings Things Gnome! - a personal organizer for the GNOME desktop

4

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

from GTG.tools.logger import Log

21

22

class MainTree():

23

24

25

def __init__(self, root=None):

26

self.root_id = 'root'

27

self.nodes = {}

28

self.old_paths = {}

29

self.pending_relationships = []

30

if root:

31

self.root = root

32

else:

33

self.root = TreeNode(id=self.root_id)

34

self.root.set_tree(self)

35

36

def __str__(self):

37

return "<Tree: root = '%s'>" % (str(self.root))

38

39

def get_node_for_path(self, path):

40

return self._node_for_path(self.root,path)

41

42

def get_path_for_node(self, node):

43

toreturn = self._path_for_node(node)

44

return toreturn

45

46

#a deleted path can be requested only once

47

def get_deleted_path(self,id):

48

toreturn = None

49

print "old paths are : %s" %self.old_paths

50

if self.old_paths.has_key(id):

51

toreturn = self.old_paths.pop(id)

52

return toreturn

53

54

55

def get_root(self):

56

return self.root

57

58

def set_root(self, root):

59

self.root = root

60

self.root.set_tree(self)

61

62

#We add a node. By default, it's a child of the root

63

def add_node(self, node, parent_id=None):

64

#print "*************adding node %s %s" %(node, parent)

65

id = node.get_id()

66

if self.nodes.has_key(id):

67

print "Error : A node with this id %s already exists" %id

68

return False

69

else:

70

#We add the node

71

node.set_tree(self)

72

if parent_id:

73

parent = self.get_node(parent_id)

74

if parent:

75

node.set_parent(parent.get_id())

76

parent.add_child(id)

77

else:

78

self.root.add_child(id)

79

self.nodes[id] = node

80

#build the relationships that were waiting for that node

81

for rel in list(self.pending_relationships):

82

if id in rel:

83

self.new_relationship(rel[0],rel[1])

84

return True

85

86

#this will remove a node and all his children

87

#does nothing if the node doesn't exist

88

def remove_node(self, id):

89

node = self.get_node(id)

90

path = self.get_path_for_node(node)

91

if not node :

92

return

93

else:

94

if node.has_child():

95

for c_id in node.get_children():

96

self.remove_node(c_id)

97

if node.has_parent():

98

for p_id in node.get_parents():

99

par = self.get_node(p_id)

100

par.remove_child(id)

101

else:

102

self.root.remove_child(id)

103

self.old_paths[id] = path

104

self.nodes.pop(id)

105

106

#create a new relationship between nodes if it doesn't already exist

107

#return False if nothing was done

108

def new_relationship(self,parent_id,child_id):

109

Log.debug("new relationship between %s and %s" %(parent_id,child_id))

110

if [parent_id,child_id] in self.pending_relationships:

111

self.pending_relationships.remove([parent_id,child_id])

112

toreturn = False

113

#no relationship allowed with yourself

114

if parent_id != child_id:

115

if parent_id == 'root':

116

# Log.debug(" -> adding %s to the root" %child_id)

117

p = self.get_root()

118

else:

119

p = self.get_node(parent_id)

120

c = self.get_node(child_id)

121

if p and c :

122

#no circular relationship allowed

123

if not p.has_parent(child_id) and not c.has_child(parent_id):

124

if not p.has_child(child_id):

125

p.add_child(child_id)

126

toreturn = True

127

if parent_id != 'root' and not c.has_parent(parent_id):

128

c.add_parent(parent_id)

129

toreturn = True

130

#removing the root from the list of parent

131

if self.root.has_child(child_id):

132

self.root.remove_child(child_id)

133

if not toreturn:

134

Log.debug(" * * * * * Relationship already existing")

135

else:

136

#a circular relationship was found

137

#undo everything

138

Log.debug(" * * * * * Circular relationship found : undo")

139

self.break_relationship(parent_id,child_id)

140

toreturn = False

141

else:

142

#at least one of the node is not loaded. Save the relation for later

143

#undo everything

144

self.break_relationship(parent_id,child_id)

145

#save it for later

146

if [parent_id,child_id] not in self.pending_relationships:

147

self.pending_relationships.append([parent_id,child_id])

148

toreturn = True

149

return toreturn

150

151

#break an existing relationship. The child is added to the root

152

#return False if the relationship didn't exist

153

def break_relationship(self,parent_id,child_id):

154

toreturn = False

155

p = self.get_node(parent_id)

156

c = self.get_node(child_id)

157

if p and c :

158

if p.has_child(child_id):

159

ret = p.remove_child(child_id)

160

toreturn = True

161

if c.has_parent(parent_id):

162

c.remove_parent(parent_id)

163

toreturn = True

164

#if no more parent left, adding to the root

165

if not c.has_parent():

166

self.root.add_child(child_id)

167

return toreturn

168

169

#Trying to make a function that bypass the weirdiness of lists

170

def get_node(self,id):

171

return self.nodes.get(id)

172

173

def get_all_keys(self):

174

return list(self.nodes.keys())

175

176

def get_all_nodes(self):

177

li = []

178

for k in self.nodes.keys():

179

no = self.get_node(k)

180

if no:

181

li.append(no)

182

return li

183

184

def has_node(self, id):

185

return (self.nodes.get(id) != None)

186

187

def print_tree(self):

188

self._print_from_node(self.root)

189

190

def visit_tree(self, pre_func=None, post_func=None):

191

if self.root.has_child():

192

for c in self.root.get_children():

193

node = self.root.get_child(c)

194

self._visit_node(node, pre_func, post_func)

195

196

### HELPER FUNCTION FOR TREE #################################################

197

#

198

def _node_for_path(self,node,path):

199

if path[0] < node.get_n_children():

200

if len(path) == 1:

201

return node.get_nth_child(path[0])

202

else:

203

node = node.get_nth_child(path[0])

204

path = path[1:]

205

return self._node_for_path(node, path)

206

else:

207

return None

208

209

def _path_for_node(self, node):

210

if node:

211

if node == self.root:

212

toreturn = ()

213

elif not node.has_parent():

214

index = self.root.get_child_index(node.get_id())

215

toreturn = self._path_for_node(self.root) + (index, )

216

else:

217

# no multiparent support here

218

parent_id = node.get_parent()

219

if len(node.get_parents()) >= 2:

220

print "multiple parents for task %s" %node.get_id()

221

print "you should use a filteredtree above this tree"

222

parent = self.get_node(parent_id)

223

if parent:

224

index = parent.get_child_index(node.get_id())

225

toreturn = self._path_for_node(parent) + (index, )

226

else:

227

toreturn = ()

228

# print "returning %s" %str(toreturn)

229

else:

230

toreturn = None

231

return toreturn

232

233

def _print_from_node(self, node, prefix=""):

234

print prefix + node.id

235

prefix = prefix + " "

236

if node.has_child():

237

for c in node.get_children():

238

cur_node = node.get_child(c)

239

self._print_from_node(cur_node, prefix)

240

241

def _visit_node(self, node, pre_func=None, post_func=None):

242

if pre_func:

243

pre_func(node)

244

if node.has_child():

245

for c in node.get_children():

246

cur_node = node.get_child(c)

247

self._visit_node(cur_node, pre_func, post_func)

248

if post_func:

249

post_func(node)

250

251

252

class TreeNode():

253

254

def __init__(self, id, parent=None):

255

self.parents = []

256

self.id = id

257

self.children = []

258

self.tree = None

259

self.pending_relationship = []

260

if parent:

261

self.add_parent(parent)

262

263

def __str__(self):

264

return "<TreeNode: '%s'>" % (self.id)

265

266

def set_tree(self,tree):

267

self.tree = tree

268

for rel in list(self.pending_relationship):

269

self.tree.new_relationship(rel[0],rel[1])

270

self.pending_relationship.remove(rel)

271

272

def get_tree(self):

273

return self.tree

274

275

def get_id(self):

276

return self.id

277

278

279

def new_relationship(self,par,chi):

280

if self.tree:

281

return self.tree.new_relationship(par,chi)

282

else:

283

self.pending_relationship.append([par,chi])

284

#it's pending, we return False

285

Log.debug("** There's still no tree, relationship is pending")

286

return False

287

288

289

##### Parents

290

291

def has_parent(self,id=None):

292

if id:

293

return id in self.parents

294

else:

295

toreturn = len(self.parents) > 0

296

return toreturn

297

298

#this one return only one parent.

299

#useful for tree where we know that there is only one

300

def get_parent(self):

301

#we should throw an error if there are multiples parents

302

if len(self.parents) > 1 :

303

print "Warning: get_parent will return one random parent for task %s because there are multiple parents." %(self.get_id())

304

print "Get_parent is deprecated. Please use get_parents instead"

305

if self.has_parent():

306

return self.parents[0]

307

else:

308

return None

309

310

def get_parents(self):

311

'''

312

Return a list of parent ids

313

'''

314

return list(self.parents)

315

316

def add_parent(self, parent_id):

317

# root = self.tree.get_root()

318

# print "removing root node has parent"

319

# self.tree.break_relationship(root.get_id(),self.get_id())

320

if parent_id not in self.parents:

321

self.parents.append(parent_id)

322

toreturn = self.new_relationship(parent_id, self.get_id())

323

# if not toreturn:

324

# Log.debug("** parent addition failed (probably already done)*")

325

else:

326

toreturn = False

327

return toreturn

328

329

#set_parent means that we remove all other parents

330

def set_parent(self,par_id):

331

is_already_parent_flag = False

332

if par_id:

333

for i in self.parents:

334

if i != par_id:

335

assert(self.remove_parent(i) == True)

336

else:

337

is_already_parent_flag = True

338

if not is_already_parent_flag:

339

self.add_parent(par_id)

340

341

def remove_parent(self,id):

342

if id in self.parents:

343

self.parents.remove(id)

344

ret = self.tree.break_relationship(id,self.get_id())

345

return ret

346

else:

347

return False

348

349

###### Children

350

351

def has_child(self,id=None):

352

if id :

353

return id in self.children

354

else:

355

return len(self.children) != 0

356

357

def get_children(self):

358

return list(self.children)

359

360

def get_n_children(self):

361

return len(self.children)

362

363

def get_nth_child(self, index):

364

try:

365

id = self.children[index]

366

return self.tree.get_node(id)

367

except(IndexError):

368

raise ValueError("Index is not in the children list")

369

370

def get_child(self, id):

371

if id in self.children:

372

return self.tree.get_node(id)

373

else:

374

return None

375

376

def get_child_index(self, id):

377

if id in self.children:

378

return self.children.index(id)

379

else:

380

return None

381

382

#return True if the child was added correctly. False otherwise

383

#takes the id of the child as parameter.

384

#if the child is not already in the tree, the relation is anyway "saved"

385

def add_child(self, id):

386

if id not in self.children:

387

self.children.append(id)

388

toreturn = self.new_relationship(self.get_id(),id)

389

# Log.debug("new relationship : %s" %toreturn)

390

else:

391

Log.debug("%s was already in children of %s" %(id,self.get_id()))

392

toreturn = False

393

return toreturn

394

395

def remove_child(self, id):

396

if id in self.children:

397

self.children.remove(id)

398

ret = self.tree.break_relationship(self.get_id(),id)

399

return ret

400

else:

401

return False

402

403

404

def change_id(self,newid):

405

oldid = self.id

406

self.id = newid

407

for p in self.parents:

408

par = self.tree.get(p)

409

par.remove_child(oldid)

410

par.add_child(self.id)

411

for c in self.get_children():

412

c.add_parent(newid)

413

c.remove_parent(oldid)