Question

Please Modify TestPart2 to test the correctness and efficiency of FasterDefaultList. Thanks

Note: A DumbDefaultList class has already been implemented for you. You can use it to help test correctness of your implementation.

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

public class DumbDefaultList<T> extends AbstractList<T> {
  Map<Integer,T> map;

  public DumbDefaultList() {
    map = new HashMap<Integer,T>();
  }

  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<Integer, T> map2 = new HashMap<Integer,T>();
    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<Integer,T> e : map2.entrySet()) {
      map.put(e.getKey()+1, e.getValue());
    }
    map.put(i, x);
  }

  public T remove(int i) {
    Map<Integer, T> map2 = new HashMap<Integer,T>();
    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<Integer,T> e : map2.entrySet()) {
      map.put(e.getKey()-1, e.getValue());
    }
    return retval;
  }

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

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

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<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);
   }

   /**
    * 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<Integer>());
   }
}

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

This needs to be modified

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

public class Tester {

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

  public static void testDefaultList(List<Integer> 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());
  }

}

Answer 1

//

//Tester.java

import java.util.Random;

import java.util.List;

public class Tester {

public static boolean testPart2(List<Integer> ell) {

if(ell==null)

return false;

Random rand = new Random();

  

for(int i=0;i<1000;i++){

ell.add(i,rand.nextInt(500));

}

if(ell.isEmpty())

return false;

int ele = ell.get(4);

int ele2 = ell.remove(4);

if(ele != ele2)

return false;

for(int i=0; i<999;i++){

ell.remove(0);

}

if(!ell.isEmpty())

return false;

return true;

}

public static void testDefaultList(List<Integer> 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());

}

}