按任意数量的子字符串对字符串数组进行排序

Question

我正在尝试修改 php-cs-fixer 中的 the OrderedImportsFixer class，这样我就可以按照我想要的方式清理我的文件。我想要的是以类似于您在文件系统列表中看到的方式对我的导入进行排序，“目录”列在“文件”之前。

所以，给定这个数组：

$indexes = [
    26 => ["namespace" => "X\Y\Zed"],
    9 =>  ["namespace" => "A\B\See"],
    3 =>  ["namespace" => "A\B\Bee"],
    38 => ["namespace" => "A\B\C\Dee"],
    51 => ["namespace" => "X\Wye"],
    16 => ["namespace" => "A\Sea"],
    12 => ["namespace" => "A\Bees"],
    31 => ["namespace" => "M"],
];

我想要这个输出：

$sorted = [
    38 => ["namespace" => "A\B\C\Dee"],
    3 =>  ["namespace" => "A\B\Bee"],
    9 =>  ["namespace" => "A\B\See"],
    12 => ["namespace" => "A\Bees"],
    16 => ["namespace" => "A\Sea"],
    26 => ["namespace" => "X\Y\Zed"],
    51 => ["namespace" => "X\Wye"],
    31 => ["namespace" => "M"],
];

在典型的文件系统列表中：

我已经在 uasort 进行了一段时间（必须保持密钥关联）并且已经接近。诚然，这更多是由于绝望的失败，而不是任何形式的严格方法。不真正了解 uasort 的工作原理有点限制了我。

