#include<iostream.h>
// the next include is needed for ifstream
#include<fstream.h>
// the next include is needed for exit.
#include<stdlib.h>
// the next include is needed for strtok
#include<strings.h>

// MoveToFront.C
// burton rosenberg 22 April 1997
// adapted from UniqueCount.C of same date,
// to use mode-to-front heuristic for linked lists.


// Changes are marked in comments ADDED

char * DELIMIT = " \t\n" ;

// -------------------------------------------------

struct Node {
   char * word ;
   int count ;
   Node * next ;
} ;

// ADDED to UniqueCount.C
void moveToFront( Node * ll, Node * n ) {
   // move n to front of ll
   if ( n==NULL || n->next==NULL) return ; // bad arguments
   Node * nn = n->next ;
   n->next = nn->next ;
   nn->next = ll->next ;
   ll->next = nn ; 
}
// END ADD.

Node * createLinkedList() {
   // create dummy header
   Node *  n = new Node ;
   n->next = NULL ;
   n->count = 0 ;
   n->word = NULL ;
   return n ;
}

void addLinkedList( Node * ll, char * w ) {

  char * s = new char[strlen(w)+1] ;
  Node * n = new Node ;
  n->word = strcpy( s, w ) ;
  n->next = ll->next ;
  ll->next = n ;
  n->count = 1 ;

}

Node * findLinkedList( Node * ll, char * w ) {
    Node * tp = ll ;
    ll = ll->next ;
    // LI: ll points to next to check, tp->next = ll
    while ( ll != NULL && strcmp( w, ll->word ) != 0 ) {
       tp = ll ;
       ll = ll->next ;
    }
    return (tp->next==NULL) ? NULL : tp ;
}

int incrementCount( Node * ll, Node * n ) {
    if ( n==NULL || n->next==NULL ) return 0 ;
    return ++(n->next->count) ;
}

void printLinkedList( Node * ll ) {
   ll = ll->next ;
   while ( ll!=NULL ) {
      cout << ll->count << ": " << ll->word << endl ;
      ll = ll->next ;
   }
}

// -------------------------------------------------

void processWord( Node * ll, char * oneWord ) 
{
   // oneWord is the word to process, ll is the linked list
   Node * n = findLinkedList( ll, oneWord ) ;

   if ( n != NULL ) {
      incrementCount( ll, n ) ;
      moveToFront( ll, n ) ;   // ADDED to UniqueCount.C
   }
   else {
      addLinkedList( ll, oneWord ) ;
   }
}

void processLine( Node * ll, char * line )
{
   char * aWord ;
   aWord = strtok( line, DELIMIT ) ;
   // work word by word
   while  (aWord!=NULL)
   {
      processWord( ll, aWord ) ;
      aWord = strtok( NULL, DELIMIT ) ;
   }
}

void bailOut( char * progName ) 
{
   cout << "usage: " << progName  << " filename" << endl ;
   exit(-1) ;
}

int main( int argc, char * argv[] ) 
{
   ifstream ifs ;
   const int BUFFER_N = 500 ;
   char buffer[BUFFER_N] ;

   if ( argc<2 ) 
   {
      bailOut( argv[0] ) ;
   }

   ifs.open(argv[1]) ;
   if ( ! ifs ) {
      bailOut( argv[0] ) ;
   }

   Node * myLL = createLinkedList() ;

   // work line by line
   while ( ifs.getline(buffer, BUFFER_N) )
   {
      processLine( myLL, buffer ) ;
   } 
   ifs.close() ;  

   printLinkedList( myLL ) ;

   exit(0) ;

}