package L2;

import java.util.Random;

public class SkipList<Object extends Comparable<Object>, U>
{
	private Element _head;
	private Random _random;
	private long _size;
	private double _p;
	
	private class Element
	{
		public Object key;
		public Object value;
		public long level;
		public Element next;
		public Element down;
		
		public Element(Object key, Object value, long level, Element next, Element down)
		{
			this.key = key;
			this.value = value;
			this.level = level;
			this.next = next;
			this.down = down;
		}
	}
	
	
	
	private long generujlevel()
	{
		long level = 0;
		while (level <= _size && _random.nextDouble() < _p) {
			level++;
		}
		
		return level;
	}
	//konstrukor ustawiajacy nasza liste jako pusta
	public SkipList()
	{
		
		_head = new Element(null, null, 0, null, null);
		_random = new Random();
		_size = 0;
		_p = 0.5;
	}
	
	public void add(Object key, Object value)
	{
		long level = generujlevel();
		if (level > _head.level) {
			_head = new Element(null, null, level, null, _head);
		}
		
		Element cur = _head;
		Element last = null;
		
		while (cur != null) {
			if (cur.next == null || cur.next.key.compareTo(key) > 0) {
				if (level >= cur.level) {
					Element n = new Element(key, value, cur.level, cur.next, null);
					if (last != null) {
						last.down = n;
					}
					
					cur.next = n;
					last = n;
				}
				
				cur = cur.down;
				continue;
				//jak juz mamy dany element to go nadpisujemy
			} else if (cur.next.key.equals(key)) {
				cur.next.value = value;
				return;
			}
			
			cur = cur.next;
		}
		
		_size++;
	}
	
	
	
	
	
	public Object get(Object key)
	{
		Element cur = _head;
		while (cur != null) {
			if (cur.next == null || cur.next.key.compareTo(key) > 0) {
				cur = cur.down;
				continue;
			} else if (cur.next.key.equals(key)) {
				return cur.next.value;
			}
			
			cur = cur.next;
		}
		
		return null;
	}
}