Part 1: develop a class called DynamicArray with the following requirements: pub
ID: 672004 • Letter: P
Question
Part 1:
develop a class called DynamicArray with the following requirements:
public interface:
DynamicArray should be declared in the CSCI2421 namespace.
A constructor that allows the user to specify the initial size of the array. If no initial size is given default to 10.
A copy constructor
An assignment operator
void push_back(const value_type &x); // adds an element to the end of the array, increasing the size of the array as necessary
void insert(const std::size_t position, const value_type &x); // inserts an element at the specified position, increasing the size of the array as necessary
void erase(const std::size_t position); // removes an element at the specified position
std::size_t size() const; // returns the number of elements in the array
std::size_t capacity() const; // returns the current capacity of the array
value_type get(const std::size_t position) const; // gets the element at the specified position
Your print function should be implemented exactly as below (this will help with my testing)
void CSCI2421::DynamicArray::print() {
std::cout << "DynamicArray contains " << m_NumberOfElements << " elements: ";
for (std::size_t i = 0; i < m_NumberOfElements; i++) {
std::cout << m_Data[i] << " "; }
std::cout << std::endl; }
Allow the user to insert an unlimited number of elements.
The internal dynamically allocated array should grow by 2X when it fills (like how Bag works) Make sure that you update any preconditions and asserts to reasonable values.
Hint: Use the Bag class as an example of dynamic arrays.
Hint: Start with copying the Array class into a new class called DynamicArray, a lot of the required functionality is the same.
Hint: Make sure you fully test your implementation! You don’t have to submit a main.cpp.
Part 2:(50
Update the Bag class to be a template class that can use any type. Use the slides from 101 and the LinkedList class provided as an example. Again it’s up to you to fully test your Bag class. No main.cpp is required to be submitted. The public interface for Bag shouldn't change, with the exception of now having to specify the type at creation.
CSCI2421::Bag<int> bag;
//// main.cpp
#include <iostream>
#include "LinkedList.h"
using namespace std;
int main()
{
CSCI2421::LinkedList<int> list;
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtFront(0);
list.insertAtEnd(2);
list.print();
list.removeAtFront();
list.print();
list.clear();
list.print();
return 0;
}
///Array.h
#ifndef PA5_ARRAY_H
#define PA5_ARRAY_H
#include <cstdlib>
namespace CSCI2421
{
class Array
{
public:
static const std::size_t MAX_CAPACITY = 20;
typedef int value_type;
// constructs an Array
// Precondition: none
// Postcondition: Array is initialized
Array();
// inserts an element into the end of the array
// Precondition: m_NumberOfElements < MAX_CAPACITY
void push_back(const value_type &x);
// inserts an element at the specified position in the Array, maintaining the order of the elements
// Precondition: position < m_NumberOfElements
// Precondition: m_NumberOfElements < MAX_CAPACITY
void insert(const std::size_t position, const value_type &x);
// removes the element at the specified position in the Array.
// Precondition: position < m_NumberOfElements
void erase(const std::size_t position);
// returns the number of elements in the Array
// Precondition: none
std::size_t size() const;
// returns the current capacity of the Array
// Precondition: none
std::size_t capacity() const;
// returns the element at the specified position in the Array
// Precondition: position < m_NumberOfElements
value_type get(const std::size_t position) const;
// print the contents of the Array
void print();
private:
// the number of elements in the Array
std::size_t m_NumberOfElements;
// the statically allocated array
value_type m_Data[MAX_CAPACITY];
};
}
#endif //PA5_ARRAY_H
////Array.cpp
#include "Array.h"
#include <cassert>
#include <algorithm>
#include <iostream>
CSCI2421::Array::Array() : m_NumberOfElements(0)
{
}
void CSCI2421::Array::push_back(const value_type &x)
{
assert (m_NumberOfElements < MAX_CAPACITY);
m_Data[m_NumberOfElements++] = x;
}
void CSCI2421::Array::insert(const std::size_t position, const CSCI2421::Array::value_type &x)
{
assert (m_NumberOfElements < MAX_CAPACITY);
assert (position < m_NumberOfElements);
std::copy_backward(m_Data + position, m_Data + m_NumberOfElements, m_Data + m_NumberOfElements +1);
m_Data[position] = x;
m_NumberOfElements++;
}
void CSCI2421::Array::erase(const std::size_t position)
{
assert (position < m_NumberOfElements);
std::copy(m_Data + position + 1, m_Data + m_NumberOfElements, m_Data + position );
m_NumberOfElements --;
}
CSCI2421::Array::value_type CSCI2421::Array::get(const std::size_t position) const
{
assert (position < m_NumberOfElements);
return m_Data[position];
}
std::size_t CSCI2421::Array::size() const
{
return m_NumberOfElements;
}
void CSCI2421::Array::print()
{
std::cout << "Array contains " << m_NumberOfElements << " elements: ";
for (std::size_t i = 0; i < m_NumberOfElements; i++)
{
std::cout << m_Data[i] << " ";
}
std::cout << std::endl;
}
std::size_t CSCI2421::Array::capacity() const
{
return MAX_CAPACITY;
}
//// Bag.h
#ifndef PA5_BAG_H
#define PA5_BAG_H
#include <cstdlib>
#include <ostream>
namespace CSCI2421
{
class Bag
{
public:
typedef int value_type;
// Initializes the Bag
// Postcondition: Bag is initialized
Bag(const std::size_t initialCapacity = 20);
// Copy Constructor
// Postcondition: Bag is a copy of source with it's own dynamic memory
Bag(const Bag &source);
// Destructor for Bag. Frees up dynamic memory
~Bag();
// inserts an element into the Bag
// Precondition: size() < CAPACITY
// Postcondition: A new copy of entry has been added to the Bag
void insert(const value_type &x);
// attempts to remove one element that is equal to x from the Bag.
// Returns: true if the element was removed, else false.
// Precondition: none
// Postcondition: one element that is equal to x is removed from the Bag.
bool erase_one(const value_type &x);
// erases every element that is equal to x from the Bag.
// Returns: the number of elements erased
// Precondition: none
// Postcondition: all the elements that are equal to x are removed from the Bag
std::size_t erase(const value_type &x);
// returns the number of elements in the bag
// Precondition: none
// Postcondition: none
std::size_t size() const;
// returns the number of elements equal to x in the Bag
// Precondition: none
// Postcondition: none
std::size_t count(const value_type &x) const;
// returns the current maximum capacity of the Bag
std::size_t capacity () const;
// print the contents of the Bag
void print();
// overloaded assignment operator deallocates m_Data and allocates new memory for m_Data
// and copies the elements from source to m_Data
void operator=(const Bag &source);
private:
// if newCapacity > m_CurrentCapacity, allocates an array with size newCapacity
// on the Heap, copies all elements from m_Data to the new array, deallocates the
// old array memory and assigns m_Data to the new array.
void resizeArray(const std::size_t newCapacity);
// the number of elements currently in the Bag
std::size_t m_NumberOfElements;
// The max capacity of the Bag before it must be resized to accept more elements
std::size_t m_CurrentCapacity;
// where the Bag stores it's elements
value_type *m_Data;
};
}
#endif //PA5_BAG_H
////Bag.cpp
#include "Bag.h"
#include <algorithm>
#include <iostream>
CSCI2421::Bag::Bag(const std::size_t initialCapacity) : m_NumberOfElements(0), m_CurrentCapacity(initialCapacity)
{
m_Data = new value_type[initialCapacity];
}
CSCI2421::Bag::Bag(const CSCI2421::Bag &source) : m_NumberOfElements(source.m_NumberOfElements),
m_CurrentCapacity(source.m_CurrentCapacity)
{
m_Data = new value_type[m_CurrentCapacity];
std::copy (source.m_Data, source.m_Data + m_NumberOfElements, m_Data);
}
CSCI2421::Bag::~Bag()
{
delete[] m_Data;
}
void CSCI2421::Bag::insert(const value_type& x)
{
if (m_NumberOfElements == m_CurrentCapacity)
{
resizeArray(m_NumberOfElements + 1);
}
m_Data[m_NumberOfElements] = x;
m_NumberOfElements++;
}
bool CSCI2421::Bag::erase_one(const value_type& x)
{
for (std::size_t index = 0; index < m_NumberOfElements; index++)
{
if (m_Data[index] == x)
{
m_NumberOfElements--;
m_Data[index] = m_Data[m_NumberOfElements];
return true;
}
}
return false;
}
std::size_t CSCI2421::Bag::erase(const value_type& x)
{
std::size_t index = 0;
std::size_t numberRemoved = 0;
while (index < m_NumberOfElements)
{
if (m_Data[index] == x)
{
m_NumberOfElements--;
m_Data[index] = m_Data[m_NumberOfElements];
numberRemoved++;
}
else
{
index++;
}
}
return numberRemoved;
}
std::size_t CSCI2421::Bag::size() const
{
return m_NumberOfElements;
}
std::size_t CSCI2421::Bag::count(const value_type& x) const
{
std::size_t counter = 0;
for (std::size_t i = 0; i < m_NumberOfElements; i++)
{
if (m_Data[i] == x)
counter++;
}
return counter;
}
void CSCI2421::Bag::resizeArray(const std::size_t newCapacity)
{
if (newCapacity <= m_CurrentCapacity)
{
// already large enough
return;
}
value_type* largerArray = new value_type[newCapacity];
std::copy (m_Data, m_Data + m_CurrentCapacity, largerArray);
delete[] m_Data;
m_Data = largerArray;
m_CurrentCapacity = newCapacity;
}
void CSCI2421::Bag::operator=(const CSCI2421::Bag &source)
{
if (this == &source)
return;
value_type* newData;
if (m_CurrentCapacity != source.m_CurrentCapacity)
{
newData = new value_type[source.m_CurrentCapacity];
delete[] m_Data;
m_Data = newData;
m_CurrentCapacity = source.m_CurrentCapacity;
}
m_NumberOfElements = source.m_NumberOfElements;
std::copy (source.m_Data, source.m_Data + m_NumberOfElements, m_Data);
}
void CSCI2421::Bag::print()
{
std::cout << "Bag contains " << m_NumberOfElements << " elements: ";
for (std::size_t i = 0; i < m_NumberOfElements; i++)
{
std::cout << m_Data[i] << " ";
}
std::cout << std::endl;
}
size_t CSCI2421::Bag::capacity() const
{
return m_CurrentCapacity;
////LinkedList.h
#ifndef PA5_LINKEDLIST_H
#define PA5_LINKEDLIST_H
#include <cstdlib>
namespace CSCI2421
{
template <typename T>
class LinkedList
{
public:
// Constructor for LinkedList
LinkedList();
// Copy Constructor
LinkedList(const LinkedList &other);
// assignment operator
LinkedList &operator=(const LinkedList &other);
// destructor. Calls clear() to free up memory
~LinkedList();
// Inserts a new element at the front of the list
void insertAtFront(const T& data);
// Inserts a new element at the end of the list
void insertAtEnd(const T& data);
// removes the element at the front of the list
void removeAtFront();
// returns the number of elements in the list
std::size_t size();
// removes all elements from the list.
void clear();
// prints the list to standard output
void print();
private:
// internal data structure for linked list
class Node
{
public:
// holds the value of the node
T m_Data;
// holds a pointer to the next node in the linked list
Node *m_Next;
};
// A pointer to the first Node in the list
Node *m_Head;
// A pointer to the last Node in the list
Node *m_Tail;
// The size of the list
std::size_t m_Size;
};
}
#include "LinkedList.cpp"
#endif //PA5_LINKEDLIST_H
//// LinkedList.cpp
#include <iostream>
#include "LinkedList.h"
template<typename T>
CSCI2421::LinkedList<T>::LinkedList() : m_Head(NULL), m_Tail(NULL), m_Size(0)
{
}
template<typename T>
CSCI2421::LinkedList<T>::LinkedList(const CSCI2421::LinkedList<T> &other) : m_Head(NULL), m_Tail(NULL), m_Size(0)
{
Node* current = other.m_Head;
while (current != NULL)
{
insertAtEnd(current->m_Data);
current = current->m_Next;
}
}
template<typename T>
CSCI2421::LinkedList<T>::~LinkedList()
{
clear();
}
template<typename T>
CSCI2421::LinkedList<T>& CSCI2421::LinkedList<T>::operator=(const CSCI2421::LinkedList<T> &source)
{
if (this == &source)
return *this;
clear();
Node* current = source.m_Head;
while (current != NULL)
{
insertAtEnd(current->m_Data);
current = current->m_Next;
}
return *this;
}
template<typename T>
void CSCI2421::LinkedList<T>::insertAtFront(const T& data)
{
Node* newNode = new Node();
newNode->m_Data = data;
newNode->m_Next = m_Head;
if (m_Head == NULL)
m_Tail = newNode;
m_Head = newNode;
m_Size++;
}
template<typename T>
void CSCI2421::LinkedList<T>::insertAtEnd(const T& data)
{
if (m_Tail == NULL)
{
insertAtFront(data);
}
else
{
Node* newNode = new Node();
newNode->m_Data = data;
newNode->m_Next = NULL;
m_Tail->m_Next = newNode;
m_Tail = newNode;
m_Size++;
}
}
template<typename T>
void CSCI2421::LinkedList<T>::removeAtFront()
{
if (m_Head != NULL)
{
Node* delPtr = m_Head;
m_Head = m_Head->m_Next;
if (m_Head == NULL)
m_Tail = NULL;
delete delPtr;
m_Size--;
}
}
template<typename T>
std::size_t CSCI2421::LinkedList<T>::size()
{
return m_Size;
}
template<typename T>
void CSCI2421::LinkedList<T>::clear()
{
while (m_Head != NULL)
{
removeAtFront();
}
m_Size = 0;
}
template<typename T>
void CSCI2421::LinkedList<T>::print()
{
std::cout << "LinkedList contains " << m_Size << " elements: ";
const Node* current = m_Head;
while (current != NULL)
{
std::cout << current->m_Data << " ";
current = current->m_Next;
}
std::cout << std::endl;
}
Explanation / Answer
Answer:
Note: modified code. Template class is modified
template<typename T>
CSCI2421::LinkedList<T>::LinkedList(const CSCI2421::LinkedList<T> &other) : m_Head(NULL), m_Tail(NULL), m_Size(0)
{
Node* current = other.m_Head;
while (current != NULL)
{
insertAtEnd(current->m_Data);
current = current->m_Next;
}
}
template<typename T>
CSCI2421::LinkedList<T>::~LinkedList()
{
clear();
}
template<typename T>
CSCI2421::LinkedList<T>& CSCI2421::LinkedList<T>::operator=(const CSCI2421::LinkedList<T> &source)
{
if (this == &source)
return *this;
clear();
Node* current = source.m_Head;
while (current != NULL)
{
insertAtEnd(current->m_Data);
current = current->m_Next;
}
return *this;
}
template<typename T>
void CSCI2421::LinkedList<T>::insertAtFront(const T& data)
{
Node* newNode = new Node();
newNode->m_Data = data;
newNode->m_Next = m_Head;
if (m_Head == NULL)
m_Tail = newNode;
m_Head = newNode;
m_Size++;
}
template<typename T>
void CSCI2421::LinkedList<T>::insertAtEnd(const T& data)
{
if (m_Tail == NULL)
{
insertAtFront(data);
}
else
{
Node* newNode = new Node();
newNode->m_Data = data;
newNode->m_Next = NULL;
m_Tail->m_Next = newNode;
m_Tail = newNode;
m_Size++;
}
}
template<typename T>
void CSCI2421::LinkedList<T>::removeAtFront()
{
if (m_Head != NULL)
{
Node* delPtr = m_Head;
m_Head = m_Head->m_Next;
if (m_Head == NULL)
m_Tail = NULL;
delete delPtr;
m_Size--;
}
}
template<typename T>
std::size_t CSCI2421::LinkedList<T>::size()
{
return m_Size;
}
template<typename T>
void CSCI2421::LinkedList<T>::clear()
{
while (m_Head != NULL)
{
removeAtFront();
}
m_Size = 0;
}
template<typename T>
void CSCI2421::LinkedList<T>::print()
{
std::cout << "LinkedList contains " << m_Size << " elements: ";
const Node* current = m_Head;
while (current != NULL)
{
std::cout << current->m_Data << " ";
current = current->m_Next;
}
std::cout << std::endl;
}