DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
bintree.py
Aller à la documentation de ce fichier.
1 #!/usr/bin/env python
2 # -*- coding: latin-1 -*-
3 ##\package DSPython.bintree Binary tree : arbre binaire générique
4 # !!! Work in progress !!!
5 
6 ##\file
7 # Binary tree : arbre binaire générique
8 # !!! Work in progress !!!
9 
10 # (c) Olivier Pirson --- DragonSoft
11 # http://www.opimedia.be/DS/
12 # Débuté le 25 mars 2008
13 ####################################
14 from __future__ import print_function
15 
16 ## Date du dernier changement pour ce module
17 VERSION = 'bintree --- 2010 March 16'
18 
19 
20 
21 #???
22 # - copier (par copy.copy()) les morceaux d'arbre ?
23 # - EulerTour()
24 # - parcours préfixe, infixe, postfixe
25 # - depth, height, nbroot, nbsubleft, nbsubright
26 
27 
28 
29 # ############
30 # Constantes #
31 ##############
32 ## Suites des parenthèses gauches
33 PARENTSLEFT = ('(', '[', '{')
34 
35 ## Suites des parenthèses droites
36 PARENTSRIGHT = (')', ']', '}')
37 
38 
39 ## Suites des parenthèses gauches pour (La)TeX en mode mathématique
40 PARENTSLEFT_TEX = (r'\left(', r'\left[', r'\left{')
41 
42 ## Suites des parenthèses droites pour (La)TeX en mode mathématique
43 PARENTSRIGHT_TEX = (r'\right)', r'\right]', r'\right}')
44 
45 
46 
47 # ########
48 # Classe #
49 ##########
50 ##\brief Arbre binaire générique
51 #
52 # Les 8 possibilités :\n
53 # \htmlonly <img src="bintree.png" alt="[bintree.png]">\endhtmlonly
54 class Bintree:
55  """Arbre binaire générique"""
56 
57  ## Compare self et value
58  def __cmp__(self, value):
59  """Compare self et value
60 
61  Pre: les éventuelles racines de self et value doivent être comparables par cmp()
62 
63  Result: -1, 0 ou 1
64 
65  O() = ..."""
66  raise NotImplementedError#???
67 
68 
69  ## Efface la racine
70  def __delroot__(self):
71  """Efface la racine (si elle existe)
72 
73  O() = 1"""
74  if hasroot(self):
75  del self._e
76 
77 
78  ## Efface le sous-arbre binaire de gauche
79  def __delsubleft__(self):
80  """Efface le sous-arbre binaire de gauche (si il existe)
81 
82  O() = 1"""
83  if hassubleft(self):
84  del self._l
85 
86 
87  ## Efface le sous-arbre binaire de droite
88  def __delsubright__(self):
89  """Efface le sous-arbre binaire de droite (si il existe)
90 
91  O() = 1"""
92  if hassubright(self):
93  del self._r
94 
95 
96  ## Arbre binaire vide ?
97  def __empty__(self):
98  """Renvoie True si l'arbre binaire est vide
99  (c.-à-d. si ni racine,
100  ni sous-arbre de gauche, ni sous-arbre de droite),
101  False sinon
102 
103  Result: bool
104 
105  O() = 1"""
106  return not(hasroot(self) or hassubleft(self) or hassubright(self))
107 
108 
109  ## self == value ?
110  def __eq__(self, value):
111  """Renvoie self == value
112 
113  Pre: les éventuelles racines de self et value doivent être comparables par ==
114 
115  Result: bool
116 
117  O() = ..."""
118  raise NotImplementedError#???
119  return (isinstance(value, Bintree)
120  and (not((hasroot(self) and hasroot(value)))
121  or (hasroot(self) and hasroot(value) and getroot(self) == getroot(value))))#...
122 
123 
124  ## Renvoie la racine
125  def __getroot__(self):
126  """Renvoie la racine
127 
128  Pre: self: Bintree possédant une racine
129 
130  Result: objet
131 
132  O() = 1"""
133  assert hasroot(self)
134 
135  return self._e
136 
137 
138  ## Renvoie le sous-arbre binaire de gauche
139  def __getsubleft__(self):
140  """Renvoie le sous-arbre binaire de gauche
141 
142  Pre: self: Bintree possédant un sous-arbre binaire de gauche
143 
144  Result: Bintree
145 
146  O() = 1"""
147  assert hassubleft(self)
148 
149  return self._l
150 
151 
152  ## Renvoie le sous-arbre binaire de droite
153  def __getsubright__(self):
154  """Renvoie le sous-arbre binaire de droite
155 
156  Pre: self: Bintree possédant un sous-arbre binaire de droite
157 
158  Result: Bintree
159 
160  O() = 1"""
161  assert hassubright(self)
162 
163  return self._r
164 
165 
166  ## Arbre binaire avec une racine ?
167  def __hasroot__(self):
168  """Renvoie True si l'arbre binaire possède une racine,
169  False sinon
170 
171  Result: bool
172 
173  O() = 1"""
174  return hasattr(self, '_e')
175 
176 
177  ## Arbre binaire avec un sous-arbre binaire de gauche ?
178  def __hassubleft__(self):
179  """Renvoie True si l'arbre binaire possède un sous-arbre binaire de gauche,
180  False sinon
181 
182  Result: bool
183 
184  O() = 1"""
185  return hasattr(self, '_l')
186 
187 
188  ## Arbre binaire avec un sous-arbre binaire de droite ?
189  def __hassubright__(self):
190  """Renvoie True si l'arbre binaire possède un sous-arbre binaire de droite,
191  False sinon
192 
193  Result: bool
194 
195  O() = 1"""
196  return hasattr(self, '_r')
197 
198 
199  ## Constucteur
200  def __init__(self, *args):
201  """Constucteur :
202  Bintree() : arbre binaire vide
203  Bintree(value) : arbre binaire avec value pour racine
204  Bintree(value, left) : arbre binaire avec value pour racine
205  et left pour sous-arbre binaire de gauche
206  Bintree(value, left, right) : arbre binaire avec value pour racine
207  et left pour sous-arbre binaire de gauche
208  et right pour sous-arbre binaire de droite
209 
210  Pre: args: vide
211  ou (Object)
212  ou (Object, Bintree)
213  ou (Object, Bintree, Bintree)
214 
215  O() = ..."""
216  assert len(args) <= 3, (len(args), args)
217 
218  # self._e : élément de la racine
219  # self._l : Bintree sous-arbre binaire de gauche
220  # self._r : Bintree sous-arbre binaire de droite
221  if len(args) > 0:
222  self._e = args[0]
223  if len(args) > 1:
224  assert isinstance(args[1], Bintree), type(args[1])
225 
226  self._l = args[1]
227  if len(args) > 2:
228  assert isinstance(args[2], Bintree), type(args[2])
229 
230  self._r = args[2]
231 
232 
233  ## Nombre de noeuds
234  def __len__(self):
235  """Renvoie le nombre de noeuds
236 
237  Result: naturel
238 
239  O() = ..."""
240  return ((len(getsubleft(self)) if hassubleft(self)
241  else 0)
242  + (len(getsubright(self)) if hassubright(self)
243  else 0)
244  + (1 if hasroot(self)
245  else 0))
246 
247 
248  ## self != value ?
249  def __ne__(self, value):
250  """Renvoie self != value
251 
252  Result: bool
253 
254  O() = ..."""
255  return not(self == value)
256 
257 
258  ## Renvoie l'arbre binaire sous forme de string (à partir d'un parcours préfixe)
259  def __repr__(self):#???
260  """Renvoie l'arbre binaire sous forme de string
261  (à partir d'un parcours préfixe)
262  (renvoie '(()())' si l'arbre binaire est vide)
263 
264  Result: string
265 
266  O() = ..."""
267  return ''.join(('(',
268  repr(getroot(self) if hasroot(self)
269  else ''),
270  repr(getsubleft(self)) if hassubleft(self)
271  else '()',
272  repr(getsubright(self)) if hassubright(self)
273  else '()',
274  ')'))
275 
276 
277  ## Vide l'arbre binaire
278  def __setempty__(self):
279  """Vide l'arbre binaire
280  (c.-à-d. efface la racine,
281  le sous-arbre de gauche et le sous-arbre de droite)
282 
283  O() = 1"""
284  delroot(self)
285  delsubleft(self)
286  delsubright(self)
287 
288 
289  ## Fixe la valeur de la racine à value
290  def __setroot__(self, value):
291  """Fixe la valeur de la racine à value
292 
293  O() = 1"""
294  self._e = value
295 
296 
297  ## Fixe le sous-arbre binaire de gauche à value
298  def __setsubleft__(self, value):
299  """Fixe le sous-arbre binaire de gauche à value
300 
301  Pre: value: Bintree
302 
303  O() = 1"""
304  assert isinstance(value, Bintree), type(value)
305 
306  self._l = value
307 
308 
309  ## Fixe le sous-arbre binaire de droite à value
310  def __setsubright__(self, value):
311  """Fixe le sous-arbre binaire de droite à value
312 
313  Pre: value: Bintree
314 
315  O() = 1"""
316  assert isinstance(value, Bintree), type(value)
317 
318  self._r = value
319 
320 
321  ## Renvoie l'arbre binaire sous forme de string (à partir d'un parcours préfixe)
322  def __str__(self):#???
323  """Renvoie l'arbre binaire sous forme de string
324  (à partir d'un parcours préfixe)
325  (renvoie '(()())' si l'arbre binaire est vide)
326 
327  Result: string
328 
329  O() = ..."""
330  return ''.join(('(',
331  str(getroot(self) if hasroot(self)
332  else ''),
333  str(getsubleft(self)) if hassubleft(self)
334  else '()',
335  str(getsubright(self)) if hassubright(self)
336  else '()',
337  ')'))
338 
339 
340 
341 # ######################
342 # Fonctions génériques #
343 ########################
344 ## Exécute t.__delroot__()
345 def delroot(t):
346  """Exécute t.__delroot__()"""
347  t.__delroot__()
348 
349 
350 ## Exécute t.__delsubleft__()
351 def delsubleft(t):
352  """Exécute t.__delsubleft__()"""
353  t.__delsubleft__()
354 
355 
356 ## Exécute t.__delsubright__()
357 def delsubright(t):
358  """Exécute t.__delsubright__()"""
359  t.__delsubright__()
360 
361 
362 ## Renvoie t.__empty__()
363 def empty(t):
364  """Renvoie t.__empty__()"""
365  return t.__empty__()
366 
367 
368 ## Renvoie t.__getroot__()
369 def getroot(t):
370  """Renvoie t.__getroot__()"""
371  return t.__getroot__()
372 
373 
374 ## Renvoie t.__getsubleft__()
375 def getsubleft(t):
376  """Renvoie t.__getsubleft__()"""
377  return t.__getsubleft__()
378 
379 
380 ## Renvoie t.__getsubright__()
381 def getsubright(t):
382  """Renvoie t.__getsubright__()"""
383  return t.__getsubright__()
384 
385 
386 ## Renvoie t.__hasroot__()
387 def hasroot(t):
388  """Renvoie t.__hasroot__()"""
389  return t.__hasroot__()
390 
391 
392 ## Renvoie t.__hassubleft__()
393 def hassubleft(t):
394  """Renvoie t.__hassubleft__()"""
395  return t.__hassubleft__()
396 
397 
398 ## Renvoie t.__hassubright__()
399 def hassubright(t):
400  """Renvoie t.__hassubright__()"""
401  return t.__hassubright__()
402 
403 
404 ## Exécute t.__setempty__()
405 def setempty(t):
406  """Exécute t.__setempty__()"""
407  t.__setempty__()
408 
409 
410 ## Exécute t.__setroot__(value)
411 def setroot(t, value):
412  """Exécute t.__setroot__(value)"""
413  t.__setroot__(value)
414 
415 
416 ## Exécute t.__setsubleft__(value)
417 def setsubleft(t, value):
418  """Exécute t.__setsubleft__(value)"""
419  t.__setsubleft__(value)
420 
421 
422 ## Exécute t.__setsubright__(value)
423 def setsubright(t, value):
424  """Exécute t.__setsubright__(value)"""
425  t.__setsubright__(value)
426 
427 
428 
429 # ######\cond MAINTEST
430 # Main #
431 ########
432 if __name__ == '__main__':
433  def main_test():
434  """Test du module"""
435  import sys
436 
437  import DSPython.debug as debug
438 
439  debug.test_begin(VERSION, __debug__)
440 
441  print('PARENTSLEFT == {0}'.format(PARENTSLEFT)); sys.stdout.flush()
442  assert isinstance(PARENTSLEFT, tuple)
443  print('PARENTSRIGHT == {0}'.format(PARENTSRIGHT)); sys.stdout.flush()
444  assert isinstance(PARENTSRIGHT, tuple)
445 
446  print('PARENTSLEFT_TEX == {0}'.format(PARENTSLEFT_TEX)); sys.stdout.flush()
447  assert isinstance(PARENTSLEFT_TEX, tuple)
448  print('PARENTSRIGHT_TEX == {0}'.format(PARENTSRIGHT_TEX)); sys.stdout.flush()
449  assert isinstance(PARENTSRIGHT_TEX, tuple)
450 
451 
452 
453  print()
454  print('Bintree()...', end=''); sys.stdout.flush()
455  t = Bintree()
456  t1 = Bintree('1')
457  t2 = Bintree('2', t)
458  t3 = Bintree('3', t1)
459  t4 = Bintree('4', t2, t3)
460 
461  t3n = Bintree('/',
462  Bintree('+',
463  Bintree('*', Bintree('3'), Bintree('n')),
464  Bintree('1')),
465  Bintree('2'))
466  print('???', end='')
467  print('ok'); sys.stdout.flush()
468 
469 
470  print('Bintree.__cmp__()...', end=''); sys.stdout.flush()
471  print('???', end='')
472  print('ok'); sys.stdout.flush()
473 
474 
475  print('Bintree.__delroot__()...', end=''); sys.stdout.flush()
476  print('???', end='')
477  print('ok'); sys.stdout.flush()
478 
479 
480  print('Bintree.__delsubleft__()...', end=''); sys.stdout.flush()
481  print('???', end='')
482  print('ok'); sys.stdout.flush()
483 
484 
485  print('Bintree.__delsubright__()...', end=''); sys.stdout.flush()
486  print('???', end='')
487  print('ok'); sys.stdout.flush()
488 
489 
490  print('Bintree.__empty__()...', end=''); sys.stdout.flush()
491  assert t.__empty__(), t
492  assert not t1.__empty__(), t1
493  assert not t2.__empty__(), t2
494  assert not t3.__empty__(), t3
495  assert not t4.__empty__(), t4
496 
497  assert not t3n.__empty__(), t3n
498  print('???', end='')
499  print('ok'); sys.stdout.flush()
500 
501 
502  print('Bintree.__eq__()...', end=''); sys.stdout.flush()
503  print('???', end='')
504  print('ok'); sys.stdout.flush()
505 
506 
507  print('Bintree.__getroot__()...', end=''); sys.stdout.flush()
508  print('???', end='')
509  print('ok'); sys.stdout.flush()
510 
511 
512  print('Bintree.__getsubleft__()...', end=''); sys.stdout.flush()
513  print('???', end='')
514  print('ok'); sys.stdout.flush()
515 
516 
517  print('Bintree.__getsubright__()...', end=''); sys.stdout.flush()
518  print('???', end='')
519  print('ok'); sys.stdout.flush()
520 
521 
522  print('Bintree.__hasroot__()...', end=''); sys.stdout.flush()
523  print('???', end='')
524  print('ok'); sys.stdout.flush()
525 
526 
527  print('Bintree.__hassubleft__()...', end=''); sys.stdout.flush()
528  print('???', end='')
529  print('ok'); sys.stdout.flush()
530 
531 
532  print('Bintree.__hassubright__()...', end=''); sys.stdout.flush()
533  print('???', end='')
534  print('ok'); sys.stdout.flush()
535 
536 
537  print('Bintree.__len__()...', end=''); sys.stdout.flush()
538  assert len(t) == 0, (len(t), t)
539  assert len(t1) == 1, (len(t1), t1)
540  assert len(t2) == 1, (len(t2), t2)
541  assert len(t3) == 2, (len(t3), t3)
542  assert len(t4) == 4, (len(t4), t4)
543 
544  assert len(t3n) == 7, (len(t3n), t3n)
545  print('???', end='')
546  print('ok'); sys.stdout.flush()
547 
548 
549  print('Bintree.__ne__()...', end=''); sys.stdout.flush()
550  print('???', end='')
551  print('ok'); sys.stdout.flush()
552 
553 
554  print('Bintree.__repr__()...', end=''); sys.stdout.flush()
555  print('???', end='')
556  print('ok'); sys.stdout.flush()
557 
558 
559  print('Bintree.__setempty__()...', end=''); sys.stdout.flush()
560  assert t.__empty__(), t
561  t.__setempty__()
562  assert t.__empty__(), t
563  print('???', end='')
564  print('ok'); sys.stdout.flush()
565 
566 
567  print('Bintree.__setroot__()...', end=''); sys.stdout.flush()
568  print('???', end='')
569  print('ok'); sys.stdout.flush()
570 
571 
572  print('Bintree.__setsubleft__()...', end=''); sys.stdout.flush()
573  print('???', end='')
574  print('ok'); sys.stdout.flush()
575 
576 
577  print('Bintree.__setsubright__()...', end=''); sys.stdout.flush()
578  print('???', end='')
579  print('ok'); sys.stdout.flush()
580 
581 
582  print('Bintree.__str__()...', end=''); sys.stdout.flush()
583  assert str(t) == '(()())', str(t)
584  assert str(t1) == '(1()())', str(t1)
585  assert str(t2) == '(2(()())())', str(t2)
586  assert str(t3) == '(3(1()())())', str(t3)
587  assert str(t4) == '(4(2(()())())(3(1()())()))', str(t4)
588 
589  assert str(t3n) == '(/(+(*(3()())(n()()))(1()()))(2()()))', str(t3n)
590  print('???', end='')
591  print('ok'); sys.stdout.flush()
592 
593 
594 
595  print()
596  print('delroot()...', end=''); sys.stdout.flush()
597  print('???', end='')
598  print('ok'); sys.stdout.flush()
599 
600 
601  print('delsubleft()...', end=''); sys.stdout.flush()
602  print('???', end='')
603  print('ok'); sys.stdout.flush()
604 
605 
606  print('delsubright()...', end=''); sys.stdout.flush()
607  print('???', end='')
608  print('ok'); sys.stdout.flush()
609 
610 
611  print('empty()...', end=''); sys.stdout.flush()
612  assert empty(t), t
613  assert not empty(t1), t1
614  assert not empty(t2), t2
615  assert not empty(t3), t3
616  assert not empty(t4), t4
617 
618  assert not empty(t3n), t3n
619  print('???', end='')
620  print('ok'); sys.stdout.flush()
621 
622 
623  print('getroot()...', end=''); sys.stdout.flush()
624  print('???', end='')
625  print('ok'); sys.stdout.flush()
626 
627 
628  print('getsubleft()...', end=''); sys.stdout.flush()
629  print('???', end='')
630  print('ok'); sys.stdout.flush()
631 
632 
633  print('getsubright()...', end=''); sys.stdout.flush()
634  print('???', end='')
635  print('ok'); sys.stdout.flush()
636 
637 
638  print('hasroot()...', end=''); sys.stdout.flush()
639  print('???', end='')
640  print('ok'); sys.stdout.flush()
641 
642 
643  print('hassubleft()...', end=''); sys.stdout.flush()
644  print('???', end='')
645  print('ok'); sys.stdout.flush()
646 
647 
648  print('hassubright()...', end=''); sys.stdout.flush()
649  print('???', end='')
650  print('ok'); sys.stdout.flush()
651 
652 
653  print('setempty()...', end=''); sys.stdout.flush()
654  print('???', end='')
655  print('ok'); sys.stdout.flush()
656 
657 
658  print('setroot()...', end=''); sys.stdout.flush()
659  print('???', end='')
660  print('ok'); sys.stdout.flush()
661 
662 
663  print('setsubleft()...', end=''); sys.stdout.flush()
664  print('???', end='')
665  print('ok'); sys.stdout.flush()
666 
667 
668  print('setsubright()...', end=''); sys.stdout.flush()
669  print('???', end='')
670  print('ok'); sys.stdout.flush()
671  debug.test_end()
672 
673  main_test()
674 ##\endcond MAINTEST