Last active
August 29, 2015 14:16
-
-
Save asterwolf/9be0aebdf8ed88bb6c1a to your computer and use it in GitHub Desktop.
COMP B12 - Lab4
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* | |
* @author: Diego Diaz | |
* Course: COMP B12 | |
* Created on: Feb 23, 2015 | |
* Source File: ArrayList.cpp | |
*/ | |
#include "ArrayList.h" | |
#include <iostream> | |
#include <string> | |
using namespace std; | |
ArrayList::ArrayList (const ArrayList& other){ | |
capacity = other.length; | |
length = other.length; | |
array = new int[capacity]; | |
for(int i = 0; i < other.length; i++) | |
array[i] = other.array[i]; | |
} | |
ArrayList::ArrayList(){ | |
capacity = 8; | |
length = 0; | |
array = new int[capacity]; | |
} | |
void ArrayList::add(int index, int item){ | |
if(index < length){ | |
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; | |
} | |
} | |
void ArrayList::add(int item){ | |
if(length >= capacity) | |
changeCapacityTo(2 * capacity); | |
array[length++] = item; | |
} | |
void ArrayList::changeCapacityTo(int newCapacity){ | |
int *newArray = new int[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; | |
} | |
int ArrayList::get(int index) const { | |
return array[index]; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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 | |
class ArrayList { | |
public: | |
/* | |
* Initialize list with a capacity of 8 | |
*/ | |
ArrayList(); | |
/* | |
* Copy constructor | |
*/ | |
ArrayList(const ArrayList& other); | |
virtual ~ArrayList() { | |
std::cout << "Destructing ArrayList at " << array << std::endl; | |
delete [] array; | |
array = NULL; | |
} | |
/* | |
* Add item to end of list | |
* @param item item to add to list | |
*/ | |
void add(int item); | |
/* | |
* 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, int 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 | |
*/ | |
int get(int index) const; | |
/* | |
* Return capacity | |
* @return capacity | |
*/ | |
int getCapacity() const { | |
return capacity; | |
} | |
/* | |
* Return current length | |
* @return current length | |
*/ | |
int getLength() const { | |
return length; | |
} | |
private: | |
int *array; | |
int length; | |
int capacity; | |
/* | |
* Change capacity to that specified by newCapacity. | |
* @param newCapacity the new capacity | |
*/ | |
void changeCapacityTo(int newCapacity); | |
}; | |
#endif /* ARRAYLIST_H_ */ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Tester program for ArrayList. | |
* @author: Diego Diaz | |
* Course: COMP B12 | |
* Created on: Mar 08, 2015 | |
* Source File: testArrayList.cpp | |
*/ | |
#include <iostream> | |
#include "ArrayList.h" | |
using namespace std; | |
void verifyArrayList(ArrayList arrayList) { | |
for(int i = 0; i < 1000; ++i) { | |
int item; | |
int itemToAdd = 2 * i; | |
if((item = arrayList.get(i)) != itemToAdd) | |
cout << "OOPS - Error at index " << i << ": " << item << " should be " | |
<< itemToAdd << endl; | |
} | |
} | |
void printArrayList(ArrayList arrayList) { | |
for(int i = 0; i < arrayList.getLength(); ++i) { | |
int item = arrayList.get(i); | |
cout << i << ":" << item << endl; | |
} | |
} | |
int main(int argc, char *argv[]) { | |
ArrayList arrayList; | |
const int highIndex = 35; | |
for(int i = highIndex; i > 0; --i) { | |
int itemToAdd = 2 * i; | |
arrayList.add(1, itemToAdd); | |
} | |
arrayList.add(99); | |
printArrayList(arrayList); | |
cout << "#items = " << arrayList.getLength() << endl; | |
cout << "capacity = " << arrayList.getCapacity() << endl; | |
arrayList.add(2000, 9999); | |
cout << "#items = " << arrayList.getLength() << endl; | |
cout << "capacity = " << arrayList.getCapacity() << endl; | |
} |
Ah, for some reason I was thinking changeCapacityTo was multiplying it by 2 (on top of the other things it does inside of the function). Thanks for the help!! :)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
changeCapacityTo
will change the capacity ofarray
to whatever we have sent it as a parameter. It does not double the parameter again, it will be used as is.