COMP B12 - Lab4

ArrayList.cpp

/*
*
* @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];
}

ArrayList.h

/*
 * 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_ */

testArrayList.cpp

/*
 * 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;
}

At line 38, we have a while loop. It's going to loop until our variable newCapacity is larger than the length. Right after we're calling changeCapacityTo and sending newCapacity as a parameter. It will then be doubled again? Do we know how newCapacity double the size that we need it to be?

changeCapacityTo will change the capacity of array to whatever we have sent it as a parameter. It does not double the parameter again, it will be used as is.

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!! :)