PackedDynamicArray.cpp

/*
	A good collection for when you need indices not to change when modifying the collection.
	Dynamically allocates when out of space.
	Values keep their indices after a remove.
	Values that are removed are quickly replaced before moved to the back of the collection.

	Trevor Berninger - Oct 18, 2015
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

#define uint unsigned int

#ifndef LOG
	#define LOG(message) std::cout << message;
#endif

template<typename T>
class PackedDynamicArray {
private:
	std::queue<uint> emptySlots;
	uint length, capacity;
	T* array;
public:
	uint Size() { return length; }
	uint Capacity() { return capacity; }
	T& operator[](uint i) { return array[i]; }
	// for(:) support:
	T* begin() { return array; }
	T* end() { return &(array[length]); }

	PackedDynamicArray(uint initCapacity = 30) { 
		array = new T[initCapacity];
		length = 0;
		capacity = initCapacity;
	}

	~PackedDynamicArray() { if(array != nullptr) delete [] array; }

	uint Add(T value) {
		if(!emptySlots.empty()) {
			uint pos = emptySlots.front();
			array[pos] = value;
			emptySlots.pop();
			return pos;
		}
		else {
			uint pos = length;
			if(length++ == capacity) {
				ReallocateWithSize(capacity + 20);
			}
			array[pos] = value;
			return pos;
		}
	}

	bool RemoveValue(T value) {
		T* i = std::find(array, array + capacity, value);
		if(i != array + capacity) {
			RemoveAt(i - array);
			return true;
		}
		return false;
	}

	void RemoveAt(uint index) {
		if(index > capacity) {
			LOG("PDA: Attempted remove at " + std::to_string(index) + " with capacity of " + std::to_string(capacity));
			return;
		}
		array[index] = T();
		emptySlots.push(index);
	}

	void Display() {
		for(uint i = 0; i < length; i++) {
			std::cout << i << '\t' << array[i] << '\n';
		}
	}

private:
	void ReallocateWithSize(uint size) {
		T* a = new T[size];
		std::copy(array, array + capacity, a);
		capacity = size;
		delete [] array;
		array = a;
	}
};

int main()
{
	PackedDynamicArray<std::string*> v(5);
	std::string special("Hello");
	v.Add(new std::string("1 string"));
	v.Add(new std::string("2 string"));
	v.Add(&special);
	v.Add(new std::string("4 string"));
	v.Add(new std::string("5 string"));
	v.Display();
	std::cout << '\n';
	v.RemoveValue(&special);
	v.Display();
	std::cout << '\n';
	v.Add(new std::string("1 string"));
	v.Add(new std::string("2 string"));
	v.Add(new std::string("3 string"));
	v.Add(new std::string("4 string"));
	v.Add(new std::string("5 string"));
	v.Display();
	for(uint i = 0; i < v.Size(); i++) {
		delete v[i];
	}
	std::cout << '\n';
}