<?php

/*

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 *

 * This software consists of voluntary contributions made by many individuals

 * and is licensed under the LGPL. For more information, see

 * <http://www.doctrine-project.org>.

 */

namespace Doctrine\ORM\Internal;

/**

 * The CommitOrderCalculator is used by the UnitOfWork to sort out the

 * correct order in which changes to entities need to be persisted.

 *

 * @since 2.0

 * @author Roman Borschel <roman@code-factory.org> 

 */

class CommitOrderCalculator

{

    const NOT_VISITED = 1;

    const IN_PROGRESS = 2;

    const VISITED = 3;

    private $_nodeStates = array();

    private $_classes = array(); // The nodes to sort

    private $_relatedClasses = array();

    private $_sorted = array();

    /**

     * Clears the current graph.

     *

     * @return void

     */

    public function clear()

    {

        $this->_classes =

        $this->_relatedClasses = array();

    }

    /**

     * Gets a valid commit order for all current nodes.

     * 

     * Uses a depth-first search (DFS) to traverse the graph.

     * The desired topological sorting is the reverse postorder of these searches.

     *

     * @return array The list of ordered classes.

     */

    public function getCommitOrder()

    {

        // Check whether we need to do anything. 0 or 1 node is easy.

        $nodeCount = count($this->_classes);

        if ($nodeCount == 0) {

            return array();

        } else if ($nodeCount == 1) {

            return array_values($this->_classes);

        }

        // Init

        foreach ($this->_classes as $node) {

            $this->_nodeStates[$node->name] = self::NOT_VISITED;

        }

        // Go

        foreach ($this->_classes as $node) {

            if ($this->_nodeStates[$node->name] == self::NOT_VISITED) {

                $this->_visitNode($node);

            }

        }

        $sorted = array_reverse($this->_sorted);

        $this->_sorted = $this->_nodeStates = array();

        return $sorted;

    }

    private function _visitNode($node)

    {

        $this->_nodeStates[$node->name] = self::IN_PROGRESS;

        if (isset($this->_relatedClasses[$node->name])) {

            foreach ($this->_relatedClasses[$node->name] as $relatedNode) {

                if ($this->_nodeStates[$relatedNode->name] == self::NOT_VISITED) {

                    $this->_visitNode($relatedNode);

                }

            }

        }

        $this->_nodeStates[$node->name] = self::VISITED;

        $this->_sorted[] = $node;

    }

    public function addDependency($fromClass, $toClass)

    {

        $this->_relatedClasses[$fromClass->name][] = $toClass;

    }

    public function hasClass($className)

    {

        return isset($this->_classes[$className]);

    }

    public function addClass($class)

    {

        $this->_classes[$class->name] = $class;

    }

}