1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: /** ADT bag: Link-based implementation.
5: @file LinkedBag.cpp */
7: #include "LinkedBag.h"
8: #include "Node.h"
9: #include <cstddef>
11: template<class ItemType>
12: LinkedBag<ItemType>::LinkedBag() : headPtr(nullptr), itemCount(0)
13: {
14: } // end default constructor
16: template<class ItemType>
17: LinkedBag<ItemType>::LinkedBag(const LinkedBag<ItemType>& aBag)
18: {
19: itemCount = aBag->itemCount;
20: Node<ItemType>* origChainPtr = aBag->headPtr; // Points to nodes in original chain
21:
22: if (origChainPtr == nullptr)
23: headPtr = nullptr; // Original bag is empty; so is copy
24: else
25: {
26: // Copy first node
27: headPtr = new Node<ItemType>();
28: headPtr->setItem(origChainPtr->getItem());
29:
30: // Copy remaining nodes
31: Node<ItemType>* newChainPtr = headPtr; // Last-node pointer
32: while (origChainPtr != nullptr)
33: {
34: origChainPtr = origChainPtr ->getNext(); // Advance pointer
35:
36: // Get next item from original chain
37: ItemType nextItem = origChainPtr->getItem();
38:
39: // Create a new node containing the next item
40: Node<ItemType>* newNodePtr = new Node<ItemType>(nextItem);
41:
42: // Link new node to end of new chain
43: newChainPtr->setNext(newNodePtr);
44:
45: // Advance pointer to new last node
46: newChainPtr = newChainPtr->getNext();
47: } // end while
48:
49: newChainPtr->setNext(nullptr); // Flag end of new chain
50: } // end if
51: } // end copy constructor
53: template<class ItemType>
54: LinkedBag<ItemType>::~LinkedBag()
55: {
56: clear();
57: } // end destructor
59: template<class ItemType>
60: bool LinkedBag<ItemType>::isEmpty() const
61: {
62: return itemCount == 0;
63: } // end isEmpty
65: template<class ItemType>
66: int LinkedBag<ItemType>::getCurrentSize() const
67: {
68: return itemCount;
69: } // end getCurrentSize
71: template<class ItemType>
72: bool LinkedBag<ItemType>::add(const ItemType& newEntry)
73: {
74: // Add to beginning of chain: new node references rest of chain;
75: // (headPtr is null if chain is empty)
76: Node<ItemType>* nextNodePtr = new Node<ItemType>();
77: nextNodePtr->setItem(newEntry);
78: nextNodePtr->setNext(headPtr); // New node points to chain
79: // Node<ItemType>* nextNodePtr = new Node<ItemType>(newEntry, headPtr); // alternate code
81: headPtr = nextNodePtr; // New node is now first node
82: itemCount++;
83:
84: return true;
85: } // end add
87: template<class ItemType>
88: vector<ItemType> LinkedBag<ItemType>::toVector() const
89: {
90: vector<ItemType> bagContents;
91: Node<ItemType>* curPtr = headPtr;
92: int counter = 0;
93: while ((curPtr != nullptr) && (counter < itemCount))
94: {
95: bagContents.push_back(curPtr->getItem());
96: curPtr = curPtr->getNext();
97: counter++;
98: } // end while
99:
100: return bagContents;
101: } // end toVector
103: template<class ItemType>
104: bool LinkedBag<ItemType>::remove(const ItemType& anEntry)
105: {
106: Node<ItemType>* entryNodePtr = getPointerTo(anEntry);
107: bool canRemoveItem = !isEmpty() && (entryNodePtr != nullptr);
108: if (canRemoveItem)
109: {
110: // Copy data from first node to located node
111: entryNodePtr->setItem(headPtr->getItem());
112:
113: // Delete first node
114: Node<ItemType>* nodeToDeletePtr = headPtr;
115: headPtr = headPtr->getNext();
116:
117: // Return node to the system
118: nodeToDeletePtr->setNext(nullptr);
119: delete nodeToDeletePtr;
120: nodeToDeletePtr = nullptr;
121:
122: itemCount--;
123: } // end if
124:
125: return canRemoveItem;
126: } // end remove
128: template<class ItemType>
129: void LinkedBag<ItemType>::clear()
130: {
131: Node<ItemType>* nodeToDeletePtr = headPtr;
132: while (headPtr != nullptr)
133: {
134: headPtr = headPtr->getNext();
135:
136: // Return node to the system
137: nodeToDeletePtr->setNext(nullptr);
138: delete nodeToDeletePtr;
139:
140: nodeToDeletePtr = headPtr;
141: } // end while
142: // headPtr is nullptr; nodeToDeletePtr is nullptr
143:
144: itemCount = 0;
145: } // end clear
148: template<class ItemType>
149: int LinkedBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
150: {
151: int frequency = 0;
152: int counter = 0;
153: Node<ItemType>* curPtr = headPtr;
154: while ((curPtr != nullptr) && (counter < itemCount))
155: {
156: if (anEntry == curPtr->getItem())
157: {
158: frequency++;
159: } // end if
160:
161: counter++;
162: curPtr = curPtr->getNext();
163: } // end while
164:
165: return frequency;
166: } // end getFrequencyOf
168: template<class ItemType>
169: bool LinkedBag<ItemType>::contains(const ItemType& anEntry) const
170: {
171: return (getPointerTo(anEntry) != nullptr);
172: } // end contains
174: // private
175: // Returns either a pointer to the node containing a given entry
176: // or the null pointer if the entry is not in the bag.
177: template<class ItemType>
178: Node<ItemType>* LinkedBag<ItemType>::getPointerTo(const ItemType& anEntry) const
179: {
180: bool found = false;
181: Node<ItemType>* curPtr = headPtr;
182:
183: while (!found && (curPtr != nullptr))
184: {
185: if (anEntry == curPtr->getItem())
186: found = true;
187: else
188: curPtr = curPtr->getNext();
189: } // end while
190:
191: return curPtr;
192: } // end getPointerTo