9.5/_sorted_tree_node_collection_8php_source.html

<?php

namespace ‪TYPO3\CMS\Backend\Tree;


/*

 * This file is part of the TYPO3 CMS project.

 *

 * It is free software; you can redistribute it and/or modify it under

 * the terms of the GNU General Public License, either version 2

 * of the License, or any later version.

 *

 * For the full copyright and license information, please read the

 * LICENSE.txt file that was distributed with this source code.

 *

 * The TYPO3 project - inspiring people to share!

 */


class ‪SortedTreeNodeCollection extends ‪\TYPO3\CMS\Backend\Tree\TreeNodeCollection

{

    public function ‪contains(\‪TYPO3\CMS\Backend\Tree\‪TreeNode $node)

    {

        return $this->‪offsetOf($node) !== -1;

    }


    protected function ‪offsetOf(\‪TYPO3\CMS\Backend\Tree\‪TreeNode $node)

    {

        return $this->‪binarySearch($node, 0, $this->count() - 1);

    }


    protected function ‪binarySearch(\‪TYPO3\CMS\Backend\Tree\‪TreeNode $node, $start, $end)

    {

        if (!$start && $end - $start >= 2 || $end - $start > 2) {

            $divider = ceil(($end - $start) / 2);

            if ($this->offsetGet($divider)->equals($node)) {

                return $divider;

            }

            if ($this->offsetGet($divider)->compareTo($node) > 0) {

                return $this->‪binarySearch($node, $start, $divider - 1);

            }

            return $this->‪binarySearch($node, $divider + 1, $end);

        }

        if ($this->offsetGet($start)->equals($node)) {

            return $start;

        }

        if ($this->offsetGet($end)->equals($node)) {

            return $end;

        }

        return -1;

    }


    protected function ‪normalize()

    {

        $nodes = [];

        foreach ($this as $node) {

            $nodes[] = $node;

        }

        $this->exchangeArray($nodes);

    }


    public function ‪append($node)

    {

        parent::append($node);

        $this->‪asort();

        $this->‪normalize();

    }

}