/*
 *  =================================================================== 
 *  Library of functions to create linked lists of numbers
 *                                                                     
 *  Copyright (C) 1993-96 by Mark Austin and David Mazzoni.
 *                                                                     
 *  This software is provided "as is" without express or implied warranty.
 *  Permission is granted to use this software on any computer system,
 *  and to redistribute it freely, subject to the following restrictions:
 * 
 *  1. The authors are not responsible for the consequences of use of
 *     this software, even if they arise from defects in the software.
 *  2. The origin of this software must not be misrepresented, either
 *     by explicit claim or by omission.
 *  3. Altered versions must be plainly marked as such, and must not
 *     be misrepresented as being the original software.
 *  4. This notice is to remain intact.
 *                                                                    
 *  Written by: M.A. Austin                                  July, 1993
 *  ===================================================================
 */

#include <stdio.h>
#include <math.h>
#include "numlist.h"       /* List Data Structure and functions prototuyes    */
#include "miscellaneous.h" /* Interface to safeMalloc() etc...                */

/* 
 *  ========================================================================== 
 *  listPrint() : Print List of Numbers: Ncol = Number of columns in printout.
 * 
 *  Input  :  char    *cpTitle  -- Title for List Printout.
 *         :  NUMLIST *spList   -- Pointer to beginning of linked list.
 *  Output :  void               
 *  ========================================================================== 
 */ 

enum boolean { True = 1, False = 0 };
enum { Ncol = 3 };

void listPrint( char *cpTitle, NUMLIST *spList ) {
NUMLIST  *spListp;
int       iCount = 0;

  /* [a] : Print list Header */

     printf("NUMERICAL LIST : \"%s\"\n", cpTitle );

  /* [b] : Walk along spList and print items */

     printf("\n               : ");
     if(listEmpty( spList ) == ((int) True))  
        printf(" (NULL) ");
     else {
        for(spListp = spList; spListp != (NUMLIST *) NULL; spListp = spListp->spNext) {
            if( iCount%Ncol == 0 && spListp != spList ) {
                printf("\n               : ");
            }

            iCount += 1;
            printf("%8.3f ", (double) spListp->item);
        }
     }

     printf("\n\n");
}

/* 
 *  ============================================================== 
 *  listEmpty() : Test for Empty Numerical List 
 *  
 *  Input  :  NUMLIST *spList -- Pointer to beginning of linked list.
 *  Output :  int             -- True or False.               
 *  ============================================================== 
 */ 

listEmpty( NUMLIST *spList ) {
    if(spList == NULL)
       return( True );
    else
       return( False );
}

/* 
 *  ================================================================= 
 *  listFree() : Free Memory for List 
 * 
 *  Input  :  NUMLIST *spList -- Pointer to beginning of linked list.
 *  Output :  void
 *  ================================================================= 
 */ 

void listFree( NUMLIST *spList) {
NUMLIST *spListp1, *spListp2;

    /* [a] : Check for Empty List */

    if(spList != NULL) {

       spListp1 = spList->spNext;
       free((char *) spList);

       while(spListp1 != (NUMLIST *) NULL) {
             spListp2 = spListp1->spNext;
             free((char *) spListp1);
             spListp1 = spListp2;
       }
       spList = (NUMLIST *) NULL;

    }
}

/* 
 *  ============================================================== 
 *  listAddItem() : Add Item to Linked List 
 *  
 *  Input  :  NUMLIST *spList -- Pointer to beginning of linked list.
 *         :  ELEMENT item    -- item to be added to linked list.
 *  Output :  NUMLIST *spList -- Pointer to new linked list.
 *  ============================================================== 
 */ 

