You will write code that implements and exercises skiplists.
Hand in your code as per the instructions under Assignment 6 in Sakai. There will be zipping and naming instructions there.
For uniformity, and to aid timely grading, you must write your program with these specific structures.
/**
* COMP 410
*
* Make your class and its methods public!
*
* Your skiplist implementation will implement this interface.
*
*/
package SkipList;
/*
Interface: The skiplist will provide this collection of operations:
insert:
in: a string (the element to be stored into the skiplist)
return: boolean, return true if insert is successful, false otherwise
effect: if the string is already in the skiplist, then there is no change to
the skiplist state, and return false
if the string is not already in the skiplist, then a new skiplist node
is created, the string put into it as data, the new node is linked
into the skiplist at the proper place; size is incremented by 1,
and return a true
remove:
in: a string (the element to be taken out of the skiplist)
return: boolean, return true if the remove is successful, false otherwise
this means return false if the skiplist size is 0
effect: if the element being looked for is in the skiplist, unlink the node containing
it and return true (success); size decreases by one
if the element being looked for is not in the skiplist, return false and
make no change to the skiplist state
contains:
in: a string (the element to be seaarched for)
return: boolean, return true if the string being looked for is in the skiplist;
return false otherwise
this means return false if skiplist size is 0
effect: no change to the state of the skiplist
findMin:
in: none
return: string, the element value from the skiplist that is smallest
effect: no skiplist state change
error: is skiplist size is 0, return null
findMax:
in: none
return: string, the element value from the skiplist that is largest
effect: no skiplist state change
error: is skiplist size is 0, return null
size:
in: nothing
return: number of elements stored in the skiplist
effect: no change to skiplist state
empty:
in: nothing
return: boolean, true if the skiplist has no elements in it, true if size is 0
return false otherwise
effect: no change to skiplist state
level:
in: none
return: integer, the level of the highest node in the skiplist
effect: no change in skiplist state
error: return -1 if skiplist is empty (size is 0, only head and tail nodes are there)
getHead:
in: none
return: a skiplist node, the one that is the starter of the entire skiplist
means return a null if the skiplist is empty
effect: no change to skiplist state
*/
// ADT operations
public interface SkipList_Interface {
public boolean insert(String s);
public boolean remove(String s);
public String findMin();
public String findMax();
public boolean empty();
public boolean contains(String s);
public int size();
public int level();
public SkipList_Node getHead();
}
package SkipList;
public class SkipList_Node {
String data;
int level;
SkipList_Node[] forward;
SkipList_Node(String s, int level) {
this.data = s;
this.level = level;
this.forward = new SkipList_Node[level + 1];
}}
// --- fill in these methods ------------------------------------------
//
// at the moment, they are stubs returning false
// or some appropriate "fake" value
//
// you make them work properly
// add the meat of correct implementation logic to them
// you MAY change the signatures if you wish...
// make the take more or different parameters
// have them return different types
/*
public boolean setForward(int level, SkipList_Node forward) { return false; }
String getData() { return null; }
*/
// --- end fill in these methods --------------------------------------
// --------------------------------------------------------------------
// you may add any other methods you want to get the job done
// --------------------------------------------------------------------
}
package SkipList;
public class SkipList implements SkipList_Interface {
SkipList_Node head;
SkipList_Node tail;
int level;
int size;
static final int levelSize = 100;
double probability = 0.5;
SkipList() {
head = new SkipList_Node(null, levelSize);
tail = new SkipList_Node(null, levelSize);
for (int i = 1; i <= levelSize; i++) {
head.setForward(i, tail);
}
level = 0;
size = 0;
}
@Override
//used for testing, please leave as is
public SkipList_Node getHead() {
if (size == 0)
return null;
return head;
}
//use this when creaing a new node, please leave as is
public int randomLevel() {
int level = 1;
while (Math.random() < probability)
level++;
return level;
}
}
package SkipList;
public class SkipList_Playground {
/*
* you will test your own skiplist implementation in here
*
* we will replace this with our own when grading, and will
* do what you should do in here... create SkipList objects,
* put data into them, take data out, look for values stored
* in it, checking size and level, and looking at if they
* are all linked up correctly for a SkipList
*
*/
public static void main(String[]args){
// you should test your skiplist implementation in here
// it is up to you to test it thoroughly and make sure
// the methods behave as requested above in the interface
// do not simple depend on the oracle test we will give
// use the oracle tests as a way of checking AFTER you have done
// your own testing
// one thing you might find useful for debugging is a print skiplist method
// feel free to use the printSkipList method to verify your skiplists manually
// or write one you like better
}
public static void printSkipList(SkipList sl) {
SkipList_Node x = sl.getHead();
for (int i = 0; i < sl.size(); i++) {
System.out.print(x.forward[1].getData() + " ");
x = x.forward[1];
}
System.out.println();
}
}
package SkipList;
import gradingTools.comp410s18.assignment6.testcases.Assignment6Suite;
public class RunTests {
public static void main(String[] args){ //runs Assignment 6 oracle tests
Assignment6Suite.main(args);
}
}
In the beginning, there are only two initial nodes called head and tail and all the forward pointers of the head node point to the tail. Their string data is null and they should not be changed in any case.
When a new node is inserted, it needs to be placed between the head and tail nodes and relevant pointers should be rearranged accordingly. A right place for a newly-created node should be searched with forward pointers starting from the head node. When creating a node for insertion, it should get a level along with string data. The level should be determined by using randomLevel method provided in SkipList class, which randomly generates each level with probability 0.5. The maximum level of a node in skiplist is pre-defined as 100 in class SkipList. We expect the probability 0.5^100 is small enough to cover almost all levels generated by randomLevel method for our implementation.
For removing, the target node to be deleted should be first searched with forward pointers starting from the head node as same as insertion. Forward pointers of relevant nodes need to be adjusted correctly and the size of skiplist is decreased by one if remove succeed.