Skiplist - 尝试实现 get() 和 set() 方法

Question

所以我正在尝试实现一个 FastDefaultList class，它基本上是一个跳过列表，代表一个索引为 0,1,2,3,...,∞ 的无限列表。开始时，此列表中的每个值都被分配了默认值 null。否则，这个 class 的行为就像一个列表；它具有 add(i,x)、remove(i)、set(i,x) 和 get(i)，它们的行为与列表中的相同方法一样。这些操作中的每一个都应该在 O(log n) 时间内运行。我的很多 skiplist 代码来自：

https://opendatastructures.org/odsjava/4_2_SkiplistSSet_Efficient_.html

我想我大部分时间都在工作，但我正在尝试修复我的 get() 和 set() 方法。每当我尝试编译程序时，我都会收到错误消息：

错误：找不到适合 add(int,FastDefaultList.Node,int) 的方法添加（我，节点，0）；

我不确定为什么。任何帮助将不胜感激。

package comp;
import java.lang.reflect.Array;
import java.lang.IllegalStateException;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Random;


public class FastDefaultList<T> extends AbstractList<T> {
    class Node {
        T x;
        Node[] next;
        int[] length;
        @SuppressWarnings("unchecked")
        public Node(T ix, int h) {
            x = ix;
            next = (Node[])Array.newInstance(Node.class, h+1);
            length = new int[h+1];
        }
        public int height() {
            return next.length - 1;
        }
    }

    /**
     * This node sits on the left side of the skiplist
     */
    protected Node sentinel;

    /**
     * The maximum height of any element
     */
    int h;

    /**
     * The number of elements stored in the skiplist
     */
    int n;   // Hint: You don't need this anymore!

    /**
     * A source of random numbers
     */
    Random rand;


    public FastDefaultList() {
        n = 0;
        sentinel = new Node(null, 32);
        h = 0;
        rand = new Random(0);
    }


    /**
     * Represents a node/index Pair
     */
    protected class Pair {
        Node u;
        int j;

        Pair(Node u, int j) {
            this.u = u;
            this.j = j;
        }
    }

    protected Pair findPred(int i) {
        Node u = sentinel;
        int r = h;
        int j = -1;   // index of the current node in list 0
        while (r >= 0) {
            while (u.next[r] != null && j + u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            r--;
        }
        return new Pair(u, j);
    }

    public T get(int i) {

        if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
        Pair n = findPred(i);
        if(n.u.next[0] != null && n.j + n.u.length[0] == i){ return n.u.next[0].x; }
        return null;        
    }

    public T set(int i, T x) {

        if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
        Pair n = findPred(i);
        if (n.u.next[0] != null && n.j + n.u.length[0] == i) {
            Node u = n.u.next[0];
            T y = u.x;
            u.x = x;
            return y;
        }
        else{
            Node node = new Node(x, pickHeight());
            if(node.height() > h){ h = node.height(); }
            add(i, node, 0);
        }
        return null;
    }

    /**
     * Insert a new node into the skiplist
     * @return the node u that precedes v in the skiplist
     */
    protected Node add(int i, Node w) {
        Node u = sentinel;
        int k = w.height();
        int r = h;
        int j = -1; // index of u
        while (r >= 0) {
            while (u.next[r] != null && j+u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            u.length[r]++; // accounts for new node in list 0
            if (r <= k) {
                w.next[r] = u.next[r];
                u.next[r] = w;
                w.length[r] = u.length[r] - (i - j);
                u.length[r] = i - j;
            }
            r--;
        }
        n++;
        return u;
    }

    /**
     * Simulate repeatedly tossing a coin until it comes up tails.
     * Note, this code will never generate a height greater than 32
     * @return the number of coin tosses - 1
     */
    protected int pickHeight() {
        int z = rand.nextInt();
        int k = 0;
        int m = 1;
        while ((z & m) != 0) {
            k++;
            m <<= 1;
        }
        return k;
    }

    public void add(int i, T x) {
        if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
        Node w = new Node(x, pickHeight());
        if (w.height() > h)
            h = w.height();
        add(i, w);
    }

    public T remove(int i) {
        if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
        T x = null;
        Node u = sentinel;
        int r = h;
        int j = -1; // index of node u
        while (r >= 0) {
            while (u.next[r] != null && j+u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            u.length[r]--;  // for the node we are removing
            if (j + u.length[r] + 1 == i && u.next[r] != null) {
                x = u.next[r].x;
                u.length[r] += u.next[r].length[r];
                u.next[r] = u.next[r].next[r];
                if (u == sentinel && u.next[r] == null)
                    h--;
            }
            r--;
        }
        n--;
        return x;
    }


    public int size() {
        return Integer.MAX_VALUE;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
            int i = -1;
            Node u = sentinel;
            while (u.next[0] != null) {
                i += u.length[0];
                u = u.next[0];
                sb.append(" " + i + "=>" + u.x);
            }
            return sb.toString();
    }

    public static void main(String[] args) {

    }
}

Answer 1

您的添加函数接受 2 个参数

protected Node add(int i, Node w)

然而你用 3 个参数调用它 -

此处：

 if(node.height() > h){ h = node.height(); }
        add(i, node, 0);

Answer 2

您的代码和 AbstractList 都没有定义签名为 add(int,Node,int) 的方法。

尽管如此，在您的 set() 方法中调用了这样的方法：

public T set(int i, T x) {

    if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
    Pair n = findPred(i);
    if (n.u.next[0] != null && n.j + n.u.length[0] == i) {
        Node u = n.u.next[0];
        T y = u.x;
        u.x = x;
        return y;
    }
    else{
        Node node = new Node(x, pickHeight());
        if(node.height() > h){ h = node.height(); }
        /**/add(i, node, 0)/**/;
    }
    return null;
}

Skiplist - 尝试实现 get() 和 set() 方法

Skiplist - trying to implement get() and set() methods

java

list

set

time-complexity

skip-lists