class.t3lib_tree_sortednodecollection.php

Go to the documentation of this file.

<?php
/***************************************************************
 *  Copyright notice
 *
 *  (c) 2010-2011 TYPO3 Tree Team <http://forge.typo3.org/projects/typo3v4-extjstrees>
 *  All rights reserved
 *
 *  This script is part of the TYPO3 project. The TYPO3 project is
 *  free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  The GNU General Public License can be found at
 *  http://www.gnu.org/copyleft/gpl.html.
 *  A copy is found in the textfile GPL.txt and important notices to the license
 *  from the author is found in LICENSE.txt distributed with these scripts.
 *
 *
 *  This script is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  This copyright notice MUST APPEAR in all copies of the script!
 ***************************************************************/

/**
 * Sorted Tree Node Collection
 *
 * Note: This collection works only with integers as offset keys and not
 * with much datasets. You have been warned!
 *
 * @author Stefan Galinski <stefan.galinski@gmail.com>
 * @author Steffen Ritter <info@steffen-ritter.net>
 * @package TYPO3
 * @subpackage t3lib
 */
class t3lib_tree_SortedNodeCollection extends t3lib_tree_NodeCollection {
    /**
     * Checks if a specific node is inside the collection
     *
     * @param t3lib_tree_Node $node
     * @return boolean
     */
    public function contains(t3lib_tree_Node $node) {
        return $this->offsetOf($node) !== -1;
    }

    /**
     * Returns the offset key of given node
     *
     * @param t3lib_tree_Node $node
     * @return int
     */
    protected function offsetOf(t3lib_tree_Node $node) {
        return $this->binarySearch($node, 0, $this->count() - 1);
    }

    /**
     * Binary search that returns the offset of a given node
     *
     * @param t3lib_tree_Node $node
     * @param int $start
     * @param int $end
     * @return int
     */
    protected function binarySearch(t3lib_tree_Node $node, $start, $end) {
        if ((!$start && ($end - $start) >= 2) || ($end - $start) > 2) {
            $divider = ceil(($end - $start) / 2);
            if ($this->offsetGet($divider)->equals($node)) {
                return $divider;
            } elseif ($this->offsetGet($divider)->compareTo($node) > 0) {
                return $this->binarySearch($node, $start, $divider - 1);
            } else {
                return $this->binarySearch($node, $divider + 1, $end);
            }
        } else {
            if ($this->offsetGet($start)->equals($node)) {
                return $start;
            } elseif ($this->offsetGet($end)->equals($node)) {
                return $end;
            } else {
                return -1;
            }
        }
    }

    /**
     * Normalizes the array by reordering the keys
     *
     * @return void
     */
    protected function normalize() {
        $nodes = array();
        foreach ($this as $node) {
            $nodes[] = $node;
        }
        $this->exchangeArray($nodes);
    }

    /**
     * Adds a node to the internal list in a sorted approach
     *
     * @param t3lib_tree_Node $node
     * @return void
     */
    public function append(t3lib_tree_Node $node) {
        parent::append($node);
        $this->asort();
        $this->normalize();
    }

}
?>