public class SkipList {

	public static final double PROB = 0.5;
	public static final int MAX_LEVEL = 5;
	public static final int MIN_KEY = 0;	//only keys between 0-1000 are valid for prac
	public static final int MAX_KEY = 1000;

	//private int listLevel; //leaving out for now
	private SkipNode headerNode, nilNode;

	public SkipList() {
	    //current list level
		//listLevel = 0;

		//create header/tail nodes
	    headerNode = new SkipNode(MAX_LEVEL, MIN_KEY-1, 0);
	    nilNode = new SkipNode(MAX_LEVEL, MAX_KEY+1, 0);

	    //connect header to tail
	    for (int i=0; i<MAX_LEVEL; i++) {
	      headerNode.forward[i] = nilNode;
	    }
	  }

	public SkipNode search(int searchKey) {
		SkipNode currentNode = headerNode;
		int currentLevel = currentNode.getLevel();

		if(searchKey > MAX_KEY) {
			System.out.println("Key cannot be greater than "+MAX_KEY);
			return null;
		}

		while(currentLevel != 0) { 										//while current != bottom of stack
			currentLevel--; 												//current = current.down
			while(searchKey >= currentNode.forward[currentLevel].getKey()) { 	//while(key >= current.right.key)
				currentNode = currentNode.forward[currentLevel]; 				//current = current.right
				System.out.println("checking key "+currentNode.getKey());
			}
		}
		//return (currentNode.key == searchKey); //returns True if the key is found
		if(currentNode.getKey() == searchKey)
			return currentNode;
		else
			return null;
	}

	public void delete(int searchKey) {
		if(searchKey > MAX_KEY)
			System.out.println("Key cannot be greater than "+MAX_KEY);
		else {
			SkipNode currentNode = headerNode;
			int currentLevel = currentNode.getLevel();
			SkipNode record[] = new SkipNode[MAX_LEVEL];
			//record[currentLevel] = currentNode;

			while(currentLevel != 0) { //searches for node
				currentLevel--;
				//record[currentLevel] = currentNode;
				while(searchKey >= currentNode.forward[currentLevel].getKey()) {
					currentNode = currentNode.forward[currentLevel]; 	//change node
					//record[currentLevel] = currentNode; //update record
					//System.out.println("checking key "+currentNode.getKey());
				}
				record[currentLevel] = currentNode;
			}
			if(currentNode.getKey() == searchKey) { //updates pointers
				for(int i=0; i<record.length; i++) {
					System.out.println(record[i].toString());
				}
				for(int i=0; i<MAX_LEVEL; i++) {
					//System.out.println("for i= "+i); //test
					//System.out.println(currentNode.toString());
					//System.out.println("Comparing "+record[i].forward[i].getKey()+" to "+currentNode.getKey());
					if(record[i].forward[i].getKey() == currentNode.getKey()) { //doesnt pass !!!! record[i].forward[i] == currentNode
						//System.out.println("record["+i+"].forward["+i+"] == currentNode"); //test
						//System.out.println();
						record[i].forward[i] = currentNode.forward[i];
					}
				}
				currentNode = null; //removes node after severing links
			} else {
				System.out.println("Key does not exist.");
			}
		}
	}

	public void insert(int maxLevel, int newKey, int newValue) {
		if(newKey > MAX_KEY)
			System.out.println("Key cannot be greater than "+MAX_KEY);
		else {
			SkipNode currentNode = headerNode;
			int currentLevel = currentNode.getLevel();
			SkipNode record[] = new SkipNode[MAX_LEVEL];
			//record[currentLevel] = currentNode;

			while(currentLevel != 0) { //searches for node
				currentLevel--;
				record[currentLevel] = currentNode;
				while(newKey >= currentNode.forward[currentLevel].getKey()) {
					currentNode = currentNode.forward[currentLevel]; 	//change node
					record[currentLevel] = currentNode; //update record
				}
			}
			if(currentNode.getKey() == newKey) {
				System.out.println("Key already exists, updating value.");
				currentNode.setValue(newValue); //if node with same key exists, update value
			} else {
				SkipNode newNode = new SkipNode(maxLevel, newKey, newValue); //creates new node, links bottom level
				newNode.forward[0] = currentNode.forward[0];
				currentNode.forward[0] = newNode;

				int levelCount = 1;
				while(Math.random() <= PROB && levelCount < MAX_LEVEL) { //randomly decides level and updates pointers
					newNode.forward[levelCount] = record[levelCount].forward[levelCount]; //updates forward
					record[levelCount].forward[levelCount] = newNode; //updates back
					levelCount++;
				}
			}
		}
	}

	public void printList() {
		SkipNode currentNode = this.headerNode;
		while(currentNode.getKey() != MAX_KEY+1) {
			System.out.println(currentNode.toString()); //prints header and all inserted nodes
			currentNode = currentNode.forward[0];
		}
		System.out.println(currentNode.toString()); //prints tail/nil node
	}

	////////////////////

	public SkipNode getHeaderNode() {
		return headerNode;
	}

	public SkipNode getNilNode() {
		return nilNode;
	}
}