CMSC 433 - Project 1 - C++ exercise

Due Feb 15th, 6pm

Part 1 - IntList

Write IntList, linked-list of integers class. It should support the following functionality:

class IntList {
    int pop();
    const boolean empty();
    const int top();
    void push(int);
    int & operator[](int); 
    void appendCopyAtEnd(const IntList &)
    }

• It also needs things such as copy constructor, destructor, operator=, ...
• All lists should be distinct: changes to one list should never cause changes to been seen in other lists.
• Operator= should reuse existing list cells storage when possible.
• L[0] should return the same result as L.top()
• Don't worry about the possible problems caused by operator[] returning a dangling reference.
• Don't worry about error conditions (top called on an empty list, operator[] being called with out of bound index). We should throw an exception, but we haven't covered those yet.

Part 2 - IntEArray

Write IntEArray, an array of integers class. It support the following functionality:

• All arrays should be distinct: changes to one array should never cause changes to been seen in other arrays.
• Conceptually, the IntEArray is an infinite length array initialized to all zeros.
• It should be copy-on-write (the copy-constructor and operator= should be constant-time). To do this, there will need to be a separate representation that is shared and ref-counted.
• It should be expandable. Referencing a non-negative index which hasn't been allocated yet will transparently reallocate the representation.
• Write operator[] so that it returns an ElementRef, to avoid the dangling-ref problem.
• operator() acts similar to operator[], except:
  • It returns an rval, not an lval. It cannot be used to update the array (it is a const function).
  • If the index to operator() is outside the allocated space, it returns 0.
• The function startingFrom(int offset) returns a new IntEArray where element 0 of the new array is the same as element offset of the array startingFrom was invoked on. This function should use copy-on-write.
• Asking for an unallocated array element using operator() shouldn't allocate more space (e.g., a(1000000000) shouldn't blow out your memory, while a[1000000000] might).
• Having 100 copies of an identical, unmodified large array shouldn't take much more space than having one copy.

Submission details

Headers should be in files named IntList.h and IntEArray.h. You should submit those files and any other C++ files that need to be compiled as part of your project. Do not submit any files containing a main function.

Submission will be handled using the submit program.