<?php
/**
 * Created by PhpStorm.
 * User: net15
 * Date: 22/03/2018
 * Time: 14:43
 */

namespace JsRoutingBundle\Classes;


use JsonSerializable;

/**
 * Class BSTGenesis
 *
 * balanced Binary Search Tree
 *
 * @package App\Euro4x4\JsRoutingBundle\Classes
 */
class BSTGenesis implements JsonSerializable
{
    /**
     * @var null|BSTNode
     */
    protected $node;


    public function __construct()
    {
    }

    /**
     * JSON representation
     *
     * @return array|mixed
     */
    public function jsonSerialize() {
        return [
            'tree' => $this->node,
        ];
    }

    /**
     * insert value without rotating the tree
     *
     * @param BSTNode $node
     * @param string $key
     * @param mixed $val
     * @return bool
     */
    private function insert(BSTNode &$node, string $key, $val){
        if($key > $node->getKey()){
            $nodeRight = $node->getRight();
            //if node exist we go deeper in the rabbit hole
            if(!is_null($nodeRight) && $nodeRight instanceof BSTNode){
                return $this->insert($nodeRight,$key,$val);
            } else {
                //then this is a leaf and create a new node
                $node->setRight(new BSTNode($key,$val,$node));
            }
        }elseif($key < $node->getKey()){
            //same for left node
            $nodeLeft = $node->getLeft();
            //if node exist we go deeper in the rabbit hole
            if(!is_null($nodeLeft) && $nodeLeft instanceof BSTNode){
                return $this->insert($nodeLeft,$key,$val);
            } else {
                //then this is a leaf and create a new node
                $node->setLeft(new BSTNode($key,$val,$node));
            }
        }
        return true;
    }

    /**
     * Balance bst
     */
    public function balance()
    {
        $list = $this->leftRootRight($this->node);
        // find the medium! Because the list is ordered
        // we can find the middle element in various ways
        $chunks = array_chunk($list, ceil(count($list) / 2));
        $mid = array_pop($chunks[0]);
        // empty the tree
        //reset
        $this->setNode(new BSTNode($mid['key'], $mid['val']));
        $this->_balance($chunks[0]);
        $this->_balance($chunks[1]);
    }

    /**
     * @param $list
     */
    private function _balance($list)
    {
        if (empty($list)) {
            return;
        }

        // split the list
        $chunks = array_chunk($list, ceil(count($list) / 2));
        $mid = array_pop($chunks[0]);

        $this->insert($this->node,$mid['key'], $mid['val']);


        $this->_balance($chunks[0]);
        if (isset($chunks[1]))
            $this->_balance($chunks[1]);
    }

    /**
     * export node to array
     *
     * @param null|BSTNode $rootNode
     * @return array
     */
    protected function leftRootRight(?BSTNode $rootNode)
    {
        if ($rootNode == null) {
            return array();
        }

        return array_merge(
            $this->leftRootRight($rootNode->getLeft()),
            array(array('key' => $rootNode->getKey(), 'val' => $rootNode->getVal())),
            $this->leftRootRight($rootNode->getRight()));
    }

    /**
     * add an individual value
     *
     * @param string $key
     * @param mixed $val
     * @param bool $autoBalance
     * @return bool
     */
    public function addElement(string $key, $val, $autoBalance = false){
        if(is_null($this->node)){
            $this->node = new BSTNode($key,$val);
            return true;
        }

        $i = $this->insert($this->node,$key,$val);
        if($i && $autoBalance)
            $this->balance();

        return $i;
    }

    /**
     * return the tree in JSON
     *
     * @return string
     */
    public function toJSON(){
        return json_encode($this->node,0,1024);
    }

    /**
     * @param BSTNode|null $node
     * @return BSTGenesis
     */
    public function setNode(?BSTNode $node): BSTGenesis
    {
        $this->node = $node;
        return $this;
    }

    /**
     * @return BSTNode|null
     */
    public function getNode(): ?BSTNode
    {
        return $this->node;
    }

    /**
     * utility
     *
     * @param $array
     * @return array
     */
    public static function kSplitArray($array){
        $ret = [0=>[],1=>[]];

        $length = count($array);
        $mid = $length/2;
        $i = 0;
        foreach($array as $k=>$v){
            if($i < $mid){
                $ret[0][$k] = $v;
            } else {
                $ret[1][$k] = $v;
            }

            $i++;
        }

        return $ret;
    }

    /**
     * @param array $arr
     * @param $keyToFind
     * @return bool|mixed
     */
    public static function searchBSTasArray(array $arr, $keyToFind){
        if($keyToFind == $arr['key']){
            return $arr['val'];
        } else if($keyToFind > $arr['key']){
            $nodeRight = $arr['right'];
            //if node exist we go deeper in the rabbit hole
            if(!is_null($nodeRight)){
                return self::searchBSTasArray($nodeRight,$keyToFind);
            }
        }elseif($keyToFind < $arr['key']){
            //same for left node
            $nodeLeft = $arr['left'];
            //if node exist we go deeper in the rabbit hole
            if(!is_null($nodeLeft)){
                return self::searchBSTasArray($nodeLeft,$keyToFind);
            }
        }

        return false;
    }
}