xyzshop/helper/algorithm.php

<?php
declare(strict_types=1);

/**
 * 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();
        }
    }

    private function __clone()
    {

    }
}

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 [];
        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;
    }
}