Librairie d'arbres intervallaires
Posté : 09 août 2008, 16:42
Bonjour à tous,
Dans la mesure où la gestion de ce genre de choses est difficile, j'ai dû créer une librairie d'arbres intervallaires. Cette librairie fait le lien entre la base de données et des objets, effectue les requêtes de sélection, d'insertion, et de délétion et assure un cache sommaire.
Elle ne gère qu'un arbre d'id, il est suggéré de l'associer avec une table contenant les données à hiérarchiser (menus, arborescences, etc…).
Après avoir vu quelques sujets s'ouvrir à ce sujet, il semble y avoir une demande pour ce genre de choses, je la publie ici.
Fichier php :
NB : La racine doit être insérée à la main.
Cette classe est utilisée sur un site en cours de développement, il peut subsister des bugs, n'hésitez pas à me prévenir pour tout bug, toute suggestion, toute question par message privé ou mail.
Si vous voulez gérer vous même vos arbres ou en savoir plus à ce sujet, je vous suggère l'excellent tutoriel sur developpez.com : http://sqlpro.developpez.com/cours/arborescence/
Voilà
Dans la mesure où la gestion de ce genre de choses est difficile, j'ai dû créer une librairie d'arbres intervallaires. Cette librairie fait le lien entre la base de données et des objets, effectue les requêtes de sélection, d'insertion, et de délétion et assure un cache sommaire.
Elle ne gère qu'un arbre d'id, il est suggéré de l'associer avec une table contenant les données à hiérarchiser (menus, arborescences, etc…).
Après avoir vu quelques sujets s'ouvrir à ce sujet, il semble y avoir une demande pour ce genre de choses, je la publie ici.
Fichier php :
<?php
/**
* Auteur : Emmanuel Thierry
* Créé en juillet 2008.
* Code soumis à droit d'auteur, peut être modifié (notamment pour intégration),
* mais non redistribué. Pour toute utilisation commerciale, veuillez me contacter à
* l'adresse mail [email protected]
*/
/**
* Classe gérant l'arbre.
*/
class tree
{
/**
* @var string Nom de la table arborescente.
*/
private $tree_table;
/**
* @var int Identifiant de l'arbre.
*/
private $tree_id;
/**
* @var tree_node Arbre.
*/
private $tree = NULL;
/**
* @var bool Indique si la table est verrouillée.
*/
private $locked = FALSE;
/**
* Constructeur de la classe.
* @param string Nom de la table arborescente.
* @param int Identifiant de l'arbre.
* @param bool Verrouille automatiquement la table à l'instanciation.
* Permet de s'assurer que les données du cache ne seront pas corrompues durant l'exécution du script.
*/
public function __construct($tree_table, $tree_id = 1, $autolock = TRUE)
{
if(!preg_match('/[\w\-_]{1,64}/',$tree_table))
{
trigger_error('Nom de table incorrect');
}
$this->tree_table = $tree_table;
$this->tree_id = $tree_id;
if($autolock)
{
$this->lock();
}
}
/**
* Destructeur de la classe.
*/
public function __destruct()
{
$this->unlock();
}
/**
* Exécute une requête.
* @param string Requête à exécuter.
* @return mixed Renvoie le tableau de résultats ou TRUE si la requête a réussi, sinon FALSE.
*/
private function query($query)
{
static $mysql = NULL;
if(empty($mysql) && !($mysql = mysql_connect('127.0.0.1:3306', 'root', '')) || !mysql_select_db('test', $mysql))
{
return NULL;
}
$result = mysql_query($query, $mysql);
if(is_resource($result))
{
$i = 0;
$rows = array();
while($row = mysql_fetch_assoc($result))
{
$rows[$i++] = $row;
}
return $rows;
}
return $result;
}
/**
* Verrouille la table.
* @param bool Indique si la table doit être verrouillée en écriture.
* @return bool TRUE si la table n'était pas déjà lockée, FALSE sinon.
*/
public function lock($write = FALSE)
{
if(!$this->locked)
{
$this->locked = $this->query('LOCK TABLES ' . $this->tree_table . ' ' . ($write ? 'WRITE' : 'READ') . ';');
return TRUE;
}
return FALSE;
}
/**
* Déverrouille la table.
* @param bool Indique si la table doit vraiment être déverrouillée.
* On y passe la valeur de retour de lock().
* @return bool TRUE si la table était lockée, FALSE sinon.
*/
public function unlock($do_lock=TRUE)
{
if($do_lock && $this->locked)
{
$this->query('UNLOCK TABLES;');
$this->locked = FALSE;
return TRUE;
}
return FALSE;
}
/**
* Construit un noeud à partir d'informations tirées de la base.
* @param array Tableau associant au nom de la colonne sa valeur.
* @return tree_node Noeud représentant les données en entrée.
*/
public function make_node(array $info)
{
$node = new tree_node($info['id'], $info['tleft'], $info['tright']);
if(!isset($this->tree))
{
$this->tree = $node;
}
elseif($ret = $this->tree->insert($node))
{
$this->tree = $ret;
}
return $node;
}
/**
* Sélectionne un ou plusieurs noeuds selon une condition.
* @param array Liste des condtions, l'opérateur AND leurs seront appliqués.
* @return mixed Résultat de la requête.
*/
public function select_node(array $where = array())
{
return $this->query(
'SELECT id, tleft, tright ' .
'FROM ' . $this->tree_table . ' ' .
'WHERE tree=' . intval($this->tree_id) . (!empty($where) ? ' AND ' . implode(' AND ', $where) : '') . ';'
);
}
/**
* Récupère un élément.
* @param int Identifiant de l'élément à sélectionner.
* @param bool TRUE pour passer outre le cache, FALSE sinon.
* @return tree_node Noeud représentant l'élément.
*/
public function get_element($id, $force = FALSE)
{
if(!$force && isset($this->tree) && ($cached = $this->tree->get($id)))
{
return $cached;
}
if($result = $this->select_node(array('id=' . intval($id))))
{
return $this->make_node($result[0]);
}
return NULL;
}
/**
* Récupère la racine.
* @param bool TRUE pour passer outre le cache, FALSE sinon.
* @return tree_node Noeud représentant la racine.
*/
public function get_root($force = FALSE)
{
if(!$force && isset($this->tree) && ($this->tree->left == 1))
{
return $this->tree;
}
if($result = $this->select_node(array('tleft=1')))
{
return $this->make_node($result[0]);
}
return NULL;
}
/**
* Récupère les éléments parents.
* @param int Identifiant de l'élément dont récupérer les parents.
* @param bool TRUE pour passer outre le cache, FALSE sinon.
* @return tree_node Noeud représentant l'élément passé en paramètre.
*/
public function get_parents($id, $force = FALSE)
{
$lock = $this->lock();
if(!($element = $this->get_element($id)))
{
$this->unlock($lock);
return NULL;
}
if(!$force && $element->complete_up())
{
$this->unlock($lock);
return $element;
}
if($results = $this->select_node(array('tleft<' . intval($element->left), 'tright>' . intval($element->right))))
{
foreach($results as $result)
{
$this->make_node($result);
}
}
$this->unlock($lock);
return $element;
}
/**
* Récupère les éléments enfants.
* @param int Identifiant de l'élément dont récupérer les enfants.
* @param bool TRUE pour passer outre le cache, FALSE sinon.
* @return tree_node Noeud représentant l'élément passé en paramètre.
*/
public function get_children($id, $force = FALSE)
{
$lock = $this->lock();
if(!($element = $this->get_element($id)))
{
$this->unlock($lock);
return NULL;
}
if(!$force && $element->complete_down())
{
$this->unlock($lock);
return $element;
}
$results = $this->select_node(array('tleft>' . intval($element->left), 'tright<' . intval($element->right)));
foreach($results as $result)
{
$this->make_node($result);
}
$this->unlock($lock);
return $element;
}
/**
* Construit l'arbre entier.
* @param bool TRUE pour passer outre le cache, FALSE sinon.
* @return tree_node Noeud représentant la racine de l'arbre.
*/
public function get_all($force = FALSE)
{
if(!$force && isset($this->tree) && $this->tree->complete_tree())
{
return $this->tree;
}
$results = $this->select_node();
foreach($results as $result)
{
$this->make_node($result);
}
return $this->tree;
}
/**
* Insère un noeud dans l'arbre.
* @param int Identifiant de l'élément auquel ajouter un enfant.
* @param int Identifiant de l'élément à ajouter.
* @return bool TRUE si l'insertion a réussi, FALSE sinon.
*/
public function insert($parent, $id)
{
$unlock = $this->unlock();
$this->lock(TRUE);
if($e = $this->get_element($parent))
{
unset($this->tree);
$this->query('UPDATE ' . $this->tree_table . ' SET tleft=tleft+2 WHERE tree=' . $this->tree_id . ' AND tleft>=' . intval($e->right) . ';');
$this->query('UPDATE ' . $this->tree_table . ' SET tright=tright+2 WHERE tree=' . $this->tree_id . ' AND tright>=' . intval($e->right) . ';');
$this->query('INSERT ' . $this->tree_table . '(id, tleft, tright, tree) VALUES(' . intval($id) . ', ' . intval($e->right) . ', ' . (intval($e->right)+1) . ', ' . $this->tree_id . ');');
$this->unlock();
if($unlock)
{
$this->lock();
}
return TRUE;
}
$this->unlock();
if($unlock)
{
$this->lock();
}
return FALSE;
}
/**
* Supprime un noeud de l'arbre (ainsi que ses enfants).
* @param int Identifiant de l'élément à supprimer.
* @return bool TRUE si la suppression a réussi, FALSE sinon.
*/
public function delete($id)
{
$unlock = $this->unlock();
$this->lock(TRUE);
if($e = $this->get_element($id))
{
unset($this->tree);
$this->query('DELETE FROM ' . $this->tree_table . ' WHERE tree=' . $this->tree_id . ' AND tright<=' . intval($e->right) . ' AND tleft>=' . intval($e->left) . ';');
$this->query('UPDATE ' . $this->tree_table . ' SET tleft=tleft-' . ($e->right-$e->left+1) . ' WHERE tree=' . $this->tree_id . ' AND tleft>=' . intval($e->right) . ';');
$this->query('UPDATE ' . $this->tree_table . ' SET tright=tright-' . ($e->right-$e->left+1) . ' WHERE tree=' . $this->tree_id . ' AND tright>=' . intval($e->right) . ';');
$this->unlock();
if($unlock)
{
$this->lock();
}
return TRUE;
}
$this->unlock();
if($unlock)
{
$this->lock();
}
return FALSE;
}
}
/**
* Classe représentant l'arbre.
*/
class tree_node
{
/**
* @var int Valeur de gauche (exploité par la librairie).
*/
private $left;
/**
* @var int Valeur de droite (exploité par la librairie).
*/
private $right;
/**
* @var int Identifiant de l'élément.
*/
private $id;
/**
* @var tree_node Noeud parent.
*/
private $parent = NULL;
/**
* @var array Noeuds enfants.
*/
private $children = array();
/**
* Constructeur de la classe.
* @param int Identifiant de l'élément.
* @param int Valeur de gauche (exploité par la librairie).
* @param int Valeur de droite (exploité par la librairie).
*/
public function __construct($id, $left, $right)
{
$this->id = $id;
$this->left = $left;
$this->right = $right;
}
public function __get($name)
{
return (in_array($name, array('id', 'left', 'right', 'parent', 'children')) ? $this->$name : NULL);
}
/**
* Recherche un élément dans les enfants de l'élément courant.
* @param int Identifiant de l'élément à rechercher.
* @return tree_node Elément recherché.
*/
public function get($id)
{
if($this->id == $id)
{
return $this;
}
foreach($this->children as $child)
{
if($ret = $child->get($id))
{
return $ret;
}
}
return NULL;
}
/**
* Récupère l'élément le plus haut dans l'arbre.
* @return tree_node Elément racine de l'arbre.
* A noter que l'élément racine de l'arbre stocké en cache peut ne pas être la racine réelle
* mais seulement un enfant si la racine réelle n'a pas encore fait partie d'une opération de sélection.
*/
public function get_root()
{
if(!isset($this->parent))
{
return $this;
}
return $this->parent->get_root();
}
/**
* Teste si le noeud courant est un enfant d'un autre noeud.
* @param tree_node Elément auquel comparer le noeud courant.
* @return bool Résultat du test.
*/
public function in(tree_node $node)
{
return ($this->left>$node->left) && ($this->right<$node->right);
}
/**
* Insère un noeud dans l'arbre.
* @param tree_node Elément à insérer.
* @return tree_node Retourne la nouvelle racine si elle a changé, NULL sinon.
*/
public function insert(tree_node $node)
{
if($node->in($this))
{
$in = array();
foreach($this->children as $id=>$child)
{
if($node->in($child))
{
return $child->insert($node);
}
if($child->in($node))
{
$in[] = $child;
}
}
$tmp = array();
$node->parent = $this;
$node->children = $in;
foreach($in as $child)
{
$child->parent = $node;
$tmp[] = $child->id;
}
$this->children = array_values(array_filter(
$this->children,
create_function('$e','return !in_array($e->id,' . var_export($tmp, TRUE) . ');')
));
$this->children[] = $node;
}
elseif($this->in($node) && !isset($this->parent))
{
$this->parent = $node;
$node->children = array($this);
return $node;
}
elseif(isset($this->parent))
{
return $this->parent->insert($node);
}
return NULL;
}
/**
* Teste si l'arbre est complet par le bas.
* @return bool Résultat du test.
*/
public function complete_down()
{
return $this->complete_node() && array_reduce($this->children, create_function('$ret,$node', 'return $ret && $node->complete_down();'), TRUE);
}
/**
* Teste si l'arbre est complet par le haut.
* @return bool Résultat du test.
*/
public function complete_up()
{
if($this->left == 1)
{
return true;
}
elseif(!isset($this->parent))
{
return false;
}
if(
$this->parent->complete_node() ||
array_reduce(
$this->parent->children,
create_function('$ret,$node', 'return $ret || ($node->left == ' . ($this->parent->left+1) . ') || ($node->right == ' . ($this->parent->right-1) . ') ;'),
FALSE
)
)
{
return $this->parent->complete_up();
}
}
/**
* Teste si le noeud est complet, c'est à dire que la somme des noeuds enfants est égale à la taille du noeud, donc que le noeud n'a pas d'enfants directs cachés (utilisé pour tester la complétude par le haut).
* @return bool Résultat du test.
*/
public function complete_node()
{
return (array_sum(array_map(create_function('$node', 'return $node->right-$node->left+1;'), $this->children)) == ($this->right-$this->left-1));
}
/**
* Teste si l'arbre est complet.
* @return bool Résultat du test.
*/
public function complete_tree()
{
return $this->get_root()->complete_down();
}
}
?>Code : Tout sélectionner
CREATE TABLE tree
(
id INT UNSIGNED NOT NULL,
tleft INT UNSIGNED NOT NULL,
tright INT UNSIGNED NOT NULL,
tree INT UNSIGNED NOT NULL,
INDEX(tree, tleft),
INDEX(tree, tright),
INDEX(tree, id)
);Cette classe est utilisée sur un site en cours de développement, il peut subsister des bugs, n'hésitez pas à me prévenir pour tout bug, toute suggestion, toute question par message privé ou mail.
Si vous voulez gérer vous même vos arbres ou en savoir plus à ce sujet, je vous suggère l'excellent tutoriel sur developpez.com : http://sqlpro.developpez.com/cours/arborescence/
Voilà
. En plus, c'est vachement sympa comme méthode. C'est une bonne façon de représenter des arbres « sur un plan » (a contrario d'espace, c'est à dire à plusieurs dimensions — plus de 2 —).