Help on applying the doubling strategy to double the size of array

[dan.gerald]

I am trying implementing a vector ADT by means of an extandable array used in circular fashion. So now I want to apply the doubling strategy to double the current size of array Wheenever the full exception happens, by using a template to make the vector work

here are my source codes with two header files and three source files, any idea i will be appreciative.

deque.h
**********************************************************
#include "vector.h"

using namespace std;

class deque
{
private:
    int qSize;
    vector *data;
public:
    deque(int size);
    ~deque();
    void insertFirst(int newData);
    void insertLast(int newData);
    void removeFirst();
    void removeLast();
    int first();
    int last();
    int size();
    bool isEmpty();
    void print();
};
**********************************************************
vector.h

using namespace std;

class vector
{
private:
    int *data;
    int vSize;
    int capacity;
    void overflow(); // handle overflow situation

public:
    vector(int s);
    int elementAtRank(int r);
    void insertAtRank(int r, int newData);
    void removeAtRank(int r);
    void replaceAtRank(int r, int newData);
    int size();
    bool isEmpty();
    ~vector();
    void print();
};
*****************************************************************
deque.cpp
#include <iostream>
#include "deque.h"

deque::deque(int size)
{
    data = new vector(size);
}

deque::~deque()
{
    delete data;
}

int deque::size()
{
    return data->size();
}

bool deque::isEmpty()
{
    return (size()==0);
}

int deque::first()
{
    return data->elementAtRank(0);
}

int deque::last()
{
    return data->elementAtRank(data->size()-1);
}

void deque::removeFirst()
{
    data->removeAtRank(0);
}

void deque::removeLast()
{
    data->removeAtRank(data->size()-1);
}

void deque::insertFirst(int newData)
{
    data->insertAtRank(0,newData);
}

void deque::insertLast(int newData)
{
    data->insertAtRank(data->size(),newData);
}

void deque::print()
{
    data->print();
}
***************************************************************
vector.cpp
#include <iostream>
#include "vector.h"

vector::vector(int s)
{
    data = new int[s];
    capacity=s;
    vSize=0;
}

vector::~vector()
{
    delete data;
}

int vector::elementAtRank(int r)
{
    if(r>=capacity || r<0)  // protect data from overflow
        return -1;
    return data[r];
}

int vector::size()
{
    return vSize;
}

bool vector::isEmpty()
{
    return (size()==0);
}

void vector::replaceAtRank(int r, int newData)
{
    if(r>=capacity || r<0)
        return;
    data[r]=newData;
}


void vector::removeAtRank(int r)
{
    if(r>=capacity || r<0 || isEmpty())
        return;
    for(int i=r; i<vSize; i++)  // shift every element to its left
        data[i]=data[i+1];
    vSize--;
}

void vector::overflow()
{
    capacity*=2;  // doubling its size
    int *newArray=new int[capacity];
    for(int i=0; i<vSize; i++)  // copy from old array to the new array
        newArray[i]=data[i];
    delete data;  // delete old data
    data = newArray;  // old data points to new array
}

void vector::insertAtRank(int r, int newData)
{
    if(vSize==capacity)  // array is full
        overflow();
    for(int i=vSize-1; i>=r; i--)  // shift every element to its right
        data[i+1] = data[i];
    data[r] = newData;  // insert new data at rank r
    vSize++;  // size increments
    //cout << r << "," << newData << "," << vSize << endl;
}

void vector::print()
{
    for(int i=0; i<vSize; i++)
        cout << data[i] << ", ";
    cout << endl;
}
*******************************************************
main cpp
#include <iostream>
#include "deque.h"

using namespace std;

int main()
{
    deque *myQueue = new deque(10);
    myQueue->insertFirst(5);
    myQueue->insertFirst(7);
    myQueue->insertLast(4);
    myQueue->insertFirst(3);
    myQueue->print();
    system("pause");
}

[deceptikon]

So...is your question how to turn these classes into templates?

[dan.gerald]

my question is how to use the template to make my vector work for different data types with the application of doubling strategy to double the current size of array in case of full exception occurance

[deceptikon]

First you need to add a template parameter list to all of your classes and functions. Then you need to make sure that all uses of vector and deque include template arguments. After that you need to replace all instances of int as your stored data type to the template parameter. Finally, because these functions are now templates, you will want to merge the .h and .cpp files for each class into just a single .h file.

