Sunday 24 March 2013

OOP344 Week 11: Copy Bits

The following is the code for copying bits from a mask to a number:
#include <cstdio>

void prnBits(unsigned int val){
    unsigned int m = 1 << sizeof(val)*8-1;
    while(m){
        printf("%d", (val & m)&&1);
        m = m >> 1;
    }
}

//set the bit at bitNo to value
void setBit(unsigned int& V, int bitNo, bool value){
    unsigned int mask;
    if (bitNo >= 1 && bitNo <= (sizeof(V) * 8)){
        mask = 1 << (bitNo - 1);
        V = (value)? (V | mask): (V & ~(mask)); 
    }
}
// from bit number "bitNo" in mask copies NoOfBits bits into V
void copyBits(unsigned int& V, int bitNo, int NoOfBits, unsigned int mask){
    unsigned int m;
    int i;
    if (bitNo >= 1 && NoOfBits >= 1){
        m = 1 << (bitNo - 1);
        for (i = bitNo; i < bitNo + NoOfBits && i <= (sizeof(V) * 8); i++){
            // (mask & m) >> (i - 1) give mask's bitNo-th digit
            setBit(V, i, (mask & m)>>(i-1));
            m= m << 1;
        } 
    }
}

int main(){
    unsigned int A = 0x5C;
    unsigned int M = 0x85025512;
    printf("A (Before copy): %02X\n", A);
    prnBits(A); putchar('\n');
    printf("M: %02X\n", M);
    prnBits(M); putchar('\n');
    copyBits(A,5,8,M);
    printf("A (After copy): %02X\n", A);
    prnBits(A); putchar('\n');
    return 0;
}

Saturday 23 March 2013

OOP344 Week 11: Bit Dump Function

The following is a function that prints the address of a pointer in bits with formatting (a space after every 4th binary digit):

#include <cstdio>

void bitDump(void* address, unsigned int sizeInBytes){
    unsigned char* c = (unsigned char*)address;
    int i;
    for (i = 0; i < sizeInBytes; i++){
        unsigned int hex = (int)c[i];
        unsigned int m = 1 << sizeof(hex)*8-1;
        int j;
        for(j = 0; m; j++){ 
            if ((j+ 1)% 5 == 0){
                printf(" ");
            }
            else {
                printf("%d", (hex & m)&&1);
                m = m >> 1;
            }
        }
        printf(" ");
    } 
}
int main(){
    long double ld = 12345.123456;
    bitDump(&ld, sizeof(ld)); // print the bit pattern (cool if formatted)
    return 0;
}

OOP344 Week 11: Object Oriented Binary String Print

The following is a class that prints the binary string. It also has a static varaible in the class to set the formatting of the string. If the string is formatted, then it will display the binary string with a space every 4th binary digit.

#include <iostream>

using namespace std;

class bits{
    unsigned int _val;
public:
    static bool formatted;  
    bits(unsigned int val){
        _val = val;
    }
    const char* displayBin() const{
        unsigned int m = 1 << sizeof(_val)*8-1;
        char* str = (formatted)?new char[sizeof(_val)*8 + (sizeof(_val)*8)/4 - 1 + 1]:new char[sizeof(_val)*8 + 1];
        int i = 0;
        while(m){
            if (formatted && (i+1)%5 == 0){
                str[i] = ' ';
            }
            else {
                str[i] = (_val & m)? '1' : '0';
                m = m >> 1;
            }
            i++;
        }
        str[i] = 0;
        return str;
    }
};
ostream& operator<<(ostream& os, const bits& b){
    os<<b.displayBin();
    return os;
}

bool bits::formatted = false; // by default false
int main(){
    char A = 0x5c;
    char B = 0x95;
    char C = 0;

    cout<<bits(A)<<endl;
    bits::formatted = true;
    cout<<bits(B)<<endl;
    return 0;
}

I should note that when setting statics in C++ using the class name, the scope resolution operator(::)needs to be used. Also, the default value of the static variable must be set outside the class.

OOP344 Week 11: Binary String Function

The following function takes an integer and returns the binary string:

const char* bits(unsigned int val){
    unsigned int m = 1 << sizeof(val)*8-1;
    char* str = new char[sizeof(val)*8 + 1];
    int i = 0;
    while(m){
        str[i] = (val & m)?'1':'0';   
        i++;
        m = m >> 1;
    }
    str[i] = 0;
    return str;
}

