SkipListNode -- 跳跃表节点

package skiplist;

@Data
public class SkipListNode<T> {

    //索引层数组
    private SkipListLevel[] level;

    //后退所指向的节点
    private SkipListNode<T> backword;

    //分值
    private double score;

    //成员对象
    private T obj;

    //初始化头节点时用到的构造方法
    SkipListNode(T obj) {
        this.obj = obj;
        //redis要求索引层数最高是32层
        this.level = new SkipListLevel[32];
        initLevel(this.level, 32);
        this.score = 0;
    }

     //根据"层高"和"分值"新建一个节点，在插入节点时使用
    SkipListNode(T obj, int levelHeight, double score) {
        this.obj = obj;
        this.level = new SkipListLevel[levelHeight];
        initLevel(this.level, levelHeight);
        this.score = score;
    }

    //初始化每一层
    private void initLevel(SkipListLevel[] level, int height) {
        for (int i = 0; i < height; ++i) {
            level[i] = new SkipListLevel();
        }
    }
}

package skiplist;

import lombok.Data;

@Data
public class SkipListLevel {
    //指向下一个节点
    private SkipListNode forward;

    /**
     * 跨度，当前节点和下一个节点间的距离
     * 如果下一个节点为null，当前节点为头节点或尾节点时，跨度为0，否则跨度不为0
     */
    private int span;
}

package skiplist;

import java.util.Random;

public class SkipList <T extends Comparable<? super T>> {
    //头节点
    private SkipListNode<T> header;
    //尾结点
    private SkipListNode<T> tail;

    //跳跃表中节点的数量，（头节点不算）
    private int length;

    //当前跳跃表最高的层数，（头节点不算，头节点的索引层高固定为32）
    private int maxLevel;

    //构造方法初始化SkipList
    public SkipList() {
        //初始化头节点
        SkipListNode<T> node = new SkipListNode<>(null);
        this.header = node;
        this.tail = node;
        this.length = 0;
        this.maxLevel = 0;
    }
}

 /**
 * 获取随机的层高度
 **/
private int getRandomHeight() {
    Random random = new Random();
    int i = 1;
    for (; i < 32; ++i) {
        if (random.nextInt(4) == 0) {
            break;
        }
    }
    return i;
}

public SkipListNode slInsert(double score, T obj) {
    int i;
    //存放待修改的节点
    SkipListNode[] update = new SkipListNode[32];
    //存放待修改的节点到头节点的距离
    int[] rank = new int[32];
    //当前节点
    SkipListNode node = header;
    //新插入节点的索引层高度
    int level = getRandomHeight();

    //从上往下,从左往右先找到要修改的节点
    for(i = maxLevel -1 ;i>=0;--i){
        //如果左侧已经数好距离，则直接使用，减少数距离的次数
        rank[i] = i==(maxLevel-1)? 0 : rank[i+1];
        SkipListNode<T> next = node.getLevel()[i].getForward();
        //向右一个一个比较，找到最后一个比待插入节点分数小的节点，作为修改节点
        while(next!=null && (score> next.getScore() || (score == next.getScore() && next.getObj().compareTo(obj) <0))){
            rank[i]+= node.getLevel()[i].getSpan();
            node = next;
            next = node.getLevel()[i].getForward();
        }
        update[i] = node;
    }

    //找到新插入节点索引层高比原先节点索引层 高的部分要修改的节点
    if(level > maxLevel){
        for(i =maxLevel;i<level;++i){
            //比原先高的层前一个节点，一定是头节点，span=0，forward = null
            rank[i] = 0;
            update[i] = header;
            //写入头节点到尾结点真实的距离
            update[i].getLevel()[i].setSpan(length);
        }
        maxLevel = level;
    }

    SkipListNode<T> target = new SkipListNode<>(obj, level, score);
    for (i = 0; i < level; i++) {
        //新插入左侧节点的下一个节点就是新插入节点的下一个节点
        target.getLevel()[i].setForward(update[i].getLevel()[i].getForward());
        //新插入节点变成前一个节点的下一个节点
        update[i].getLevel()[i].setForward(target);
        target.getLevel()[i].setSpan(update[i].getLevel()[i].getSpan() - (rank[0] - rank[i]));
        update[i].getLevel()[i].setSpan((rank[0] - rank[i]) + 1);
    }
    for (i = level; i < maxLevel; i++) {
        update[i].getLevel()[i].setSpan(update[i].getLevel()[i].getSpan() + 1);
    }
    //处理后置节点
    target.setBackword(update[0] == header ? null : update[0]);
    if(target.getLevel()[0].getForward()!=null){
        target.getLevel()[0].getForward().setBackword(target);
    }else{
        tail = target;
    }
    length++;
    return target;
}

public static void main(String[] args) {
    SkipList<String> list= init();
    sout(list);
    list.slInsert2(4.0,"第4个元素");
    System.out.println("____________________________________________________________________________________________________________________________________");
    sout(list);
}

public static SkipList init(){
    SkipList<String> list = new SkipList<>();
    list.slInsert2(1.0,"第1个元素");
    list.slInsert2(2.0,"第2个元素");
    list.slInsert2(3.0,"第3个元素");
    list.slInsert2(5.0,"第5个元素");
    list.slInsert2(6.0,"第6个元素");
    list.slInsert2(7.0,"第7个元素");
    return list;
}

public static void sout(SkipList list){
    for(int y=10 ;y>=0;y--) {
        SkipListNode node = list.header;
        for (; ; node = node.getLevel()[0].getForward()) {
            if (node != null) {
                if (y >= node.getLevel().length) {
                    System.out.print("                  |");
                } else {
                    System.out.print("  " + node.getScore() + ",span="+node.getLevel()[y].getSpan()+","+(node.getLevel()[y].getForward()==null?null:"next")+" |");
                }
            } else {
                System.out.println();
                break;
            }
        }
    }

}