Les arbres généraux permettent de représenter efficacement un système
de fichiers comme il en existe sous Linux ou sous Windows. En effet,
dans un tel système, des répertoires contiennent des fichiers et des
répertoires qui contiennent à leur tour des fichiers et des
répertoires qui...
Dans un tel système, fichiers et répertoires sont décrits à l'aide de
descripteurs qui, dans la réalité, comportent le nom du
fichier ou du répertoire, la date de création, la date de
modification... ainsi que des informations pour situer le fichier sur
le disque. Dans notre modèle, le descripteur ne comportera que les
informations suivantes:
-
le nom du fichier ou du répertoire,
- est-ce un fichier ou un répertoire?,
- pour un fichier, la taille du fichier.
Barrière d'abstraction Descripteur
Nous manipulerons les descripteurs à l'aide des fonctions suivantes:
;;;;;;;; Constructeurs
;;;
;;;
;;;
;;;
;;;
;;;;;;;; Reconnaisseurs
;;;
;;;
;;;
;;;
;;;;;;;; Accesseurs
;;;
;;;
;;;
;;;
;;;
Implantation de la barrière d'abstraction Descripteur
On peut implanter cette barrière d'abstraction en utilisant des
vecteurs (de longueur deux pour les répertoires et 3 pour les
fichiers):
-
le premier composant contient 'D (lorsque c'est un répertoire)
ou 'F (lorsque c'est un fichier),
- le second composant contient le nom du répertoire ou du fichier,
- pour les fichiers, le troisième composant contient la taille du
fichier.
Remarque: dans notre exemple, les nombres d'informations à mémoriser
étant différents pour les fichiers et pour les répertoires, le premier
composant du vecteur est inutile. Nous avons tout de même préféré la
solution donnée ci-dessus, car, dans le futur, on pourrait être amené
à ajouter, dans notre modèle, une autre information pour les
répertoires (par exemple, le nombre d'éléments qu'il contient).
L'implantation est alors très simple et nous ne la commenterons pas:
;;;;;;;; Constructeurs
;;;
;;;
;;;
(define (fichier nom taille)
(vector 'F nom taille))
;;;
;;;
(define (repertoire nom)
(vector 'D nom))
;;;;;;;; Reconnaisseurs
;;;
;;;
(define (fichier? desc)
(equal? (vector-ref desc 0) 'F))
;;;
;;;
(define (repertoire? desc)
(equal? (vector-ref desc 0) 'D))
;;;;;;;; Accesseurs
;;;
;;;
(define (nom desc)
(vector-ref desc 1))
;;;
;;;
;;;
(define (taille desc)
(vector-ref desc 2))
Un système de fichiers peut être représenté par un arbre général dont
les étiquettes sont des descripteurs.
Noter que tout arbre ainsi défini ne représente pas un système de
fichiers valide: dans un système de fichiers réel, tout noeud qui a
comme étiquette un descripteur de fichier doit être une feuille et les
noms des différents éléments d'un répertoire doivent être tous
différents. Dans la suite, nous nommerons
Systeme le type des
éléments de
ArbreGeneral[Descripteur] qui vérifient ces deux
propriétés.
Nous voudrions définir la fonction
du-s qui correspond à la
commande
du -s d'Unix:
(du-s (syst1)) -> 1111
;;;
;;;
;;;
Autrement dit,
(du-s systeme) rend la somme des tailles de tous
les fichiers présents dans le système. La définition de cette fonction
est une définition « classique » pour les arbres généraux:
-
soit l'étiquette de l'arbe est le descripteur d'un fichier et le
résultat est la taille de ce fichier,
- soit c'est un répertoire et il faut sommer les quantités
d'espace disque utilisées par les différents éléments du répertoire,
cette sommation pouvant être effectuée en utilisant la fonctionnelle
map:
(define (du-s systeme)
(if (fichier? (ag-etiquette systeme))
(taille (ag-etiquette systeme))
(reduce + 0 (map du-s (ag-foret systeme)))))
Nous voudrions définir la fonction
ll qui correspond à la
commande
ls -l d'Unix:
(ll (syst1)) ->
"
0 rab/
0 rgh/
66 fbc
"
;;;
;;;
;;;
;;;
;;;
;;;
Pour calculer le résultat de cette fonction, on peut:
-
extraire la liste des descripteurs de tous les sous-arbres du
système (en utilisant la fonctionnelle map appliquée à la
forêt des sous-répertoires et à la fonction ag-etiquette),
- fabriquer la liste des lignes du paragraphe recherché (toujours
à l'aide de la fonctionnelle map, appliquée à la liste des
descripteurs obtenue dans le point précédent et à une
fonction -- à définir -- qui rend la ligne pour un descripteur donné),
- et il n'y a plus qu'à fabriquer le paragraphe de toutes ces
lignes.
Voici la définition Scheme correspondante:
(define (ll systeme)
;;
;;
;;
;;
;;
(define (desc-ll descripteur)
(string-append
(->string (if (fichier? descripteur)
(taille descripteur)
0))
(string #\tab)
(nom descripteur)
(if (fichier? descripteur) "" "/")))
;;
(paragraphe (map desc-ll
(map ag-etiquette (ag-foret systeme)))))
Nous voudrions définir la fonction
find qui correspond à la
commande Unix de même nom:
;;;
;;;
;;;
Voici un exemple de résultat de cette fonction:
(find "fbc" (syst1)) ->
"
./rab/rgh/fbc
./rab/fbc
./rcd/fbc
"
Comme il faut les noms complets, on doit définir une fonction
auxiliaire qui a un argument de plus, une chaîne de caractères qui
sera un préfixe des lignes de son résultat. De plus, comme d'habitude, pour
les définitions de fonctions ayant un arbre généralisé comme donnée,
il faut également définir une fonction qui a une forêt comme donnée.
D'autre part, on peut noter que la valeur de l'argument « ident » (le
nom à chercher) sera inchangée pour tous les appels récursifs: dans
les deux fonctions auxiliaires précédentes, cet argument peut être mis
en variable globale. D'où la structure de la définition de la fonction
find:
(define (find ident systeme)
;;
;;
;;
;;
... à faire
... à faire
;;
;;
;;
... à faire
... à faire
;;
(findAux "" systeme))
Définition de la fonction findAux
Le résultat de l'application de
findAux est composé
-
d'une ligne comportant le nom complet du système donné lorsque
le nom de ce système est le nom recherché,
- du résultat de la recherche sur la forêt du contenu du système donné
lorsque ce système est un répertoire.
D'où la définition:
(define (find ident systeme)
;;
;;
;;
;;
(define (findAux path systeme)
(paragraphe-append
(if (equal? ident (nom (ag-etiquette systeme)))
(paragraphe (list (string-append path ident)))
(paragraphe '()))
(if (repertoire? (ag-etiquette systeme))
(find-foret (string-append path (nom (ag-etiquette systeme)) "/")
(ag-foret systeme))
(paragraphe '()))))
;;
;;
;;
...
Définition de la fonction find-foret
Nous pouvons utiliser les fonctionnelles
map et
reduce,
map permettant de fabriquer la liste des paragraphes résultats
de la recherche sur les éléments de la forêt et
reduce
permettant de concaténer ces paragraphes.
-
Comme d'habitude, pour concaténer les paragraphes, nous
appliquons reduce à la fonction paragraphe-append et
au paragraphe vide.
- Pour fabriquer la liste des paragraphes, nous devons appliquer
la fonction findAux à chacun des éléments de la forêt, mais
avec un autre argument, le préfixe: nous définissons donc une
fonction interne qui a ce dernier argument comme variable globale.
D'où la définition:
(define (find ident systeme)
;;
;;
;;
;;
... cf. ci-dessus
;;
;;
;;
(define (find-foret path F)
;
;
(define (findAux-path G)
(findAux path G))
(reduce paragraphe-append (paragraphe '()) (map findAux-path F)))
...
