CMSC 433 - Project 1 - C++ exercise - due Feb. 15, 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 support 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.
• It should be expandable. Assigning to a non-negative index that hasn't been allocated yet should transparently reallocate the representation.
• Write operator[] so that it returns an ElementRef, to avoid the dangling reference 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 currently allocated space, the operation 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 (e.g. ~as43301/bin/submit 1 *.h *.c)

Web Accessibility