Friday 15 March 2013

Dynamic Double Linked List

For week 10 of OOP344, I was asked to do the insert function of a dynamic double linked list. Insert works back inserting a new node before the current pointer.

Below is the header file for the two classes, Node and DDL:

class DLL;

class Node{
  int _data;
  Node* _prev;
  Node* _next;
  Node(int data, Node* prev=(Node*)0, Node* next=(Node*)0);
  friend class DLL;
};


class DLL{
  Node* _head;
  Node* _curr;
  Node* _tail;
  void copy(DLL& D);
public:
  DLL();
  DLL(DLL& D);
  virtual ~DLL();
  bool isEmpty();
  void append(int data);
  DLL& operator=(DLL& D);
  int remove();   // removes the current node and returns the data
  bool del();     // removes the current node returns false if is empty
  void insert(int data); // insterts before current
  bool goHead();
  bool goTail();
  bool goNext();
  bool goPrev();
  int visit();    // returns the current data
};
Here is the full implmentation of the two classes:
#include "dll.h"
Node::Node(int data, Node* prev, Node* next){
    _data = data;
    _prev = prev;
    _next = next;
}

DLL::DLL(){
    _head = _tail = _curr = 0;
}
DLL::~DLL(){
    while(del());
}
void DLL::copy(DLL& D){
    int curpos;
    for(curpos=0;D.goPrev();curpos++); // findout where is current
    if(!D.isEmpty()){
        do{
            this->append(D.visit());
        }while(D.goNext());
    }
    for(D.goHead(), this->goHead();curpos;D.goNext(), this->goNext(),curpos--); 
}
DLL::DLL(DLL& D){
    _head = _tail = _curr = 0;
    copy(D);
}
DLL& DLL::operator=(DLL& D){
    if (this != &D){
        while(del());
        copy(D);
    }
    return *this;
}

void DLL::append(int data){
    Node* newnode = new Node(data);
    if(_tail){  // ! empty
        _tail->_next = newnode;
        newnode->_prev = _tail;
        _tail = _curr = newnode;
    }
    else{
        _tail = _curr = _head = newnode;
    }

}
int DLL::remove(){
    int data = visit();
    del();
    return data;
}
bool DLL::del(){
    bool ok = false;
    bool tailMoved = false;
    if(_curr){
        ok = true;
        Node* todel = _curr;
        if(_curr->_next){
            _curr->_next->_prev = _curr->_prev;
        }
        else{
            _tail = _tail->_prev;
            tailMoved = true;
        }
        if(_curr->_prev){
            _curr->_prev->_next = _curr->_next;
        }
        else{
            _head = _head->_next;
        }

        if (!tailMoved){
            _curr = _curr->_next;
        }
        else {
            _curr = _curr -> _prev;
        }
        delete todel;
    }
    return ok;
}
void DLL::insert(int data){
    //Create a new node
    Node* newNode = new Node (data);
    if (_curr){
        Node* temp = _curr -> _prev;

        //Connect the new node to the current node
        _curr -> _prev = newNode;
        newNode -> _next = _curr;

        if (temp){
            //Connect the new node to the previous node
            temp -> _next = newNode;
            newNode -> _prev = temp;
        }
        else {
            _head = newNode;
        }
    }
    else {
        _head = _tail = newNode;
    }
    //Move current pointer to the new node
    _curr = newNode;
}

int DLL::visit(){               // retruns data of current
    return _curr ->_data;
}

bool DLL::goHead(){
    bool success = false;
    if (!isEmpty()){
        _curr = _head;
        success = true;
    }
    return success;
}
bool DLL::goTail(){
    bool success = false;
    if (!isEmpty()){
        _curr = _tail;
        success = true;
    }
    return success;
}
bool DLL::goNext(){
    bool success = false;
    if (!isEmpty() && _curr -> _next){
        _curr = _curr ->_next;
        success = true;
    }
    return success;
}
bool DLL::goPrev(){
    bool success = false;
    if (!isEmpty() && _curr -> _prev){
        _curr = _curr ->_prev;
        success = true;
    }
    return success;
}
bool DLL::isEmpty(){
    return (!_curr)?true:false;
}

Thursday 14 March 2013

Dynamic 2D Integer Array

I would like to share my experience on implementing the square brakets ([ ]) operator overloading method in the dynamic 2D integer array class, IntArrArr.

