package skiplist_m;

/******************************************************************************

* AbstractSortedSet                                                           *

*                                                                             *

* Extends AbstractSet and implements SortedSet, and contains stub methods     *

*                                                                             *

* View README file for information about this project.                        *

* View LICENSE file for license information.                                  *

******************************************************************************/

import java.util.*;

abstract class AbstractSortedSet<E>

    extends AbstractSet<E>

    implements SortedSet<E> {

    public E first() {

    return null;

    }

    public E last() {

    return null;

    }

    public Iterator<E> iterator() {

    return null;

    }

    public SortedSet<E> headSet(E toElement) {

    return null;

    }

    public SortedSet<E> tailSet(E fromElement) {

    return null;

    }

    public SortedSet<E> subSet(E fromElement, E toElement) {

    return null;

    }

    public Comparator<? super E> comparator() {

    return null;  // uses natural ordering

    }

}

package skiplist_m;

/******************************************************************************

* Skiplist                                                                    *

*                                                                             *

* View README file for information about this project.                        *

* View LICENSE file for license information.                                  *

******************************************************************************/

import java.util.Iterator;

public class SkipList<E extends Comparable<E>> extends AbstractSortedSet<E> {

    private SkipListNode<E> head;

    private int maxLevel;

    private int size;

    private static final double PROBABILITY = 0.5;

    public SkipList() {

        size = 0;

        maxLevel = 0;

        // a SkipListNode with value null marks the beginning

        head = new SkipListNode<E>(null);

        // null marks the end

        head.nextNodes.add(null);

        }

        public SkipListNode getHead() {

        return head;

    }

    // Adds e to the skiplist.

    // Returns false if already in skiplist, true otherwise.

    public boolean add(E e) {

        if(contains(e)) return false;

        size++;

        // random number from 0 to maxLevel+1 (inclusive)

        int level = 0;

        while (Math.random() < PROBABILITY)

            level++;

        while(level > maxLevel) { // should only happen once

            head.nextNodes.add(null);

            maxLevel++;

        }

        SkipListNode newNode = new SkipListNode<E>(e);

        SkipListNode current = head;

            do {

            current = findNext(e,current,level);

            newNode.nextNodes.add(0,current.nextNodes.get(level));

            current.nextNodes.set(level,newNode);

        } while (level-- > 0);

        return true;

    }

    // Returns the skiplist node with greatest value <= e

    private SkipListNode find(E e) {

        return find(e,head,maxLevel);

    }

    // Returns the skiplist node with greatest value <= e

    // Starts at node start and level

    private SkipListNode find(E e, SkipListNode current, int level) {

        do {

            current = findNext(e,current,level);

        } while(level-- > 0);

        return current;

    }

    // Returns the node at a given level with highest value less than e

    private SkipListNode findNext(E e, SkipListNode current, int level) {

        SkipListNode next = (SkipListNode)current.nextNodes.get(level);

        while(next != null) {

            E value = (E)next.getValue();

            if(lessThan(e,value)) // e < value

                break;

            current = next;

            next = (SkipListNode)current.nextNodes.get(level);

        }

        return current;

    }

    public int size() {

        return size;

    }

    public boolean contains(Object o) {

        E e = (E)o;

        SkipListNode node = find(e);

        return node != null &&

            node.getValue() != null &&

            equalTo((E)node.getValue(),e);

        }

        public Iterator<E> iterator() {

        return new SkipListIterator(this);

    }

/******************************************************************************

* Utility Functions                                                           *

******************************************************************************/

    private boolean lessThan(E a, E b) {

    return a.compareTo(b) < 0;

    }

    private boolean equalTo(E a, E b) {

    return a.compareTo(b) == 0;

    }

    private boolean greaterThan(E a, E b) {

    return a.compareTo(b) > 0;

    }

/******************************************************************************

* Testing                                                                     *

******************************************************************************/

    public static void main(String[] args) {

    SkipList testList = new SkipList<Integer>();

        System.out.println(testList);

    testList.add(4);

        System.out.println(testList);

    testList.add(1);

        System.out.println(testList);

        testList.add(2);

        System.out.println(testList);

    testList = new SkipList<String>();

        System.out.println(testList);

    testList.add("hello");

        System.out.println(testList);

    testList.add("beautiful");

        System.out.println(testList);

        testList.add("world");

        System.out.println(testList);

    }

    public String toString() {

        String s = "SkipList: ";

        for(Object o : this)

            s += o + ", ";

        return s.substring(0,s.length()-2);

    }

}

package skiplist_m;

/******************************************************************************

* SkipListIterator                                                            *

*                                                                             *

* View README file for information about this project.                        *

* View LICENSE file for license information.                                  *

******************************************************************************/

import java.util.*;

public class SkipListIterator<E extends Comparable<E>> implements Iterator<E> {

        SkipList<E> list;

        SkipListNode<E> current;

        public SkipListIterator(SkipList<E> list) {

        this.list = list;

        this.current = list.getHead();

    }

    public boolean hasNext() {

    return current.nextNodes.get(0) != null;

    }

    public E next() {

        current = (SkipListNode<E>)current.nextNodes.get(0);

        return (E)current.getValue();

    }

    public void remove() throws UnsupportedOperationException {

        throw new UnsupportedOperationException();

    }

}

package skiplist_m;

/******************************************************************************

 * SkipListNode                                                                *

 *                                                                             *

 * View README file for information about this project.                        *

 * View LICENSE file for license information.                                  *

 ******************************************************************************/

import java.util.*;

public class SkipListNode<E> {

    private E value;

    public List<SkipListNode<E> > nextNodes;

    public E getValue() {

        return value;

    }

    public SkipListNode(E value) {

        this.value = value;

        nextNodes = new ArrayList<SkipListNode<E> >();

    }

    public int level() {

        return nextNodes.size()-1;

    }

    public String toString() {

    return "SLN: " + value;

    }

}