简易跳跃表 - php代码

php代码 /** * 数据链表节点 * / class skipListNode { public $d = null; public $mem = null; public $pre = null; public $level = 0; public $levelNode = array(); } /** * 层链表节点 * / class skipListLevelNode { public $node = null; public $next = null; public $cur_level = 0; public $next_step = 0; } /** * 跳跃表 */ class skipList { private $max_level = 1; private $head = null; private $hash_table = array(); public function __construct($max_level = 10) { $this->max_level = (int)$max_level; $skipListNode = new skipListNode(); $skipListNode->level = $max_level; for ($i=0; $i < $this->max_level; $i++) { $skipListLevelNode = new skipListLevelNode(); $skipListLevelNode->cur_level = $i; $skipListLevelNode->node = $skipListNode; $skipListNode->levelNode[] = $skipListLevelNode; } $this->head = $skipListNode; } public function add(string $mem, $d) { $mem = strval($mem); $d = floatval($d); if (!$this->update($mem, $d)) { # 新加 $listNode = $this->getNodePos($d); $nextNode = isset($listNode->levelNode[0]->next) ? $listNode->levelNode[0]->next->node : null; $skipListNode = new skipListNode(); $skipListNode->pre = $listNode; $skipListNode->mem = $mem; $skipListNode->d = $d; $skipListNode->level = $this->node_level(); if ($nextNode) $nextNode->pre = $skipListNode; $pre_next_step = $next_step = 1; for ($i=0; $i < $this->max_level; $i++) { while ($i >= $listNode->level && $listNode->pre!==null) { $listNode = $listNode->pre; $pre_next_step++; } if (empty($listNode)) { break; } if (!empty($nextNode) && $i >= $nextNode->level) { $nextNode = isset($nextNode->levelNode[0]->next) ? $nextNode->levelNode[0]->next->node : null; if ($nextNode) $next_step++; } if ($i < $skipListNode->level) { $skipListLevelNode = new skipListLevelNode(); $skipListLevelNode->node = $skipListNode; $skipListLevelNode->cur_level = $i; $skipListLevelNode->next = null; $skipListLevelNode->next_step = $next_step; if ($nextNode && isset($nextNode->levelNode[$i]) && !empty($nextNode->levelNode[$i])) { $skipListLevelNode->next = $nextNode->levelNode[$i]; } $skipListNode->levelNode[] = $skipListLevelNode; $listNode->levelNode[$i]->next = $skipListLevelNode; $listNode->levelNode[$i]->next_step = $pre_next_step; }else{ $listNode->levelNode[$i]->next_step++ ; } } $this->hash_table[$mem] = $skipListNode; } return true; } public function update(string $mem, $d) { $mem = strval($mem); $d = floatval($d); $node = $this->getNodePosByMem($mem); if ($node) { if ($node->d === $d) { return true; } if ($this->del($mem)) { $this->add($mem, $d); return true; } return false; } return false; } public function del(string $mem) { $mem = strval($mem); $node = $this->getNodePosByMem($mem); if ($node) { $preNode = $node->pre; if (isset($node->levelNode[0]->next->node)) { $node->levelNode[0]->next->node->pre = $preNode; } for ($i=0; $i < $this->max_level; $i++) { while($i >= $preNode->level && $preNode->pre!==null) { $preNode = $preNode->pre; } if ($preNode->levelNode[$i]->next === null) { continue; } if ($i < $node->level) { $preNode->levelNode[$i]->next = $node->levelNode[$i]->next; $preNode->levelNode[$i]->next_step += $node->levelNode[$i]->next_step; $node->levelNode[$i] = null; } $preNode->levelNode[$i]->next_step--; } $node = null; $this->delNodePosByMem($mem); return true; } return false; } public function getByScore($s) { $s = intval($s); $node = $this->head; for ($i=$this->max_level-1; $i >= 0 && $s>0; $i--) { if (!isset($node->levelNode[$i]) || empty($node->levelNode[$i]->next) || $node->levelNode[$i]->next_step > $s) { continue; } do { if ($node->levelNode[$i]->next_step === $s) { $s=0; }else{ $s -= $node->levelNode[$i]->next_step; } $node = $node->levelNode[$i]->next->node; if ($s<=0) break; } while (isset($node->levelNode[$i]->next->node) && $node->levelNode[$i]->next->node && $node->levelNode[$i]->next_step <= $s); } return isset($node->mem) && $s<=0 ? $node->mem : null; } public function getRank($s, $e) { $s = intval($s); $e = intval($e); $ret = array(); if ($s > $e || $s <1 ) { return $ret; } $node = $this->head; $step = 0; for ($i=$this->max_level; $i >= 0; $i--) { while(isset($node->levelNode[$i]->next) && $node->levelNode[$i]->next && ($step + $node->levelNode[$i]->next_step) <= $s) { $step += $node->levelNode[$i]->next_step; $node = $node->levelNode[$i]->next->node; } if ($step === $s) { break; } } if ($step === $s) { do { if ($step > $e || empty($node)) { break; } $ret[] = $node->mem; $step += $node->levelNode[0]->next_step; $node = isset($node->levelNode[0]->next->node) ? $node->levelNode[0]->next->node : null; } while (true); } return $ret; } public function getScore($mem) { $mem = strval($mem); $node = $this->getNodePosByMem($mem); if ($node) { $step = 0; $preNode = $node; do { $preNode = $preNode->pre; if ($preNode === null) { break; } if ($preNode->level < $node->level) { continue; } $step += $preNode->levelNode[$node->level-1]->next_step; } while (true); return $step; } return null; } private function getNodePosByMem($mem) { return isset($this->hash_table[$mem]) ? $this->hash_table[$mem] : null; } private function delNodePosByMem($mem) { unset($this->hash_table[$mem]); } private function getNodePos($d) { $listNode = $this->head; $i = $listNode->level-1; do{ $node = isset($listNode->levelNode[$i]->next->node) ? $listNode->levelNode[$i]->next->node : null; if ($i>0) { if (empty($node)) { $i--; continue; } }else{ if (empty($node)) { break; } } if ($node->d > $d) { if ($i === 0) { break; }else{ while ($i>0 && $node->levelNode[$i]->next_step === $node->levelNode[--$i]->next_step) {}; } }elseif ($node->d === $d) { break; }else{ $listNode = $node; continue; } }while ($i>=0); return $listNode; } private function node_level() { $level = 1; do{ if (mt_rand(0,10000) > 1999) break; }while (++$level && $level < $this->max_level); if ($level === $this->max_level) { $skipListLevelNode = new skipListLevelNode(); $skipListLevelNode->cur_level = $level-1; $skipListLevelNode->node = $this->head; $this->head->levelNode[] = $skipListLevelNode; $this->max_level++; } return $level; } public function print_list() { $node = $this->head; do { if (!isset($node->levelNode[0]->next) || empty($node->levelNode[0]->next)) { break; } $node = $node->levelNode[0]->next->node; var_dump($node->mem . " = " . $node->d, $node->level, isset($node->pre) ? $node->pre->mem:'null'); for ($i=0; $i < $node->level; $i++) { echo "+++ {$i} +++"; var_dump($node->levelNode[$i]->next_step, isset($node->levelNode[$i]->next)); } echo "-----------------------
"; } while (1); echo "-----------head------------
"; foreach ($this->head->levelNode as $key => $n) { if (isset($n->next)) { $node = $n->next->node; var_dump($node->level . ":" . $node->mem . " = " . $node->d, $n->next_step); } } } }