README

注意：这是对 marcj/topsort 的直接复制，唯一的区别是保证与PHP 5.3的兼容性

此库提供了拓扑排序（topSort）的多种实现。除了普通的排序算法外，它还提供了分组拓扑排序的实现，这意味着您可以传递带有类型的项，这些项将在排序中分组在一起。由于其使用字符串而不是数组来实现，其速度比普通实现快20多倍。

这是什么？

拓扑排序对于确定依赖加载非常有用。它告诉您哪些元素需要首先执行，以便按正确顺序满足所有依赖项。

示例用法：工作单元（关系），简单的包管理器，依赖注入等。

示例

$sorter = new StringSort();

$sorter->add('car1', ['owner1', 'brand1']);
$sorter->add('brand1');
$sorter->add('brand2');
$sorter->add('owner1', ['brand1']);
$sorter->add('owner2', ['brand2']);

$result = $sorter->sort();
// output would be:
[
 'brand1',
 'owner1',
 'car1',
 'brand2',
 'owner2'
]

有时您希望将相同类型的项分组在一起（想象一个希望将同一类型的所有元素组合在一起存储的工作单元）

$sorter = new GroupedStringSort();

$sorter->add('car1', 'car', ['owner1', 'brand1']);
$sorter->add('brand1', 'brand');
$sorter->add('brand2', 'brand');
$sorter->add('owner1', 'user', ['brand1']);
$sorter->add('owner2', 'user', ['brand2']);

$result = $sorter->sort();
// output would be:
[
 'brand2',
 'brand1',
 'owner2',
 'owner1',
 'car1'
]

$groups = $sorter->getGroups();
[
   {type: 'brand', level: 0, position: 0, length: 2},
   {type: 'user', level: 1, position: 2, length: 2},
   {type: 'car', level: 2, position: 4, length: 1},
]
//of course there may be several groups with the same type, if the dependency graphs makes this necessary.

foreach ($groups as $group) {
   $firstItem = $result[$group->position];
   $allItemsOfThisGroup = array_slice($result, $group->position, $group->length);
}

您只能将字符串作为元素存储。要排序PHP对象，您可以存储其哈希值。 $sorter->add(spl_object_hash($obj1), [spl_object_hash($objt1Dep)])。

安装

使用composer包：[marcj/topsort)[https://packagist.org.cn/packages/marcj/topsort]

{
    "require": {
        "marcj/topsort": "~0.1"
    }
}

include 'vendor/autoload.php';

$sorter = new GroupedStringSort;
$sorter->add(...);

$result = $sorter->sort();

实现

tl;dr：对于常规topSort，请使用FixedArraySort；对于分组topSort，请使用GroupedStringSort，因为它们总是最快的，并且具有良好的内存占用。

ArraySort

这是使用普通PHP数组的topSort最基本、最不高效的实施。

FixedArraySort

这使用php的SplFixedArray，因此更具内存友好性。

StringSort

这使用字符串作为存储，因此没有数组开销。因此，它稍微快一些，并且与FixedArraySort具有几乎相同的内存占用。小缺点：您不能存储包含空字符的元素ID。

GroupedArraySort

这是使用普通PHP数组实现的分组topSort最基本、不太高效的实施。

GroupedStringSort

这使用字符串作为存储，因此没有数组操作开销。它非常快，并且比GroupedArraySort具有更好的内存占用。小缺点：您不能存储包含空字符的元素ID。

PHP 7.0.9的基准测试

测试数据：1/3有两个边，1/3有一个边，1/3没有边。使用./bin/console中的benchmark命令来玩它。