#include <iostream>
using namespace std;

#include "tqueue.h"

template <class T>
void print(Tqueue<T>& Q){
  bool done = false;
  Q.goHead();
  cout<<"NULL <- [HEAD] ";
  if(!Q.isEmpty()){
    do{
      cout<<Q.visit();
      if(Q.goNext()) cout<<" <=> ";
      else{
        done = true;
      }
    }while(!done);
  }
  cout<<" [TAIL] -> NULL"<<endl;
  cout<<endl<<endl;
}

int main(){
  Tqueue<int> Q;
  cout<<"Before Data to be Added:"<<endl;
  print(Q);

  for(int i=1;i<=6;i+=1){
    Q.append((rand()%rand())%100+1);
  }
  cout<<"After Data Added Ramndomly:"<<endl;
  print(Q);

  cout<<"After Assending Order:"<<endl;
  Q.sort();
  print(Q);
  cout<<"After Dessending Order:"<<endl;
  Q.sort(0);
  print(Q);

  cout<<"Let's POP some data:"<<endl;
  cout<<Q.pop()<<endl;
  cout<<Q.pop()<<endl;
  cout<<Q.pop()<<endl<<endl;
  cout<<"After Poped some data:"<<endl;
  print(Q);

  cout<<"After Pushed some data:"<<endl;
  Q.push(111);
  Q.push(555);
  Q.push(999);
  print(Q);

  Q.append(55);
  cout<<"AFTER APPENDED A DATA:"<<endl;
  print(Q);


  cout<<"MOVE CURRENT TO SECOND NODE (if exist) AND USE INSERTBEFORE TO ADD 1234:"<<endl;
  Q.goHead();
  Q.goNext();
  Q.insertBefore(1234);
  print(Q);

  cout<<"MOVE CURRENT TO FIFTH NODE (if exist) AND USE INSERTAFTER TO ADD 1000:"<<endl;
  Q.goHead();
  Q.goNext();
  Q.goNext();
  Q.goNext();
  Q.goNext();
  Q.insertAfter(1000);
  print(Q);

  cout<<"MOVE CURRENT TO SECOND NODE (if exist) AND REMOVE:"<<endl;
  Q.goHead();
  Q.goNext();
  Q.removeCurrent();
  print(Q);

  getchar();
  return 0;
}

Double Linked List with Templates

Posted: March 21, 2012 in OOP344
#ifndef __TQUEUE_H__
#define __TQUEUE_H__

template <class T>
class Tqueue;

template <class T>
class Tqnode{
  Tqnode<T>* _next;
  Tqnode<T>* _prev;
  T _data;
  Tqnode(T data, 
    Tqnode<T>* prev = (Tqnode<T>*)0, 
    Tqnode<T>* next = (Tqnode<T>*)0):_data(data){
    _next = next;
    _prev = prev;
  }
  friend class Tqueue<T>;
};

template <class T>
class Tqueue{
  Tqnode<T>* _head;
  Tqnode<T>* _curr;
  Tqnode<T>* _tail;
public:
  Tqueue();
  virtual ~Tqueue();
  bool goNext();
  bool goPrev();
  bool goHead();
  bool goTail();
  bool isEmpty();
  void append(T data);// appends to tail
  T remove(); // removes the data from the head of the list
  void insertBefore(T data);  // before current (prev side)
  void insertAfter(T data);  // after current  (next side)
  T visit(); // returs the data of the current
  T removeCurrent(); // removes curent
  bool sort(bool Ascending = true);  // sorts the nodes
  void push(T data);
  T pop();

};

template <class T>
Tqueue<T>::Tqueue(){
  _head = _tail = _curr = (Tqnode<T>*)0;
}

template <class T>
Tqueue<T>::~Tqueue(){
  goHead();
  while(_curr){
    _head = _curr;
    _curr = _curr->_next;
    delete _head;
  }
}

template <class T>
T Tqueue<T>::visit(){ 
  return _curr->_data;
}

template <class T>
bool Tqueue<T>::sort(bool Ascending){
  Tqnode<T>* tmp = _curr = _head;
  bool done = false;
  goNext();
  while(tmp && tmp->_next){
    if((Ascending && tmp->_data > _curr->_data) || (!Ascending && tmp->_data < _curr->_data)){
      T buff = tmp->_data;
      tmp->_data = _curr->_data;
      _curr->_data = buff;
    }
    if(!goNext()){
      tmp = tmp->_next;
      if(tmp->_next) _curr = tmp->_next;
      else done = true;
    }
  }
  return done;
}

template <class T>
void Tqueue<T>::append(T data){ 
  _tail = new Tqnode<T>(data, _tail);
  if(_curr) _tail->_prev->_next = _tail;
  else _curr = _head = _tail;
}

template <class T>
T Tqueue<T>::remove(){
  T data = _head->_data;
  if(_head == _tail){
    delete _head;
    _head = _tail = _curr = (Tqnode<T>*)0;
  }
  else{
    Tqnode<T>* todel = _head;
    if(!_curr->_prev)_curr = _curr->_next;
    _head = _head->_next;
    _head->_prev = (Tqnode<T>*)0;
    delete todel;
  }
  return data;
}

template <class T>
void Tqueue<T>::insertBefore(T data){
  if(_curr){
    _curr = new Tqnode<T>(data, _curr->_prev, _curr);
    _curr->_next->_prev = _curr; 
    if(_curr->_prev) _curr->_prev->_next = _curr;
    else _head = _curr;
  }
  else _tail = _head = _curr = new Tqnode<T>(data);
}