This is how vector.h would look after doing all of those things:

// vector.h
#ifndef VECTOR_H
#define VECTOR_H

template <typename T>
class vector
{
private:
    T *data;
    int vSize;
    int capacity;
    void overflow(); // handle overflow situation

public:
    vector(int s);
    T elementAtRank(int r);
    void insertAtRank(int r, T newData);
    void removeAtRank(int r);
    void replaceAtRank(int r, T newData);
    int size();
    bool isEmpty();
    ~vector();
    void print();
};

template <typename T>
vector<T>::vector(int s)
{
    data = new T[s];
    capacity=s;
    vSize=0;
}

template <typename T>
vector<T>::~vector()
{
    delete data;
}

template <typename T>
T vector<T>::elementAtRank(int r)
{
    if(r>=capacity || r<0)  // protect data from overflow
        return T();
    return data[r];
}

template <typename T>
int vector<T>::size()
{
    return vSize;
}

template <typename T>
bool vector<T>::isEmpty()
{
    return (size()==0);
}

template <typename T>
void vector<T>::replaceAtRank(int r, T newData)
{
    if(r>=capacity || r<0)
        return;
    data[r]=newData;
}

template <typename T>
void vector<T>::removeAtRank(int r)
{
    if(r>=capacity || r<0 || isEmpty())
        return;
    for(int i=r; i<vSize; i++)  // shift every element to its left
        data[i]=data[i+1];
    vSize--;
}

template <typename T>
void vector<T>::overflow()
{
    capacity*=2;  // doubling its size
    T *newArray=new T[capacity];
    for(int i=0; i<vSize; i++)  // copy from old array to the new array
        newArray[i]=data[i];
    delete data;  // delete old data
    data = newArray;  // old data points to new array
}

template <typename T>
void vector<T>::insertAtRank(int r, T newData)
{
    if(vSize==capacity)  // array is full
        overflow();
    for(int i=vSize-1; i>=r; i--)  // shift every element to its right
        data[i+1] = data[i];
    data[r] = newData;  // insert new data at rank r
    vSize++;  // size increments
    //cout << r << "," << newData << "," << vSize << endl;
}

template <typename T>
void vector<T>::print()
{
    for(int i=0; i<vSize; i++)
        cout << data[i] << ", ";
    cout << endl;
}

#endif

And this is deque.h:

// deque.h
#ifndef DEQUE_H
#define DEQUE_H

template <typename T>
class deque
{
private:
    int qSize;
    vector<T> *data;
public:
    deque(int size);
    ~deque();
    void insertFirst(T newData);
    void insertLast(T newData);
    void removeFirst();
    void removeLast();
    T first();
    T last();
    int size();
    bool isEmpty();
    void print();
};

#include <iostream>

template <typename T>
deque<T>::deque(int size)
{
    data = new vector<T>(size);
}

template <typename T>
deque<T>::~deque()
{
    delete data;
}

template <typename T>
int deque<T>::size()
{
    return data->size();
}

template <typename T>
bool deque<T>::isEmpty()
{
    return (size()==0);
}

template <typename T>
T deque<T>::first()
{
    return data->elementAtRank(0);
}

template <typename T>
T deque<T>::last()
{
    return data->elementAtRank(data->size()-1);
}

template <typename T>
void deque<T>::removeFirst()
{
    data->removeAtRank(0);
}

template <typename T>
void deque<T>::removeLast()
{
    data->removeAtRank(data->size()-1);
}

template <typename T>
void deque<T>::insertFirst(T newData)
{
    data->insertAtRank(0,newData);
}

template <typename T>
void deque<T>::insertLast(T newData)
{
    data->insertAtRank(data->size(),newData);
}

template <typename T>
void deque<T>::print()
{
    data->print();
}

#endif

Note the inclusion guards, those are a good idea for any of your header files.

Also notice elementAtRank(). Since you were returning -1 before, that may not be applicable now that your vector can store a multitude of types. This is a case where you probably want to take advantage of exceptions, but to avoid changing the code too much I simply used the default value of the template argument type. For int this will be 0, any the problem is that you really can't assume that any valid value for the type will be universally treated as an error value. Once again, this is a place where exceptions are better suited than reducing the range of the type to meet an arbitrary choice of error code.