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 "-----------------------<br/>";
} while (1);
echo "-----------head------------<br/>";
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);
}
}
}
}
有疑问加站长微信联系（非本文作者））
