Starting with the SkipListList class, implement a FastDefaultList class that represents an infinite list with indices 0, 1, 2, 3, ...., . When we 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 the same as list methods. Each of these operations should run in O(log n)time. The size() method is already implemented for you, it returns the largest value you can store in an int.

Note: Two provided files for this question are the DumbDefaultList and the FastDefaultList classes. DumbDefaultList implements the correct behaviour but does so very inefficiently, you can use this to test the correctness of your implementation. The FastDefaultList is mostly just a copy of the SkipListList class. Your task is to modify this to solve this problem.

Tip: Work slowly. There is not much code you have to change in the FastDefaultList.java file, but it is delicate. Checkpoint your work often and test carefullly as you go.

-------------------------------------------------------------------------------------------------------------------------------------

protected Node findPred(int i) {

// Hint: It's not enough to know u, you also need the value j,

// maybe return the pair (u,j)

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 u;

}

public T get(int i) {

// Hint: this is too restrictive any non-negative i is allowed

if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();

// Hint: Are you sure findPred(i).next is the node you're looking for?

return findPred(i).next[0].x;

}

public T set(int i, T x) {

// Hint: this is too restrictive any non-negative i is allowed

if (i < 0 || i > n-1) throw new IndexOutOfBoundsException();

// Hint: Are you sure findPred(i).next is the node you're looking for?

// If it's not, you'd better add a new node, maybe get everything

// else working and come back to this later.

Node u = findPred(i).next[0];

T y = u.x;

u.x = x;

return y;

}

-------------------------------------------------------------------------------------

So what should I modify in those method?