-
April 12th, 2009, 01:37 PM
#1
<template> and insertionSort()
I am having some trouble understanding how to properly use template functions. This is my first exposure to them and my textbook is not very helpful. Any help would be appreciated. Here is what I have so far...
driver
Code:
#include <iostream>
#include "d_random.h"
#include "d_vector.h"
#include "d_sort.h"
using namespace std;
template <typename T>
void writeMiniVector(const miniVector<T> &v)
{
for (int x=0; x<v.size(); x++)
{
cout << v[x] << " ";
}
}
template <typename T>
sortMiniVector(miniVector<T> &v)
{
insertionSort(v);
}
int main()
{
miniVector<int> v;
randomNumber rnd;
for(int x=0; x<15; x++)
{
v.push_back(rnd.random(100));
}
writeMiniVector(v);
sortMiniVector(v);
cout << endl;
writeMiniVector(v);
system("pause");
return 0;
}
d_sort.h
Code:
#include <iostream>
template <typename T>
void insertionSort(miniVector<T>& v)
{
int i, j, n = v.size;
T target;
for (i=1; i<n; i++)
{
j=i;
target=v[i];
while (j>0 && target<v[j-1])
{
v[j]=v[j-1];
j--;
}
v[j]=target;
}
}
d_random.h
Code:
#include <iostream>
#include <time.h>
using namespace std;
// generate random numbers
class randomNumber
{
public:
// initialize the random number generator
randomNumber(long s = 0);
// return a 32-bit random integer m, 1 <= m <= 2^31-2
long random();
// return a 32-bit random integer m, 0 <= m <= n-1,
// where n <= 2^31-1
long random(long n);
// return a real number x, 0 <= x < 1
double frandom();
private:
static const long A;
static const long M;
static const long Q;
static const long R;
long seed;
};
const long randomNumber::A = 48271;
const long randomNumber::M = 2147483647;
const long randomNumber::Q = M / A;
const long randomNumber::R = M % A;
randomNumber::randomNumber(long s)
{
if (s < 0)
s = 0;
if (s == 0)
{
// get time of day in seconds since 12:00 AM,
// January 1, 1970
long t_time = time(NULL);
// mix-up bits by squaring
t_time *= t_time;
// result can overflow. handle cases
// > 0, < 0, = 0
if (t_time > 0)
s = t_time ^ 0x5EECE66DL;
else if (t_time < 0)
s = (t_time & 0x7fffffff) ^ 0x5EECE66DL;
else
s = 0x5EECE66DL;
}
seed = s;
}
long randomNumber::random()
{
long tmpSeed = A * ( seed % Q ) - R * ( seed / Q );
if( tmpSeed >= 0 )
seed = tmpSeed;
else
seed = tmpSeed + M;
return seed;
}
long randomNumber::random(long n)
{
double fraction = double(random())/double(M);
return int(fraction * n);
}
double randomNumber::frandom()
{
return double(random())/double(M);
}
d_vector.h
Code:
#ifndef MINI_VECTOR
#define MINI_VECTOR
#include "d_except.h" // include exception classes
using namespace std;
template <typename T>
class miniVector
{
public:
miniVector(int size = 0);
// constructor.
// Postconditions: allocates array with size number of elements
// and capacity. elements are initialized to T(), the default
// value for type T
miniVector(const miniVector<T>& obj);
// copy constructor
// Postcondition: creates current vector as a copy of obj
~miniVector();
// destructor
// Postcondition: the dynamic array is destroyed
miniVector& operator= (const miniVector<T>& rhs);
// assignment operator.
// Postcondition: current vector holds the same data
// as rhs
T& back();
// return the element at the rear of the vector.
// Precondition: the vector is not empty. if vector
// is empty, throws the underflowError exception
const T& back() const;
// const version used when miniVector object is a constant
T& operator[] (int i);
// provides general access to elements using an index.
// Precondition: 0 <= i < vSize. if the index is out
// of range, throws the indexRangeError exception
const T& operator[] (int i) const;
// const version used when miniVector object is a constant
void push_back(const T& item);
// insert item at the rear of the vector.
// Postcondition: the vector size is increased by 1
void pop_back();
// remove element at the rear of the vector.
// Precondition: vector is not empty. if the vector is
// empty, throws the underflowError exception
int size() const;
// return current list size
bool empty() const;
// return true if vector is empty and false otherwise
int capacity() const;
// return the current capacity of the vector
private:
int vCapacity; // amount of available space
int vSize; // number of elements in the list
T *vArr; // the dynamic array
void reserve(int n, bool copy);
// called by public functions only if n > vCapacity. expands
// the vector capacity to n elements, copies the existing
// elements to the new space if copy == true, and deletes
// the old dynamic array. throws the memoryAllocationError
// exception if memory allocation fails
};
// set the capacity to n elements
template <typename T>
void miniVector<T>::reserve(int n, bool copy)
{
T *newArr;
int i;
// allocate a new dynamic array with n elements
newArr = new T[n];
if (newArr == NULL)
throw memoryAllocationError(
"miniVector reserve(): memory allocation failure");
// if copy is true, copy elements from the old list to the new list
if (copy)
for(i = 0; i < vSize; i++)
newArr[i] = vArr[i];
// delete original dynamic array. if vArr is NULL, the vector was
// originally empty and there is no memory to delete
if (vArr != NULL)
delete [] vArr;
// set vArr to the value newArr. update vCapacity
vArr = newArr;
vCapacity = n;
}
// constructor. initialize vSize and vCapacity.
// allocate a dynamic array of vSize integers
// and initialize the array with T()
template <typename T>
miniVector<T>::miniVector(int size):
vSize(0), vCapacity(0), vArr(NULL)
{
int i;
// if size is 0, vSize/vCapacity are 0 and vArr is NULL.
// just return
if (size == 0)
return;
// set capacity to size. since we are building the vector,
// copy is false
reserve(size, false);
// assign size to vSize
vSize = size;
// copy T() into each vector element
for (i=0;i < vSize;i++)
vArr[i] = T();
}
// copy constructor. make the current object a copy of obj.
// for starters, use initialization list to create an empty
// vector
template <typename T>
miniVector<T>::miniVector (const miniVector<T>& obj):
vSize(0), vCapacity(0), vArr(NULL)
{
int i;
// if size is 0, vSize/vCapacity are 0 and vArr is NULL.
// just return
if (obj.vSize == 0)
return;
// set capacity to obj.vSize. since we are building the vector,
// copy is false
reserve(obj.vSize, false);
// assign size to obj.vSize
vSize = obj.vSize;
// copy items from the obj.vArr to the newly allocated array
for (i = 0; i < vSize; i++)
vArr[i] = obj.vArr[i];
}
// destructor. deallocate the dynamic array
template <typename T>
miniVector<T>::~miniVector()
{
if (vArr != NULL)
// de-allocate memory for the array
delete [] vArr;
}
// replace existing object (left-hand operand) by
// rhs (right-hand operand)
template <typename T>
miniVector<T>& miniVector<T>::operator= (const miniVector<T>& rhs)
{
int i;
// check vCapacity to see if a new array must be allocated
if (vCapacity < rhs.vSize)
// make capacity of current object the size of rhs. don't
// do a copy, since we will replace the old values
reserve(rhs.vSize, false);
// assign current object to have same size as rhs
vSize = rhs.vSize;
// copy items from rhs.vArr to vArr
for (i = 0; i < vSize; i++)
vArr[i] = rhs.vArr[i];
return *this;
}
// check vSize and throw an underflowError exception if the
// value is 0; otherwise return the element vArr[vSize-1]
template <typename T>
T& miniVector<T>::back()
{
if (vSize == 0)
throw underflowError(
"miniVector back(): vector empty");
return vArr[vSize-1];
}
template <typename T>
const T& miniVector<T>::back() const
{
if (vSize == 0)
throw underflowError(
"miniVector back(): vector empty");
return vArr[vSize-1];
}
// provides general access to array elements
template <typename T>
T& miniVector<T>::operator[] (int i)
{
if (i < 0 || i >= vSize)
throw indexRangeError(
"miniVector: index range error", i, vSize);
return vArr[i];
}
// provides general access to array elements. constant version
template <typename T>
const T& miniVector<T>::operator[] (int i) const
{
if (i < 0 || i >= vSize)
throw indexRangeError(
"miniVector: index range error", i, vSize);
return vArr[i];
}
// insure that list has sufficient capacity,
// add the new item to the list, and increment vSize
template <typename T>
void miniVector<T>::push_back(const T& item)
{
// if space is full, allocate more capacity
if (vSize == vCapacity)
{
if (vCapacity == 0)
// if capacity is 0, set capacity to 1.
// set copy to false because there are
// no existing elements
reserve(1,false);
else
// double the capacity
reserve(2 * vCapacity, true);
}
// add item to the list, update vSize
vArr[vSize] = item;
vSize++;
}
// if not empty, just decrement the size
template <typename T>
void miniVector<T>::pop_back()
{
if (vSize == 0)
throw underflowError(
"miniVector pop_back(): vector is empty");
vSize--;
}
template <typename T>
int miniVector<T>::size() const
{
return vSize;
}
template <typename T>
bool miniVector<T>::empty() const
{
return vSize == 0;
}
template <typename T>
int miniVector<T>:: capacity() const
{
return vCapacity;
}
#endif // MINI_VECTOR
-
April 12th, 2009, 07:09 PM
#2
Re: <template> and insertionSort()
Specifying the actual problem will help you with responses.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|