Wednesday 30 October 2013

Introduction to Templates

0 comments
Two weeks ago we learned about templates and this week we are to implement a template for Fardad's dynamic array of integer array class. My understanding is that templates are used to abstract code in such a way that a generic datatype is used to account for the multiple instances of a known receiving datatype used within the class. This would allow the class to operate the same for different datatypes. From our previous lecture we used the Stack to point to nodes that store an integer and coded methods to work with that specific datatype. Using templates we could have created a stack to handle any type of data and still operate similarly.

/* 
   This Array of Int Array now works with Char and
   floating point numbers, but not with external 
   functions associated with strings such as strcpy. 
*/

#include <iostream>
using namespace std;

template <class T> 
class IntArray {
    T* _data;
    unsigned int _size;
  public:
    IntArray(unsigned int size) {
      _data = new T[_size = size];
    }
    T& operator[](unsigned int index) {
      if (index >= _size) {
        size(index < 1024 ? index + 1 : index + 1024);
      }
      return _data[index];
    }
    unsigned int size() {
      return _size;
    }
    void size(unsigned int newsize) {
      T* temp = new T[newsize];
      for (int i = 0; i < _size && i < newsize; i++) {
        temp[i] = _data[i];
      }
      delete[]_data;
      _data = temp;
      _size = newsize;
    }
    T* display(){
      return _data;
    }
    virtual ~IntArray() {
      delete[] _data;
    }
};

template <class T> 
class IntArrArr {
    IntArray<T>** _data;
    unsigned int _size;
    unsigned int _width;
  public:
    IntArrArr(unsigned int size, unsigned int width) {
      _data = new IntArray<T>*[_size = size];
      for (int i = 0; i < _size; i++) {
        _data[i] = (IntArray <T>*)0;
      }
      _width = width;
    }
    T Size() const {
      return _size;
    } 
    IntArray<T>& operator[] (unsigned int index) {
      if (_data[index % _size] == 0) {
        _data[index % _size] = new IntArray<T>(_width);
      }
      return *_data[index % _size];
    }
    virtual ~IntArrArr() {
      for (int i = 0; i < _size; i++) {
        if (_data[i]) {
          delete _data[i];
        }
      }
      delete[] _data;
    }
};

int main()
{
    IntArrArr<int> I(5, 4);   
    IntArrArr<double> D(5,4); 
    IntArrArr<char> C(5, 4);  
    int i;
    int j;
    int x = 0;
    
    for (i = 0; i < 5; i++) {
      for (j = 0; j < 4; j++) {
        I[i][j] = (i + 1) * (j + 1);
        D[i][j] = (i + 0.5) * (j + 0.5);
      }
    }

    cout << "Array of Int Array:" << endl;
    for (i = 0; i < 5; i++) {
      for (j = 0; j < 4; j++) {
        cout << I[i][j] << " ";
      }
      cout << endl;
    }

    cout << "Array of Double Array:" << endl;
    for (i = 0; i < 5; i++) {
      for (j = 0; j < 4; j++) {
        cout << D[i][j] << " ";
      }
      cout << endl;
    }

    cout << "Array of Char Array:" << endl;
    for (i = 0; i < 5; i++) {
      for (j = 0; j < 4; j++) {
        C[i][j] = 'a' + x++;
      }
    }

    for (i = 0; i < 5; i++) {
      for (j = 0; j < 4; j++) {
        cout << C[i][j] << " ";
      }
      cout << endl;
    }


    return 0;
}

Saturday 12 October 2013

Linked Lists - copy constructor, depth(), reverse()

6 comments
What a busy week with tests, assignments, and co-op interviews... Anyway, here is my
solution to the copy constructor, depth(), and reverse() function for Fardad's challenge
of the week. Each week things are getting a little bit more interesting. 


/* 
  copy constructor
  
  1. Create temporary node pointer (for cycling) and copy top 
     node pointer of source
  2. Create temporary node pointer (for cycling) for destination 
     and create new Node with source data (this will be the top node)
  3. Mark down the top node
  4. Cycle through the nodes in a way that makes dest 
     become the pointer for the next new node as the data copies over.    
*/


Stack::Stack(const Stack& S)
{
    Node* src = S._top;
    Node* dest = new Node(src->_data);
    _top = dest;

    while (src->_next != 0) {
      src = src->_next;
      dest->_next = new Node(src->_data);
      dest = dest->_next;
    }
}

----------------------------------------------------------------

/* 
  depth()
  
  1. Create temporary variable to mark the level of depth
  2. Create a temporary node pointer to cycle through the nodes
  3. Cycle through the nodes while marking down the depth
  4. Return the depth level   
*/


unsigned int Stack::depth()
{
    unsigned int lvl = 0;
    Node* top = _top;

    while (top) {
      lvl++;
      top = top->_next;
    }
    return lvl;
}

----------------------------------------------------------------

/* 
  reverse()
  
  1. Create temporary node pointer to a new node and pop the 
     first node while retrieving data (this is your new bottom node)
  2. Cycle through all the nodes, popping all the previous nodes 
     and creating new nodes with their data and using a pointer
     to the current instance and immediately assigning it to a
     new instance(this will reverse the order and destroy the 
     previous nodes)
  3. Copy the pointer to the top of your new reversed list
*/


void Stack::reverse()
{
    Node* temp = new Node(pop());

    while (!isEmpty()) {
      temp = new Node(pop(), temp);
    }
    _top = temp;
}