Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
6.2 kB
8
Indexable
Never
#include <iostream>
#include <string>
#include "SortedLinkedList.h"
#include "ItemType.h"
#include "ListNode.h"
#include <fstream>

using namespace std;

SortedLinkedList::SortedLinkedList() {
    // OK
    head = NULL;
    currentPos = head;
    lengthOfList = 0;
}

SortedLinkedList::~SortedLinkedList() {
    // ?
    delete head;
    delete currentPos;
    lengthOfList = 0;
}

int SortedLinkedList::length() const {
    // OK
    return lengthOfList;
}

void SortedLinkedList::insertItem(ItemType item) {
    ListNode* newNode; // Pointer to node being inserted
    ListNode* previousLoc; // Trailing pointer
    ListNode* location;
    bool moreToSearch;

    location = head;
    previousLoc = NULL;
    moreToSearch = (location != NULL);

    while (moreToSearch) {
        if (item.compareTo(location->item) == GREATER) {
            // traversing through nodes until it finds the right spot
            previousLoc = location;
            location = location->next;
            moreToSearch = (location != NULL);
        } else if (item.compareTo(location->item) == EQUAL) {
            // else it is found
            moreToSearch = false;
            cout << "Sorry you cannot enter a duplicate item" << endl;
            return;
        } else if (item.compareTo(location->item) == LESS) {
            moreToSearch = false;
        }
    } // while

        newNode = new ListNode();
        newNode->item = item;

        // if the previous node is empty (insert at first element in the list)
        if (previousLoc == NULL) {
            newNode->next = head;
            head = newNode;
        } else {
            newNode->next = location;
            previousLoc->next = newNode;
        }
        lengthOfList++;
}






void SortedLinkedList::deleteItem(ItemType item) {
    // if deleteing something not there, it doesn't work
    ListNode* location = head;
    ListNode* tempLocation;
    int notFound = 1;

    if (notFound == 0) {
        cout << "Item not found" << endl;
    } else {
        // Locate node to be deleted.
        if (item.compareTo(head->item) == EQUAL) {
            tempLocation = location;
            head = head->next;    // Delete first node.
        } else {
            while (item.compareTo((location->next)->item) != EQUAL) {
                location = location->next;
            }

            // Delete node at location->next
            tempLocation = location->next;
            location->next = (location->next)->next;
        }
        delete tempLocation;
        lengthOfList--;
    }
}


int SortedLinkedList::searchItem(ItemType item) {
        bool moreToSearch;
        ListNode* location;
        int index = 0;
        location = head;
        moreToSearch = (location != NULL);

        while (moreToSearch)
        {
            index++;
            switch(item.compareTo(location->item))
            {
                case GREATER:
                    location = location->next;
                    moreToSearch = (location != NULL);
                    break;
                case EQUAL:
                    return index;
                    break;
                case LESS:
                    moreToSearch = false;
                    break;
            }
        }
        //cout << "Item is not found" << endl;
        return -1;
}

ItemType SortedLinkedList::getNextItem() {

    /*
    if (currentPos == NULL) {
        currentPos = head;
        //cout << (currentPos->item).getValue() << "first" << endl;
        return currentPos->item;
    } else {
        currentPos = currentPos->next;
        if (currentPos == NULL) {
            cout << "End of the list has reached." << endl;
        } else {
            //cout << (currentPos->item).getValue() << "second" << endl;
            return currentPos->item;
        }
    }
     */
    if (currentPos == NULL) {
        currentPos = head;
    } else if (currentPos->next == NULL) {
        cout << "Reached end of the list." << endl;
    } else {
        currentPos = currentPos->next;
    }
    return currentPos->item;


}

void SortedLinkedList::resetList() {
    currentPos = NULL;
}

void SortedLinkedList::mergeList(SortedLinkedList list) {
    resetList();
    int length2 = list.length();
    for (int i = 0; i < length2; i++) {
        ItemType a = list.getNextItem();
        insertItem(a);
    }
}

void SortedLinkedList::deleteAlternateNodes() {
    if (head == NULL)
    {
        return;
    }

    ListNode* location = head;
    ListNode* tempLocation = head->next;

    while (location != NULL && tempLocation != NULL)
    {
        lengthOfList--;
        /* Change next link of previous node */
        location->next = tempLocation->next;

        /* Update prev and node */
        location = location->next;
        if (location != NULL)
            tempLocation = location->next;
    }
}

void SortedLinkedList::commonList(SortedLinkedList list) {
    // New list

    SortedLinkedList listt;

    // Making Item Types
    ItemType a;
    ItemType b;

    // a is the calling list
    a = getNextItem();
    // b is the input list
    b = list.getNextItem();

    // length of calling list
    for (int i = 0; i < length(); i++) {
        // length of input list
        for (int j = 0; j < list.length(); j++) {
            // if calling list item is equal to input list item
            if (a.compareTo(b) == EQUAL) {
                 //insert it into the new list?
                 listt.insertItem(a);
            }
            // move onto next item in input list
            b = list.getNextItem();

        }
            // move onto next item in calling list
            a = getNextItem();
            // reset the input list position
            list.resetList();
    }


    list.resetList();
    resetList();
    // prints out element in new list
    cout << "Intersection: ";
    for (int i = 0; i < listt.length(); i++) {
        ItemType a = listt.getNextItem();
        cout << a.getValue() << " ";
    }
    resetList();


    /*
    // use with delete
    resetList();
    cout << "Before" << endl;
    for (int b = 0; b < length(); b++) {
        ItemType a = getNextItem();
        cout << a.getValue() << " ";
    }
    resetList();
     */

    cout << endl;


}