<?php

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

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)
    {
        array_splice($arr,$pos,0,$val);
    }
    static function array_erase(&$arr,$pos)
    {
        return array_splice($arr,$pos,1);
    }

    static function set_intersection($ar1, $ar2)
    {
        $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;
    }
}