Création d'un ramasse-miettes en Python

Publié le 23/05/2013

L'idée ci-dessous est de construire une arborescence en SQL, avec son API en Python. Cette arborescence sera relativement simple:

  • Chaque noeud de l'arbre peut avoir entre 1 et N enfants.
  • Si un noeud ne poss√®de pas de parent, il sera consid√©r√© comme une racine.
  • Si un noeud ne poss√®de aucun enfant, il sera consid√©r√© comme une feuille.

En SQL

Au niveau de la repr√©sentation relationnelle, le plus simple est d'avoir une table Node qui poss√®de une r√©f√©rence vers elle-m√™me. De cette mani√®re, nous pouvons repr√©senter un noeud gr√Ęce √† trois attributs:

  • Son identifiant, Id
  • L'identifiant de son parent, ParentId, qui peut √™tre √©ventuellement nul
  • Un libell√©, Label.

Un petit exemple ci-dessous en T-SQL:

CREATE TABLE Node (
	[Id] int IDENTITY(1,1) NOT NULL PRIMARY KEY,
	[ParentId] int NULL FOREIGN KEY REFERENCES Entity(Id),
	[Label] nvarchar(255) NOT NULL
)

Cette m√©thode rend par contre impossible la r√©cup√©ration des descendants ou ascendants gr√Ęce √† une requ√™te directe. En fonction du nombre de niveaux √† parcourir, il sera n√©cessaire d'effectuer autant de requ√™tes distinctes qu'il y a de niveaux. Pour construire une arborescence sur trois niveaux, nous devrons bien ex√©cuter trois requ√™tes diff√©rentes:

  1. Une première pour trouver un noeud par rapport à son identifiant
  2. Une deuxième pour récupérer son parent,
  3. Suivie d'une troisième qui permettra de récupérer le parent du parent.

A ce stade, nous devrions être à la racine de notre arbre, puisque le champ ParentId du dernier résultat sera nul.

Une autre possibilité est de construire une fonction tabulaire qui, pour un identifiant donné, va construire la liste et la retourner dans une table temporaire, en y ajoutant un indice de position. Dans cette implémentation, la racine aura la position zéro:

CREATE FUNCTION [dbo].[BreadCrumb]
(
	@currentid int
)
RETURNS @Tab TABLE (Id int, pos int, ParentId int, Label nvarchar(255))
	AS
Begin
	Declare @parentid int;
	Declare @label nvarchar(max);
	Declare @entitytypeid int;
	Declare @i int;

	Set @parentid = @currentid;
	Set @i = 0;

	While(@parentid is not null)
	Begin
		set @currentid = @parentid;

		(Select @parentid = ParentId, @label = Entity.Label
			From Entity Where Entity.Id = @currentid);

		INSERT INTO @Tab (id, pos, label, parentid)
		VALUES (@currentid, @i, @label, @parentid)
		set @i = @i + 1;
	End

	return;
END;

Comme expliqué ci-dessus, le résultat retourne une table qui contient quelques colonnes (l'id, le parentid, le label et la position), et permet de chipoter un peu parmi les liens de l'arborescenc: il suffit de communiquer un identifiant en paramètre à la fonction, pour ressortir toute l'arborescence. Magique (ou presque, jusqu'à ce que la table soit trop peuplée que pour être efficiente).

Avec un ORM

Une autre approche est de passer par un ORM. Pour l'exemple (et parce que "c'est le plus mieux" ©), ça sera l'ORM de Django. Pour l'exemple, j'ai créé une simple classe 'Album' (de photos), chacun d'entre eux pouvant contenir plusieurs sous-albums. Le principe est le même: pour retracer l'arborescence d'un élément, il faut remonter jusqu'à la racine, afin de pouvoir construire le ramasse-miettes.

class Album(models.Model):
	name = models.CharField(verbose_name='Nom', max_length=50)
	slug = models.SlugField(max_length=50, blank=False, editable=True)
	description = models.CharField(
        verbose_name='Description', 
        max_length=255, 
        null=True, 
        blank=True
    )
	parent = models.ForeignKey('self', null=True, blank=True)	

	def __unicode__(self):
		return self.name

	def illustration(self):
		""" returns an illustration for the album """
		pictures = self.picture_set.all()

		if len(pictures) > 0:
			return pictures[0].picture
		else:
			return None

	def parentbreadcrumb(self):
		return self.breadcrumb()[:-1]

	def breadcrumb(self):
		""" Returns the breadcrumb for the current album """
		if self.parent == None:
			return (self,)

		return self.parent.breadcrumb() + (self,)

	def path(self):
		"""
		returns the path where the album structure should be stored
		"""
		return os.sep.join((x.name for x in self.breadcrumb()))

Le problème reste entier, puisque le nombre de requêtes à effectuer sera toujours égal aux nombres de niveaux à parcourir. Mais cela devrait suffire pour des cas relativement simples.