Expert: vijayan - 11/24/2008

Question
Hi again :)

I still have some more questions there which I commented on the code.
Also if we were to write a function that sorts an array using our FilePriority , how could we use this is another function?
thank you so much for your time in advance. it's much appreciated as I am preparing myself for a test on my own! it's not easy at all!

template <typename T> void FilePrio::add( const T& t ) {

  Element<T>* previous = 0 ;
  Element<T>* current = head ;

  // we're assuming ascending order so let's say we have 5, 10, 11, 12 and our t is 7
  // which means we have to add it right after 5 so our current in this cause is 5 right?
  // and 5 happens to be the head which means there is no previous so wouldn't our while be wrong?
  // te previous is the element before current, and the next is the one after current right?
     
  while( ( current != NULL ) && ( current->val < t ) ) // ***
  {
     previous = current ;
     current = current->next ;
  }
  
  // at this point current is either 0 (end of list)
  // by the sentence above, do you mean when current is pointing to NULL?
  
  if( current == 0 )
  {// when current = 0 that means the head=0 so this is the cause when the list is empty right?

     // no, if current==0 and previous!=0, the list is not empty.
     // in this case, previous is the last element
    // I guess I'm getting more confused! hehe  in the case just above, isn't previous the first element?!
     
     if( previous != 0 )
           previous->next = new Element<T>( t ) ;

     // else ( current==0 && previous==0 ), the list is empty
     // add the new element as the head
     else head = new Element<T>( t ) ;

  // these statements are not required      
  // current->val=t;
  // previous=0;
  //

  }
  else if( current->val != t )
  {
    previous->next = new Element<T>( t, current ) ; //is that ok that we have 2 args here (t,current)?
                                       // don't we need to define this somewhere?
  }
  else
  {
    // the element is already present
  }
}


Answer
 // let's say we have 5, 10, 11, 12 and our t is 7
template <typename T> void FilePrio::add( const T& t ) {

 Element<T>* previous = 0 ;
 Element<T>* current = head ;

 // at this point previous==NULL, current points to 5     
 // we go through this loop exactly once

 while( ( current != NULL ) && ( current->val < t ) )
 {
    previous = current ; // previous now points to 5
    current = current->next ; current now points to 10
    // current->val (10) is not less than 7, so be come out of this loop
 }
 
 // at this point previous points to 5 and current points to 10
 
 if( current == NULL ) // current is not NULL, so  
 {
    // ...
 }
 else if( current->val != t ) // here, current->val(10) != t(7)  
 {
   // add 7 as next of 5(previous), next of 7 is current(10)
   // the list should have 5, 7, 10, 11, 12 after this
 
   previous->next = new Element<T>( t, current ) ;

   //is that ok that we have 2 args here (t,current)?
   // don't we need to define this somewhere?
  
   // you are right, we need to add a constructor to Element<T>
   // template <typename T> class Element

   //{
   //    public:
   //        Element( const T& t, Element<T>* nxt )
   //                  : val(t), next(nxt){}
   //    ....
   //}
 }

 else // this too does not hold
 {
   // ...
 }
}


 // let's say we have 5, 10, 11, 12 and our t is 25
template <typename T> void FilePrio::add( const T& t ) {

 Element<T>* previous = 0 ;
 Element<T>* current = head ;

 // at this point previous==NULL, current points to 5     
 // we go through this loop four times

 while( ( current != NULL ) && ( current->val < t ) )
 {
    previous = current ; // previous NULL->5->10->11->12
    current = current->next ; current 5->10->11->12->NULL
    // current is NULL after 4 iterations, so be come out of this loop
 }
 
 // at this point previous points to 12 and current is NULL
 
 if( current == NULL ) // here, current is NULL  
 {
    if( previous != 0 ) // this too holds, previous(12) is not NULL

          previous->next = new Element<T>( t ) ;  
          // ie. add the new element at the end
          // to get 5, 10, 11, 12, 25

    else // this does not hold
       // ....
 }

 else if( current->val != t ) // not entered into  
 {
   // ....
 }

 else // this too does not hold
 {
   // ....
 }
}


> a function that sorts an array using our FilePriority , how could we use this is another function?

this is simple.
1. add every element in the array to FilePriority<>.
     FilePriority<> is in sorted order. all we have to do is:
2. make the array empty.
3. loop till  FilePriority<> is empty, each time through the loop:
      pick off the smallest element (head) from FilePriority<> (we have a function to do this) and append it to the array.