// get the maximum number of namespace components in the list
$ns_counts = array_map(function($val){
    return count(explode("\", $val["namespace"]));
}, $indexes);
$limit = max($ns_counts);

for ($depth = 0; $depth <= $limit; $depth++) {
    uasort($indexes, function($first, $second) use ($depth, $limit) {
        $fexp = explode("\", $first["namespace"]);
        $sexp = explode("\", $second["namespace"]);
        if ($depth === $limit) {
            // why does this help?
            array_pop($fexp);
            array_pop($sexp);
        }
        $fexp = array_slice($fexp, 0, $depth + 1, true);
        $sexp = array_slice($sexp, 0, $depth + 1, true);
        $fimp = implode(" ", $fexp);
        $simp = implode(" ", $sexp);
        //echo "$depth: $fimp <-> $simp\n";
        return strnatcmp($fimp, $simp);
    });
}
echo json_encode($indexes, JSON_PRETTY_PRINT);

这给了我正确排序的输出，但底部而不是顶部有更深的命名空间：

{
    "31": {
        "namespace": "M"
    },
    "12": {
        "namespace": "A\Bees"
    },
    "16": {
        "namespace": "A\Sea"
    },
    "3": {
        "namespace": "A\B\Bee"
    },
    "9": {
        "namespace": "A\B\See"
    },
    "38": {
        "namespace": "A\B\C\Dee"
    },
    "51": {
        "namespace": "X\Wye"
    },
    "26": {
        "namespace": "X\Y\Zed"
    }
}

我在想我可能必须为每个级别的命名空间构建一个单独的数组并分别对其进行排序，但对于我可能如何做到这一点却一无所知。有什么关于完成此工作的最后一步的建议，或者完全不同但不涉及这么多循环的建议吗？

Answer 1

我认为以下应该有效：

uasort($indexes, static function (array $entry1, array $entry2): int {  
    $ns1Parts = explode('\', $entry1['namespace']);
    $ns2Parts = explode('\', $entry2['namespace']);

    $ns1Length = count($ns1Parts);
    $ns2Length = count($ns2Parts);

    for ($i = 0; $i < $ns1Length && isset($ns2Parts[$i]); $i++) {
        $isLastPartForNs1 = $i === $ns1Length - 1;
        $isLastPartForNs2 = $i === $ns2Length - 1;

        if ($isLastPartForNs1 !== $isLastPartForNs2) {
            return $isLastPartForNs1 <=> $isLastPartForNs2;
        }

        $nsComparison = $ns1Parts[$i] <=> $ns2Parts[$i];

        if ($nsComparison !== 0) {
            return $nsComparison;
        }
    }

    return 0;
});

它的作用是：

将名称空间拆分成多个部分，
从第一个开始比较每个部分，并且：
- 如果我们在一个部分而不是另一个部分的最后一部分，请优先考虑部分最多的部分，
- 否则，如果各个部分不同，则按字母顺序优先考虑在另一部分之前的部分。

Demo

Answer 2

我们将其分为 4 个步骤。

步骤 1： 从数据集创建层次结构。

function createHierarchicalStructure($indexes){
    $data = [];
    foreach($indexes as $d){
        $temp = &$data;
        foreach(explode("\",$d['namespace']) as $namespace){
            if(!isset($temp[$namespace])){
                $temp[$namespace] = [];
            }
            $temp = &$temp[$namespace];
        }
    }
    
    return $data;
}

将命名空间拆分 \ 并维护一个 $data 变量。使用 & 地址引用来保持编辑数组的相同副本。

第 2 步： 对层次结构进行排序，首先是文件夹，然后是文件。

function fileSystemSorting(&$indexes){
    foreach($indexes as $key => &$value){
        fileSystemSorting($value);
    }
    
    uksort($indexes,function($key1,$key2) use ($indexes){
        if(count($indexes[$key1]) == 0 && count($indexes[$key2]) > 0) return 1;
        if(count($indexes[$key2]) == 0 && count($indexes[$key1]) > 0) return -1;
        return strnatcmp($key1,$key2);
    });
}

对下级文件夹进行排序，当前级别的文件夹使用uksort。 Vice-versa 也可以。如果比较的两个文件夹都有子文件夹，则将它们作为字符串进行比较，否则如果一个是文件夹另一个是文件，则将文件夹放在上面。

第 3 步： 扁平化层次结构，因为它们是有序的。

function flattenFileSystemResults($hierarchical_data){
    $result = [];
    foreach($hierarchical_data as $key => $value){
        if(count($value) > 0){
            $sub_result = flattenFileSystemResults($value);
            foreach($sub_result as $r){
                $result[] = $key . "\" . $r;
            }   
        }else{
            $result[] = $key;
        }
    }
    
    return $result;
}

步骤 4： 恢复初始数据密钥和 return 结果。

function associateKeys($data,$indexes){
    $map = array_combine(array_column($indexes,'namespace'),array_keys($indexes));
    $result = [];
    foreach($data as $val){
        $result[ $map[$val] ] = ['namespace' => $val];
    }
    return $result;
}

Driver代码：

function foldersBeforeFiles($indexes){
   $hierarchical_data = createHierarchicalStructure($indexes);
   fileSystemSorting($hierarchical_data);
   return associateKeys(flattenFileSystemResults($hierarchical_data),$indexes);
}

print_r(foldersBeforeFiles($indexes));

演示： https://3v4l.org/cvoB2

Answer 3

这是进一步分解步骤的另一个版本，虽然它可能不是最佳的，但绝对有助于我的大脑思考它。有关正在发生的事情的更多详细信息，请参阅评论：

uasort(
    $indexes,
    static function (array $a, array $b) {

        $aPath = $a['namespace'];
        $bPath = $b['namespace'];

        // Just in case there are duplicates
        if ($aPath === $bPath) {
            return 0;
        }

        // Break into parts
        $aParts = explode('\', $aPath);
        $bParts = explode('\', $bPath);

        // If we only have a single thing then it is a root-level, just compare the item
        if (1 === count($aParts) && 1 === count($bParts)) {
            return $aPath <=> $bPath;
        }

        // Get the class and namespace (file and folder) parts
        $aClass = array_pop($aParts);
        $bClass = array_pop($bParts);

        $aNamespace = implode('\', $aParts);
        $bNamespace = implode('\', $bParts);

        // If the namespaces are the same, sort by class name
        if ($aNamespace === $bNamespace) {
            return $aClass <=> $bClass;
        }

        // If the first namespace _starts_ with the second namespace, sort it first
        if (0 === mb_strpos($aNamespace, $bNamespace)) {
            return -1;
        }

        // Same as above but the other way
        if (0 === mb_strpos($bNamespace, $aNamespace)) {
            return 1;
        }

        // Just only by namespace
        return $aNamespace <=> $bNamespace;
    }
);

Online demo

Answer 4

我觉得 Jeto 的算法设计没有问题，但我决定更简洁地实现它。我的代码片段避免了 for() 循环中的迭代函数调用和算术运算，使用单个宇宙飞船运算符和单个 return。我的片段短了 50% 以上，而且我通常觉得它更容易阅读，但每个人都认为自己的宝宝很可爱，对吧？

代码：(Demo)

uasort($indexes, function($a, $b) {  
    $aParts = explode('\', $a['namespace']);
    $bParts = explode('\', $b['namespace']);
    $aLast = count($aParts) - 1;
    $bLast = count($bParts) - 1;

    for ($cmp = 0, $i = 0; $i <= $aLast && !$cmp; ++$i) {
        $cmp = [$i === $aLast, $aParts[$i]] <=> [$i === $bLast, $bParts[$i]];
    }
    return $cmp;
});

就像 Jeto 的回答一样，它同时迭代每个数组并且

检查任一元素是否是数组的最后一个元素，如果是，则将其向下移动（因为我们想要更长的路径来赢得决胜局）；
如果两个元素都不是其数组中的最后一个，则按字母顺序比较元素的当前字符串。
重复该过程，直到生成非零评估。
由于预计不会出现重复条目，因此 return 值应始终为 -1 或 1（永远不会 0）

注意，我在两个条件下停止 for() 循环。

如果 $i 大于 $aParts 中的元素数（仅）——因为如果 $bParts 的元素少于 $aParts，则 $cmp 将在触发通知之前生成一个非零值。
如果 $cmp 是一个非零值。

最后，解释一下飞船运算符两边的数组语法...
飞船运算符将从左到右比较数组，因此它的行为如下：

leftside[0] <=> rightside[0] then leftside[1] <=> rightside[1]

以这种方式进行多重比较不会影响性能，因为 <=> 两边都没有函数调用。如果涉及函数调用，以后备方式进行个别比较会更高效：

fun($a1) <=> fun($b1) ?: fun($a2) <=> fun($b2)

这样后续的函数调用只会在需要决胜局时才真正进行。

按任意数量的子字符串对字符串数组进行排序

Sorting an array of strings by arbitrary numbers of substrings

php

arrays

sorting

usort