skiplist

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;
    }
}