#ifndef EXLIST_H #define EXLIST_H // ********************************************************* // Header file ExList.h for an expandable list ADT using // an array-based implementation. Initially based on the // ADT list presented in chapter 3 of "Data Abstraction // and Problem Solving with C++" by Frank Carrano, 2005, // this ADT now differs from Carrano's in a number of ways. // // -- // Andrew Vardy // www.cs.mun.ca/~av // 2 May, 2006 // // Revisions: // // 1.0 - Initial revision (2/5/06) // 1.1 - Made into a template class. This required // concatenating the header and source files to avoid // complaints from the compiler. // - Removed printouts to standard output for list // expansion/contraction. // - Added prepend function to allow insertion at the // front of the list. // 1.2 - Overloaded assignment operator (26/6/06) // // ********************************************************* #include <iostream> #include <cassert> using namespace std; template <class T> class ExList { public: ExList(int initCapacity=10, int growAmount=5, int shrinkAmount=5); // Constructs an ExList with space for 'capacity' elements. See 'append' // and 'remove' for the meaning of 'growAmount' and 'shrinkAmount'. ExList(ExList& oList); // Copy constructor. ExList& operator=(ExList& oList); // Assignment operator. ~ExList(); // Destructor. // accessors: bool isEmpty() const; // Determines whether the list is empty. // Postcondition: Returns true if the list is empty; otherwise returns false. int getLength() const; // Determines the current length of the list. // Postcondition: Returns the number of items that are currently in the list. T get(int index) const; // Postcondition: // If 0 <= index < length, // result = items[index] // Else an appropriate error message is printed to the console. void printOut() const; // Postcondition: The list is printed to the console on a single line with // adjacent entries separated by a comma and a space character. // modifiers: void prepend(T newItem); // Inserts an item into the list at position 0, expanding list capacity // if necessary. // Postcondition: // length' = length + 1 // existing list contents shifted upwards by one // newItem is inserted at position 0 in the list // If length' > capacity, // capacity' = capacity + growAmount // items is expanded to allow capacity' items void append(T newItem); // Inserts an item into the list at position length, expanding list capacity // if necessary. // Postcondition: // length' = length + 1 // newItem is inserted at position length in the list // If length' > capacity, // capacity' = capacity + growAmount // items is expanded to allow capacity' items void remove(int index); // Deletes an item from the list at a given position. // Postcondition: // If 0 <= index < length, // items'[j] = items[j+1] for all index <= j < length-1 // If length-1 <= capacity-shrinkAmount AND capacity-shrinkAmount > 0 // capacity' = capacity-shrinkAmount // items is contracted to allow capacity' items // Else an appropriate error message is printed to the console. private: // Private helper method void expand(); int capacity, growAmount, shrinkAmount; int length; T* items; // Array of list items }; // // Implementation: // template <class T> ExList<T>::ExList(int initCapacity, int growAmount, int shrinkAmount) : capacity(initCapacity), growAmount(growAmount), shrinkAmount(shrinkAmount) { items = new T[capacity]; length = 0; } template <class T> ExList<T>::ExList(ExList<T> &oList) : capacity(oList.capacity), growAmount(oList.growAmount), shrinkAmount(oList.shrinkAmount), length(oList.length) { items = new T[capacity]; for (int i=0; i<length; i++) items[i] = oList.items[i]; } template <class T> ExList<T>& ExList<T>::operator=(ExList<T> &oList) { capacity = oList.capacity; growAmount = oList.growAmount; shrinkAmount = oList.shrinkAmount; length = oList.length; delete []items; items = new T[capacity]; for (int i=0; i<length; i++) items[i] = oList.items[i]; return *this; } template <class T> ExList<T>::~ExList() { delete []items; } template <class T> bool ExList<T>::isEmpty() const { return (length == 0); } template <class T> int ExList<T>::getLength() const { return length; } template <class T> T ExList<T>::get(int index) const { if (index < 0 || index >= length) { cout << "ExList: index out of range!" << endl; exit(-1); } return items[index]; } template <class T> void ExList<T>::printOut() const { for (int i=0; i<length; i++) { cout << items[i]; if (i != length-1) cout << ", "; } cout << endl; } template <class T> void ExList<T>::expand() { // We must make some new space, copy the current contents into it, and // delete the old array. capacity += growAmount; T* oldItems = items; items = new T[capacity]; for (int i=0; i<length; i++) { items[i] = oldItems[i]; } delete []oldItems; } template <class T> void ExList<T>::prepend(T newItem) { // Record some initial values of variables so that later we can check // the postcondition. int length0 = length; int capacity0 = capacity; if ((length + 1) > capacity ) expand(); // Shift all items up in the array to allow room for newItem for (int i=length-1; i!=-1; i--) items[i+1] = items[i]; items[0] = newItem; length++; // Check most of the postcondition (not checking for expansion of array // or associated printout). Written using the ternary operator to check // the "If" condition. assert( (length == length0 + 1) && (length > capacity) ? (capacity == capacity0 + growAmount) : true /*&& get(0) == newItem*/ ); } template <class T> void ExList<T>::append(T newItem) { // Record some initial values of variables so that later we can check // the postcondition. int length0 = length; int capacity0 = capacity; if ((length + 1) > capacity ) expand(); items[length] = newItem; length++; // Check most of the postcondition (not checking for expansion of array // or associated printout). Written using the ternary operator to check // the "If" condition. assert( (length == length0 + 1) && (length > capacity) ? (capacity == capacity0 + growAmount) : true /*&& get(length0) == newItem*/ ); } template <class T> void ExList<T>::remove(int index) { // Record some initial values of variables so that later we can check // the postcondition. int length0 = length; int capacity0 = capacity; if (index < 0 || index >= length) { cout << "ExList: index out of range!" << endl; exit(-1); } if (length - 1 <= capacity - shrinkAmount && capacity - shrinkAmount > 0) { // We must make some new space, copy the current contents into it // (but not the item to be removed), and delete the old array. capacity -= shrinkAmount; T* oldItems = items; items = new T[capacity]; for (int i0=0; i0<index; i0++) items[i0] = oldItems[i0]; for (int i=index; i<length - 1; i++) items[i] = oldItems[i+1]; delete []oldItems; length--; //cout << "ExList: contracting from " << (capacity + shrinkAmount) // << " to " << capacity << endl; } else { for (int i=index; i<length - 1; i++) items[i] = items[i+1]; length--; } // Check most of the postcondition (not checking for contraction of array, // removal of appropriate element, or printout). Written by transforming // the statement "If A then B" into the logical form "!A || B". assert( !(index >= 0 && index < length0) || ( !(length0-1 <= capacity0-shrinkAmount && capacity0-shrinkAmount > 0) || (capacity == capacity0-shrinkAmount) ) ); } #endif
