| Evelinas |
07-28-2012 02:07 AM |
Skip List
Hello, I am creating a skip list in java. right now I am working on the insertion method. I did the insertion and the search to insert, but the part where I do the coin flip to build the tower, the tower does not grow. Can someone probably take a look at what I have and point out my problem please.
Code:
// SkipList.java
import java.awt.List;
import java.util.ArrayList;
import java.util.Random;
public class SkipList
{
Random generator = new Random();
// int level;
private PositiveInfinityNode posInf;
private NegativeInfinityNode negInf;
//private NormalNode node;
private Node head;
private Node tail;
// The constructor initializes a newly-constructed SkipList to be empty.
// Remember that an empty skip list actually contains one level, numbered
// "level 0," that contains only the special -INF and +INF nodes.
public SkipList()
{
negInf = new NegativeInfinityNode();
posInf = new PositiveInfinityNode();
posInf.prev = negInf;
negInf.next = posInf;
head = negInf;
tail = posInf;
}
// insert() takes a key/value pair as parameters, adding the key and its
// associated value into the skip list. If the key already exists in the
// skip list, a DuplicateKeyException is thrown.
public void insert(int key, ArrayList<Integer> value)
throws DuplicateKeyException
{
NormalNode node = new NormalNode(key, value);
if(negInf == head)
{
node.next = posInf;
posInf.prev = node;
node.prev = negInf;
negInf.next = node;
negInf.above = new NegativeInfinityNode();
head = negInf.above;
posInf.above = new PositiveInfinityNode();
tail = posInf.above;
head.next = tail;
tail.prev = head;
// negInf.next = posInf.above;
// posInf.above = negInf.above;
negInf.above = head;
head.below= negInf;
posInf.above = tail;
tail.below= posInf;
buildUp(node);
return;
}
Node temp = null;
while(true)
{
if(temp instanceof NegativeInfinityNode)
{
temp = temp.next;
temp = temp.below;
temp = null;
continue;
}
else if(temp instanceof PositiveInfinityNode)
{
temp = temp.prev;
temp = temp.below;
temp = null;
continue;
}
else if(temp.getKey() == key)
{
throw new DuplicateKeyException();
}
else if(temp.getKey() > key)
{
temp = temp.below;
continue;
}
else if(temp.getKey() < key)
{
temp = temp.next;
continue;
}
}
}
private void buildUp(Node node) {
while(true)
{
int temp = generator.nextInt(2);
if(temp == 1)
{
node.above = new NormalNode(node.getKey(), node.getValue());
node = node.above;
node.next = tail;
tail.prev = node;
node.prev = head;
head.next = node;
head.above = new NegativeInfinityNode();
tail.above = new PositiveInfinityNode();
head = head.above;
tail = tail.above;
head.next = tail;
tail.prev = head;
}
else
{
break;
}
}
}
public String toString()
{
StringBuilder builder = new StringBuilder();
Node temp;
Node tempStart;
temp = head;
tempStart = head;
while(true)
{
builder.append(temp + " -> ");
temp = temp.next;
if(temp == null)
{
if(tempStart.below == null) break;
temp = tempStart.below;
tempStart = temp;
builder.append("\n");
}
}
return builder.substring(0);
}
// lookup() takes a key as a parameter and returns the value associated
// with that key in the skip list. If the key does not appear in the skip
// list, a NoSuchKeyException is thrown.
public ArrayList<Integer> lookup(int key) throws NoSuchKeyException
{
return null;
}
// remove() takes a key as a parameter and removes it, along with its
// associated value, from the skip list. If the key does not appear in
// the skip list, a NoSuchKeyException is thrown.
public void remove(int key)
throws NoSuchKeyException
{
}
// update() takes a key and a new value as parameters. If the key appears
// in the skip list already, its value is replaced with the new value; if
// not, a NoSuchKeyException is thrown instead.
public void update(int key, ArrayList<Integer> newValue)
throws NoSuchKeyException
{
}
// There are three kinds of nodes in a skip list. All kinds of nodes
// have references that point to the node before, after, above, and
// below that node. But, other than that, there are differences between
// the three kinds of nodes:
//
// * Normal nodes contain a key/value pair. Comparing a search key
// to a normal node is done by comparing the search key to the key
// in the node, so that a node containing the key 50 will be
// considered to come before the search key 60, while a node
// containing the key 70 will be considered to come after the
// search key 40.
//
// * -INF nodes do not contain a key/value pair, so it is impossible
// to ask such a node for its key or its value. Comparing a search
// key to a -INF node always has the same result: a -INF node is
// considered to come before any search key.
//
// * +INF nodes are somewhat like -INF nodes, in that they contain no
// key/value pair. However, when comparing a search key to a +INF
// node, the +INF node is always considered to come after any search
// key.
//
// I've provided a hierarchy of node classes that address these issues.
// The abstract class Node forms the basis for all kinds of nodes,
// containing the four references (prev, next, above, and below). The
// class NormalNode represents a normal node, with a key/value pair.
// The abstract class InfinityNode forms the basis for the two kinds of
// infinity nodes (-INF and +INF). Finally, the classes NegativeInfinityNode
// and PositiveInfinityNode represent -INF and +INF nodes, respectively.
private abstract static class Node
{
public Node prev;
public Node next;
public Node above;
public Node below;
// Because nodes are interdependent, it's easier for all four references
// to be set to null at construction time, then filled in one by one
// afterward.
public Node()
{
prev = null;
next = null;
above = null;
below = null;
}
// getKey() returns the key stored in this node. If the node is an
// infinity node, an UnsupportedOperationException is thrown, since you
// can't get a key out of an infinity node.
public abstract int getKey();
// getValue() returns the value stored in this node. If the node is
// an infinity node, an UnsupportedOperationException is thrown, since
// you can't get a value out of an infinity node.
public abstract ArrayList<Integer> getValue();
// setValue() changes the value stored in this node. If the node is
// an infinity node, an UnsupportedOperationException is thrown, since
// you can't get a value out of an infinity node.
public abstract void setValue(ArrayList<Integer> value);
// compareToSearchKey() compares the key in this node to the given
// search key, returning a negative number if this key is less than
// the search key, zero if they are equal, and a positive number if
// this key is greater than the search key. This method is handy
// for implementing several parts of the skip list without having to
// specially handle the cases of -INF and +INF (since polymorphism
// will cause the appropriate version of compareToSearchKey() to be
// called automatically).
public abstract int compareToSearchKey(int searchKey);
}
private abstract static class InfinityNode
extends Node
{
public InfinityNode()
{
}
public int getKey()
{
throw new UnsupportedOperationException();
}
public ArrayList<Integer> getValue()
{
throw new UnsupportedOperationException();
}
public void setValue(ArrayList<Integer> value)
{
throw new UnsupportedOperationException();
}
public abstract int compareToSearchKey(int searchKey);
}
private static class NegativeInfinityNode
extends InfinityNode
{
public NegativeInfinityNode()
{
}
public int compareToSearchKey(int searchKey)
{
return -1;
}
public String toString() {
return "[NEG]";
}
}
private static class PositiveInfinityNode
extends InfinityNode
{
public PositiveInfinityNode()
{
}
public int compareToSearchKey(int searchKey)
{
return 1;
}
public String toString() {
return "[POS]";
}
}
private static class NormalNode
extends Node
{
private int key;
private ArrayList<Integer> value;
public NormalNode(int key, ArrayList<Integer> value)
{
this.key = key;
this.value = value;
}
public int getKey()
{
return key;
}
public ArrayList<Integer> getValue()
{
return value;
}
public void setValue(ArrayList<Integer> value)
{
this.value = value;
}
public int compareToSearchKey(int searchKey)
{
if (key < searchKey)
{
return -1;
}
else if (key > searchKey)
{
return 1;
}
else
{
return 0;
}
}
public String toString() {
return " " + key + " ";
}
}
}
|
