DSPython  00.03.03 — 25 juin 2012
 Tout Classes Espaces de nommage Fichiers Fonctions Variables Pages
baset.py
Aller à la documentation de ce fichier.
1 #!/usr/bin/env python
2 # -*- coding: latin-1 -*-
3 ##\package DSPython.baset Base tree : arbre binaire "de base b"
4 # !!! Work in progress !!!
5 
6 ##\file
7 # Base tree : arbre binaire "de base b"
8 # !!! Work in progress !!!
9 
10 # (c) Olivier Pirson --- DragonSoft
11 # http://www.opimedia.be/DS/
12 # Débuté le 13 novembre 2007
13 ####################################
14 from __future__ import print_function
15 
16 ## Date du dernier changement pour ce module
17 VERSION = 'baset --- 2010 March 16'
18 
19 import types
20 
21 import DSPython
22 import DSPython.nbsystem as nbsystem
23 
24 
25 
26 # ########
27 # Classe #
28 ##########
29 ##\brief Abre binaire de base b :
30 # arbre binaire donc chaque noeud peut contenir un naturel < base.
31 # Les feulles de l'arbre binaire ne sont jamais nuls.
32 # Les indices parcourent l'arbre binaire comme suit :
33 # 0
34 # 1 2
35 # 3 4 5 6
36 # 7 8 9 10 11 12 ...
37 class Baset:
38  """Abre binaire de base b :
39  arbre binaire donc chaque noeud peut contenir un naturel < base.
40  Les feulles de l'arbre binaire ne sont jamais nuls.
41  Les indices parcourent l'arbre binaire comme suit :
42  0
43  1 2
44  3 4 5 6
45  7 8 9 10 11 12 ..."""
46 
47  ## Constucteur
48  def __init__(self, n=0, b=2):
49  """Crée un Baset liée à la base b et l'initialise avec n
50  Si n est un string il représente la valeur de n en base b
51 
52  Pre: n: naturel ou string ne contenant que des chiffres < b <= 36
53  b: naturel >= 2
54 
55  O(n, b) = ..."""
56  assert DSPython.natural_is(n) or isinstance(n, str), (type(n), n)
57  assert DSPython.natural_is(b), b
58  assert 2 <= b, b
59 
60  ## Le nombre en base b représentant l'arbre
61  self.n = (nbsystem.str_to(n, b) if isinstance(n, str)
62  else n)
63  ## Base liée à ce Baset
64  self.b = b
65 
66 
67  ## self[key]
68  def __getitem__(self, key):
69  """Renvoie l'élément d'indice key
70 
71  Pre: key: naturel ou slice
72 
73  Result: naturel < self.b
74 
75  O(key) = ..."""
76  assert DSPython.natural_is(key) or isinstance(key, slice), type(key)
77 
78  if DSPython.natural_is(key): # indice simple
79  return nbsystem.fig(self.n, key, self.b)
80  else: # slice
81  n = 0
82  p = 1
83  if key.step == None:
84  for i in range(key.start, key.stop):
85  n += p*self[i]
86  p *= self.b
87  else:
88  for i in range(key.start, key.stop, key.step):
89  n += p*self[i]
90  p *= self.b
91  return n
92 
93 
94  ## Nombre d'éléments
95  def __len__(self):
96  """Renvoie le nombre d'éléments
97 
98  Result: naturel
99 
100  O() = ..."""
101  nb = 0
102  n = self.n
103  while n > 0:
104  nb += 1
105  n //= self.b
106  return nb
107 
108 
109  ## Renvoie un string quoté 'Baset(n, b)'
110  def __repr__(self):
111  """Renvoie un string quoté 'Baset(n, b)'
112 
113  Result: string quoté
114 
115  O() = ..."""
116  return ("'Baset({0})'".format(self.n) if self.b == 2
117  else "'Baset({0}, b={1})'".format(self.n, self.b))
118 
119 
120  ## self[key] = value
121  def __setitem__(self, key, value): # ??? traiter aussi les slice
122  """Modifie l'élément d'indice key par value
123 
124  Pre: key: naturel
125  value: naturel < self.b
126 
127  O(key, value) = ..."""
128  assert DSPython.natural_is(key), type(key)
129  assert DSPython.natural_is(value), type(value)
130  assert value < self.b, (value, self.b)
131 
132  p = self.b**key
133  (q, r) = divmod(self.n, p)
134  # "reste" : chiffres qui précèdent
135  q //= self.b
136  # "quotient" : chiffres qui suivent
137  self.n = q*(p*self.b) + (value*p + r)
138 
139 
140  ## Renvoie True ssi l'élément d'indice key est une feuille
141  def leaf_is(self, key):
142  """Renvoie True si l'élément d'indice key est une feuille
143  (càd que l'élément est non nul et qu'il ne possède pas de fils),
144  False sinon
145 
146  Pre: key: naturel
147 
148  Result: bool
149 
150  O(key) = ..."""
151  assert DSPython.natural_is(key), type(key)
152 
153  return (self[key] != 0) and ((self.subtree(key) if key > 0
154  else self).nb_not0() == 1)
155 
156 
157  ## Nombre d'éléments non nul
158  def nb_not0(self):
159  """Renvoie le nombre d'éléments non nul
160 
161  Result: naturel
162 
163  O() = ..."""
164  nb = 0
165  n = self.n
166  while n > 0:
167  (n, e) = divmod(n, self.b)
168  if e > 0:
169  nb += 1
170  return nb
171 
172 
173  ## Renvoie True ssi l'élément d'indice key est un noeud
174  def node_is(self, key):
175  """Renvoie True si l'élément d'indice key est un noeud
176  (càd qu'il est non nul, ou nul mais avec une descendance non nulle),
177  False sinon
178 
179  Pre: key: naturel
180 
181  Result: bool
182 
183  O(key) = ..."""
184  assert DSPython.natural_is(key), type(key)
185 
186  return (self[key] != 0) or ((self.subtree(key) if key > 0
187  else self).nb_not0() != 0)
188 
189 
190  ## Renvoie True ssi tous les noeuds internes de l'arbre sont nuls
191  def normal_is(self):
192  """Renvoie True si tous les noeuds internes de l'arbre sont nuls
193  (càd si que pour chaque feuille ces ancêtres sont nuls),
194  False sinon
195 
196  Result: bool
197 
198  O() = ..."""
199 
200  for k in range(len(self)):
201  if self.leaf_is(k) and (not self.orphanleaf_is(k)):
202  return False
203  return True
204 
205 
206  ## Renvoie True ssi l'élément d'indice key est un noeud dont tous les ancêtre sont nuls
207  def orphan_is(self, key):
208  """Renvoie True si l'élément d'indice key est un noeud dont tous les ancêtre sont nuls,
209  False sinon
210 
211  Pre: key: naturel
212 
213  Result: bool
214 
215  O(key) = ..."""
216  assert DSPython.natural_is(key), type(key)
217 
218  if self.node_is(key):
219  if key > 0:
220  key = (key - 1) // 2
221  while (key > 0) and (self[key] == 0):
222  key = (key - 1) // 2
223  return self[key] == 0
224  else:
225  return True
226  else:
227  return False
228 
229 
230  ## Renvoie True ssi l'élément d'indice key est une feuille dont tous les ancêtres sont nuls,
231  # False sinon
232  def orphanleaf_is(self, key):
233  """Renvoie True si l'élément d'indice key est une feuille dont tous les ancêtre sont nuls,
234  False sinon
235 
236  Pre: key: naturel
237 
238  Result: bool
239 
240  O(key) = ..."""
241  assert DSPython.natural_is(key), type(key)
242 
243  return self.leaf_is(key) and self.orphan_is(key)
244 
245 
246  ## Envoie une représentation de l'arbre sur la sortie standard
247  def print_tree(self): #??? à changer
248  """???
249 
250  O() = ..."""
251  n = self.n
252  p = 1
253  while n > 0:
254  for i in range(p):
255  (n, e) = divmod(n, self.b)
256  print(e, end='')
257  print()
258  p *= self.b
259 
260 
261  ## Renvoi le sous-arbre dont la racine est l'élément d'indice key
262  def subtree(self, key):
263  """Renvoi le sous-arbre dont la racine est l'élément d'indice key
264 
265  Pre: key: naturel
266 
267  Result: Baset
268 
269  O(key) = ..."""
270  assert DSPython.natural_is(key), type(key)
271 
272  if key != 0:
273  r = 0 # naturel du sous-arbre résultat
274  p = 1 # puissance de b
275  nb = 1 # nombre de chiffres à "extraire"
276  n = self.n // self.b**key # reste du nombre à traiter
277  while n > 0:
278  c = self[key:key + nb] # paquet de nb chiffres
279  r += c*p
280  p *= self.b**nb
281  key = key*2 + 1 # indice du premier chiffre du paquet suivant
282  n //= self.b**nb
283  nb *= 2
284  return Baset(r, self.b)
285  else:
286  return Baset(self.n, self.b)
287 
288 
289 
290 # ######\cond MAINTEST
291 # Main #
292 ########
293 if __name__ == '__main__':
294  def main_test():
295  """Test du module"""
296  import sys
297 
298  import DSPython.debug as debug
299 
300  debug.test_begin(VERSION, __debug__)
301 
302  print('Baset()...', end=''); sys.stdout.flush()
303  t = Baset()
304  assert t.n == 0, (t.n, t.b)
305  assert t.b == 2, (t.n, t.b)
306 
307  t = Baset(b=10)
308  assert t.n == 0, (t.n, t.b)
309  assert t.b == 10, (t.n, t.b)
310 
311  t = Baset(n=123, b=10)
312  assert t.n == 123, (t.n, t.b)
313  assert t.b == 10, (t.n, t.b)
314 
315  t = Baset(n='1011',)
316  assert t.n == 11, (t.n, t.b)
317  assert t.b == 2, (t.n, t.b)
318 
319  t = Baset(n='123', b=10)
320  assert t.n == 123, (t.n, t.b)
321  assert t.b == 10, (t.n, t.b)
322  print('ok'); sys.stdout.flush()
323 
324 
325  print('Baset.__getitem__()...', end=''); sys.stdout.flush()
326  t = Baset()
327  for i in range(100):
328  assert t[i] == 0, (i, t[i], t)
329 
330  t = Baset(b=10)
331  for i in range(100):
332  assert t[i] == 0, (i, t[i], t)
333 
334  t = Baset('543210', b=10)
335  for i in range(5):
336  assert t[i:i+2] == nbsystem.str_to('012345'[i + 1] + '012345'[i], b=10), \
337  (t, i, t[i:i+2], nbsystem.str_to('012345'[i + 1] + '012345'[i], b=10))
338 
339  for b in range(2, 37):
340  t = Baset('1'*100, b=b)
341  for i in range(1, 100):
342  assert t[i] == 1, (b, i, t[i], t)
343 
344  for b in range(2, 37):
345  for k in range(b):
346  c = nbsystem.fig_to_chr(k)
347  t = Baset(c*50, b=b)
348  for i in range(1, 50 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
349  assert t[i] == nbsystem.chr_to_fig(c), \
350  (b, k, c, nbsystem.chr_to_fig(c), i, t[i], t)
351  assert t[50] == 0, (b, k, t[50], t)
352  print('???', end='')
353  if debug.assertspeed < debug.ASSERT_NORMAL:
354  print(debug.assertspeed_str(), end='')
355  print('ok'); sys.stdout.flush()
356 
357 
358  print('Baset.__len__()...', end=''); sys.stdout.flush()
359  t = Baset()
360  assert len(t) == 0, (len(t), t)
361  for i in range(100):
362  t[i] = i%2
363  assert len(t) == 100, (len(t), t)
364 
365  t = Baset()
366  assert len(t) == 0, (len(t), t)
367  for i in range(99):
368  t[i] = i%2
369  assert len(t) == 98, (len(t), t)
370  print('???', end='')
371  print('ok'); sys.stdout.flush()
372 
373 
374  print('Baset.__repr__()...', end=''); sys.stdout.flush()
375  t = Baset(n='123', b=10)
376  assert repr(t) == "'Baset({0}, b={1})'".format(t.n, t.b), (repr(t), t)
377  print('???', end='')
378  print('ok'); sys.stdout.flush()
379 
380 
381  print('Baset.__setitem__()...', end=''); sys.stdout.flush()
382  t = Baset()
383  for i in range(100):
384  t[i] = i%2
385  for i in range(100):
386  assert t[i] == i%2, (i, t[i], t)
387 
388 
389  t = Baset(b=10)
390  for i in range(100):
391  t[i] = i%10
392  for i in range(100):
393  assert t[i] == i%10, (i, t[i], t)
394 
395  t = Baset(b=10)
396  for i in range(100,0,-1):
397  t[i] = i%10
398  for i in range(100,0,-1):
399  assert t[i] == i%10, (i, t[i], t)
400  print('???', end='')
401  print('ok'); sys.stdout.flush()
402 
403 
404  print('Baset.leaf_is()...', end=''); sys.stdout.flush()
405  t = Baset()
406  for k in range(100):
407  assert not t.leaf_is(k), (k, t[k])
408 
409  t = Baset('9876543010', 10)
410  assert not t.leaf_is(0), t[0]
411  assert not t.leaf_is(1), t[1]
412  assert not t.leaf_is(2), t[2]
413  assert not t.leaf_is(3), t[3]
414  assert not t.leaf_is(4), t[4]
415  assert t.leaf_is(5), t[5]
416  assert t.leaf_is(6), t[6]
417  assert t.leaf_is(7), t[7]
418  assert t.leaf_is(8), t[8]
419  assert t.leaf_is(9), t[9]
420  for k in range(10, 100):
421  assert not t.leaf_is(k), (k, t[k])
422 
423  t = Baset('9876543210', 10)
424  assert not t.leaf_is(0), t[0]
425  assert not t.leaf_is(1), t[1]
426  assert not t.leaf_is(2), t[2]
427  assert not t.leaf_is(3), t[3]
428  assert not t.leaf_is(4), t[4]
429  assert t.leaf_is(5), t[5]
430  assert t.leaf_is(6), t[6]
431  assert t.leaf_is(7), t[7]
432  assert t.leaf_is(8), t[8]
433  assert t.leaf_is(9), t[9]
434  for k in range(10, 100):
435  assert not t.leaf_is(k), (k, t[k])
436  print('???', end='')
437  print('ok'); sys.stdout.flush()
438 
439 
440  print('Baset.nb_not0()...', end=''); sys.stdout.flush()
441  t = Baset()
442  assert t.nb_not0() == 0, (t.nb_not0(), t)
443  for i in range(100):
444  t[i] = i%2
445  assert t.nb_not0() == 50, (t.nb_not0(), t)
446 
447  t = Baset()
448  assert t.nb_not0() == 0, (t.nb_not0(), t)
449  for i in range(99):
450  t[i] = i%2
451  assert t.nb_not0() == 49, (t.nb_not0(), t)
452  print('???', end='')
453  print('ok'); sys.stdout.flush()
454 
455 
456  print('Baset.node_is()...', end=''); sys.stdout.flush()
457  t = Baset()
458  for k in range(100):
459  assert not t.node_is(k), (k, t[k])
460 
461  t = Baset('9876543210', 10)
462  for k in range(10):
463  assert t.node_is(k), (k, t[k])
464  for k in range(10, 100):
465  assert not t.node_is(k), (k, t[k])
466 
467  t = Baset('9876543010', 10)
468  for k in range(10):
469  assert t.node_is(k), (k, t[k])
470  for k in range(10, 100):
471  assert not t.node_is(k), (k, t[k])
472  print('???', end='')
473  print('ok'); sys.stdout.flush()
474 
475 
476  print('Baset.normal_is()...', end=''); sys.stdout.flush()
477  assert Baset().normal_is(), Baset()
478  assert Baset(1).normal_is(), Baset(1)
479  assert Baset('10').normal_is(), Baset('10')
480  assert not Baset('11').normal_is(), Baset('11')
481  assert Baset('100').normal_is(), Baset('100')
482  assert not Baset('101').normal_is(), Baset('101')
483  assert Baset('110').normal_is(), Baset('110')
484  assert not Baset('111').normal_is(), Baset('111')
485 
486  assert Baset('3200010', 10).normal_is(), Baset('3200010', 10)
487  assert not Baset('3205010', 10).normal_is(), Baset('3205010', 10)
488 
489  assert not Baset('9876543210', 10).normal_is(), Baset('9876543210', 10)
490  assert not Baset('9876543010', 10).normal_is(), Baset('9876543010', 10)
491  assert Baset('9876500000', 10).normal_is(), Baset('9876500000', 10)
492  print('???', end='')
493  print('ok'); sys.stdout.flush()
494 
495 
496  print('Baset.orphan_is()...', end=''); sys.stdout.flush()
497  t = Baset()
498  for k in range(100):
499  assert not t.orphan_is(k), (k, t[k])
500 
501  t = Baset('9876543210', 10)
502  assert t.orphan_is(0), t[0]
503  assert t.orphan_is(1), t[1]
504  assert t.orphan_is(2), t[2]
505  for k in range(3, 100):
506  assert not t.orphan_is(k), (k, t[k])
507 
508  t = Baset('9876543010', 10)
509  assert t.orphan_is(0), t[0]
510  assert t.orphan_is(1), t[1]
511  assert t.orphan_is(2), t[2]
512  assert not t.orphan_is(3), t[3]
513  assert not t.orphan_is(4), t[4]
514  assert t.orphan_is(5), t[5]
515  assert t.orphan_is(6), t[6]
516  for k in range(7, 100):
517  assert not t.orphan_is(k), (k, t[k])
518  print('???', end='')
519  print('ok'); sys.stdout.flush()
520 
521 
522  print('Baset.orphanleaf_is()...', end=''); sys.stdout.flush()
523  t = Baset()
524  for k in range(100):
525  assert not t.orphanleaf_is(k), (k, t[k])
526 
527  t = Baset('9876543210', 10)
528  for k in range(100):
529  assert not t.orphanleaf_is(k), (k, t[k])
530 
531  t = Baset('9876543010', 10)
532  assert not t.orphanleaf_is(0), t[0]
533  assert not t.orphanleaf_is(1), t[1]
534  assert not t.orphanleaf_is(2), t[2]
535  assert not t.orphanleaf_is(3), t[3]
536  assert not t.orphanleaf_is(4), t[4]
537  assert t.orphanleaf_is(5), t[5]
538  assert t.orphanleaf_is(6), t[6]
539  for k in range(7, 100):
540  assert not t.orphanleaf_is(k), (k, t[k])
541  print('???', end='')
542  print('ok'); sys.stdout.flush()
543 
544 
545  print('Baset.print_tree()...', end=''); sys.stdout.flush()
546  t = Baset()
547  t.print_tree()
548  for i in range(100):
549  t[i] = i%2
550 # t.print_tree()
551  print('???', end='')
552  print('ok'); sys.stdout.flush()
553 
554 
555  print('Baset.subtree()...', end=''); sys.stdout.flush()
556  for b in range(2, 37):
557  for k in range(100):
558  t = Baset('9876543210', b)
559  assert t.subtree(k).b == b, (k, t.subtree(k).b, b)
560  t = Baset('9876543210', 10)
561  assert t.subtree(0).n == t.n, t.subtree(0).n
562  assert t.subtree(1).n == 987431, t.subtree(1).n
563  assert t.subtree(2).n == 652, t.subtree(2).n
564  assert t.subtree(3).n == 873, t.subtree(3).n
565  assert t.subtree(4).n == 94, t.subtree(4).n
566  assert t.subtree(5).n == 5, t.subtree(5).n
567  assert t.subtree(9).n == 9, t.subtree(9).n
568  assert t.subtree(10).n == 0, t.subtree(10).n
569  print('???', end='')
570  print('ok'); sys.stdout.flush()
571  debug.test_end()
572 
573  main_test()
574 ##\endcond MAINTEST