Here is the IntArrArr class header file:
class IntArrArr{
  IntArr** _data;
  unsigned int _size;
  unsigned int _width;
  public:
    IntArrArr(unsigned int size,unsigned int width);
    IntArr& operator[](unsigned int index);
    unsigned int Size()const;
    virtual ~IntArrArr();
}; 
IntArr is a dynamic 1D integer array class implemented during week 5 of my OOP344 class. The original implementation for IntArrArr was also done in class, which had index loop back for the operator overload method.

Below is the implementation for the operater overload method that resizes the array when the index given is greater than the array size:
  IntArr& operator[](unsigned int index){
        IntArr** temp;
        if (index >= _size){
            int i;

            //Step 1: Make a temporary array with a new size
            unsigned int newsize = index < 1024? index*2 : index + 1024;
            temp = new IntArr* [newsize];

            //Step 2: Null each element of the temporary array
            for (i = 0; i < (int)newsize; i++){
                temp[i] = 0;
            }

            //Step 3: Copy data from the old array to the temporary array 
            for (i = 0; i < _size; i++){
                temp[i] = _data[i];
            }
            //Step 4: Add a new array to the next avaliable index
            temp[i] = new IntArr(_width);

            //Step 5: Delete the old array
            delete [] _data;

            //Step 6: Update the size and data pointer 
            _size = newsize;
            _data = temp;
        }
        else if(_data[index] == 0){
            _data[index] = new IntArr(_width);
        }
        return *_data[index];
    }

I struggled with step 5 of the implementation. Previously, I deleted each of the elements in the old array using a for loop. The reason why deleting each element of the old array does not work is because shallow copying  was used to copy elements from the old array to the new array in step 3. Deleting each element in the old array would mean deleting the elements in the temporary array as well. So when I tried accessing the array, I got a runtime error for accessing an IntArr object that does not exist.

Special thanks to my OOP344 group members in iCODE for showing me the proper way to implement the CDialog add function.

For those interested in viewing the full implmentation of IntArrArr, it is in my github repository.


Monday 21 January 2013

OOP344 Week 2 - Addition, Subtraction, Multiplication and Division Programs

Addition Program
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <iostream>

using namespace std;

bool validateInt (const char* value){
 bool valid = true;
 int i;
 int len = strlen(value);
 
 if (isdigit(value[0]) || value[0] == '-' && len > 1){
  for (i =  1; i < len && valid; i++){
   if (value[i] < '0' || value[i] > '9'){
    valid = false;
   }
  } 
 }
 else {
  valid = false;
 }
 return valid;
}

int main(int argc, char* argv[])
{
 int num1;
 int num2;
 bool valid = false;

 if (argc == 3){ 
  valid = validateInt(argv[1]) && validateInt(argv[2]);
 }

 if (valid){
  num1 = atoi(argv[1]);
  num2 = atoi(argv[2]);
  cout << "The sum is " << num1 + num2 << endl;
 }
 else {
  cout << "Error: invalid input" << endl;
 }
 return 0;
}

Before compiling the following programs, please copy the validateInt() function in the addition program and paste it before main().

Subtraction Program
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
 int num1;
 int num2;
 bool valid = false;

 if (argc == 3){ 
  valid = validateInt(argv[1]) && validateInt(argv[2]);
 }

 if (valid){
  num1 = atoi(argv[1]);
  num2 = atoi(argv[2]);
  cout << "The difference is " << num1 - num2 << endl;
 }
 else {
  cout << "Error: invalid input" << endl;
 }
 return 0;
}
Multiplication Program
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
 int num1;
 int num2;
 bool valid = false;

 if (argc == 3){ 
  valid = validateInt(argv[1]) && validateInt(argv[2]);
 }

 if (valid){
  num1 = atoi(argv[1]);
  num2 = atoi(argv[2]);
  cout << "The product is " << num1 * num2 << endl;
 }
 else {
  cout << "Error: invalid input" << endl;
 }
 return 0;
}
Division Program
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
 int num1;
 int num2;
 bool valid = false;

 if (argc == 3){ 
  valid = validateInt(argv[1]) && validateInt(argv[2]);
 }

 if (valid){
  num1 = atoi(argv[1]);
  num2 = atoi(argv[2]);

  if (num2 != 0){
   cout << "The quotient is " << num1 / num2 << endl;
  }
  else {
   cout << "Error: cannot divide by 0" << endl;
  }
 }
 else {
  cout << "Error: invalid input" << endl;
 }
 return 0;
}