1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: /** Implementation file for the class ArrayBag: Recursive version.
5: @file ArrayBag.cpp */
7: #include "ArrayBag.h"
8: #include <cstddef>
10: template<class ItemType>
11: ArrayBag<ItemType>::ArrayBag(): itemCount(0), maxItems(DEFAULT_CAPACITY)
12: {
13: } // end default constructor
15: template<class ItemType>
16: int ArrayBag<ItemType>::getCurrentSize() const
17: {
18: return itemCount;
19: } // end getCurrentSize
21: template<class ItemType>
22: bool ArrayBag<ItemType>::isEmpty() const
23: {
24: return itemCount == 0;
25: } // end isEmpty
27: template<class ItemType>
28: bool ArrayBag<ItemType>::add(const ItemType& newEntry)
29: {
30: bool hasRoomToAdd = (itemCount < maxItems);
31: if (hasRoomToAdd)
32: {
33: items[itemCount] = newEntry;
34: itemCount++;
35: } // end if
36:
37: return hasRoomToAdd;
38: } // end add
40: template<class ItemType>
41: bool ArrayBag<ItemType>::remove(const ItemType& anEntry)
42: {
43: int locatedIndex = getIndexOf(anEntry, 0);
44: bool canRemoveItem = !isEmpty() && (locatedIndex > -1);
45: if (canRemoveItem)
46: {
47: itemCount--;
48: items[locatedIndex] = items[itemCount];
49: } // end if
50:
51: return canRemoveItem;
52: } // end remove
54: template<class ItemType>
55: void ArrayBag<ItemType>::clear()
56: {
57: itemCount = 0;
58: } // end clear
60: template<class ItemType>
61: bool ArrayBag<ItemType>::contains(const ItemType& anEntry) const
62: {
63: return getIndexOf(anEntry, 0) > -1;
64: } // end contains
66: template<class ItemType>
67: int ArrayBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const
68: {
69: return countFrequency(anEntry, 0);
70: } // end getFrequencyOf
72: template<class ItemType>
73: vector<ItemType> ArrayBag<ItemType>::toVector() const
74: {
75: vector<ItemType> bagContents;
76: for (int i = 0; i < itemCount; i++)
77: bagContents.push_back(items[i]);
78:
79: return bagContents;
80: } // end toVector
82: // private
83: template<class ItemType>
84: int ArrayBag<ItemType>::countFrequency(const ItemType& anEntry, int searchIndex) const
85: {
86: int frequency = 0;
87: if (searchIndex < itemCount)
88: {
89: if (items[searchIndex] == anEntry)
90: {
91: frequency = 1 + countFrequency(anEntry, searchIndex + 1);
92: }
93: else
94: {
95: frequency = countFrequency(anEntry, searchIndex + 1);
96: } // end if
97: } // end if
99: return frequency;
100: } // end countFrequency
102: // private
103: template<class ItemType>
104: int ArrayBag<ItemType>::getIndexOf(const ItemType& target, int searchIndex) const
105: {
106: int result = -1;
107: if (searchIndex < itemCount)
108: {
109: if (items[searchIndex] == target)
110: {
111: result = searchIndex;
112: }
113: else
114: {
115: result = getIndexOf(target, searchIndex + 1);
116: } // end if
117: } // end if
118:
119: return result;
120: } // end getIndexOf