So I'm trying to implement a FastDefaultList class which is basically a skiplist that represents an infinite list with indices 0,1,2,3,…,∞. At the start, every value in this list is assigned the default value null. Otherwise, this class behaves just like a List; it has the add(i,x), remove(i), set(i,x), and get(i) that behave just like the same methods in a list. Each of these operations should run in O(log n) time. A lot of my skiplist code comes from:
https://opendatastructures.org/odsjava/4_2_SkiplistSSet_Efficient_.html
I think I have most of it working for the most part but I'm trying to fix my get() and set() methods. Whenever I try to compile the program I get the error:
error: no suitable method found for add(int,FastDefaultList.Node,int) add(i, node, 0);
and I'm not sure why. Any help would be appreciated.
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) {
}
}
Your add function is accepting 2 params
protected Node add(int i, Node w)
Yet you call it with 3 params -
Here:
if(node.height() > h){ h = node.height(); }
add(i, node, 0);