Programming Assignment #5

> > > > Programming Assignments > Assignment #5 - BST of Intervals

Objectives

to implement a set using balanced binary search trees

Introduction

The Integer-Set-With-Next-Excluded ADT is an ADT with the usual set operations add, remove, contains, and size, along with new operations count-intervals, which determines the minimum number of complete intervals the integers in a set can be divided into, and next-excluded, which, given an integer x returns the smallest integer greater than or equal to x that is not in the set.

Assignment

Complete the implementation of the functions in isset.h to implement the Integer-Set-With-Next-Excluded ADT using some variant of a balanced binary search tree. "Balanced" can mean "approximately balanced" or "balanced enough often enough" as long as any sequence of $k$ add, remove, contains, and/or next-excluded operations starting on an empty set takes total time $O(k \log k)$ for large enough $k$ (so the efficiency requirement will be met if each operation takes time $O(\log n)$ in the worst case or if each operation takes amortized time $O(\log n)$ where $n$ is the number of integers currently in the set). The size and count-intervals operations should take $\Theta(1)$ time.

The provided header file isset.h and your implementation file isset.c must be the only files needed to use your implementation of the ADT.

If the input is not as specified or testable preconditions to the ADT functions are violated then your program must behave gracefully – it must not crash or go into an infinite loop.

Your program and any program that uses your implementation correctly must not produce any error messages when run with valgrind --tool=memcheck --leak-check=yes -q.

If you choose to implement a splay tree, you may cast away the const qualifier where necessary to account for the logical-but-not-physical-const-ness of some of the isset functions.

We reserve the right to deduct points from submissions for violations of the following guidelines.

All source code should be easily comprehended, with adequate and consistent spacing, concise but descriptive idenitifiers, comments before long sequences of code, and enumerations and constants favored over literals.
Submissions should be modularized, with collections of related functions divided into separate files.
Each function should be documented with a comment before its declaration. The comment should include 1) a description of the parameters including any limitations on the values allowed (preconditions), and 2) a description of what the function does and/or what it returns (postconditions).
Header files should be written so that they can be #included regardless of what other files have been #included -- if a declaration is required by your header files, then #include the appropriate header file in your header file (or write a forward declaration in your header) rather than relying on your #includers to have already #included those header files before they #include yours.
Things that make sense to be declared as const should be declared as const.
There should be no warnings when your code is compiled with the -Wall and -pedantic options.

Files and Submissions

Files are available in /home/httpd/html/zoo/classes/cs223/f2017/Assignments/ISSet:

isset.h (do not change)
isset.c (an incomplete implementation of isset using an unbalanced binary search tree; can be used as a starting point for your efficient implementation)
isset_test.c
grundy.c (an application of isset; do not change, and note that this application does not fully test all of the required functions)

Submit your isset.c, the provided isset.h, isset_test.c, and a makefile that produces an executable called Test from isset_test.c.