/* SortedType.cpp */

#include <iostream>                  /* needed for std I/O */

using namespace std;                 /* ISO/ANSI standards */

#ifndef SORTED_TYPE_CPP              /* g++ bug with template instantiation */
    #include "SortedType.h"          /* the SortedType class */
#endif

/***********************************************************************
 * SortedType() -- default constructor                                 *
 *                                                                     *
 * Parameters                                                          *
 *     none                                                            *
 * Returns                                                             *
 *     none                                                            *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     length is zero and listData is null                             *
 ***********************************************************************/
template <class UserType1, class UserType2>
SortedType<UserType1, UserType2>::SortedType()
{
    length = 0;
    listData = NULL;
    currentPos = NULL;
}

/***********************************************************************
 * ~SortedType() -- default destructor                                 *
 *                                                                     *
 * Parameters                                                          *
 *     none                                                            *
 * Returns                                                             *
 *     none                                                            *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     heap is clean                                                   *
 ***********************************************************************/
template <class UserType1, class UserType2>
SortedType<UserType1, UserType2>::~SortedType() 
{
    MakeEmpty();
}

/***********************************************************************
 * SortedType() -- default copy constructor                            *
 *                                                                     *
 * Parameters                                                          *
 *     SortedType -- the other SortedType                              *
 * Returns                                                             *
 *     none                                                            *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     we have made a deep copy                                        *
 ***********************************************************************/
template <class UserType1, class UserType2>
SortedType<UserType1, UserType2>::SortedType(const SortedType<UserType1,
                                             UserType2> &anotherList)
{
    NodeType<UserType1, UserType2> *ptr1;
    NodeType<UserType1, UserType2> *ptr2;

    /* if anotherList is empty make this one that way too */
    if(anotherList.listData == NULL && anotherList.length == 0 &&
       anotherList.currentPos == NULL)
    {
        listData = NULL;
        currentPos = NULL;
        length = 0;
    }
    else                             /* deep copy into the calling class */
    {
        /* make the new node */
        listData = (NodeType<UserType1, UserType2> *)
                  malloc(sizeof(NodeType<UserType1, UserType2>));
        if(listData == NULL)
        {
            fprintf(stderr, "Heap full\n");
            exit(1);                 /* exit if true */
        }
        listData->variable.MakeEmpty();

        /* copy everything into the new node */
        listData->coefficient = anotherList.listData->coefficient;
        listData->exponent = anotherList.listData->exponent;
        listData->variable = anotherList.listData->variable;

        /* set up our pointers */
        ptr1 = anotherList.listData->next;
        ptr2 = listData;

        while(ptr1 != NULL)          /* loop until the end of original list */
        {
            /* make the new node */
            ptr2->next = (NodeType<UserType1, UserType2> *)
                        malloc(sizeof(NodeType<UserType1, UserType2>));
            if(ptr2->next == NULL)
            {
                fprintf(stderr, "Heap full\n");
                exit(1);             /* exit if true */
            }
            ptr2 = ptr2->next;       /* move right along */
            ptr2->variable.MakeEmpty();

            /* copy everything into the new node */
            ptr2->coefficient = ptr1->coefficient;
            ptr2->exponent = ptr1->exponent;
            ptr2->variable = ptr1->variable;

            ptr1 = ptr1->next;       /* advance the node to copy */
        }

        ptr2->next = NULL;           /* end of list */
    }
}

/***********************************************************************
 * IsFull() -- finds out if the heap is full                           *
 *                                                                     *
 * Parameters                                                          *
 *     none                                                            *
 * Returns                                                             *
 *     bool -- true or false                                           *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     none                                                            *
 ***********************************************************************/
template <class UserType1, class UserType2>
bool SortedType<UserType1, UserType2>::IsFull() const
{
    NodeType<UserType1, UserType2> *tempPtr;

    /* make a new node */
    tempPtr = (NodeType<UserType1, UserType2> *)
              malloc(sizeof(NodeType<UserType1, UserType2>));
    if(tempPtr == NULL)
    {
        return(true);                /* if it fails return true */
    }
    else
    {
        free(tempPtr);               /* remove from heap */
        tempPtr = NULL;              /* be clean about things */
        return(false);               /* return not full */
    }
}

