CMSC 433 - Project 1 - C++ exercise - due Sept. 20, 6:00PM

Part 1 - IntList

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

class IntList {
    int pop();
    bool empty() const;
    int top() const;
    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 cell 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). Your program should throw an exception, but we haven't covered those yet.

Part 2 - IntEArray

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

• All arrays should be distinct: changes to one array should never cause changes to been seen in other arrays.
• Conceptually, an 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, you will have to implement a representation that is shared and reference counted.  Sharing should be on an element-by-element basis, not on the entire array representation.  This means that a write to a non-shared array element should not cause creation of a new array, while a write to a shared element causes a new array to be allocated.
• It should be expandable. Assigning to a non-negative index (i.e. using the result of operator[] as an lval) that hasn't been allocated yet should transparently reallocate the representation.
• For grading purposes, whenever the representation is allocated/reallocated, set the boolean member updated .  It's up to the driver program to reset it.
• Write operator[] so that it returns an ElementRef (see IntEArray.h), to avoid the dangling reference problem.
• If the index to operator[] used as an rval (i.e. in an expression) is outside the currently allocated space, the operation returns 0.
• The operator() function, which takes two integer arguments start and end,  returns a new IntEArray that is the subarray of the array the function was invoked on that starts at index start and ends at index end (with start <= end). This function should use copy-on-write, and conceptually any element of the new IntEArray past index end has the value zero.
• Asking for an unallocated array element using operator[] as an rval shouldn't allocate more space (e.g., using a[1000000000] in an expression shouldn't blow out your memory).
• 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 (e.g. ~as43301/bin/submit 1 *.h *.c)

Web Accessibility