skipinho

package adt.skipList;

public class SkipListImpl<T> implements SkipList<T> {

    protected SkipListNode<T> root;
    protected SkipListNode<T> NIL;

    protected int maxHeight;

    protected double PROBABILITY = 0.5;

    public SkipListImpl(int maxHeight) {
        this.maxHeight = maxHeight;
        root = new SkipListNode(Integer.MIN_VALUE, maxHeight, null);
        NIL = new SkipListNode(Integer.MAX_VALUE, maxHeight, null);
        connectRootToNil();
    }

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


    @Override
    public void insert(int key, T newValue, int height) {
        SkipListNode<T> current = this.root;

        SkipListNode<T> update[] = new SkipListNode[this.maxHeight + 1];

        for(int h = this.maxHeight-1; h >= 0; h--) {
            while(current.forward[h] != this.NIL && current.getForward(h).getKey() < key ) {
                current = current.getForward(h);
            }
            update[h] = current;
        }

        current = current.getForward(0);
        if(current.getKey() != key) {
            SkipListNode<T> node = new SkipListNode<T>(key, height, newValue);
            for(int i = 0; i < height; i++) {
                node.forward[i] = update[i].forward[i];
                update[i].forward[i] = node;
            }
        }else if(current.getKey() == key){
            System.out.println("opa");
            current = new SkipListNode(key, height, newValue);
            for(int i = 0; i < height; i++) {
                current.forward[i] = update[i].forward[i];
                update[i].forward[i] = current;
            }
        }
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public int height() {
        int ans = 0;
        SkipListNode<T> current = this.root;
        while(current != NIL) {
            ans = Math.max(ans, current.height());
            current = current.getForward(0);
        }
        return ans;
    }

    @Override
    public SkipListNode<T> search(int key) {
        SkipListNode<T> current = this.root;

        for(int h = this.maxHeight-1; h >= 0; h--) {
            while(current.forward[h] != this.NIL && current.getForward(h).getKey() < key ) {
                current = current.getForward(h);
            }
        }
        current = current.getForward(0);
        if(current.getKey() > key || current == NIL) return null;
        return current;
    }

    @Override
    public int size() {
        int sz = 0;
        SkipListNode<T> current = this.root;
        while(current != NIL) {
            sz++;
            //System.out.println(current.getValue());
            current = current.getForward(0);
        }
        --sz;
        return sz;
    }

    @Override
    public SkipListNode<T>[] toArray() {
        SkipListNode<T> arr[] = new SkipListNode[this.size()+2];
        int i = 0;
        SkipListNode<T> current = this.root;
        while(current != NIL) {
            arr[i++] = current;
            current = current.getForward(0);
        }
        arr[i] = current;
        return arr;
    }

}