-
-
Save asterwolf/c919ff7fba7e998d0b45 to your computer and use it in GitHub Desktop.
/* | |
* ArrayList is a container class that grows as needed. | |
* Need to add destructor, copy constructor, and, later, | |
* operator= | |
* | |
* @author: Diego Diaz | |
* Course: COMP B12 | |
* Created on: Feb 23, 2015 | |
* Source File: ArrayList.h | |
*/ | |
#ifndef ARRAYLIST_H_ | |
#define ARRAYLIST_H_ | |
#include <iostream> // Normally wouldn't do this, but needed to support output in destructor | |
template<typename T> | |
class ArrayList { | |
private: | |
T *array; | |
int length; | |
int capacity; | |
/* | |
* Change capacity to that specified by newCapacity. | |
* @param newCapacity the new capacity | |
*/ | |
void changeCapacityTo(int newCapacity){ | |
T *newArray = new T[newCapacity]; | |
this -> capacity = newCapacity; | |
if(newCapacity < this ->length) | |
length = newCapacity; | |
for(int i = 0; i < length; ++i) | |
newArray[i] = array[i]; | |
delete[] array; | |
array = newArray; | |
} | |
public: | |
/* | |
* Initialize list with a capacity of 8 | |
*/ | |
ArrayList(){ | |
capacity = 8; | |
length = 0; | |
array = new T[capacity]; | |
} | |
/* | |
* Copy constructor | |
*/ | |
ArrayList (const ArrayList& other){ | |
capacity = other.length; | |
length = other.length; | |
array = new T[capacity]; | |
for(int i = 0; i < other.length; i++) | |
array[i] = other.array[i]; | |
} | |
virtual ~ArrayList() { | |
std::cout << "Destructing ArrayList at " << array << std::endl; | |
delete [] array; | |
array = NULL; | |
} | |
/* | |
* Adds item to list, at index, shifting items as necessary and increasing | |
* capacity of list as necessary. If capacity must increase, it must always | |
* be a power of 2. Note that if index is beyond capacity, capacity must be | |
* increased to allow adding the item at that index. Also, length should | |
* reflect the HIGHEST index (plus one, naturally) at which an item is | |
* stored, even if lower-indexed slots contain undefined values. | |
* | |
* @param item item to add to list | |
*/ | |
void add(int index, T item){ | |
if(index < length && index >= 0){ | |
length++; | |
if(capacity < length){ | |
changeCapacityTo(capacity * 2); | |
} | |
for(int i = length - 1; i > index; i--){ | |
array[i] = array[i - 1]; | |
} | |
array[index] = item; | |
} | |
else if (index == length){ | |
length++; | |
if(capacity < length){ | |
changeCapacityTo(capacity * 2); | |
} | |
array[index] = item; | |
} | |
// else{ | |
// length = index + 1; | |
// if(capacity < length){ | |
// int newCapacity = capacity; | |
// while (newCapacity < length){ | |
// newCapacity *= 2; | |
// } | |
// changeCapacityTo(newCapacity); | |
// } | |
// array[index] = item; | |
// } | |
} | |
/* | |
* Add item to end of list | |
* @param item item to add to list | |
*/ | |
void add(T item){ | |
if(length >= capacity) | |
changeCapacityTo(2 * capacity); | |
array[length++] = item; | |
} | |
/* | |
* Return item at index. For now, we assume index is legal. | |
* Later we will throw an exception when index is illegal. | |
* @param index index of item to return | |
* @return item at index | |
*/ | |
T get(int index) const { | |
return array[index]; | |
} | |
/* | |
* Return capacity | |
* @return capacity | |
*/ | |
int getCapacity() const { | |
return capacity; | |
} | |
/* | |
* Return current length | |
* @return current length | |
*/ | |
int getLength() const { | |
return length; | |
} | |
T& operator[](int index){ | |
if(index >= length) { | |
std::ostringstream err; | |
err << "Index [" << index << "] Out of range"; | |
throw std::out_of_range(err.str()); | |
} | |
return array[index]; | |
} | |
}; | |
#endif /* ARRAYLIST_H_ */ |
/* | |
* Tester program for ArrayListTemplate. | |
* @author: Diego Diaz | |
* Course: COMP B12 | |
* Created on: Mar 10, 2015 | |
* Source File: testArrayListTemplate.cpp | |
*/ | |
#include <iostream> | |
#include "ArrayListTemplate.h" | |
using namespace std; | |
template<typename T> | |
void printArrayList(ArrayList<T> arrayList) { | |
for(int i = 0; i < arrayList.getLength(); ++i) { | |
T item = arrayList.get(i); | |
cout << i << ":" << item << endl; | |
} | |
} | |
template<typename T> | |
void testArrayListTemplate(T startItem) { | |
ArrayList<T> arrayList; | |
const int NUM_ITEMS = 10; | |
T itemToAdd = startItem; | |
for(int i = 0; i < NUM_ITEMS; ++i) { | |
arrayList.add(itemToAdd); | |
itemToAdd += startItem; | |
} | |
try { | |
arrayList[NUM_ITEMS / 2] = startItem; | |
arrayList[NUM_ITEMS + 1] = arrayList[NUM_ITEMS + 1] | |
+ arrayList[NUM_ITEMS + 1]; | |
} | |
catch (out_of_range error) { | |
// use cout so that error output synched with stdout | |
cout << error.what() << endl; | |
} | |
printArrayList(arrayList); | |
} | |
int main(int argc, char *argv[]) { | |
testArrayListTemplate(2); | |
testArrayListTemplate(string("ab")); | |
} |
Revision 2: Changed Item and *array (the two variables made type T in this template). Created the function to overload the subscript operator([]) with returning type (still lack's it's body that should complete the try and catch out of range boxes in the tester). Commented out if index > length (which by default would be the else) in our add function with two parameters. The if statement that checks if index < length also checks if (or should've been checking *a mistake I just discovered) that index is also greater than 0.
Revision 3: Changed if (index < length && index > 0).
Revision 4: Changed the if statement once again, as 0 is a usable index and is not out of range. If (index < length && index >= 0)
Look at you, adding comments to your commits! You're going to be a Git pro in no time!
</proud>
Revision 5: A few more mistakes were found. Didn't completely change all the ints to type T where it was necessary, but I believe I have them all now. The overloading subscript operator is still not complete, but I believe it shall work once it's complete.
Revision 6: The subscript operator is now complete and the code works as it should. Now with a few comments by pathawks, there might more work to be done to polish it up.
@pathawks: I think some people in class might be peaking around. Hopefully my comments will help them understand what I did.
Revision 1: Took lab 4's ArrayList.cpp and ArrayList.h file and merged them to create a template file called ArrayListTemplate.h