JMU logo

Skip Sorted Set PA

Introduction

The objective of this assignment is to implement a contiguous implementation of a sorted set data structure. Section 1.2.4 in our textbook describes the SSet interface, which is very similar. Even though this set structure will store its members in sorted order, many of the operations will be asymptotically faster than their PA2 equivalents due to the use of the clever skip list structure.

Getting Started

First download and decompress one of the starter files:

Don't forget to download the appropriate Makefile for your platform from Piazza or the course website.

The Sorted Set ADT

For the purposes of this assignment, the sorted set interface (an abstract data type) should support the following operations:

In addition, you will need to implement standard data structure features:

For this assignment, your implementation of this set interface should store elements in a standard skip list as described in Chapter 4 of the textbook. Here is an example skip list containing seven integers:

Skip List

Please refer to the textbook or lecture slides for details on the theory and implementation of skip lists.

Definitions

As in PA2, we provide a data_t typedef in skip_set.h:



typedef 
int data_t;

We also need data type definitions for the skip set structure as well as for skip list nodes. These definitions are also in the provided skip_set.h:



typedef 
struct skip_node {
    data_t data;
    size_t height;
    
struct skip_node **next;
} skip_node_t;


typedef 
struct skip_set {
    skip_node_t *head;
    size_t max_height;
    size_t size;
} skip_set_t;

Finally, we will need an iterator type for our set. Iterators will allow us to traverse the set in a way that is independent of the underlying implementation. For the purposes of this assignment, an iterator will be a pointer to a skip list node; i.e., a skip_node_t* value. As before, the definition is in skip_set.h:



typedef skip_node_t* skip_set_iter_t;

IMPORTANT: This iterator definition is different that the one in PA2, where an interator was defined as a pointer to a data_t value. Now it will be a pointer to a skip_node_t struct. This will allow you to iterate over the skip list properly. If you wrote your Part 2 and Part 3 functions to use iterators, you should only need to make minimal modifications after you implement the iterator functions: change any iterator dereferences from


*it

(where it is an interator) to


it->data

or


(*it).data

Of course, you will also need to change function calls as follows:


array_set_begin()  =>  skip_set_begin()
array_set_end()    =>  skip_set_end()
array_set_next()   =>  skip_set_next()

WARNING: You should not modify skip_set.h! Your code (in skip_set.c) must compile against the original skip_set.hwithout errors or warnings.

Pseudocode

The textbook's pseudocode uses a stack to help re-arrange the skip list on insertion. This works but is a bit overly complicated. Here is some simpler pseudocode for inserting in a skip list:


add(x):
    if the set contains x, return
    choose new random height new_height
    if max_height < new_height:
        expand the sentinel
    w = allocate a new node of height new_height
    u = sentinel
    r = max_height - 1
    while r >= 0 do
        while u.next[r] != NULL and u.next[r].data < x do
            u = u.next[r]
        if r < new_height:
            w.next[r] = u.next[r]
            u.next[r] = w
        r = r - 1
    size = size + 1

Similarly, here is simplified pseudocode for searching in a skip list:


contains(x):
    u = sentinel
    r = max_height - 1
    while r >= 0 do
        while u.next[r] != NULL and u.next[r].data < x do
            u = u.next[r]
        r = r - 1
    return u.next[r].data == x

Some of the iteration variables used above were chosen to match the textbook and aren't terribly descriptive, so here are some alternative names:


w       new_node        (skip_node_t*)
u       cur_node        (skip_node_t*)
r       cur_height      (int)

Part 1: Basic Set Operations

The following operations should all be O(1); i.e., their running time should not depend on the number of elements in the set.

The following operations deal with adding, removing, and searching in the set, and they should all run in O(log n) time.

The following operations clear all elements from the set. Because the skip list is a linked structure, these functions should run in O(n) time.

Part 2: Iterators and Comparisons

The following operations handle iteration over a set. They should all be O(1).

The following operations handle comparisons between two sets. Because the underlying storage structure for this assignment supports O(log n) lookups, these methods should run in O(n log n) time.

Part 3: Mathematical Set Operations

The last few operations implement standard mathematical set operations. One thing that they all have in common is that they should populate a destination set with elements drawn from other sets. Thus, they all take a "dest" pointer to a set. Each function should ensure that the destination set is empty by clearing it before performing whatever operations are appropriate for that function.

The first function creates a copy of a set, and should run in O(n log n) time.

IMPORTANT: The sets should be independent after the copying! In other words, changes made to one of the sets after copying should not affect the other.

The following operations build new sets using two existing sets. Because the underlying storage structure for this assignment supports O(log n) lookups, these methods will require O(n log n) time.

Final Submission

DUE DATE: Friday, October 30, 2015 at 23:59 EDT (11:59pm)

Submit ONLY your completed skip_set.c file on Canvas using the appropriate assignment submission. Make sure the file contains a comment field at the top with your name and a statement of compliance with the JMU honor code.

Please check your code carefully and make sure that it complies with the project specification. In addition, make sure that your code adheres to general good coding style guidelines. Fix any spelling mistakes, incorrect code formatting, and inconsistent whitespace before submitting. Make sure you include any appropriate documentation.

Contact chaoaj[at]jmu.edu for more information about this page or Twitter: @chaoaj