Task 1: Skip Lists

In Java you have been given a partially implemented skip list class and a skip list node class to use. Your task is to implement the following methods in the skip list class according to the given specication:

boolean isEmpty() This function should determine whether the skip list is empty or not. It returns true if the skip list is empty and false otherwise.

void insert(T key) This function should insert the given key in the skip list. key should be inserted in the correct position in the skip list to maintain the increasing order. key should also be added to all the levels as determined by the chooseLevel() method.

T first() This function should determine the rst key in the skip list. It returns the rst key value in the skip list.

T last() This function should determine the last key in the skip list. It returns the last key value in the skip list.

T search(T key) This function should nd the given key in the skip list. If key is found in the skip list it should return the key value and otherwise it should return null.

Only implement the methods listed above. Do not modify any of the other code that you were given for this task.

Given files:

//SkipListNode.java

public class SkipListNode {

public T key; public SkipListNode[] next;

@SuppressWarnings("unchecked") SkipListNode(T i, int n) { key = i; next = new SkipListNode[n];

for (int j = 0; j < n; j++) next[j] = null; }

}

//main.java

public class Main {

public static void firstKey(SkipList skiplist) { if (skiplist.isEmpty()) System.out.println("List is empty"); else System.out.println("First key : " + skiplist.first()); }

public static void lastKey(SkipList skiplist) { if (skiplist.isEmpty()) System.out.println("List is empty"); else System.out.println("Last key : " + skiplist.last()); }

public static void searchKey(SkipList skiplist, Integer key) { if (skiplist.isEmpty()) System.out.println("List is empty"); else { Integer result = skiplist.search(key); if (result != null) System.out.println("Found key " + result); else System.out.println("Key " + key + " not found"); } }

public static void printList(SkipList skiplist) { System.out.println(); System.out.println("Skip List Content:"); for (int i = 0; i < skiplist.maxLevel; i++) { SkipListNode node = skiplist.root[i]; System.out.print("Level " + i + ": "); while (node != null) { System.out.print(node.key + " "); node = node.next[i]; } System.out.println(); } System.out.println(); }

public static void main(String[] args) { //Practical 1 - Tuesday

SkipList skiplist = new SkipList(); skiplist.insert(8);

skiplist.insert(5);

skiplist.insert(12);

firstKey(skiplist); lastKey(skiplist);

printList(skiplist); searchKey(skiplist, 10);

skiplist.insert(10);

printList(skiplist);

searchKey(skiplist, 10); /* Expected Output: First key : 5 Last key : 12

Skip List Content: Level 0: 5 8 12 Level 1: 5 12 Level 2: 5 Level 3:

Key 10 not found

Skip List Content: Level 0: 5 8 10 12 Level 1: 5 12 Level 2: 5 Level 3:

Found key 10 */

} }

//Files to implement here

//SkipList.java

import java.util.Random;

@SuppressWarnings("unchecked") public class SkipList> {

public int maxLevel; public SkipListNode[] root; private int[] powers; private Random rd = new Random();

SkipList(int i) { maxLevel = i; root = new SkipListNode[maxLevel]; powers = new int[maxLevel]; for (int j = 0; j < i; j++) root[j] = null; choosePowers(); rd.setSeed(1230456789); }

SkipList() { this(4); }

public void choosePowers() { powers[maxLevel-1] = (2 << (maxLevel-1)) - 1; for (int i = maxLevel - 2, j = 0; i >= 0; i--, j++) powers[i] = powers[i+1] - (2 << j); }

public int chooseLevel() { int i, r = Math.abs(rd.nextInt()) % powers[maxLevel-1] + 1; for (i = 1; i < maxLevel; i++) { if(r < powers[i]) return i-1; } return i-1; }

public boolean isEmpty() { //Your code goes here }

public void insert(T key) { //Your code goes here }

public T first() { //Your code goes here }

public T last() { //Your code goes here }

public T search(T key) { //Your code goes here } }