//******************************************************************
// IMPLEMENTATION FILE (Hybrid.cpp)
// This file implements the HybridList class member functions
// List representation: a linked list of dynamic nodes
//******************************************************************
#include "HybridList.h"
#include <iostream>
#include <cstddef>     // For NULL

using namespace std;

typedef NodeType* NodePtr;
struct NodeType
{
    ComponentType component;
    NodePtr       link;
};

// Private members of class:
//     int length;		length of the list	
//     NodePtr currPtr;		Can be used for the iterator
//     NodePtr head;            External pointer to linked list

//******************************************************************

HybridList::HybridList()

// Constructor

// Postcondition:
//     head == NULL

{
    head = NULL;
}

//******************************************************************

HybridList::HybridList( const HybridList& otherList )

// Copy-constructor

// Postcondition:
//     IF otherList.head == NULL  (i.e., the other list is empty)
//         head == NULL
//     ELSE
//         head points to a new linked list that is a copy of
//         the linked list pointed to by otherList.head

{
    NodePtr fromPtr;    // Pointer into list being copied from
    NodePtr toPtr;      // Pointer into new list being built

    if (otherList.head == NULL)
    {
        head = NULL;
        return;
    }

    // Copy first node

    fromPtr = otherList.head;
    head = new NodeType;
    head->component = fromPtr->component;

    // Copy remaining nodes

    toPtr = head;
    fromPtr = fromPtr->link;
    while (fromPtr != NULL)
    {
        toPtr->link = new NodeType;
        toPtr = toPtr->link;
        toPtr->component = fromPtr->component;
        fromPtr = fromPtr->link;
    }
    toPtr->link = NULL;
}

//******************************************************************

HybridList::~HybridList()

// Destructor

// Postcondition:
//     All linked list nodes have been deallocated from free store

{
    ComponentType temp;    // Temporary variable

    while ( !IsEmpty() )
        RemoveFirst(temp);
}

//******************************************************************

bool HybridList::IsEmpty() const

// Postcondition:
//     Function value == true, if head == NULL
//                    == false, otherwise

{
    return (head == NULL);
}

//******************************************************************

void HybridList::Print() const

// Postcondition:
//     component members of all nodes (if any) in linked list
//     have been output

{
    NodePtr currPtr = head;    // Loop control pointer

    while (currPtr != NULL)
    {
        cout << currPtr->component << endl;
        currPtr = currPtr->link;
    }
}

//******************************************************************

void HybridList::InsertAsFirst( /* in */ ComponentType item )

// Precondition:
//     component members of list nodes are in ascending order
//  && item < component member of first list node
// Postcondition:
//     New node containing item is at top of linked list
//  && component members of list nodes are in ascending order

{
    NodePtr newNodePtr = new NodeType;    // Temporary pointer

    newNodePtr->component = item;
    newNodePtr->link = head;
    head = newNodePtr;
}

//******************************************************************

void HybridList::Insert( /* in */ ComponentType item )

// Precondition:
//     component members of list nodes are in ascending order
//  && item is assigned
// Postcondition:
//     New node containing item is in its proper place
//       in linked list
//  && component members of list nodes are in ascending order

{
    NodePtr currPtr;       // Moving pointer
    NodePtr prevPtr;       // Pointer to node before *currPtr
    NodePtr newNodePtr;    // Pointer to new node

    // Set up node to be inserted

    newNodePtr = new NodeType;
    newNodePtr->component = item;

    // Find previous insertion point

    prevPtr = NULL;
    currPtr = head;
    while (currPtr != NULL && item > currPtr->component)
    {
        prevPtr = currPtr;
        currPtr = currPtr->link;
    }

    // Insert new node

    newNodePtr->link = currPtr;
    if (prevPtr == NULL)
        head = newNodePtr;
    else
        prevPtr->link = newNodePtr;
}

//******************************************************************

void HybridList::RemoveFirst( /* out */ ComponentType& item )

// Precondition:
//     Linked list is not empty (head != NULL)
//  && component members of list nodes are in ascending order
// Postcondition:
//     item == component member of first list node at entry
//  && Node containing item is no longer in linked list
//  && component members of list nodes are in ascending order

{
    NodePtr tempPtr = head;    // Temporary pointer

    item = head->component;
    head = head->link;
    delete tempPtr;
}

//******************************************************************

void HybridList::Delete( /* in */ ComponentType item )

// Precondition:
//     item == component member of some list node
//  && component members of list nodes are in ascending order
// Postcondition:
//     Node containing first occurrence of item is no longer in
//       linked list
//  && component members of list nodes are in ascending order

{
    NodePtr delPtr;     // Pointer to node to be deleted
    NodePtr currPtr;    // Loop control pointer

    // Check if item is in first node

    if (item == head->component)
    {
        // Delete first node

        delPtr = head;
        head = head->link;
    }
    else
    {
        // Search for node in rest of list

        currPtr = head;
        while (currPtr->link->component != item)
            currPtr = currPtr->link;

        // Delete *(currPtr->link)

        delPtr = currPtr->link;
        currPtr->link = currPtr->link->link;
    }
    delete delPtr;
}