Homework 1 for CS 340

PerfectSkipList.java

import java.util.*;
public class PerfectSkipList {

    private class Node {
        int key;
        Node[] next;

        private Node(int k, int size) {
            key = k;
            next = new Node[size]; //Items are initialized to null by Java
        }

    }

    private Node head;
    private int height;

    public boolean find(int key){
        Node temp = head;
        for(int activeHeight = height-1; activeHeight >= 0; activeHeight--){
            while(temp.next[activeHeight] != null && temp.next[activeHeight].key < key) temp = temp.next[activeHeight];
            if(temp.next[activeHeight] != null && temp.next[activeHeight].key == key) return true;
        }
        return false;
    }

    public void printList(){
        for(int i=height-1; i>=0; i--) {
            for (Node temp = head.next[i]; temp != null; temp = temp.next[i]) System.out.print(temp.key + " ");
            System.out.println();
        }
    }

    public PerfectSkipList(int[] keys, int numKeys){
        height = log2(numKeys)+1;

        // Create a sentinel
        head = new Node(Integer.MIN_VALUE, height);

        Node temp = head;
        for(int i=0; i<numKeys; i++){
            temp.next[0] = new Node(keys[i], height);
            temp = temp.next[0];
        }

        // Traverses the array of lists
        for(int i=1; i<height; i++) {
            temp = head.next[i-1];
            Node temp2 = head;
            int x=0;

            // Traverses the list of the lower layer and
            // decides whether or not to add it to the
            // higher list
            while (temp != null) {
                if (x % 2 != 0) {
                    temp2.next[i] = temp;
                    temp2 = temp2.next[i];
                }
                temp = temp.next[i-1];
                x++;
            }

        }
    }

    private int log2(int bits) {
        //PRE: bits >= 0
        //Implementation taken from StackOverflow
        //https://stackoverflow.com/questions/3305059/
        //how-do-you-calculate-log-base-2-in-java-for-integers
        //returns floor(log(bits))
        int log = 0;
        if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
        if( bits >= 256 ) { bits >>>= 8; log += 8; }
        if( bits >= 16 ) { bits >>>= 4; log += 4; }
        if( bits >= 4 ) { bits >>>= 2; log += 2; }
        return log + ( bits >>> 1 );
    }

    public static void main(String[] args){
        int[] list = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        PerfectSkipList skipList = new PerfectSkipList(list, list.length);
        skipList.printList();
        System.out.println("Found 62: " + skipList.find(62) + "\n");


        list = new int[] {20, 30, 50, 70, 90, 100};
        skipList = new PerfectSkipList(list, list.length);
        skipList.printList();
        System.out.println("Found 70: " + skipList.find(70)+ "\n");

        list = new int[] {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100};
        skipList = new PerfectSkipList(list, list.length);
        skipList.printList();
        System.out.println("Found 55: " + skipList.find(55) + "\n");

        list = new int[] {1};
        skipList = new PerfectSkipList(list, list.length);
        skipList.printList();
        System.out.println("Found 1: " + skipList.find(1) + "\n");

        list = new int[]{0, 2, 4};
        skipList = new PerfectSkipList(list, list.length);
        skipList.printList();
        System.out.println("Found 3: " + skipList.find(3) + "\n");

        list = new int[]{1, 2};
        skipList = new PerfectSkipList(list, list.length);
        skipList.printList();
        System.out.println("Found 2: " + skipList.find(2) + "\n");

        list = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
        skipList = new PerfectSkipList(list, list.length);
        skipList.printList();
        System.out.println("Found 12: " + skipList.find(12) + "\n");

        list = new int[1027];
        for(int i=0; i<list.length; i++) list[i] = i*2;
        skipList = new PerfectSkipList(list, list.length);
        skipList.printList();
        System.out.println("Found 550: " + skipList.find(550));
        System.out.println("Found 613: " + skipList.find(613));
        System.out.println("Found 220: " + skipList.find(220));
        System.out.println("Found 186: " + skipList.find(186));
        System.out.println("Found 788: " + skipList.find(788));

    }
}