#include<iostream.h>
#include<conio.h>
#include<string.h>

 //generic doubly linked list class
class dblink  {
  dblink *next;   //pointer to the next object
  dblink *prior; //pointer to previous object
public:
  dblink()  {
    next=NULL;
    prior=NULL;
  };

  void store(dblink **start,dblink **end);
  void remove(dblink **start,dblink **end);

  dblink *getnext() { return next; }
  dblink *getprior() { return prior; }
};
/*This class inherits dblink class and creates a doubly linked list
 that stores integer arrays consisting of two members each ((x,y))*/
class mylink : public dblink {
  int info[3];
public:
  mylink() { info[0]=info[1]=info[2]=0; }
  mylink(int f,int g,int h) { info[0]=f; info[1]=g; info[2]=h; }

  mylink *selsort();   //make a selection sort on a list

  mylink *find(int d1,int d2,int d3); // find an item

  void change(int f,int g,int h) { info[0]=f; info[1]=g;info[2]=h; }

  int get1() { return info[0]; }
  int get2() { return info[1]; }    //return value
  int get3() { return info[2]; }
  //Overload << for mylink objects
  friend ostream &operator<<(ostream &stream,mylink o)
  {
    stream<<o.info[0];
    stream<<o.info[1];
    stream<<o.info[2];
    return stream;
  }
  //Overload << for mylink pointers
  friend ostream &operator<<(ostream &stream,mylink *o)
  {
    stream<<o->info[0];
    stream<<o->info[1];
    stream<<o->info[2];
    return stream;
  }
  //Overload << for mylink references
  friend istream &operator>>(istream &stream,mylink &o)
  {
    stream >>o.info[0];
    stream >>o.info[1];
    stream >>o.info[2];
    return stream;
  }

  void frwdlist(); //display list in forward direction
  void bkwdlist(); //display list in backward direction
};


//Add the next entry.
void dblink::store(dblink **start,dblink **end)
{
  if(*start==NULL) {  //first element in list
    next=NULL;
    prior=NULL;
    *end=*start=this;
  }
  else { //put on end
    next = NULL;
    prior = *end;
    (*end)->next = this;
    *end=this;
  }
}

 //Delete an object ;update start and end pointers
 void dblink::remove(dblink **start,dblink **end)
 {
   if(prior) {
     prior->next=next;
     if(next)
       next->prior=prior;
     else
       *end=prior;
   }
   else {
     if(next) {
       next->prior=NULL;
       *start=next;
     }
     else  //list now empty
       *start=*end=NULL;
   }
 }

 //Display list in forward direction
 void mylink::frwdlist()
 {
   mylink *temp;

   temp=this;
   do {
     cout <<"{"<< temp->info[0]<<" "<< temp->info[1]<<" "<< temp->info[2]<<"} ";
     temp= (mylink *) temp ->getnext();
   } while(temp);
   cout<<"\n";
 }

// Display the list in backward direction
 void mylink::bkwdlist()
 {
   mylink *temp;

   temp=this;
   do {
     cout <<"{"<< temp->info[0]<<" "<< temp->info[1]<<" "<< temp->info[2]<<"} ";
     temp= (mylink *) temp ->getprior();
   } while(temp);
   cout<<"\n";
 }

 //look for matching info and return pointer to it
 mylink *mylink::find(int d1,int d2,int d3)
 {
   mylink *p;

   p=this;

   while(p) {
     if( (d1==p->info[0])&&(d2==p->info[1])&&(d3==p->info[2]) )return p;
     p=(mylink *) p->getnext();
     }
     return NULL;
 }
//Selection Sort member function  the iterative algorithm
 mylink  *mylink::selsort()
 {
   int temp0,temp1;
   mylink *p;
   mylink *l;
   p=this;
   while(p->getnext())
   {
    temp0=p->info[0];
    for(l=(mylink *) p->getnext();l!=NULL;l= (mylink *) l->getnext())
    {
      if( (l->info[0]) < (p->info[0]) )
      {
	temp1=p->info[0];
	p->info[0]=l->info[0];
	l->info[0]=temp1;
      }
    }
    p= (mylink *) p->getnext();
   }
/*  while (p)
  {
    p= (mylink *) p->getprior();
  }   */
  return(p);
}
void main()
{
  clrscr();
  dblink *start,*end;
  static int vals[]={ 1,2,5,6,3,2,6,3,1,3,10,8,4,-100 };
  start=end=NULL;
  int i;
  mylink *p;

  for(i=0;vals[i]!= (-100);i++)
  {
     p=new mylink(vals[i],0,0);
     p->store(&start,&end);
  }
  cout<<"After insertion"<<"\n";
    p=(mylink *) start;
    p->frwdlist();

  cout<<"After sorting"<<"\n";
  p=(mylink *) p->selsort();
  p->bkwdlist();
  cout<<"\n"<<"Don't look at the zeros ,\n"<<"because I used this class for three dimensional problem";  ;
//  p->frwdlist();
}