<?php
/**
 * Created by PhpStorm.
 * User: stanley-king
 * Date: 2016/10/20
 * Time: 下午7:02
 */

namespace search;

use algorithm;

class word_segment
{
    const special_character = array(' ','“','”','Ⅰ','、','。','「','」','【','】','！','＆','（','）','，','：','’','┊', '╭','╮','╯','╰','▔','▽','　','《','》','の','＊','８','；','？','°');

    static function mb_str_split( $string )
    {
        $val =  preg_match_all('/./u', $string,$datas);
        if($val === false) {
            return false;
        }
        else {
            return $datas[0];
        }
    }

    static private function non_english($word)
    {
        $ar = str_split($word);
        return count($ar) == 1 ? true : false;
    }

    static public function filter($keywords)
    {
        $words = [];
        $keywords = self::mb_str_split(mb_strtolower($keywords));
        if($keywords === false) return $words;

        $word = '';
        foreach ($keywords as $ch)
        {
            $ret = word_segment::filter_word($ch);
            if($ret == false)
            { //抛弃——》之前的词当成单独的词
                if(!empty($word)) {
                    $words[] = $word;
                    $word = '';
                }
            }
            elseif($ret === 1) { //可见的ASCII字，可连接上
                $word .= $ch;
            }
            else
            { //独立的中文单词
                if(!empty($word)) {
                    $words[] = $word;
                    $word = '';
                }
                $words[] = $ch;
            }
        }

        if(!empty($word)) {
            $words[] = $word;
        }

        return $words;
    }

    static private function filter_word($word)
    {
        if($word == '') return false;

        if(self::non_english($word))
        {
            if(ctype_space($word)) {
                return false;
            }
            elseif (ctype_graph($word)) {
                return 1;
            }
            elseif (ctype_cntrl($word)) {
                return false;
            }
            else {
                return false;
            }
        }
        else
        {
            if(in_array($word,self::special_character)) {
                return false;
            }
            else {
                return 2;
            }
        }
    }
}

//通过字找到key，通过key找到词
class indexer
{
    protected $mDict;
    protected $mContainer;

    public function __construct()
    {
        $this->mDict = array();
        $this->mContainer = array();
    }

    public function parase($words,$value)
    {
        $fwords = word_segment::filter($words);
        foreach ($fwords as $word) {
            $this->add($word,$value);
        }
        $this->mContainer[$value] = $words;
    }

    protected function add($key,$value)
    {
        if(isset($this->mDict[$key]))
        {
            $datas = &$this->mDict[$key];
            if(algorithm::binary_search($datas,$value) == false) {
                $pos = algorithm::lower_bonud($datas,$value);
                algorithm::array_insert($datas,$pos,$value);
            }
        }
        else {
            $this->mDict[$key] = array($value);
        }
    }
    public function find($key)
    {
        if(isset($this->mDict[$key])) {
            return $this->mDict[$key];
        } else {
            return array();
        }
    }

    public function name($val)
    {
        if(isset($this->mContainer[$val])) {
            return $this->mContainer[$val];
        } else {
            return false;
        }
    }
}

class one_multi
{
    private $mContainer;
    public function __construct()
    {
        $this->mContainer = array();
    }

    public function add($key,$val)
    {
        if(isset($this->mContainer[$key]))
        {
            $values = &$this->mContainer[$key];
            if(algorithm::binary_search($values,$val) == false) {
                $pos = algorithm::lower_bonud($values,$val);
                algorithm::array_insert($values,$pos,$val);
            }
        }
        else {
            $this->mContainer[$key] = [];
            $this->mContainer[$key][] = $val;
        }
    }

    public function get($key)
    {
        if(isset($this->mContainer[$key]))
        {
            return $this->mContainer[$key];
        }
        else {
            return array();
        }
    }
    public function values() {
        return $this->mContainer;
    }
    public function reset($values) {
        $this->mContainer = $values;
    }
}

