Java coding question 2: A Fast Default List

For whoever attempting this I've attached all the classes down below. I appreciate whoever take on this interesting challenge!

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.

Again, this is not a hack job. First understand how the SkipListList class works and figure out how you can modify it to do what this question asks.

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.

---------------------------------------------------------------------- The actual code is:

package comp2402a3; 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;

/** * Implements the List interface as a skiplist so that all the * standard operations take O(log n) time * * TODO: Modify this so that it creates a DefaultList, which is basically * an infinitely long list whose values start out as null * */ public class FastDefaultList extends AbstractList { 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); }

/** * Find the node that precedes list index i in the skiplist. * * @param x - the value to search for * @return the predecessor of the node at index i or the final * node if i exceeds size() - 1. */ 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; }

/** * Insert a new node into the skiplist * @param i the index of the new node * @param w the node to insert * @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) { // Hint: bounds checking again! if (i < 0 || i > n) throw new IndexOutOfBoundsException(); Node w = new Node(x, pickHeight()); if (w.height() > h) h = w.height(); add(i, w); }

public T remove(int i) { // Hint: bounds checking again! if (i < 0 || i > n-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() { // This is just here to help you a bit with debugging 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) { Tester.testDefaultList(new FastDefaultList()); } }

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

package comp2402a3;

import java.util.List; import java.util.AbstractList; import java.util.Map; import java.util.HashMap;

public class DumbDefaultList extends AbstractList { Map map;

public DumbDefaultList() { map = new HashMap(); }

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

public T get(int i) { return map.get(i); }

public T set(int i, T x) { return map.put(i, x); }

public void add(int i, T x) { Map map2 = new HashMap(); for (Integer k : map.keySet()) { if (k >= i) { map2.put(k, map.get(k)); } } for (Integer k : map2.keySet()) { map.remove(k); } for (Map.Entry e : map2.entrySet()) { map.put(e.getKey()+1, e.getValue()); } map.put(i, x); }

public T remove(int i) { Map map2 = new HashMap(); for (Integer k : map.keySet()) { if (k >= i) { map2.put(k, map.get(k)); } } for (Integer k : map2.keySet()) { map.remove(k); } T retval = map2.remove(i); for (Map.Entry e : map2.entrySet()) { map.put(e.getKey()-1, e.getValue()); } return retval; }

public static void main(String[] args) { Tester.testDefaultList(new DumbDefaultList()); } }

------------------------------------------------------------------------------------------------------------------------------ A Tester class :

package comp2402a3;

import java.util.Random; import java.util.List; import java.util.ArrayList; import java.util.Collections;

public class Tester {

// Handy for testing correctness now that we know A2Table works public static boolean tableEquals(Table t1, Table t2) { if (t1.rows() != t2.rows()) return false; if (t1.cols() != t2.cols()) return false; for (int i = 0; i < t1.rows(); i++) { for (int j = 0; j < t2.cols(); j++) { T x1 = t1.get(i, j); T x2 = t2.get(i, j); if (x1 != null && x2 == null) return false; if (x1 == null && x2 != null) return false; if (x1 != null && !x1.equals(x2)) return false; } } return true; }

public static boolean testPart1(Table t) { // put your testing code here return true; }

public static void testTable(Table tab) { long start = System.nanoTime(); boolean result = Tester.testPart1(tab); long stop = System.nanoTime(); double elapsed = (stop-start)/1e9; System.out.println("testPart1 returns " + result + " in " + elapsed + "s" + " when testing a " + tab.getClass().getName()); }

public static boolean testPart2(List ell) { // put your testing code here return true; }

public static void testDefaultList(List ell) { long start = System.nanoTime(); boolean result = Tester.testPart2(ell); long stop = System.nanoTime(); double elapsed = (stop-start)/1e9; System.out.println("testPart1 returns " + result + " in " + elapsed + "s" + " when testing a " + ell.getClass().getName()); }

}