<?php
namespace KommaApp\Tree;

class Tree
{
    protected $tree = ['index' => []];
    protected $nodes;

    /**
     * @param array $data
     * @return array
     */
    public function make($root, array $data)
    {
        $this->nodes = $data;
        $disable_later = array();
        //$root = $this->createRoot();
        $last_parent_rgt = null;
        foreach ($this->nodes as $key => &$node) {
            if ($node->lft > $last_parent_rgt)

                if ($this->nodeHasChildren($node)) {
                    $children = $this->findChildren($node, $key);
//            if($node->id == 294){
//                print $key;
//                var_dump($children);
//            }
                    if ($children) $this->tree[] = $children;
                } else {
                    $entity = new TreeNode((array)$node);
                    $this->tree[] = $entity;
                    $this->tree['index'][$entity->id] = $entity;
                    unset($this->nodes[$key]);
                }

            if ($last_parent_rgt = $this->nodeIsLastLeaf($node, $root)) {
                break;
                return $this->tree;
            }
        }
        return $this->tree;
    }

    /**
     * @param $entityId
     * @param $entityTree
     * @return int
     */
    public function findNodeLevel($entityId, $entityTree)
    {
        $level = 0;
        if (isset($entityTree['index']) && $index = $entityTree['index']) {
            $level++;

            // Get rid of the index
            unset($entityTree['index']);
            $entity = $index[$entityId];

            while ($entity = $entity->parent) {
                $level++;
            }
        }
        return $level;
    }

    /**
     * @param $tree
     */
    public function alphabetize($tree)
    {
        $index = $tree['index'];
        unset($tree['index']);
        $tree = $this->alphabetizeTree($tree);

        $tree['index'] = $index;
        return $tree;
    }

    /**
     * @param $children
     * @return
     */
    public function alphabetizeTree($children)
    {
        usort($children, array($this, 'compare'));
        foreach ($children as &$child) {
            if ($child->hasChildren()) {
                $child->children = $this->alphabetizeTree($child->children);
            }
        }
        return $children;
    }


    /**
     * @param $tree
     * @param $key
     * @param $value
     * @return array
     */
    public function search($tree, $key, $value)
    {
        unset($tree['index']);
        $return = array();
        foreach ($tree as $object) {
            $objVars = get_object_vars($object);
            if (isset($objVars[$key]) && $objVars[$key] == $value) {
                $return[] = $object;
            }
        }
        return $return;
    }

    /**
     * @param $a
     * @param $b
     * @return int
     */
    protected function compare($a, $b)
    {
        return strcmp(strtoupper($a->name), strtoupper($b->name));
    }


    /**
     * @param TreeNode $node
     * @param          $key
     * @param null     $parent
     * @return array
     */
    protected function findChildren($node, $key, &$parent = null)
    {
        if (!isset($node->active) || $node->active == 1) {
            $entity = new TreeNode((array)$node, $parent);
            $this->tree['index'][$entity->id] = $entity;

            unset($this->nodes[$key]);

            $start = $key + 1;
            $end = $start + count($this->nodes);

            for ($i = $start; $i < $end; $i++) {
                if (isset($this->nodes[$i])) {
                    $childNode = $this->nodes[$i];

                    $next = null;
                    if (isset($this->nodes[$i + 1])) $next = $this->nodes[$i + 1];
                    //Check if the current node belongs in an other tree
                    if ($this->belongsInOtherTree($childNode, $node, $next)) {
                        //It doesn't belong in this tree so return the entity
                        return $entity;
                    }

                    //Check if the node has children, recursive
                    if ($this->nodeHasChildren($childNode)) {
                        $children = $this->findChildren($childNode, $i, $entity);
                        //There are children so add these
                        if ($children) $entity->addChild($children);
                    } else {
                        //no childen create new treeNode
                        $childEntity = new TreeNode((array)$childNode, $entity);
                        $entity->addChild($childEntity);

                        $this->tree['index'][$childNode->id] = $childEntity;

                        unset($this->nodes[$i]);
                    }
                    //If it is the last leaf, me must return the entity
                    if ($test = $this->nodeIsLastLeaf($childNode, $node, $next)) {
                        return $entity;
                    }

                }

            }
            return $entity;
        }
    }

    /**
     * This function will check if the current node is the last leaf
     * Based on the node, the parent and the nxt_node, if present
     *
     * @param $node, current node
     * @param $parent, the parent node
     * @param $nxt_node, the next node if pressent
     * @return bool
     */
    protected function nodeIsLastLeaf($node, $parent, $nxt_node = null)
    {

        //Check if parrent right exist and node lft exist
        if (isset($parent->rgt) && $node->lft) {
            //Check if node rgt is one smaller then parent rgt (realy the last of the tree but the last can be set to inactive)
            if ($node->rgt == ($parent->rgt - 1)) {
                //End of tree return true
                return true;
            }
            //Check if next node is set and of the parent rgt is smaller than the next left, the next node doesn't belong in this tree
            elseif (isset($nxt_node) && $parent->rgt < $nxt_node->lft) {
                //End of tree return true
                return true;
            }
            //Still not the end of the tree return false
            return false;
        }
        return false;
    }

    /**
     * This function will check if the current node
     * Belongs to the parent or the nxt_node
     *
     * @param      $node , current node
     * @param      $parent , parent node
     * @param null $nxt_node , if exist the next node
     * @return bool
     */
    protected function belongsInOtherTree($node, $parent, $nxt_node = null)
    {
        //if nxt_node exist AND parent right is smaller than next_node lft AND  node rgt is bigger than parent rgt (last item of list)
        if (isset($nxt_node) && $parent->rgt < $nxt_node->lft && $node->rgt > $parent->rgt) {
            //The current node doesn't belong to this tree, return true
            return true;
        }
    }

    /**
     * This function will verify if the node has children
     * based on the lft and the rgt values of the node
     *
     * @param $node
     * @return bool
     */
    protected function nodeHasChildren($node)
    {
        //Check if node lft exist and node rgt exist
        if (isset($node->lft) && $node->rgt) {
            //return true if node lft+1 is not node rgt => there are childrenr
            return ($node->lft + 1) != $node->rgt;
        }
        return false;
    }


}