Sorting blog posts - every 3rd should be featured post

<?php
/*
Sorting blog posts - every third place should be taken only by a featured post
*/

echo '<style type="text/css"> p { margin: 10px 0 0; } .success { color: #070; } .error { color: #F66; }</style>';

class Category {
    public $id;
    public $is_featured = false;

    public function __construct($id, $is_featured = false) {
        $this->id = $id;
        $this->is_featured = $is_featured;
    }
}

class Post {
    public $id;
    public $category;

    public function __construct($id, $category) {
        $this->id = $id;
        $this->category = $category;
    }

    public static function sort($posts, $groupLength = 3) {
        $moveElementInArray = function(&$array, $fromIndex, $toIndex) {
            array_splice($array, $toIndex, 0, array_splice($array, $fromIndex, 1));
        };

        $sortedPosts = $posts;

        for ($index = 0; $index < count($posts); $index++) {
            $post = $sortedPosts[$index];

            /* If we don't need a featured post here or this post is a featured - leave it as is */
            if ($index % 3 !== 0 || $post->category->is_featured) {
                continue;
            }

            $featuredPostPlaces = [];
            foreach ($sortedPosts as $i => $p) {
                if ($p->category->is_featured) {
                    $featuredPostPlaces[$i] = $p;
                }
            }

            /* Check if we have enough featured posts */
            $groupNumber = floor($index / $groupLength);
            if ($groupNumber < count($featuredPostPlaces)) {

                /* We should split featured posts into two groups - prevous posts and next posts.
                   We should take the closest post from group which have a suitable post. */

                /* Check if we have enough featured posts on previous items */
                $previousFeaturedPostPositions = array_filter(array_keys($featuredPostPlaces), function($position) use ($index) { return $position < $index; });
                $closestPreviousFeaturedPostPosition = null;
                if (count($previousFeaturedPostPositions) > $groupNumber) {
                    $closestPreviousFeaturedPostPosition = max($previousFeaturedPostPositions);
                }

                /* Check if we have featured posts on next items */
                $nextFeaturedPostPositions = array_filter(array_keys($featuredPostPlaces), function($position) use ($index) { return $position > $index; });
                $closestNextFeaturedPostPosition = null;
                if (count($nextFeaturedPostPositions) > 0) {
                    $closestNextFeaturedPostPosition = min($nextFeaturedPostPositions);
                }

                if ( $closestPreviousFeaturedPostPosition !== null &&
                          ($closestNextFeaturedPostPosition === null || abs($closestPreviousFeaturedPostPosition - $index) < abs($closestNextFeaturedPostPosition - $index)) ) {
                    /* Featured element to move is on previous elements */

                    $moveElementInArray($sortedPosts, $closestPreviousFeaturedPostPosition, $index);

                    /* We need to sort previous elements again */
                    $resortedPreviousElements = self::sort(array_slice($sortedPosts, 0, $index - 1));
                    $sortedPosts = array_merge($resortedPreviousElements, array_slice($sortedPosts, $index - 1));
                } elseif ($closestNextFeaturedPostPosition !== null) {
                    /* Featured element to move is on next elements */
                    $moveElementInArray($sortedPosts, $closestNextFeaturedPostPosition, $index);
                }
            }
        }

        return array_values($sortedPosts);
    }
}

$categories = [
    1 => new Category(1, true),
    2 => new Category(2, true),
    3 => new Category(3, false),
];

$posts = [
    // Featured
    1 => new Post(1, $categories[1]),
    2 => new Post(2, $categories[1]),
    3 => new Post(3, $categories[1]),
    4 => new Post(4, $categories[1]),
    5 => new Post(5, $categories[1]),
    6 => new Post(6, $categories[2]),
    7 => new Post(7, $categories[2]),
    8 => new Post(8, $categories[2]),
    9 => new Post(9, $categories[2]),

    // Usual
    10 => new Post(10, $categories[3]),
    11 => new Post(11, $categories[3]),
    12 => new Post(12, $categories[3]),
    13 => new Post(13, $categories[3]),
    14 => new Post(14, $categories[3]),
    15 => new Post(15, $categories[3]),
    16 => new Post(16, $categories[3]),
    17 => new Post(17, $categories[3]),
    18 => new Post(18, $categories[3]),
    19 => new Post(19, $categories[3]),
    20 => new Post(20, $categories[3]),
];