class one_one
{
    private $mContainer;
    public function __construct()
    {
        $this->mContainer = array();
    }

    public function add($key,$val)
    {
        $this->mContainer[$key] = $val;
    }

    public function get($key)
    {
        if(isset($this->mContainer[$key]))
        {
            return $this->mContainer[$key];
        }
        else {
            return false;
        }
    }
}

class parent_sub_tree
{
    private $mTree;

    public function __construct()
    {
        $this->mTree = [];
    }
    public function add($id,$pid)
    {
        $id = intval($id);
        $pid = intval($pid);

        if(isset($this->mTree[$pid]) == false) {
            $this->mTree[$pid] = [];
            $this->mTree[$pid]['pid'] = 0;
            $this->mTree[$pid]['subids'] = [];
            $this->mTree[$pid]['subids'][] = $id;
        } else {
            $sub_ids = &$this->mTree[$pid]['subids'];
            $this->add_sub($sub_ids,$id);
        }

        if(isset($this->mTree[$id]) == false) {
            $this->mTree[$id] = [];
            $this->mTree[$id]['pid'] = $pid;
            $this->mTree[$id]['subids'] = [];
        }
    }

    private function add_sub(&$values,$val)
    {
        if(algorithm::binary_search($values,$val) == false) {
            $pos = algorithm::lower_bonud($values,$val);
            algorithm::array_insert($values,$pos,$val);
        }
    }

    public function is_parent($hot)
    {
        if (isset($this->mTree[$hot]) == false) {
            return false;
        }

        return (count($this->mTree[$hot]['subids']) > 0);
    }
    public function subs($hot)
    {
        if (isset($this->mTree[$hot]) == false) {
            return array();
        }

        return $this->mTree[$hot]['subids'];
    }
}

class valtokey
{
    private $mKeys;
    private $mValMap;
    private $mKeyMap;
    private $mCount;

    public function __construct()
    {
        $this->mKeys   = [];
        $this->mValMap = [];
        $this->mKeyMap = [];
        $this->mCount = 0;
    }

    public function add($key,$val)
    {
        if(algorithm::binary_search($this->mKeyMap,$key) == true) {
            return false;
        } else {
            $pos = algorithm::lower_bonud($this->mKeyMap,$key);
            algorithm::array_insert($this->mKeyMap,$pos,$key);
        }

        $pos = algorithm::lower_bonud($this->mValMap,$val);
        algorithm::array_insert($this->mValMap,$pos,$val);
        algorithm::array_insert($this->mKeys,$pos,$key);

        return true;
    }
    public function finish() {
        $this->mKeyMap = [];
        $this->mCount = count($this->mKeys);
    }

    public function findless($val,$start,$length)
    {
        $pos = algorithm::upper_bound($this->mValMap,$val);
        if($pos < 0) {
            return false;
        }
        elseif ($pos >= $this->mCount) {
            $pos = $this->mCount - 1;
        }
        else {
            $data = $this->mValMap[$pos];
            if($data > $val) {
                $pos -= 1;
            }
        }

        $pos = $pos - $start;
        if($pos < 0) {
            return false;
        }

        $result = [];
        for ($i = $pos; $i >= 0 && $length > 0; $i--,$length--) {
            $result[] = $this->mKeys[$i];
        }

        return array('total' => $pos + 1,'cids' => $result);
    }

    public function findall($val)
    {
        $pos = algorithm::upper_bound($this->mValMap,$val);
        if($pos < 0) {
            return false;
        }
        elseif ($pos >= $this->mCount) {
            $pos = $this->mCount - 1;
        }
        else {
            $data = $this->mValMap[$pos];
            if($data > $val) {
                $pos -= 1;
            }
        }

        $result = [];
        for ($i = $pos; $i >= 0; $i--) {
            $result[] = $this->mKeys[$i];
        }

        return $result;
    }
}