<?php
/**
 * @desc PHP7.4 实现跳跃表
 */
//跳跃表节点
class SkipListNode
{
    public ?int $id;//节点id
    public ?string $val;//节点值
    public array $forwards;//各层级后继节点集合
    public int $level;//节点层级

    //初始化头节点
    public function __construct(int $maxLevel, $id, $val)
    {
        $this->level = $maxLevel;
        $this->id = $id;
        $this->val = $val;
        for ($i = $this->level; $i >= 0; $i--) {
            $this->forwards[$i] = null;
        }
    }
}

//跳跃表
class SkipList
{
    private float $p = 0.6;//生成层高的随机概率

    private int $maxLevel;//最高层级

    private SkipListNode $header;//跳跃表头节点

    private int  $currentMaxLevel = 0;//节点最大层数 不包含头节点

    //初始化头节点
    public function __construct(int $maxLevel = 10, $id = null, $val = null)
    {
        $this->maxLevel = $maxLevel;
        $this->header = new SkipListNode($this->maxLevel, $id, $val);
    }

    //获取随机层高
    public function getRandomLevel()
    {
        $level = 0;
        //lcg_value()生成0-1之间的伪随机数，比mt_rand()快，但是没它随机性好
        while (lcg_value() < $this->p && $level <= $this->maxLevel) {
            $level++;
        }
        return $level ?: 1;
    }

    //添加节点
    public function add(SkipListNode $node)
    {
        //初始当前节点为头结点
        $current = $this->header;
        //记录将要和新节点相邻的节点信息
        $toUpdate = [];
        if ($this->currentMaxLevel < $node->level) {
            $this->currentMaxLevel = $node->level;
        }
        //遍历链表索引，自上而下，由于是跳跃表，所以需要全量遍历
        for ($i = $node->level; $i >= 0; $i--) {
            //索引定义了 && 索引小于要插入的索引id 则更新当前节点
            while (!empty($current->forwards[$i]) && $current->forwards[$i]->id < $node->id) {
                $current = $current->forwards[$i];
            }
            //即记录的都是要插入节点的前面的某个节点
            $toUpdate[$i] = $current;//记录将要和新节点相邻的节点信息
        }
        unset($i);
        //更新要插入节点的forwards信息 和toUpdate中节点信息
        foreach ($node->forwards as $i => &$forward) {
            if (isset($toUpdate[$i]) && in_array($i, array_keys($toUpdate[$i]->forwards))) {
                $forward = $toUpdate[$i]->forwards[$i];
                $toUpdate[$i]->forwards[$i] = $node;
            } else {
                $forward = null;
            }
        }
    }

    public function foreachList()
    {
        $current = $this->header;
        $list = [];
        while ($current->forwards[0] != null) {
            $list[] = '[' . $current->forwards[0]->id . ',' . $current->forwards[0]->val . ',' . $current->forwards[0]->level . ']';
            $current = $current->forwards[0];
        }
        $list = $list ? implode('->', $list) : "空链表";
        echo "遍历跳跃表: {$list}";
        echo PHP_EOL;
    }

    public function search($id)
    {
        $count = 1;
        $current = $this->header;
        for ($i = $this->currentMaxLevel; $i >= 0; $i--) {
            while (!empty($current->forwards[$i]) && $current->forwards[$i]->id < $id) {
                $count++;
                $current = $current->forwards[$i];
            }
        }
        if (!empty($current->forwards[0]) && $current->forwards[0]->id == $id) {
            echo "查找id:{$id}: [" . $current->forwards[0]->id . "," . $current->forwards[0]->val . "," . $current->forwards[0]->level . "], 查找次数:{$count}" . PHP_EOL;
            exit;
        }
        echo"未找到id:{$id}节点信息";
    }
}

$list = new SkipList();
for ($i = 1; $i <= 15; $i++) {
    $list->add(new SkipListNode($list->getRandomLevel(), $i, $i . $i . $i));
}
$list->foreachList();

$list->search(5);