/***********************************************************************
 * LengthIs() -- reports the length of our linked list                 *
 *                                                                     *
 * Parameters                                                          *
 *     none                                                            *
 * Returns                                                             *
 *     int -- the length of our linked list                            *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     none                                                            *
 ***********************************************************************/
template <class UserType1, class UserType2>
int SortedType<UserType1, UserType2>::LengthIs() const
{
    return(length);
}

/***********************************************************************
 * MakeEmpty() -- make list empty and clean up the heap                *
 *                                                                     *
 * Parameters                                                          *
 *     none                                                            *
 * Returns                                                             *
 *     void                                                            *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     heap is clean                                                   *
 ***********************************************************************/
template <class UserType1, class UserType2>
void SortedType<UserType1, UserType2>::MakeEmpty()
{
    NodeType<UserType1, UserType2> *tempPtr;

    /* traverse list, deallocating each node in turn*/
    while (listData != NULL)
    {
        tempPtr = listData;          /* make tempPtr listData */
        listData = listData->next;   /* move listData along */
        free(tempPtr);               /* remove old location from heap */
        tempPtr = NULL;              /* again being clean about things */
    }

    currentPos = NULL;
    length = 0;                      /* all nodes are clean length is zero */
}

/***********************************************************************
 * RetrieveItem() -- Retrieves list element whose key == item's key    *
 *                                                                     *
 * Parameters                                                          *
 *     NodeType<UserType1, UserType2> -- item to compare (pass by ref) *
 *     bool -- whether we found it or not (pass by ref)                *
 * Returns                                                             *
 *     void                                                            *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     If there is an element someItem whose key matches item's key,   *
 *     then found = true and item is a copy of someItem; otherwise     *
 *     found = false and item is unchanged. List is unchanged.         *
 ***********************************************************************/
template <class UserType1, class UserType2>
void SortedType<UserType1, UserType2>::
     RetrieveItem(NodeType<UserType1, UserType2> &item, bool &found)
{
    bool moreToSearch;               /* is there more to search */
    NodeType<UserType1, UserType2> *tempPtr;

    tempPtr = listData;              /* begin at first node */
    found = false;                   /* not found yet */

    /* is this the first and last node */
    moreToSearch = (tempPtr != NULL);

    while (moreToSearch && !found)   /* not at last and not found */
    {
        /* if we are not there yet */
        if (tempPtr->exponent < item.exponent)
        {
            tempPtr = tempPtr->next; /* move right along */

            /* is this the first and last node */
            moreToSearch = (tempPtr != NULL);
        }
        else if(item.exponent == tempPtr->exponent)
        {
            found = true;            /* if we found the item return true */

            /* not sure but isn't item already that */
            item.exponent = tempPtr->exponent;
        }
        else
        {
            moreToSearch = false;    /* gone past where it should be */
        }
    }
}

/***********************************************************************
 * InsertItem() -- Adds item to list.                                  *
 *                                                                     *
 * Parameters                                                          *
 *     NodeType<UserType1, UserType2> -- item to add to the list       *
 * Returns                                                             *
 *     void                                                            *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     item is now in the list                                         *
 ***********************************************************************/