template <class T>
void Tqueue<T>::insertAfter(T data){
  if(_curr){
    _curr = new Tqnode<T>(data, _curr, _curr->_next);
    _curr->_prev->_next = _curr; 
    if(_curr->_next) _curr->_next->_prev = _curr;
    else _tail = _curr;
  }
  else _tail = _head = _curr = new Tqnode<T>(data);
}

template <class T>
T Tqueue<T>::removeCurrent(){
  T data = _curr->_data;
  if(_curr == _head){
    data = remove();
  }
  else{
    Tqnode<T>* todel = _curr;
    if(_tail == _curr){
      _curr->_prev->_next = (Tqnode<T>*)0;
      _curr = _tail = _curr->_prev;
    }
    else{
      _curr->_prev->_next = _curr->_next;
      _curr->_next->_prev = _curr->_prev;
      _curr = _curr->_next;
    }
    delete todel;
  }
  return data;
}

template <class T>
void Tqueue<T>::push(T data){
  _head = new Tqnode<T>(data, (Tqnode<T>*)0, _head);
  if(_curr) _head->_next->_prev = _head;
  else _curr = _tail = _head;
}

template <class T>
T Tqueue<T>::pop(){
  return remove();
}

template <class T>
bool Tqueue<T>::isEmpty(){
  return !_curr;
}

template <class T>
bool Tqueue<T>::goTail(){
  bool res = false;
  if(_curr){  // is not null
    _curr = _tail;
    res = true;
  }
  return res;
}

template <class T>
bool Tqueue<T>::goHead(){
  bool res = false;
  if(_curr){  // is not null
    _curr = _head;
    res = true;
  }
  return res;
}

template <class T>
bool Tqueue<T>::goNext(){
  bool res = false;
  if(_curr && _curr->_next){
    _curr = _curr->_next;
    res = true;
  }
  return res;
}

template <class T>
bool Tqueue<T>::goPrev(){
  bool res = false;
  if(_curr->_prev){
    _curr = _curr->_prev;
    res = true;
  }
  return res;
}

#endif

This is modified & compacted version from Balwinder, XLIAN3 and Gulnaz codes.

Thank you!!

char*  bits(int val){
  static char str[sizeof(int)*8+1];
  for(int size=sizeof(int)*8; size; val>>=1){
    str[--size]= (val & 1) + 48;
  }
  str[sizeof(int)*8]=0;
  return str;
}

Cout bits

Posted: March 12, 2012 in OOP344
#include <iostream>
#include <string>
using namespace std;

string bits(int val){
  string A="01";
  string ret;
  for(int i = sizeof(int)*8-1; i >= 0; i--, val>>=1)
    ret = A[val & 1] + ret;
  return ret;
}

string bitsTrim(int val){
  string ret;
  do{
    ret = (char)(!!(val & 1)+48) + ret;
    val>>=1;
  }while(val);
  return ret;
}

int main()
{
  int x = 2345;
  cout << "Binary:  " << bits(x) << endl;
  cout << "Binary:  " << bitsTrim(x) << endl;
  return 0;
}

METHOD 1

bool isOn(unsigned int val, int bitNo){
  return (val>>bitNo)%2;
}

bool isOff(unsigned int val, int bitNo){
  return (~val>>bitNo)%2;
}

METHOD 2

bool isOn(unsigned int val, int bitNo){
  return ((val>>bitNo)!=(val>>(bitNo+1))<<1);
}

bool isOff(unsigned int val, int bitNo){
  return ((val>>bitNo)==(val>>(bitNo+1))<<1);
}

Priority Queue

Posted: March 5, 2012 in Uncategorized

QUEUE.CPP

#include "queue.h"
Node::Node(int data, Node* next){
  _data = data;
  _next = next;
}
Queue::Queue(){
  _head = (Node*)0;
}
Queue::~Queue(){
  while(!isEmpty()) remove();
}
int Queue::remove(int pos){
  int ret = 0;
  Node* cur = _head;
  Node* prev = (Node*)0;
  bool flag = false;
  int i = 1;
  while(cur && i != pos){
    prev = cur;
    cur = cur->_next;
    i++;
  }
  if (i == pos && cur){
    ret = cur->_data;
    if (!prev){
      _head = _head->_next;
      delete cur;
    }
    else{
      cur = cur->_next;
      delete prev->_next;
      prev->_next = cur;
    }
  }
  return ret;
}
bool Queue::add(int val, int pos){
  Node* cur = _head;
  Node* prev = (Node*)0;
  bool flag = false;
  int i = 0;
  while(cur && i != pos){
    prev = cur;
    cur = cur->_next;
    i++;
  }
  if(pos == -1) pos = i;
  if(i == pos){
    if (i == 0){
      _head = new Node(val, _head);
      flag = true;
    }
    else{
      prev->_next = new Node(val, cur);
      flag = true;
    }
  }
  return flag;
}
bool Queue::isEmpty(){
  return !_head;
}

QUEUE.H

#ifndef __TV_QUEUE_H__
#define __TV_QUEUE_H__

class Queue;

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

class Queue{
  Node* _head;
public:
  Queue();
  virtual ~Queue();
  int remove(int pos=1);
  bool add(int, int pos = -1);
  bool isEmpty();
};

QUEMAIN.CPP

#include <iostream>
using namespace std;
#include "queue.h"
int main(){
  Queue Q;
  for(int i = 10;i<101;i+=10){
    Q.add(i);
  }
  cout<<"Removed the "<<Q.remove(1)<<endl;
  cout << "append at 9th is: ";
  cout<<(Q.add(2222, 9)?"SUCCESS":"FAIL")<<endl;
  while(!Q.isEmpty()){
    cout<<Q.remove()<<endl;
  }
  getchar();
  return 0;
}