Problems: Sorting:

There are some methods we will have trouble implementing in a generic way. Consider:

1.

The sorting methods do not seem to be useful for the void * lists as it is not clear what we should sort upon.

2.

Searching methods.

    // ********************************************************** //
    // split a chain of VOID_SL_CELLS into the set                //
    // of odd indices and even indices                            //
    // ********************************************************** //
VOID_SL_CELL* VOID_SL_CELL::split(VOID_SL_CELL* A)
{
  //every other element of the chain A is stored in the new
  //chain ``second'' and so A is smaller by about half.
  //output incoming list
  int diagnostic = 0;
  
  if(diagnostic==1)
    cout << "split called on ";
  if(A!=NULL){
    VOID_SL_CELL *temp;
    temp = A;
    while(!(temp==NULL)){
      if(diagnostic==1)
        cout << *temp;
      temp = temp->next;
      }
    if(diagnostic==1)
      cout << endl;
    }
  else{
    if(diagnostic==1)
      cout << "NULL." << endl;
    }
  VOID_SL_CELL *temp1,*temp2;
  temp1 = A;
  if(temp1==NULL) return (NULL);
  else if(temp1->next==NULL) return (NULL);
  else{
    temp2 = temp1->next;
    temp1->next = temp2->next;
    temp2->next = split(temp2->next);
    return(temp2);
    }
}
    // ********************************************************** //
    // merge 2 chains of VOID_SL_CELLS into one chain             //
    // of odd indices and even indices                            //
    // ********************************************************** // 
VOID_SL_CELL* VOID_SL_CELL::merge(VOID_SL_CELL* A1,VOID_SL_CELL* A2)
{
  //output incoming list
  int diagnostic = 0;
  if(diagnostic==1)
    cout << "merge called on ";
  if(A1!=NULL){
    VOID_SL_CELL *temp;
    temp = A1;
    while(!(temp==NULL)){
      if(diagnostic==1)
        cout << *temp;
      temp = temp->next;
      }
    if(diagnostic==1)
      cout << "  ";
    }
  else{
    if(diagnostic==1)
      cout << "NULL  ";
    }
  if(diagnostic==1)
    cout << "and ";
  if(A2!=NULL){
    VOID_SL_CELL *temp;
    temp = A2;
    while(!(temp==NULL)){
      if(diagnostic==1)
        cout << *temp;
      temp = temp->next;
      }
    if(diagnostic==1)
      cout << endl;
    }
  else{
    if(diagnostic==1)
      cout << "NULL  " << endl;
    }

  VOID_SL_CELL *temp1,*temp2;
  temp1 = A1;
  temp2 = A2;
  if(temp1==NULL){
    return(temp2);
    }
  if(temp2==NULL){
    return(temp1);
    }
  if(element_access->lte(temp1->element,temp2->element)){
    //if we knew what the elements were we could say
      //if(temp1->element <= temp2->element)
    //but we must use the access methods
    //
    //Neither list is empty and A1 has smaller
    //first element than A2. So new list is
    //first element of A1 followed by a merge of remaining
    //elements
    temp1->next = merge(temp1->next,temp2);
    return(temp1);
    }
  else{
    temp2->next = merge(temp1,temp2->next);
    return(temp2);
    }
}

    // ************************************ //
    // mergesort a chain of VOID_SL_CELLs   //
    // ************************************ //
VOID_SL_CELL* VOID_SL_CELL::mergesort(VOID_SL_CELL* A)
{
  int diagnostic = 0;
  VOID_SL_CELL *temp1,*temp2;
  temp1 = A;
  
  //output incoming list
  if(diagnostic==1)
    cout << "mergesort called on ";
  if(A!=NULL){
    VOID_SL_CELL *temp;
    temp = A;
    while(!(temp==NULL)){
      if(diagnostic==1)
        cout << *temp;
      temp = temp->next;
      }
    if(diagnostic==1)
      cout << endl;
    }
  else{
    if(diagnostic==1)
      cout << "NULL" << endl;
    }
  if(temp1==NULL) return NULL;
  else if (temp1->next==NULL) return temp1; 
  else{
    //at least 2 elements in list
    temp2 = split(temp1);
    return merge(mergesort(temp1),mergesort(temp2));
    }
}
    // ************************************ //
    //      merge sort for VOID_SLLIST      //
    // ************************************ //
void VOID_SLLIST::mergesort()
{
   head = head->mergesort(head); 
}