Sparse Array cs115

SparseArray.cpp

#include <string>
#include <iostream>
#include "SparseArray.h"
using namespace std;

SparseArray::SparseArray()
{
    default_value = "";
    headPtr = NULL;
}
SparseArray::~SparseArray()
{
    // assert(invariant());
    clear();
    // printNodes();
    // assert(invariant());
}
SparseArray::SparseArray(const string &default_value1)
{
    default_value = default_value1;
    headPtr = NULL;
}
SparseArray::SparseArray(const SparseArray &to_copy)
{
    // assert(to_copy.invariant());

    headPtr = copyLinkedList(to_copy.headPtr);
    default_value = to_copy.default_value;
    printNodes();
}
// assignment operator
SparseArray &SparseArray::operator=(const SparseArray &to_copy)
{
    // assert(invariant());
    // if current array is inequal to address of array being copied
    if (this != &to_copy)
    {
        default_value = to_copy.default_value;
        headPtr = to_copy.headPtr;
    }
    // always use this at the end of the operator=
    // if you declare it to return ClassName&
    // assert(invariant());
    // printNodes();
    return *this;
}
bool SparseArray::isAnyDefault() const
{
    for (SparseArrayNode const *pNode = headPtr; pNode != NULL; pNode = pNode->next)
    {
        if (pNode->value == default_value)
        {
            return true;
        }
    }
    return false;
}
bool SparseArray::isSorted() const
{
    return true;
}
// const variant
const SparseArrayNode *SparseArray::getExactNode(int index) const
{
    if (headPtr == NULL)
    {
        return NULL;
    }
    for (SparseArrayNode const *pNode = headPtr; pNode != NULL; pNode = pNode->next)
    {
        if (pNode->index == index)
        {
            return pNode;
        }
    }
    return NULL;
}
// non-const variant
SparseArrayNode *SparseArray::getExactNode(int index)
{
    for (SparseArrayNode *pNode = headPtr; pNode != NULL; pNode = pNode->next)
    {
        if (pNode->index == index)
        {
            return pNode;
        }
    }
    return NULL;
}
SparseArrayNode *SparseArray::getPreviousNode(int index)
{
    // if null or current index is greater than head index
    if (headPtr == NULL || headPtr->index >= index)
    {
        return NULL;
    }
    // assign head to cursor
    SparseArrayNode *pNode = headPtr;
    // create temp store
    SparseArrayNode *previous;
    while (pNode != NULL)
    {
        // if index is greater, than previous was less
        if (pNode->index >= index)
        {
            return previous;
        }
        // track previous so it can be returned
        previous = pNode;
        // move to next node
        pNode = pNode->next;
    }
}
SparseArrayNode *SparseArray::copyLinkedList(const SparseArrayNode *pHead) const
{
    if (pHead == NULL)
    {
        return NULL;
    }
    // copy head ptr node
    SparseArrayNode *pHead2 = new SparseArrayNode;
    pHead2->value = pHead->value;
    pHead2->index = pHead->index;
    pHead2->next = NULL;
    // create new list - set to head copy
    SparseArrayNode const *list1 = pHead;
    SparseArrayNode *list2 = pHead2;
    while (list1->next != NULL)
    {
        // allocate new node
        list2->next = new SparseArrayNode;
        // move both cursors
        list1 = list1->next;
        list2 = list2->next;
        // copy values to new list
        list2->value = list1->value;
        list2->index = list1->index;
        // cout << "COPY VAL " << list2->value << endl;
    }
    // point final node to NULL
    list2->next = NULL;
    // return ptr to new list
    return pHead2;
}
bool SparseArray::invariant() const
{
    if (isAnyDefault())
    {
        return false;
    }
    return true;
}
const string &SparseArray::getDefaultValue() const
{
    return default_value;
}
bool SparseArray::isEmpty() const
{
    // assert(invariant());
    if (headPtr != NULL)
    {
        return false;
    }
    // assert(invariant());
    return true;
}
bool SparseArray::isSet(int index) const
{
    // assert(invariant());
    printNodes();
    if (getExactNode(index) == NULL)
    {

        return false;
    }
    // assert(invariant());
    return true;
}
const string &SparseArray::getAt(int index) const
{

    if (getExactNode(index) != NULL)
    {
        return getExactNode(index)->value;
    }
    else
    {
        return default_value;
    }
}
unsigned int SparseArray::getNodeCount() const
{
    // assert(invariant());
    unsigned int count = 0;
    if (headPtr == NULL)
    {
        return count;
    }
    for (SparseArrayNode const *pNode = headPtr; pNode != NULL; pNode = pNode->next)
    {
        // cout << "node count" << count << endl;
        count++;
    }
    // assert(invariant());
    return count;
}
void SparseArray::printNodes() const
{
    // assert(invariant());
    cout << "Nodes: ";
    if (headPtr == NULL)
    {
        cout << "NONE" << endl;
        return;
    }
    else
    {
        cout << "-> ";
        for (SparseArrayNode const *pNode = headPtr; pNode != NULL; pNode = pNode->next)
        {
            cout << "[" << pNode->index << ": ";
            cout << "\"" << pNode->value << "\"";
            cout << "]";
            if (pNode->next != NULL)
            {
                cout << " -> ";
            }
        }
        cout << endl;
    }
    // assert(invariant());
}
void SparseArray::insert(int index, const string &value)
{
    // assert(invariant());
    if (value != default_value)
    {
        // check if node index exists
        SparseArrayNode *existingNode = getExactNode(index);
        // if it does, change the value
        if (existingNode)
        {
            existingNode->value = value;
        }
        else
        {
            // get previous node
            SparseArrayNode *previousNode = getPreviousNode(index);
            if (previousNode)
            {
                SparseArrayNode *s = new SparseArrayNode();
                s->index = index;
                s->value = value;
                // point new node at what previous node pointed to
                s->next = previousNode->next;
                // point previous at new node
                previousNode->next = s;
            }
            else
            // if only one node, so no previous
            {
                SparseArrayNode *s = new SparseArrayNode();
                s->index = index;
                s->value = value;
                s->next = headPtr;
                headPtr = s;
            }
        }
    }
    // assert(invariant());
}
void SparseArray::remove(int index)
{
    // assert(invariant());
    if (headPtr != NULL)
    {
        // get prev node
        SparseArrayNode *previousNode = getPreviousNode(index);
        if (previousNode->next != NULL)
        {
            // assign a new node to rep current
            SparseArrayNode *current = previousNode->next;
            // connect prev to node after current
            previousNode->next = current->next;
            // delete current
            delete current;
        }
    }
    else
    {
        headPtr = NULL;
    }
    // assert(invariant());
}
void SparseArray::clear()
{
    // assert(invariant());
    // SparseArrayNode *pNode = headPtr;
    while (headPtr != NULL)
    {
        // cout << "HEADPTR11 == " << (unsigned long int)(headPtr) << endl;
        // set temp to store memory
        SparseArrayNode *temp = headPtr;
        //    move to next
        headPtr = headPtr->next;
        // cout << "HEADPTR22 == " << (unsigned long int)(headPtr) << endl;
        // temp = 0;
        // if (headPtr != NULL)
        // {
        // cout << "delete temp1  == " << (unsigned long int)(temp) << endl;
        delete temp;
        // cout << "delete temp2  == " << (unsigned long int)(temp) << endl;

        temp = NULL;
        // cout << "delete BELOW  == " << (unsigned long int)(temp) << endl;
        // pNode = NULL;
        // }
    }
    // cout << "delete BELOW  == " << (unsigned long int)(headPtr) << endl;
    // set head to null
    headPtr = NULL;
    // printNodes();
    // assert(invariant());
}

SparseArray.h

#pragma once
#include <string>
using namespace std;

struct SparseArrayNode
{
    int index;
    string value;
    SparseArrayNode *next;
};

class SparseArray
{
private:
    string default_value;
    SparseArrayNode *headPtr;
    bool isAnyDefault() const;
    bool isSorted() const;
    const SparseArrayNode *getExactNode(int index) const;
    SparseArrayNode *getExactNode(int index);
    SparseArrayNode *getPreviousNode(int index);
    SparseArrayNode *copyLinkedList(const SparseArrayNode *p_old_head) const;
    bool invariant() const;

public:
    int number;
    SparseArray();
    SparseArray(const string &default_value1);
    SparseArray(const SparseArray &to_copy);
    ~SparseArray();
    SparseArray &operator=(const SparseArray &to_copy);
    bool isEmpty() const;
    const string &getDefaultValue() const;
    bool isSet(int index) const;
    const string &getAt(int index) const;
    unsigned int getNodeCount() const;
    void printNodes() const;
    void insert(int index, const string &value);
    void remove(int index);
    void clear();
};