$tests = [
    [
        'input'  => [],
        'output' => [],
    ],

    [
        'input'  => [1, 2, 3, 4, 5, 6],
        'output' => [1, 2, 3, 4, 5, 6],
    ],

    [
        'input'  => [1, 2, 3, 4, 10, 11],
        'output' => [1, 2, 3, 4, 10, 11],
    ],

    [
        'input'  => [10, 11, 12, 13, 14, 15, 16],
        'output' => [10, 11, 12, 13, 14, 15, 16],
    ],

    [
        'input'  => [1, 2, 3, 4, 10, 11, 12, 13, 14],
        'output' => [1, 2, 10,   3, 11, 12,   4, 13, 14],
    ],

    [
        'input'  => [1, 2, 10, 11, 12, 13],
        'output' => [1, 10, 11,   2, 12, 13],
    ],

    [
        'input'  => [10, 11, 12, 13, 1, 2],
        'output' => [1, 10, 11,   2, 12, 13],
    ],

    [
        'input'  => [10, 11, 12, 13, 14, 1, 2],
        'output' => [1, 10, 11,   2, 12, 13, 14],
    ],

    [
        'input'  => [10, 11, 12, 13, 14, 15, 1, 2, 3],
        'output' => [1, 10, 11,   2, 12, 13,   3, 14, 15],
    ],

    [
        'input'  => [10, 11, 12, 13, 14, 15, 1, 2],
        'output' => [1, 10, 11,   2, 12, 13,   14, 15],
    ],

    [
        'input'  => [10, 11, 12, 13, 14, 15, 1, 2],
        'output' => [1, 10, 11,   2, 12, 13,   14, 15],
    ],

    [
        'input'  => [10, 11, 12, 13, 14, 15, 16, 1, 2],
        'output' => [1, 10, 11,   2, 12, 13,   14, 15, 16],
    ],

    [
        'input'  => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
        'output' => [1, 2, 3,    4, 5, 10,    6, 11, 12,    7, 13, 14,    8, 15, 16,   9, 17, 18],
    ],

    [
        'input'  => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
        'output' => [1, 2, 3,    4, 10, 11,    5, 12, 13,    6, 14, 15,    7, 16, 17,   8, 18, 19, 9],
    ],

    [
        'input'  => [1, 2, 10, 11, 3, 4, 5, 12, 6, 13, 14, 15, 7, 16, 8, 17, 18, 19, 9],
        'output' => [1, 2, 10,    3, 11, 4,  5, 12, 13,    6, 14, 15,    7, 16, 17,   8, 18, 19, 9],
    ],
];

foreach ($tests as $index => $test) {
    $result = Post::sort(array_values( array_map(function($id) use ($posts) { return $posts[$id]; }, $test['input']) ));

    $inputIds = $test['input'];
    $expectedOutputIds = $test['output'];
    $realOutputIds = array_map(function($post) { return $post->id; }, $result);

    $outputDiff = array_diff_assoc($expectedOutputIds, $realOutputIds);

    if (empty($outputDiff)) {
        echo "<p class='success'>Test #{$index}: SUCCESS</p>";
    } else {
        echo "<p class='error'>Test #{$index}: ERROR.";
            echo "<table>";
                echo "<tr><td>Input:</td><td>" . json_encode($inputIds) . "</td></tr>";
                echo "<tr><td>Output:</td><td>" . json_encode($realOutputIds) . "</td></tr>";
                echo "<tr><td>Expected Output:</td><td>" . json_encode($expectedOutputIds) . "</td></tr>";
            echo "</table>";
        echo "</p>";
    }
}