template <class UserType1, class UserType2>
void SortedType<UserType1, UserType2>::
     InsertItem(NodeType<UserType1, UserType2> &item)
{
    /* pointer to node being inserted */
    NodeType<UserType1, UserType2> *newNode;
    /* trailing pointer */
    NodeType<UserType1, UserType2> *predLoc;
    /* traveling pointer */
    NodeType<UserType1, UserType2> *tempPtr;

    bool moreToSearch;               /* is there more to search */

    tempPtr = listData;              /* temporary pointer */
    predLoc = NULL;                  /* start this with NULL */

    /* is the beginning the end */
    moreToSearch = (tempPtr != NULL);

    while (moreToSearch)             /* find place to insert */
    {
        /* if we are not there yet */
        if (tempPtr->exponent < item.exponent)
        {
            predLoc = tempPtr;       /* hold the last place */
            tempPtr = tempPtr->next; /* move forward */

            /* are we at the end of the list yet */
            moreToSearch = (tempPtr != NULL);
        }
        else
        {
            moreToSearch = false;    /* we have gone past our spot */
        }
    }

    if(listData == NULL || !(IsFull()))
    {
        /* Prepare node for insertion */
        newNode = (NodeType<UserType1, UserType2> *)
                  malloc(sizeof(NodeType<UserType1, UserType2>));
        if(newNode == NULL)
        {
            fprintf(stderr, "Heap full\n");
            exit(1);                 /* exit if true */
        }
        newNode->variable.MakeEmpty();

        /* put our item into the new node */
        newNode->exponent = item.exponent;
        newNode->coefficient = item.coefficient;
        newNode->variable = item.variable;

        if (predLoc == NULL)         /* If this is the first location */
        {
            /* put at start of list */
            newNode->next = listData;
            listData = newNode;
        }
        else
        {
            /* insert between two nodes */
            newNode->next = tempPtr;
            predLoc->next = newNode;
        }

        length++;                    /* list just got longer */
    }
}

/***********************************************************************
 * DeleteItem() -- Deletes the element whose key matches item's key.   *
 *                                                                     *
 * Parameters                                                          *
 *     NodeType<UserType1, UserType2> -- item to removed from the list *
 * Returns                                                             *
 *     void                                                            *
 * Precondition                                                        *
 *     Key member of item is initialized.  One and only one element in *
 *     list has a key matching item's key.                             *
 * Postcondition                                                       *
 *     No element in list has a key matching item's key.               *
 ***********************************************************************/
template <class UserType1, class UserType2>
void SortedType<UserType1, UserType2>::
     DeleteItem(NodeType<UserType1, UserType2> item)
{
    NodeType<UserType1, UserType2> *tempPtr;     /* the pointer to find */
    NodeType<UserType1, UserType2> *delPtr;      /* the pointer to delete */

    tempPtr = listData;              /* start at the beginning of list */

    /* locate the node to be removed */
    if (item.exponent == listData->exponent)
    {
        delPtr = tempPtr;            /* if they are equal */
        listData = listData->next;   /* readjust list */
    }
    else                             /* not found yet keep moving */
    {
        /* loop until we find the item  or list ends */
        while(tempPtr->next != NULL &&
            !(item.exponent == (tempPtr->next)->exponent))
        {
            tempPtr = tempPtr->next;
        }

        /* if not the end of list */
        if(tempPtr->next != NULL)
        {
            delPtr = tempPtr->next;  /* this is the one we want */

            /* correct the list */
            tempPtr->next = (tempPtr->next)->next;
        }
        else
        {
            return;                  /* the item to delete was not there */
        }
    }

    free(delPtr);                    /* we shall set you free */
    delPtr = NULL;                   /* fugetaboutit */
    length--;                        /* reduce the list by one */
}

/***********************************************************************
 * ResetList() -- Initializes current position to end of list for      *
 *                iteration through list.                              *
 *                                                                     *
 * Parameters                                                          *
 *     void                                                            *
 * Returns                                                             *
 *     void                                                            *
 * Precondition                                                        *
 *     none                                                            *
 * Postcondition                                                       *
 *     Current position is at end of list.                             *
 ***********************************************************************/
template <class UserType1, class UserType2>
void SortedType<UserType1, UserType2>::ResetList()
{
    currentPos = NULL;
}

/***********************************************************************
 * GetNextItem() -- Gets the next element in list.                     *
 *                                                                     *
 * Parameters                                                          *
 *     NodeType<UserType1, UserType2> -- make item next in list        *
 * Returns                                                             *
 *     void                                                            *
 * Precondition                                                        *
 *     Current position is defined. Element at current position is not *
 *     last in list.                                                   *
 * Postcondition                                                       *
 *     If Current position is at end,  currentPos points to head of    *
 *     list, else item is  copy  of  element at current position.      *
 *     Advance current position.                                       *
 ***********************************************************************/
