11/25/10

Sparse Matrix

Sparse Matrix

Numerical analysis in which  a matrix most elements are zeros

 Introduction
 in some situation we face with matrix that they have a lot of zeros element and as you know it is not necessary to multiple,add,... all of them.if there exists a way to ignore them then the matrix algorithms go better and more efficient.
so we can store matrix as list and everywhere that the element is zero we dont store it but in referencing to it we return zero.
if you do a quick look at  it you can see the algorithm,and if you run it you will enjoy



//in the name of allah
#include
using namespace std;
class sparseElem{
  public:
    int row,col;
    double value;
    sparseElem *nextRow;
    sparseElem *nextCol;
    sparseElem(){
    }
   
};



class sparseMatrix{
  public:
    int n,m;
    sparseElem *head_col;
    sparseElem *head_row;
    sparseElem*c;
    sparseElem *r;
    sparseMatrix(){
       m=3;n=3;
      head_col=head_row=NULL;
      c=new sparseElem[n];
      r=new sparseElem[m];
      for(int i=0;i
        r[i].row=i;
      for(int i=0;i
        c[i].col=i;
     }
    sparseMatrix(int m1,int n1){
      m=m1;n=n1;
      head_col=head_row=NULL;
      c=new sparseElem[n];
      r=new sparseElem[m];
      for(int i=0;i
        r[i].row=i;
      for(int i=0;i
        c[i].col=i;
    }
    void setElem(int i,int j,double x){
      sparseElem *tmp=new sparseElem;
        tmp->row=i;
        tmp->col=j;
        tmp->value=x;
        //important
        tmp->nextRow=NULL;                                        //point
        tmp->nextCol=NULL;
      if(!head_row){//head_row=head_col=NULL
        head_row=r+i;
        head_col=c+j;
        r[i].nextRow=tmp;
        r[i].nextCol=NULL;
        c[j].nextCol=tmp;
        c[j].nextRow=NULL;
        tmp->nextRow=NULL;
        tmp->nextCol=NULL;
      }
      else{
        sparseElem *pc=head_col;
        sparseElem *lpc=NULL;
        while(pc->nextRow!=NULL && tmp->col>pc->col){
        //cout<<"while 1"<
          lpc=pc;
          pc=pc->nextRow;
        }
        if(tmp->col < pc->col){
          if(lpc)
            lpc->nextRow=c+j;
          else
            head_col=c+j;
          (c+j)->nextRow=pc;
          c[j].nextCol=NULL;                                                                    //new
        }
      
        else if(tmp->col > pc->col){
          pc->nextRow=c+j;
          c[j].nextRow=NULL;                                      //new added                                                         maybe error
          c[j].nextCol=NULL;                                            //new added maybe optional
        }
        else//both are equal
          pc=c+j;
        //fixing r[i] ha
        sparseElem *pr=head_row;
        sparseElem *lpr=NULL;
        while(pr->nextCol!=NULL && tmp->row > pr->row){
        //cout<<"while 2"<
          lpr=pr;
          pr=pr->nextCol;
        }
        if(tmp->row < pr->row){
          if(lpr)
            lpr->nextCol=r+i;
          else
            head_row=r+i;//the first element is inserting;
          (r+i)->nextCol=pr;
          r[i].nextRow=NULL;                                                                //new
        }
        else if(tmp->row>pr->row){
          pr->nextCol=r+i;
          r[i].nextCol=NULL;                                      //new added
          r[i].nextRow=NULL;//r[i].nextCol=NULL;
        }
        else//both are equal
          pr=r+i;
        //fixing adding element to a others in sparseMatrix
       
        sparseElem *pc2=c+j;
        sparseElem *lpc2=NULL;
        while(pc2->nextCol!=NULL &&pc2->nextCol->rowrow){ 
           lpc2=pc2;
           pc2=pc2->nextCol;//chon dar haman sotun search mikonim
        }
        //agar az ghabk vojud dash faghat value ra be an midahim vagarne hame chiz be ham mirizad va hafeze ezafe mibarad
        if(pc2->nextCol && pc2->nextCol->row ==tmp->row)//      ! if(pc2->nextCol && pc2->nextCol->row>tmp->row)//                   new   error if(pc2->nextCol )
          pc2->nextCol->value=tmp->value;
          //tmp=NULL;//delete tmp; next is  deleting it in below
        else {//if(pc2->nextCol && pc2->nextCol->row > tmp->row){//``````````````````completely new
          lpc2=pc2;
          tmp->nextCol=lpc2->nextCol;
          pc2->nextCol=tmp;
          }
        sparseElem *pr2=r+i;
        sparseElem *lpr2=NULL;
        while(pr2->nextRow!=NULL &&pr2->nextRow->colcol){
           lpr2=pr2;
           pr2=pr2->nextRow;//chon dar haman sotun search mikonim
        }
        if(pr2->nextCol && pr2->nextRow->col ==tmp->col){
          delete tmp;
          }
        else{// if(pc2->nextCol && pc2->nextCol->col > tmp->col){
          lpr2=pr2;                        //       new error //lpr2=lpr;
          tmp->nextRow=lpr2->nextRow;
          pr2->nextRow=tmp;
        } 
      }
    }
    double getElem(int i,int j){
      sparseElem *pc=c+j;
      if(pc==NULL)//if there is no element in matrix returns 0
        return 0;
      while(pc->nextCol!=NULL){
        pc=pc->nextCol;
        if(pc->row==i)
          return pc->value;
        else if(pc->row>i)
          return 0;//if the row has been passed
      }
      return 0;
    }
   
    sparseMatrix *sparseAdd(sparseMatrix &A,sparseMatrix &B){
      sparseMatrix* C=new sparseMatrix(m,n);
      sparseElem *apr=A.head_row;
      while(apr!=NULL){
          sparseElem* ap=apr->nextRow;           
          while(ap){//p!=null
            C->setElem(ap->row,ap->col,A.getElem(ap->row,ap->col));
            ap=ap->nextRow;
          }
          apr=apr->nextCol;
      }
      double value;
      sparseElem *bpr=B.head_row;
      while(bpr!=NULL){
          sparseElem* bp=bpr->nextRow;
          while(bp){//p!=null
            value=C->getElem(bp->row,bp->col)+B.getElem(bp->row,bp->col);
            C->setElem(bp->row,bp->col,value);
            bp=bp->nextRow;
          }
          bpr=bpr->nextCol;
      }
     return C;
    }
    sparseMatrix *sparseMult(sparseMatrix &A,sparseMatrix &B){
      sparseMatrix *C=new  sparseMatrix(A.m,A.n);
      sparseElem *ar=A.head_row;
     
      while(ar){
        sparseElem *r=ar->nextRow;
        sparseElem *bc=B.head_col;
        while(bc){
            //bc=bc->nextRow;
            sparseElem *c=bc->nextCol;
            double value=0;
            while(c && r && c->rowcol)
                c=c->nextCol;
            while(r && c &&  r->colrow)
                r=r->nextRow;
            while(r && c){
              value+=r->value*c->value;
              r=r->nextRow;
              c=c->nextCol;
            }
            if(value)
              C->setElem(ar->row,bc->col,value);
            bc=bc->nextRow;//indexing
            r=ar->nextRow;
        }
        ar=ar->nextCol;
      }
      return C;
    }
};
int main(){
  int m,n;
  cout<<"please enter m,n:"<
  cin>>m>>n;
  sparseMatrix M(m,n);
  sparseMatrix N(m,n);
  double a;
 
  cout<<"please enter two matrix:"<
  for(int i=0;i
    for(int j=0;j
      cin>>a;
      if(a){
        M.setElem(i,j,a);
      }
    }
  cout<
  for(int i=0;i
    for(int j=0;j
      cin>>a;
      if(a){
        N.setElem(i,j,a);
      }
    }
  sparseMatrix *C=M.sparseMult(M,N);
  cout<<"this is multiplaying two matrices:"<
  for(int i=0;i
    for(int j=0;j
      a=C->getElem(i,j);
      cout<<<" ";
    }
  cout<
  }
 
}








11/7/10

Heap sorting Class

Heap Sorting class
template T&  PQueue::min(){
  return heap[0];
}
template T& PQueue ::extractMin(){
  //cout<<"12"<
  if(!heapsize)throw runtime_error(" the priority queue is empty\n");
  T *min=new T;
  //cout<<"13"<
  min[0]=heap[0];
  //cout<<"14"<
  //cout<<"heapsize:"<<
  swap(heap[0],heap[--heapsize]);//heap[0]=heap[heapsize--];
  //cout<<"15"<
  minHeapify(0);
  //cout<<"16"<
  return min[0];

templatevoid PQueue::minHeapify(int i){
  int l=i*2+1;//important indexing from zero
  int r=(i+1)*2;//important indexing from zero
  int lowest;
  //cout<<"17"<
  if(lheap[l]){lowest=l;}
  else {lowest=i;}
  if(rheap[r]){lowest=r;}
  if(lowest!=i){
    //cout<<"21 lowest="<<
    //cout<<<" heap["<<<"]="<<
    //cout<<<<"before tree is:"<
    //print();
    //cout<
    swap(heap[lowest],heap[i]);
    //cout<<"after swap:"<<<" heap["<<<"]="<<
    //cout<<<<"after tree is:"<
    //print();
    //cout<
    //cout<<"22"<
    minHeapify(lowest);
    //cout<<"23"<
  }
}
template void PQueue::swap(T &p,T &q){
  T tmp=p;//code_h tmp
  p=q;
  q=tmp;
}
template void PQueue::Delete(int e){
  if(!heapsize)throw runtime_error(" the priority queue is empty\n");
  T *min=new T;
  swap(heap[e],heap[--heapsize]);//if indexing from 1 for heapsize then:heap[0]=heap[heapsize--];
  minHeapify(e);
}
templatevoid PQueue::increaseKey(int e){
  heap[e]++;
  minHeapify(e);
}
templatevoid PQueue::decreaseKey(int e){
  heap[e]--;
  minHeapify(e);
}
templatevoid PQueue::insert(T &e){
  //cout<<"43"<
  if(heapsize>=n) throw runtime_error("invalid address :you are inserting more than n(size)\n");
  heap[heapsize]=e;//heapsize begin from 0
  buildheap(heapsize++);
}
templatevoid PQueue::insert(T *e){
  //cout<<"53"<
  if(heapsize>=n) throw runtime_error("invalid address :you are inserting more than n(size)\n");
  heap[heapsize]=*e;//heapsize begin from 0
  //cout<<"60"<
  buildheap(heapsize++);
}
templatevoid PQueue::buildheap(int h){
  while(h>0 && heap[h] s=(k-1)/2
      swap(heap[(h-1)/2],heap[h]);
      h=(h-1)/2;
  }
}
templatebool PQueue::empty() const{
  return heap==heap+heapsize;
}
templatevoid PQueue::print() const{
  int i=0;
  cout<<"the elements in the PriorityQueue:"<
  while(i
    cout<<
    i++;
  }
}

11/4/10

Huffman encoding and decoding using template

Huffman encoding  and decoding   using template

 This Hufffman using encoding  and decoding  of characters through iterating   within a  file of text

//in the name of allah
#include
#include
#include
#include"code_char.h"
#include"heap_class.h"
#include"heap.h"

using namespace std;
  int paus;
bool read_file(char* en_words,int *number,list *w){//this template must be used when we add to heap ,PQueue* heap(int * a)=0,int * number=0){
  fstream file;
  file.open(en_words,ios::in);
  if(!file)
    return false;
  //code_ch *w=new code_ch[200];
  file.seekg(0,ios::end);
  int end=file.tellg();
  file.seekg(0,ios::beg);
  int i=0;
  char ch;
  while(i
    file.seekg(i,ios::beg);
    file.read((char*)&ch,1);
    i++;
    //if(ch=='\n' ||  ch=='\13')
      //continue;
//       if(ch=='\13')
//     continue;
    if(!number[ch]){//if is not yet inserted to list
     
      code_ch *tmp=new code_ch;
      number[ch]++;
      tmp->ch=ch;
      tmp->number=number[ch];//later we update this
      w->push_back(*tmp);//w->push_front(tmp);///
    }
    else
      number[ch]++;
  }
  //updateing the numbers
  list::iterator p=w->begin();
  while(p!=w->end()){                                                                             ///point
    p->number=number[p->ch];
    p++;
  }
  //copy(w->begin(),w->end(),ostream_iterator(cout,""));
  return true;
}
code_ch * huffman(PQueue &p,int n){
  code_ch *x;//=new code_ch;
  code_ch *y;//=new code_ch;
  for(int i=1;i
    code_ch *z=new code_ch;
    z->left=x=&p.extractMin();
    z->right=y=&p.extractMin();
    z->number=x->number+y->number;
    p.insert(z);
  }
  return &p.extractMin();
}
//this function finds the code of eeach element in the huffman tree that i create.
void find_code(code_ch *h,int i=-1){///h is root
  i++;
  if(h->left!=NULL){
    for(int k=0;k
      if(h->code[0][k])
    h->left->code[0][k]=true;
      else
    h->left->code[0][k]=false;
    }
    h->left->code[0][i]=false;
    h->left->code_length=h->code_length+1;
    find_code(h->left,i);
  }
  if(h->right!=NULL){
    for(int k=0;k
      if(h->code[0][k])
    h->right->code[0][k]=true;
      else
    h->right->code[0][k]=false;
    }
    h->right->code[0][i]=true;
    h->right->code_length=h->code_length+1;
    find_code(h->right,i);
  }
}
//this function "mirizad" tree in     an array for useing when encodeing from file for each character we can find the element in the tree easily.
code_ch ** inar(code_ch *root){//,int tree_size){
  static code_ch **l=new code_ch*[200];//l[197] points to an element in the tree that its character is 'a'
  l[root->ch]=root;
  if(root->left!=NULL)
     inar(root->left);//,tree_size);
  if(root->right!=NULL)
     inar(root->right);//,tree_size);
  return l;
}
int get_size(code_ch *root){//returns number of bits
   static int size=0;
   if(root->left!=NULL)
     get_size(root->left);
   if(root->right!=NULL)
     get_size(root->right);
   if(!root->left || !root->right)
     size+=root->number*root->code_length;
   return size;//this is number of bits
 }
void encodeing(code_ch *root,char * en_file,code_ch **Arcode,int size){
  //cout<<"coming in incodeing"<
  fstream rfile,wfile;
  rfile.open(en_file,ios::in);
  wfile.open("encoded.txt",ios::out);
  if(!rfile || !wfile)
     throw runtime_error("cannot open the files...\n");
  rfile.seekg(0,ios::end);
  int end=rfile.tellg();
  rfile.seekg(0,ios::beg);
  int i=0,seek=0,j=0;
  char ch;
  //cout<<"declaring A"<
  bitArray A(size);
  //cout<<"this is size="<<
  //cout<<"after"<
  while(i
    rfile.seekg(i,ios::beg);
    rfile.read((char*)&ch,1);
    //cout<<<" ";
    //cout<<" "<
    for(j=0;jcode_length;j++){
      //cout<<"  j="<
      if(Arcode[ch]->code[0][j]){//if true
    //cout<<1;
    //cout<<" "<<1<<" ";
    A[j+seek]=true;
      }
      else{
    //cout<<0;
    //cout<<" 0 ";;
    A[j+seek]=false;
      }
    }
    seek+=j;
    //cout<<<"seek is:"<<
    //cout<
    i++;
  }
  i=0;
  while(i<=size/8+1){
    ch=(char)A.a[i];
    wfile.seekp(i,ios::beg);
    wfile.write(&ch,1);
    i++;
  }
  //wfile.write((char*)&A.a,size/8+1);                    ///point
  //cout<<"in file:"<<
  wfile.close();
  rfile.close();
  //cout<<"file closed"<
}
void inorderWalk(code_ch *root){
  if(root->left!=NULL)
    inorderWalk(root->left);
  cout<ch<<"  "<number<
  if(root->right!=NULL)
    inorderWalk(root->right);
}
void decoding(code_ch *root,int size){//very simple only read from file and if 0 go to left else go to right
//cout<<"coming into decodig"<
//cout<<"--------------------------------------------------size="<<
  code_ch *p=root;
  fstream rfile,wfile;
  rfile.open("encoded.txt",ios::in);
  wfile.open("decoded.txt",ios::out);
  //cout<<"after openning the files"<
  if(!rfile || !wfile)
     throw runtime_error("cannot open the files...\n");
  rfile.seekg(0,ios::end);
  int end=rfile.tellg();
  rfile.seekg(0,ios::beg);
  int i=0,j=0;
  char ch;
  //cout<<"before declaring A"<
  //cout<<"--------------------------------------------------size="<<
  bitArray A(size);
  //cout<<"--------------------------------------------------size="<<
  //cout<<5<
 
  //cout<<"root hehhhhhhhhhhhhhere :"<left->number<
  //cout<<"--------------------------------------------------size="<<
  i=0;
  while(i<=size/8+1){
    rfile.seekg(i,ios::beg);
    rfile.read(&ch,1);
    A.a[i]=(unsigned char)ch;
    i++;
  }
  rfile.seekg(0,ios::beg);
  i=0;
  while(i<=size){//while(!file.eof()){
 //cout<<"in while"<
    if(A[i]){//if it is true go to right
      //cout<<1;
      if(p->right!=NULL)
    p=p->right;
      else {
    wfile.seekp(j,ios::beg);
    wfile.write((char*)&p->ch,1);
    j++;
    p=root;
    continue;///point
      }
    }
    else{
     
      //cout<<"--------------before else"<
      //cout<<0;
      if(p->left!=NULL){
    //cout<<"in if of else"<
    p=p->left;
      }
      else {
    //cout<<"in else of it"<
    wfile.seekp(j,ios::beg);
    wfile.write((char*)&p->ch,1);
    j++;
    p=root;
    continue;///point
      }
     
    }
    i++;
  }
 // cout<<9<
  rfile.close();
  wfile.close();
  //cout<<10<
}
int main(int argc,char **argv){
  if(argc==1){
    cout<<"you haven't entered a file!  exiting..."<
    return 1;
  }
  listw;
  int *a=new int [200];//for saving the number of each ch
  for(int i=0;i<200;i++)
    a[i]=0;
  bool is_read=read_file(argv[1],a,&w);
  if(!is_read)
    throw runtime_error("cannot open the file you entered...\n");
  //cout<<"and the heap"<<
  PQueue p(w);
  code_ch *root=huffman(p,w.size());
  find_code(root);
  int size=get_size(root);
  //cout<<"this is size in the main:"<<
  code_ch ** Arcode=inar(root);//,int tree_size);
  char *coded;
  //cout<<"first puase:"<
  //cin>>paus;
  int paus1;
  encodeing(root,argv[1],Arcode,size);//encodeing(root,argv[1],Arcode,size);
  //cout<<" puase2:"<
  //cin>>paus;
  decoding(root,size);
  cout<<"tamam"<
  //cout<
  return 0;
}