<template> and insertionSort()
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: <template> and insertionSort()

  1. #1
    Join Date
    Jan 2009
    Posts
    14

    Question <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

  2. #2
    Join Date
    Nov 2006
    Location
    Australia
    Posts
    1,569

    Re: <template> and insertionSort()

    Specifying the actual problem will help you with responses.
    Good judgment is gained from experience. Experience is gained from bad judgment.
    Cosy Little Game | SDL | GM script | VLD | Syntax Hlt | Can you help me with my homework assignment?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center