Build Status Code coverage Dependency Status Latest Stable Version Total Downloads Latest Unstable Version License

Je viens de publier en version 1.0.0 un ensemble de classes PHP pour stocker des couples clé/valeur en utilisant un ordre particulier (défini par un comparateur sur les clés). Il utilise les arbres AVL cousus comme structures internes et exécute ses opérations en temps logarithmique (log(n)).

Création

La classe de base pour utiliser les tables d'associations triées est la classe TreeMap.

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeMap;

// This will create a map indexed by numbers
// it contains 10 key/value pairs from 0/0 to 9/9
$map = TreeMap::create()->put(
    [1=>1, 9=>9, 5=>5, 2=>2, 6=>6, 3=>3, 0=>0, 8=>8, 7=>7, 4=>4]
);

Il y a deux autres classes pour créer des tables d'association qui sont en fait des vues sur une autre table.

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeMap;
use chdemko\SortedCollection\ReversedMap;
use chdemko\SortedCollection\SubMap;

$map = TreeMap::create()->put(
    [1=>1, 9=>9, 5=>5, 2=>2, 6=>6, 3=>3, 0=>0, 8=>8, 7=>7, 4=>4]
);

// This will create a map which is the reverse of $map
$reversed = ReversedMap::create($map);

// This will create a map which is a sub map of $reversed
$sub = SubMap::create($reversed, 7, 3);

// This will display {"7":7,"6":6,"5":5,"4":4}
echo $sub . PHP_EOL;

Pour les sous-tables, il existe d'autres méthodes pour la création.

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeMap;
use chdemko\SortedCollection\SubMap;

$map = TreeMap::create()->put(
    [1=>1, 9=>9, 5=>5, 2=>2, 6=>6, 3=>3, 0=>0, 8=>8, 7=>7, 4=>4]
);

// This will create a map which is a sub map of $map from key 3 to the end
$tail = SubMap::tail($map, 3);

$map[10] = 10;

// This will display {"3":3,"4":4,"5":5,"6":6,"7":7,"8":8,"9":9,"10":10}
echo $tail . PHP_EOL;

// This will create a sub map of $map from beginning to key 7 (inclusive)
$head = SubMap::head($map, 7, true);

// This will display [0,1,2,3,4,5,6,7]
echo $head . PHP_EOL;

Les ensembles sont construits en utilisant des fonctions similaires

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeSet;
use chdemko\SortedCollection\ReversedSet;
use chdemko\SortedCollection\SubSet;

$set = TreeSet::create()->put([1, 9, 5, 2, 6, 3, 0, 8, 7, 4]);
$reversed = ReversedSet::create($set);
$sub = SubSet::create($reversed, 7, 3);

// This will display [7,6,5,4]
echo $sub . PHP_EOL;

Itération

Ces collections supportent nativement les itérateurs PHP.

Pour les tables

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeMap;
use chdemko\SortedCollection\ReversedMap;
use chdemko\SortedCollection\SubMap;

$map = TreeMap::create()->put(
    [1=>1, 9=>9, 5=>5, 2=>2, 6=>6, 3=>3, 0=>0, 8=>8, 7=>7, 4=>4]
);
$reversed = ReversedMap::create($map);
$sub = SubMap::create($reversed, 7, 3);

// This will display 7:7;6:6;5:5;4:4;
foreach ($sub as $key => $value)
{
    echo $key . ':' . $value . ';';
}
echo PHP_EOL;

Pour les ensembles

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeSet;
use chdemko\SortedCollection\ReversedSet;
use chdemko\SortedCollection\SubSet;

$set = TreeSet::create()->put([1, 9, 5, 2, 6, 3, 0, 8, 7, 4]);
$reversed = ReversedSet::create($set);
$sub = SubSet::create($reversed, 7, 3);

// This will display 0:7;1:6;2:5;3:4;
foreach ($sub as $key => $value)
{
    echo $key . ':' . $value . ';';
}
echo PHP_EOL;

Le comportement est inpredictible si la clé courante d'un itérateur est supprimée de la collection.

Comptage

Ces collections supportent le comptage PHP.

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeMap;
use chdemko\SortedCollection\ReversedMap;
use chdemko\SortedCollection\SubMap;

$map = TreeMap::create()->put(
    [1=>1, 9=>9, 5=>5, 2=>2, 6=>6, 3=>3, 0=>0, 8=>8, 7=>7, 4=>4]
);
$reversed = ReversedMap::create($map);
$sub = SubMap::create($reversed, 7, 3);

// This will display 4
echo count($sub) . PHP_EOL;

Accès tableaux

Insertion, modification, accès et suppression ont été implémentés pour utiliser nativement le comportement des tableaux.

Pour les tables

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeMap;

$map = TreeMap::create();
$map[4] = 4;
$map[2] = 2;
$map[6] = 6;
unset($map[4]);

// This will display 1
echo isset($map[2]) . PHP_EOL;

// This will display 2
echo $map[2] . PHP_EOL;

Pour les ensembles

require __DIR__ . '/vendor/autoload.php';
use chdemko\SortedCollection\TreeSet;

$set = TreeSet::create();
$set[4] = true;
$set[2] = true;
$set[6] = true;
unset($set[4]);

// This will display 1
echo isset($set[2]) . PHP_EOL;

// This will display 1
echo $set[2] . PHP_EOL;

// This will display nothing
echo $set[4] . PHP_EOL;

Beaucoup d'autres méthodes ont été implémentées pour donner accès à l'élémént minimum, l'élément immédiatement inférieur... Voir la documentation de l'API.

Citation

Si vous voulez utiliser ce projet, y compris dans des activités de recherche, merci de le citer en utilisant (BibTeX format). Vous êtes aussi invité à envoyer un courriel à Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser..