Question

C++ Error. I'm having trouble with a pointer. I keep getting the error "Thread 1: EXC_BAD_ACCESS (code=1, address=0x18)"

The objective of the assignment is to revise the public method add in class template LinkedBag so that the new node is inserted at the end of the linked chain instead of at the beginning.

This is the code I have:

linkedBag-driver.cpp

int main) LinkedBag<string> bag; cout << "Testing array-based Set:" << endl; cout << "The initial bag is empty." << endl; cout << "isEmpty: returns "<< bag.isEmpty() << "; should be 1 (true)" << endl; display (bag); string items [ ] = {"one", "two", "three", "four", cout << "Add 5 items to the bag: "<s endl; for (int i 0; i < 5; i++) "one"); bag .hdd (Items [1] ) ; Thread 1: EXC_BAD_ACCESS (code-1, address-0x18) // end for display(bag) cout << "isEmpty: returns "<< bag.isEmpty << "; should be 0 (false)"< endl; cout << "getCurrentSize: returns " << bag.getCurrentSize() <<should be 5" << endl; //Remove random entry from bag cout << "remove): returns:"<<bag.remove)<"should be 1 (true) " <<endl; cout << "contains(\"three\") returns "<< bag.contains("three") << "; should be 1 (true)" << endl; cout << "remove("twol"):returns "<<bag.remove("two") <should be 1 (true)" << endl; cout << "remove(\ "two\"): returns "<< bag.remove("two") << "; should be 0 (false)"<< endl; cout << endl; display (bag); cout <<"After clearing the bag," bag.clear); cout <<"isEmpty: returns "<< bag.isEmpty() << "; should be 1 (true)" << endl; return 0; // end main

BagInterface.hpp

LinkedBag.hpp

Node.hpp

Answer 1

main.cpp

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

void display(LinkedBag<string>& bag)
{
    cout << "The bag contains " << bag.getCurrentSize()
         << " items:" << endl;
    vector<string> bagItems = bag.toVector();

    int numberOfEntries = static_cast<int>(bagItems.size());
    for (int i = 0; i < numberOfEntries; i++)
    {
        cout << bagItems[i] << " ";
    } // end for
    cout << endl << endl;
} // end displaySet

int main()
{
    LinkedBag<string> bag;
    cout << "Testing array-based Set:" << endl;
    cout << "The initial bag is empty." << endl;
    cout << "isEmpty: returns " << bag.isEmpty()
         << "; should be 1 (true)" << endl;
    display(bag);

    string items[] = {"one", "two", "three", "four", "one"};
    cout << "Add 5 items to the bag: " << endl;
    for (int i = 0; i < 5; i++)
    {
        bag.add(items[i]);
    } // end for

    display(bag);

    cout << "isEmpty: returns " << bag.isEmpty()
         << "; should be 0 (false)" << endl;

    cout << "getCurrentSize: returns " << bag.getCurrentSize()
         << "; should be 5" << endl;

    cout << "contains(\"three\"): returns " << bag.contains("three")
         << "; should be 1 (true)" << endl;
    cout << "remove(\"two\"): returns " << bag.remove("two")
         << "; should be 1 (true)" << endl;
    cout << "remove(\"two\"): returns " << bag.remove("two")
         << "; should be 0 (false)" << endl;
    cout << endl;

    display(bag);

    cout << "remove(): returns " << bag.remove()
         << ": should be 1 (true)" << endl;
    display(bag);

    cout << "After clearing the bag, ";
    bag.clear();

    cout << "isEmpty: returns " << bag.isEmpty()
         << "; should be 1 (true)" << endl;

    return 0;
} // end main

BagInterface.h

#ifndef COSC2415_BAGINTERFACE_H
#define COSC2415_BAGINTERFACE_H

#include <vector>

template<class ItemType>
class BagInterface
{
public:
    /** Gets the current number of entries in this bag.
     @return The integer number of entries currently in the bag. */
    virtual int getCurrentSize() const = 0;

    /** Sees whether this bag is empty.
     @return True if the bag is empty, or false if not. */
    virtual bool isEmpty() const = 0;

    /** Adds a new entry to this bag.
     @post If successful, newEntry is stored in the bag and
        the count of items in the bag has increased by 1.
     @param newEntry The object to be added as a new entry.
     @return True if addition was successful, or false if not. */
    virtual bool add(const ItemType& newEntry) = 0;

    /** Removes one occurrence of a given entry from this bag,
        if possible.
     @post If successful, anEntry has been removed from the bag
        and the count of items in the bag has decreased by 1.
     @param anEntry The entry to be removed.
     @return True if removal was successful, or false if not. */
    virtual bool remove(const ItemType& anEntry) = 0;

    /** Removes a random node from the bag.
     * @post If successful, a random entry is removed from the bag
     * and the count of items in the bag has decreased by 1.
     * @return True if removal was successful, or false if not
     */
    virtual bool remove() = 0;

    /** Removes all entries from this bag.
     @post Bag contains no items, and the count of items is 0. */
    virtual void clear() = 0;

    /** Counts the number of times a given entry appears in bag.
     @param anEntry The entry to be counted.
     @return The number of times anEntry appears in the bag. */
    virtual int getFrequencyOf(const ItemType& anEntry) const = 0;

    /** Tests whether this bag contains a given entry.
     @param anEntry The entry to locate.
     @return True if bag contains anEntry, or false otherwise. */
    virtual bool contains(const ItemType& anEntry) const = 0;

    /** Empties and then fills a given vector with all entries that
        are in this bag.
     @return A vector containing all the entries in the bag. */
    virtual std::vector<ItemType> toVector() const = 0;

    /** Destroys object and frees memory allocated by object.
     (See C++ Interlude 2) */
    virtual ~BagInterface () { }

}; // end BagInterface

#endif //COSC2415_BAGINTERFACE_H

LinkedBag.h

#ifndef COSC2415_LINKEDBAG_H
#define COSC2415_LINKEDBAG_H

#include "BagInterface.h"
#include "Node.h"

template<class ItemType>
class LinkedBag : public BagInterface<ItemType>
{
private:
    Node<ItemType>* headPtr; // Pointer to first node
    int itemCount;           // Current count of bag items

    // Returns either a pointer to the node containing a given entry
    // or the null pointer if the entry is not in the bag.
    Node<ItemType>* getPointerTo(const ItemType& target) const;

public:
    LinkedBag();
    LinkedBag(const LinkedBag<ItemType>& aBag); // Copy constructor
    virtual ~LinkedBag();                       // Destructor should be virtual
    int getCurrentSize() const;
    bool isEmpty() const;
    bool add(const ItemType& newEntry);
    bool remove(const ItemType& anEntry);
    bool remove();
    void clear();
    bool contains(const ItemType& anEntry) const;
    int getFrequencyOf(const ItemType& anEntry) const;
    std::vector<ItemType> toVector() const;
}; // end LinkedBag

#include "Node.h"
#include <cstddef>
#include <cstdlib>

template<class ItemType>
LinkedBag<ItemType>::LinkedBag() : headPtr(nullptr), itemCount(0)
{
} // end default constructor

template<class ItemType>
LinkedBag<ItemType>::LinkedBag(const LinkedBag<ItemType>& aBag)
{
    itemCount = aBag.itemCount;
    Node<ItemType>* origChainPtr = aBag.headPtr; // Points to nodes in original chain

    if (origChainPtr == nullptr)
        headPtr = nullptr; // Original bag is empty
    else
    {
        // Copy first node
        headPtr = new Node<ItemType>();
        headPtr->setItem(origChainPtr->getItem());

        // Copy remaining nodes
        Node<ItemType>* newChainPtr = headPtr;      // Points to last node in new chain
        origChainPtr = origChainPtr->getNext();     // Advance original-chain pointer

        while (origChainPtr != nullptr)
        {
            // Get next item from original chain
            ItemType nextItem = origChainPtr->getItem();

            // Create a new node containing the next item
            Node<ItemType>* newNodePtr = new Node<ItemType>(nextItem);

            // Link new node to end of new chain
            newChainPtr->setNext(newNodePtr);

            // Advance pointer to new last node
            newChainPtr = newChainPtr->getNext();

            // Advance original-chain pointer
            origChainPtr = origChainPtr->getNext();
        } // end while

        newChainPtr->setNext(nullptr);              // Flag end of chain
    } // end if
} // end copy constructor

template<class ItemType>
LinkedBag<ItemType>::~LinkedBag()
{
    clear();
} // end destructor

template<class ItemType>
bool LinkedBag<ItemType>::isEmpty() const
{
    return itemCount == 0;
} // end isEmpty

template<class ItemType>
int LinkedBag<ItemType>::getCurrentSize() const
{
    return itemCount;
} // end getCurrentSize

template<class ItemType>
bool LinkedBag<ItemType>::add(const ItemType& newEntry)
{
    Node<ItemType>* newNodePtr = new Node<ItemType>();
    newNodePtr->setItem(newEntry);
    newNodePtr->setNext(nullptr);

    if (isEmpty()) {
        headPtr = newNodePtr;
    } else {
        Node<ItemType> *lastNodePtr = headPtr;
        Node<ItemType> *nextNodePtr;
        while (true) {
            nextNodePtr = lastNodePtr->getNext();
            if (nextNodePtr == nullptr) {
                break;
            }
            lastNodePtr = nextNodePtr;
        }

        // Set old last Node next to new Node
        lastNodePtr->setNext(newNodePtr);
    }

    itemCount++;

    return true;
} // end add

template<class ItemType>
std::vector<ItemType> LinkedBag<ItemType>::toVector() const
{
    std::vector<ItemType> bagContents;
    Node<ItemType>* curPtr = headPtr;
    int counter = 0;
    while ((curPtr != nullptr) && (counter < itemCount))
    {
        bagContents.push_back(curPtr->getItem());
        curPtr = curPtr->getNext();
        counter++;
    } // end while

    return bagContents;
} // end toVector

template<class ItemType>
bool LinkedBag<ItemType>::remove(const ItemType& anEntry)
{
    Node<ItemType>* entryNodePtr = getPointerTo(anEntry);
    bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);
    if (canRemoveItem)
    {
        // Copy data from first node to located node
        entryNodePtr->setItem(headPtr->getItem());

        // Delete first node
        Node<ItemType>* nodeToDeletePtr = headPtr;
        headPtr = headPtr->getNext();

        // Return node to the system
        nodeToDeletePtr->setNext(nullptr);
        delete nodeToDeletePtr;
        nodeToDeletePtr = nullptr;

        itemCount--;
    } // end if

    return canRemoveItem;
} // end remove

template<class ItemType>
bool LinkedBag<ItemType>::remove() {

    bool canRemoveItem = !isEmpty();

    if (canRemoveItem) {
        // Seed rand()
        srand(time(0));
        int itemToRemove = rand() % itemCount;

        // Remove the random node
        if (itemToRemove == 0 ) {
            Node<ItemType>* nextNode = headPtr->getNext();
            delete headPtr;
            headPtr = nextNode;
        } else {
            // Find the node previous to the one to delete
            int i = 0;
            Node<ItemType>* prevNode = headPtr;
            while (i < itemToRemove - 1) {
                prevNode = prevNode->getNext();
                i++;
            }

            // Find the node after the one to delete. If node to delete is last, it'll be nullptr
            Node<ItemType>* nodeToRemove = prevNode->getNext();
            Node<ItemType>* nextNode = nodeToRemove->getNext();

            prevNode->setNext(nextNode);
            delete nodeToRemove;
        }

        itemCount--;
    }

    return canRemoveItem;
}

template<class ItemType>
void LinkedBag<ItemType>::clear()
{
    Node<ItemType>* nodeToDeletePtr = headPtr;
    while (headPtr != nullptr)
    {
        headPtr = headPtr->getNext();

        // Return node to the system
        nodeToDeletePtr->setNext(nullptr);
        delete nodeToDeletePtr;

        nodeToDeletePtr = headPtr;
    } // end while
    // headPtr is nullptr; nodeToDeletePtr is nullptr

    itemCount = 0;
} // end clear

template<class ItemType>
int LinkedBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
{
    int frequency = 0;
    int counter = 0;
    Node<ItemType>* curPtr = headPtr;
    while ((curPtr != nullptr) && (counter < itemCount))
    {
        if (anEntry == curPtr->getItem())
        {
            frequency++;
        } // end if

        counter++;
        curPtr = curPtr->getNext();
    } // end while

    return frequency;
} // end getFrequencyOf

template<class ItemType>
bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
{
    return (getPointerTo(anEntry) != nullptr);
} // end contains

// private
// Returns either a pointer to the node containing a given entry
// or the null pointer if the entry is not in the bag.
template<class ItemType>
Node<ItemType>* LinkedBag<ItemType>::getPointerTo(const ItemType& anEntry) const
{
    bool found = false;
    Node<ItemType>* curPtr = headPtr;

    while (!found && (curPtr != nullptr))
    {
        if (anEntry == curPtr->getItem())
            found = true;
        else
            curPtr = curPtr->getNext();
    } // end while

    return curPtr;
} // end getPointerTo
#endif //COSC2415_LINKEDBAG_H

Node.h

#ifndef COSC2415_NODE_H
#define COSC2415_NODE_H

template<class ItemType>
class Node
{
private:
    ItemType        item; // A data item
    Node<ItemType>* next; // Pointer to next node

public:
    Node();
    Node(const ItemType& anItem);
    Node(const ItemType& anItem, Node<ItemType>* nextNodePtr);
    void setItem(const ItemType& anItem);
    void setNext(Node<ItemType>* nextNodePtr);
    ItemType getItem() const ;
    Node<ItemType>* getNext() const ;
}; // end Node

//#include <cstddef>

template<class ItemType>
Node<ItemType>::Node() : next(nullptr)
{
} // end default constructor

template<class ItemType>
Node<ItemType>::Node(const ItemType& anItem) : item(anItem), next(nullptr)
{
} // end constructor

template<class ItemType>
Node<ItemType>::Node(const ItemType& anItem, Node<ItemType>* nextNodePtr) :
        item(anItem), next(nextNodePtr)
{
} // end constructor

template<class ItemType>
void Node<ItemType>::setItem(const ItemType& anItem)
{
    item = anItem;
} // end setItem

template<class ItemType>
void Node<ItemType>::setNext(Node<ItemType>* nextNodePtr)
{
    next = nextNodePtr;
} // end setNext

template<class ItemType>
ItemType Node<ItemType>::getItem() const
{
    return item;
} // end getItem

template<class ItemType>
Node<ItemType>* Node<ItemType>::getNext() const
{
    return next;
} // end getNext
#endif //COSC2415_NODE_H