<?php

/**
 * Created by PhpStorm.
 * User: stanley-king
 * Date: 16/6/24
 * Time: 上午1:18
 */
function less($x,$y)
{
    return $x < $y;
}

class full_set
{
    private static $stInstance = null;
    public static function instance()
    {
        if(static::$stInstance == null) {
            static::$stInstance = new full_set();
        }
    }
}

class algorithm
{
    static function bsearch($x, $list)
    {
        $left = 0;
        $right = count($list)-1;

        while ($left <= $right) {
            $mid = ($left + $right) >> 1;

            if ($list[$mid] == $x) {
                return $mid;
            } elseif ($list[$mid] > $x) {
                $right = $mid - 1;
            } elseif ($list[$mid] < $x) {
                $left = $mid + 1;
            }
        }

        return -1;
    }

    static function binary_search($sortarr, $val, $compare = "less")
    {
        $last = count($sortarr);
        $first = self::lower_bonud($sortarr,$val,$compare);
        return $first != $last && !$compare($val, $sortarr[$first]);
    }

    //返回位置标记了一个 >= value 的值。
    static function lower_bonud($container, $val,$compare = "less")
    {
        if(!is_array($container)) {
            return -1;
        }

        $len = count($container);
        $first = 0;
        while ($len != 0)
        {
            $l2 = intval($len / 2);
            $m = $first + $l2;
            if ($compare($container[$m],$val))
            {
                $first = ++$m;
                $len -= $l2 + 1;
            }
            else {
                $len = $l2;
            }
        }
        return $first;

    }

    //返回位置标记了一个 > value 的值。
    static function upper_bound($container, $val,$compare = "less")
    {
        if (!is_array($container)) {
            return -1;
        }

        $len = count($container);
        $first = 0;
        while ($len != 0)
        {
            $l2 = intval($len / 2);
            $m = $first + $l2;
            if ($compare($val,$container[$m])) {
                $len = $l2;
            } else {
                $first = ++$m;
                $len -= $l2 + 1;
            }
        }

        return $first;
    }

    static function array_insert(&$arr,$pos,$val)
    {
        if(is_array($val)) {
            $left = array_slice($arr, 0, $pos);
            $left[] = $val;
            $right = array_slice($arr, $pos);
            $arr = array_merge($left, $right);
        }
        else {
            array_splice($arr,$pos,0,$val);
        }
    }
    static function array_erase(&$arr,$pos)
    {
        return array_splice($arr,$pos,1);
    }

    static function set_intersection($ar1, $ar2)
    {
        if($ar1 === full_set::instance()) {
            return $ar2;
        }
        if($ar2 === full_set::instance()) {
            return $ar1;
        }

        $count1 = count($ar1);
        $count2 = count($ar2);
        $pos1 = 0;
        $pos2 = 0;

        $result = [];
        while ($pos1 != $count1 && $pos2 != $count2)
        {
            $val1 = $ar1[$pos1];
            $val2 = $ar2[$pos2];

            if ($val1 < $val2) {
                ++$pos1;
            }
            elseif($val1 == $val2) {
                $result[] = $val1;
                ++$pos1;
                ++$pos2;
            }
            else {
                ++$pos2;
            }
        }
        return $result;
    }

    private static function copy($src,$pos,&$result)
    {
        $count = count($src);
        for (;$pos < $count;++$pos) {
            $result[] = $src[$pos];
        }

        return $result;
    }

    static function set_union($ar1,$ar2)
    {
        $count1 = count($ar1);
        $count2 = count($ar2);
        $pos1 = 0;
        $pos2 = 0;

        $result = [];
        for (; $pos1 != $count1; )
        {
            if ($pos2 == $count2) {
                return self::copy($ar1, $pos1, $result);
            }

            if ($ar1[$pos1] > $ar2[$pos2])
            {
                $result[] = $ar2[$pos2];
                ++$pos2;
            }
            elseif($ar1[$pos1] == $ar2[$pos2]) {
                $result[] = $ar1[$pos1];
                ++$pos1;
                ++$pos2;
            }
            else
            {
                $result[] = $ar1[$pos1];
                ++$pos1;
            }
        }

        return self::copy($ar2,$pos2,$result);
    }

    public static function not_in($src,$avables)
    {
        if(empty($src)) return array();
        if(empty($avables)) return $src;

        $src = array_unique($src);
        $avables = array_unique($avables);
        sort($src);
        sort($avables);

        $result = [];
        foreach ($src as $val)
        {
            if(algorithm::binary_search($avables,$val) == false) {
                $result[] = $val;
            }
        }

        return $result;
    }
}

class uniquer
{
    private $mContainer;
    private $mCompare;

    public function __construct($compare = 'less')
    {
        $this->mContainer = [];
        $this->mCompare = $compare;
    }

    public function add_value($val)
    {
        if(algorithm::binary_search($this->mContainer,$val,$this->mCompare) == false) {
            $pos = algorithm::lower_bonud($this->mContainer,$val,$this->mCompare);
            algorithm::array_insert($this->mContainer,$pos,$val);
            return true;
        } else {
            return false;
        }
    }
    public function add_values(array $datas)
    {
        if(!is_array($datas)) return false;
        foreach ($datas as $val) {
            $this->add_value($val);
        }
        return true;
    }
    public function remove_value($val)
    {
        if(algorithm::binary_search($this->mContainer,$val,$this->mCompare) != false) {
            $pos = algorithm::lower_bonud($this->mContainer,$val);
            algorithm::array_erase($this->mContainer,$pos);
            return true;
        } else {
            return false;
        }
    }

    public function values() {
        return $this->mContainer;
    }
    public function find($val)
    {
        return algorithm::binary_search($this->mContainer,$val,$this->mCompare);
    }

    public function range($lower,$high)
    {
        if(empty($lower)) {
            $pos_low = 0;
        }
        else {
            $pos_low = algorithm::lower_bonud($this->mContainer,$lower,$this->mCompare);
        }

        if(empty($high)) {
            $pos_high = count($this->mContainer);
        }
        else {
            $pos_high = algorithm::lower_bonud($this->mContainer,$high,$this->mCompare);
        }

        if($pos_low < 0) return [];
        return array_slice($this->mContainer, $pos_low, $pos_high - $pos_low);
    }
}

class array_helper
{
    public static function mapper($items,callable $func)
    {
        $result = [];
        foreach ($items as $item)
        {
            $key = $func($item);
            if($key === false) continue;
            $result[$key] = $item;
        }

        return $result;
    }
}