package skipList;

/**
 *
 * @author Thiago Goncalves Monteiro Viturino - 21011127
 *
 */

public class SkipListImpl implements SkipList {

	protected SkipNode root;
	protected int level;
	protected int maxLevel;
	protected double probability = 0.5;
	private static SkipNode NIL;
	private final int PROXIMO = 0;

	public SkipListImpl(int maxLevel, boolean useMaxLevelAsInitialLevel) {
		if(useMaxLevelAsInitialLevel){
			this.level = maxLevel;
		}else{
			this.level = 1;
		}
		this.maxLevel = maxLevel;
		root = new SkipNode(Integer.MIN_VALUE, maxLevel, new Integer(Integer.MIN_VALUE));
		NIL = new SkipNode(Integer.MAX_VALUE, 1, new Integer(Integer.MAX_VALUE));
		connectRootToNil();
	}

	/**
	 * Faz a ligacao inicial entre os apontadores forward do ROOT e o no NIL
	 * Caso teseja-se usando o level do ROOT igual ao maxLevel esse metodo deve
	 * conectar todos os forward. Senao o ROOT eh inicializaco com
	 * level=1 e o metodo deve conectar apenas o forward[0].
	 */
	private void connectRootToNil(){
		if (this.level == this.maxLevel){
			for (int index = 0; index < this.maxLevel; index++){
				this.root.forward[index] = NIL;
			}
		}
		else{
			this.root.forward[PROXIMO] = NIL;
		}
	}

	/**
	 * Metodo que gera uma altura aleatoria para ser atribuida a um novo no no metodo
	 * insert(int,Object)
	 */
	private int randomLevel(){
		int randomLevel = 1;
		double random = Math.random();
		while(Math.random() <= probability && randomLevel < maxLevel){
			randomLevel = randomLevel + 1;
		}
		return randomLevel;
	}

	@Override
	public void insert(int key, Object newValue) {
		SkipNode[] update = new SkipNode[this.maxLevel];
		SkipNode noAtual = this.root;
		for (int index = (this.level - 1); index >= 0; index--){
			while (noAtual.forward[index].key < key){
				noAtual = noAtual.forward[index];
			}
			update[index] = noAtual;
		}
		noAtual = noAtual.forward[PROXIMO];
		if (noAtual.key == key){
			noAtual.satteliteData = newValue;
		}
		else{
			int valor = randomLevel();
			if (valor > this.level && valor < this.maxLevel){
				for (int index = valor; index >= this.level; index--){
					update[index] = this.root;
				}
				this.level = valor;
			}
			SkipNode novoNo = new SkipNode(key, valor, newValue);
			for (int index = 0; index < valor; index++){
				novoNo.forward[index] = update[index].forward[index];
				update[index].forward[index] = novoNo;
			}
		}
	}

	@Override
	public void insert(int key, Object newValue, int height) {
		SkipNode[] update = new SkipNode[this.maxLevel];
		SkipNode noAtual = this.root;
		for (int index = (this.level - 1); index >= 0; index--){
			while (noAtual.forward[index].key < key){
				noAtual = noAtual.forward[index];
			}
			update[index] = noAtual;
		}
		noAtual = noAtual.forward[PROXIMO];
		if (noAtual.key == key){
			noAtual.satteliteData = newValue;
		}
		else{
			if (height > this.level && height < this.maxLevel){
				for (int index = height; index >= this.level; index--){
					update[index] = this.root;
				}
				this.level = height;
			}
			SkipNode novoNo = new SkipNode(key, height, newValue);
			for (int index = 0; index < height; index++){
				novoNo.forward[index] = update[index].forward[index];
				update[index].forward[index] = novoNo;
			}
		}
	}

	@Override
	public void remove(int key) throws RuntimeException{
		SkipNode[] update = new SkipNode[this.maxLevel];
		SkipNode noAtual = this.root;
		for (int index = level - 1; index >= 0; index--){
			while (noAtual.forward[index].key < key){
				noAtual = noAtual.forward[index];
			}
			update[index] = noAtual;
		}
		noAtual = noAtual.forward[PROXIMO];
		if (noAtual.key == key){
			for (int index = 0; index < this.level; index++){
				if (update[index].forward[index] != noAtual){
					break;
				}
				update[index].forward[index] = noAtual.forward[index];

			}
			while (this.level > 1 && this.root.forward[this.level - 1] == NIL){
				this.level--;
			}
		}else{
			throw new RuntimeException("No inexistente");
		}
	}


	@Override
	public int getHeight() {
		return this.level;
	}

	@Override
	public SkipNode search(int key) throws RuntimeException{
		SkipNode procurado = this.root;
		for (int index = level - 1; index >= 0; index--){
			while (procurado.forward[index].key < key){
				procurado = procurado.forward[index];
			}
		}
		procurado = procurado.forward[PROXIMO];
		if (procurado.key == key){
			return procurado;
		}
		throw new RuntimeException("No inexistente");
	}

	@Override
	public String printSkipList() {
		return localPrintSkipList(this.root).substring(0, localPrintSkipList(this.root).length() - 1);
	}

	private String localPrintSkipList(SkipNode no){
		String resp = "";
		if (no != null && no != NIL){
			resp += "<" + localKey(no) + "," + no.height + ">" + "(";
			for (int index = 0; index < no.forward.length; index++){
				if (no.forward[index] == null){
					if (resp.lastIndexOf(",") == resp.length() - 1){
						resp = resp.substring(0, resp.length() - 1);
					}
					resp += ") ";
					break;
				}
				else{
					if (index == 0 && no.forward[index].key == NIL.key && no != this.root){ //Se o no.forward[0] é NIL e ele nao é ROOT, todos seus apontadores estao para NIL. Logo teremos NIL aparecendo height vezes entre os parenteses.
						for (int index2 = 0; index2 < no.forward.length; index2++){
							if (index2 == no.forward.length - 1){
								resp += localKey(NIL) + ") ";
								break;
							}
							else{
								resp += localKey(NIL) + ",";
							}
						}
						break;
					}
					else if (index == no.forward.length - 1){
						resp += localKey(no.forward[index]) + ") ";
					}
					else{
						resp += localKey(no.forward[index]) + ",";
					}
				}
			}
			resp += localPrintSkipList(no.forward[PROXIMO]);
		}
		return resp;
	}

	private String localKey(SkipNode no){
		if (no.key == this.root.key){
			return "ROOT";
		}
		else if (no.key == NIL.key){
			return "NIL";
		}
		return "" + no.key;
	}

}