NUMLIST *listAddItem( NUMLIST *spList, ELEMENT item ) {
NUMLIST *spFirst, *spTp, *spNewItem;

   /* [a] : Add first item to list */

   spFirst = spList;
   if (spFirst == (NUMLIST *) NULL) {
       spList = (NUMLIST *) safeMalloc(sizeof( NUMLIST), __FILE__ , __LINE__ );
       spList->item   = item;
       spList->spNext = (NUMLIST *) NULL;
       return(spList);
   } 

       /* [b] : Walk along list and insert item into appropriate location */
                      
   for (spTp = spFirst; spTp != (NUMLIST *) NULL; spTp = spTp->spNext) {

       /* [b.1] : Check for double items -- do not duplicate items in list */

       if (item == spTp->item) {
           return( spList );
       }

       /* [b.2] : Put item in front of list */

       if (item < spTp->item) {
           spNewItem = (NUMLIST *) safeMalloc( sizeof( NUMLIST ),
                                               __FILE__, __LINE__ );
           spNewItem->item   =    item;
           spNewItem->spNext = spFirst;
           return ( spNewItem );
       }

       /* [b.3] : Add item to rear of list */

       if(item > spTp->item && spTp->spNext == (NUMLIST *) NULL) {
           spTp->spNext = (NUMLIST *) safeMalloc( sizeof( NUMLIST ) ,
                                                  __FILE__, __LINE__ ); 
           spTp->spNext->item   = item;
           spTp->spNext->spNext = (NUMLIST *) NULL;
           return ( spFirst );
       }

       /* [b.4] : Insert item into middle of list */

       if(item > spTp->item && item < spTp->spNext->item) {
           spNewItem = (NUMLIST *) safeMalloc(sizeof( NUMLIST ), __FILE__, __LINE__); 
           spNewItem->item   = item;
           spNewItem->spNext = spTp->spNext;
           spTp->spNext      = spNewItem;
           return ( spFirst );
       }
   }
}

/* 
 *  ============================================================== 
 *  listDeleteItem() : Delete Item from Linked List 
 *  
 *  Input  :  NUMLIST *spList -- Pointer to beginning of linked list.
 *         :  ELEMENT    item -- item to be added to linked list.
 *  Output :  NUMLIST *spList -- Pointer to new linked list.
 *  ============================================================== 
 */ 

NUMLIST *listDeleteItem( NUMLIST *spList, ELEMENT item ) {
NUMLIST *spFirst, *spTp, *spPrev;

       /* [a] : Test for Empty List */

       spFirst = spList;
       if (spFirst == (NUMLIST *) NULL) {
           printf("Cannot Delete Item from Empty List\n");
           return( spList );
       } 

       /* [b] : Walk along list and delete item from appropriate location */
                      
       spPrev = (NUMLIST *) NULL;
       for ( spTp = spFirst; spTp != (NUMLIST *) NULL; spTp = spTp->spNext ) {

            if( item == spTp->item ) {
                if( spPrev == (NUMLIST *) NULL )
                    spFirst = spTp->spNext;
                else 
                    spPrev->spNext = spTp->spNext;

                free((char *) spTp);
                return ( spFirst );
            }
            else
               spPrev = spTp;
       }
}


/* 
 *  ================================================================= 
 *  listIntersection() : Compute Intersection of One Way Linked Lists
 * 
 *  Input  :  NUMLIST * -- Pointer to first linked list.
 *         :  NUMLIST * -- Pointer to second linked list.
 *  Output :  NUMLIST * -- Pointer to "intersection" linked list.
 *  ================================================================= 
 */ 

NUMLIST *listIntersection( NUMLIST *spList1, NUMLIST *spList2 ) {
NUMLIST *spList3 = NULL;

    while( spList1 != NULL && spList2 != NULL ) {
       if( spList1->item == spList2->item) {
           spList3 = listAddItem( spList3, (ELEMENT) spList1->item);
           spList1 = spList1->spNext;
           spList2 = spList2->spNext;
       }
       else {
          if( spList1->item < spList2->item )
              spList1 = spList1->spNext;
          else 
              spList2 = spList2->spNext;
       }
    }

    return( spList3 );
}