template <class UserType1, class UserType2>
void SortedType<UserType1, UserType2>::
     GetNextItem(NodeType<UserType1, UserType2> &item)
{
    if (currentPos == NULL)          /* Wrap at end of list */
    {
        currentPos = listData; 
    }

    /* get the item */
    item.exponent = currentPos->exponent;
    item.coefficient = currentPos->coefficient;
    item.variable = currentPos->variable;

    currentPos = currentPos->next;   /* advance currentPos */
}

/***********************************************************************
 * Add() -- adds together poly1 and poly2                              *
 *                                                                     *
 * Parameters                                                          *
 *     SortedType<UserType1, UserType2> -- first one to add            *
 *     SortedType<UserType1, UserType2> -- second one to add           *
 * Returns                                                             *
 *     void                                                            *
 * Precondition                                                        *
 *     calling this is empty eg. this.MakeEmpty                        *
 * Postcondition                                                       *
 *     the sum is constructed                                          *
 ***********************************************************************/
template <class UserType1, class UserType2>
void SortedType<UserType1, UserType2>::
     Add(SortedType<UserType1, UserType2> &poly1,
         SortedType<UserType1, UserType2> &poly2)
{
    int count1 = 1;
    int count2 = 1;
    NodeType<UserType1, UserType2> item1;
    NodeType<UserType1, UserType2> item2;
    NodeType<UserType1, UserType2> newItem;

    /* get the first items from out sorted lists */
    poly1.ResetList();
    poly1.GetNextItem(item1);
    poly2.ResetList();
    poly2.GetNextItem(item2);

    /* loop while both lists have something in them */
    while(poly1.LengthIs() > 0 || poly2.LengthIs() > 0)
    {
        /* if they are the same exponent */
        if(item1.exponent == item2.exponent)
        {
            /* add and insert the new value */
            newItem.exponent = item1.exponent;
            newItem.variable = item1.variable;
            newItem.coefficient = item1.coefficient + item2.coefficient;
            InsertItem(newItem);

            /* now delete that value */
            poly1.DeleteItem(item1);
            count2--;
            poly2.DeleteItem(item2);
            count1--;

            /* if there is something still in the list */
            if(poly1.LengthIs() > 0)
            {
                poly1.ResetList();
                poly1.GetNextItem(item1);
                count2 = 1;          /* reset the counter */
            }
            else
            {
                count2 = -1;         /* make it clear that the list us empty */
            }

            /* if there is something still in the list */
            if(poly2.LengthIs() > 0)
            {
                poly2.ResetList();
                poly2.GetNextItem(item2);
                count1 = 1;          /* reset the counter */
            }
            else
            {
                count1 = -1;         /* make it clear that the list us empty */
            }
        }
        else                         /* if the exponents do not match */
        {
            if(poly2.LengthIs() > 0)
            {
                if(poly2.LengthIs() >= count1)
                {
                    poly2.GetNextItem(item2);
                    count1++;

                    /* if poly1.LengthIs happens to be a longer list */
                    if(poly1.LengthIs() > poly2.LengthIs())
                    {
                        poly1.GetNextItem(item1);
                        count2++;
                    }
                }
            }

            /* clean up the leftovers */
            if(poly1.LengthIs() < count2 || poly2.LengthIs() < count1)
            {
                /* go until both lists are empty */
                while(poly1.LengthIs() > 0 || poly2.LengthIs() > 0)
                {
                    if(poly1.LengthIs() > 0)
                    {
                        poly1.ResetList();
                        poly1.GetNextItem(item1);
                        InsertItem(item1);
                        poly1.DeleteItem(item1);
                    }
                    if(poly2.LengthIs() > 0)
                    {
                        poly2.ResetList();
                        poly2.GetNextItem(item2);
                        InsertItem(item2);
                        poly2.DeleteItem(item2);
                    }
                }
                count1 = -1;         /* be very clear that we are empty */
                count2 = -1;         /* be very clear that we are empty */
            }
        }
    }
}