跳跃表 skiplist

import java.util.Random;
import java.util.concurrent.atomic.AtomicReference;

/**
 * 跳跃表，只完成功能30% 。基本完成节点插入，读取。
 */
public class SkipList {

    class SkipListNode {
        public int value; // 当前值
        public int key; //  key
        public LevelNode levelNodes[]; //层级
        public int maxLevel;   // 当前node的最高层级
    }

    class LevelNode {
        public int level;          //层级
        public SkipListNode preNode;  // 前节点
        public SkipListNode nextNode;  // 下一个节点
    }

    AtomicReference<SkipListNode> header, tail;
    int LIST_MAXLEVEL = 64;//定义最大层数
    float LIST_P = 0.25f;

    SkipList() {
        header = new AtomicReference<>();
        tail = new AtomicReference<>();
    }

    int randomLevel() {
        int level = 1;
        Random random = new Random();
        float a = (LIST_P * 0xFFFF);
        while ((random.nextInt(0xFFFF) & 0xFFFF) < a)
            level += 1;
        return (level < LIST_MAXLEVEL) ? level : LIST_MAXLEVEL;
    }

    public void addValue(int value) {
//       随机生成一个层数，
        int level = randomLevel();
        SkipListNode newNode = new SkipListNode();
        newNode.value = value;
        newNode.maxLevel = level;
        newNode.levelNodes = new LevelNode[level];
//       判断header 的最大层级
//        如果最大层级小于level，则直接将header指向新插入的node
        step1:
        if (header.get() == null) {
            SkipListNode h = header.get();
            boolean b = header.compareAndSet(h, newNode);
            if (!b) {
                break step1;
            }
            initLevel(newNode, 0, level);
            SkipListNode t = tail.get();
            tail.compareAndSet(t, newNode);
            return;
        }
        SkipListNode headNode = header.get();
        if (headNode.maxLevel < level) {
            int start=headNode.maxLevel-1;
            initLevel(newNode, start<0?0:start, level);
//             将新node 插入到对应的位置
            SkipListNode currentNode = header.get();
            int i = currentNode.maxLevel - 1;
            insertNode(newNode, currentNode, i);
            boolean b = header.compareAndSet(headNode, newNode);
        } else {
            SkipListNode currentNode = header.get();
            int i = level - 1;
            insertNode(newNode, currentNode, i);
            if (level == currentNode.maxLevel) {
                if (newNode.value <= currentNode.value) {
                    header.compareAndSet(headNode, newNode);
                }
            }
        }
    }

    private void initLevel(SkipListNode newNode, int startL, int endL) {
        for (int i = startL; i < endL; i++) {
            LevelNode n = new LevelNode();
            n.level = i;
            n.preNode = null;
            n.nextNode = null;
            newNode.levelNodes[i] = n;
        }
    }

    /**
     * @param newNode
     * @param currentNode
     * @param level       选择当前层插入新节点
     */
    private void insertNode(SkipListNode newNode, SkipListNode currentNode, int level) {
        step1:
        while (true) {
            if (level < 0) {
                return;
            }
            LevelNode currentLevelNode = currentNode.levelNodes[level];
            System.out.println("level="+level+",newNode="+newNode.value+",nodeLevel="
                    +newNode.maxLevel+",currentNode="+currentNode.value+",currentNodeLevel="+currentNode.maxLevel);
            if (newNode.value < currentNode.value) {
//               插入当前节点之前
                if (currentLevelNode.preNode == null) {
                    currentLevelNode.preNode = newNode;
                    LevelNode ln = new LevelNode();
                    ln.nextNode = currentNode;
                    ln.level = level;
                    ln.preNode = null;
                    newNode.levelNodes[level] = ln;
                    level--;
                    continue step1;
                } else {
//                   如果节点的前一个节点不等null
                    if (currentLevelNode.preNode.value > newNode.value) {
//                      同一层，向前扫
                        currentNode = currentLevelNode.preNode;
                        continue step1;
                    } else {
//                      插入节点中间
                        SkipListNode pre = currentLevelNode.preNode;
                        currentLevelNode.preNode = newNode;
                        pre.levelNodes[level].nextNode = newNode;
                        LevelNode n = new LevelNode();
                        n.nextNode = currentNode;
                        n.preNode = pre;
                        n.level = level;
                        newNode.levelNodes[level] = n;
                        level--;
                        continue step1;
                    }
                }
            } else {
                if (currentLevelNode.nextNode == null) {
//                   直接插入到该层的后面
                    currentLevelNode.nextNode = newNode;
                    LevelNode ln = new LevelNode();
                    ln.nextNode = null;
                    ln.level = level;
                    ln.preNode = currentNode;
                    newNode.levelNodes[level] = ln;
                    level--;
                    continue step1;
                } else {
                    SkipListNode temp = currentNode;
                    if (currentLevelNode.nextNode.value < newNode.value) {
//                      同一层继续向后扫，当前节点 为下一个节点
                        currentNode = currentLevelNode.nextNode;
                        continue step1;
                    } else {
//                      插入节点中间
                        SkipListNode nx = currentLevelNode.nextNode;
                        currentLevelNode.nextNode = newNode;
                        nx.levelNodes[level].preNode = newNode;
                        LevelNode n = new LevelNode();
                        n.nextNode = nx;
                        n.preNode = currentNode;
                        n.level = level;
                        newNode.levelNodes[level] = n;
                        level--;
                        continue step1;
                    }
                }
            }

        }
    }

    public Object get(int v) {
        SkipListNode n = header.get();
        if (n == null) {
            return null;
        }

        return getValue(v,n,n.maxLevel-1);
    }

    private Object getValue(int v, SkipListNode currentNode, int level) {
        int cnt=0;
        step:
        while (true) {
            if (level < 0) {
                return null;
            }
            cnt++;
            System.out.println("cnt="+cnt);
            if(currentNode.value==v){
                return currentNode;
            }else if(currentNode.value<v){
                LevelNode levelNode=currentNode.levelNodes[level];
                if(levelNode.nextNode==null){
                    level--;
                }else{
                    currentNode=levelNode.nextNode;
                }
                continue step;
            }else{
                LevelNode levelNode=currentNode.levelNodes[level];
                if(levelNode.preNode==null){
                    level--;
                }else{
                    currentNode=levelNode.preNode;
                }
                continue step;
            }

        }
    }


}