C++ Assignment main of the program can be found here : http://staffwww.fullcoll.
ID: 3742134 • Letter: C
Question
C++ Assignment
main of the program can be found here: http://staffwww.fullcoll.edu/aclifton/cs133/files/assign1_test.cpp
Some hints
Here are some things that don’t work:
Creating the array as a global variable. The test runner will create more than one instance of ordered_array and expects all instances to be independent.
Assuming that 0, -1, or some other value will “never” be stored into the array (and hence can be used as a marker for the end of the array or something). All ints are valid values in the array. (Note that NULL is equal to 0.)
Assuming that all inserts will be performed at once. The test code may mix up a sequence of insert and removes.
In this assignment, youllimplement a simple data structure which maintains a sorted array. This is essentially just a simple wrapper around a dynamically-allocated array of int (you can also use a vector ) which allows the user to insert and remove values. The elements of the array should always be sorted in ascending order this means that when you add new elements, you need to figure out where they go in the array, shift everything after them up, and then drop the new element into place. Likewise, when you remove an element, you have to find it, and then shift everything after it down. The ordered array has a maximum size known as its capacity which is specified when it is created, and fixed from that point forward. This is the maximum number of elements that can be insert-ed into the array, if none are renove-d, before the array is full. The number of elements currently in the array is its size. Member functions .size() and .capacity() provide access to both these values. Note that an array's size is always 20 and its capacity. The size of an ordered array should be O when it is first created. Use the following class definition, supplying definitions for the the various member functions, and adding whatever private members you needExplanation / Answer
assign1_test.cpp
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
#include <algorithm>
#include <functional>
#include <random>
#include <vector>
inline std::vector<int> make_random_vector(
std::size_t len,
int seed = 1)
{
std::default_random_engine generator(seed);
std::uniform_int_distribution<int> distribution;
auto gen = std::bind(distribution, generator);
// Fill with random values
std::vector<int> ret(len, 0);
for(std::size_t i = 0; i < len; ++i)
ret.at(i) = gen() % 100;
return ret;
}
/* make_random_permutation(len)
Returns a vector of length len containing a random permutation of the
integers 0...len-1. This can, of course, be used to randomly permute any
vector of length len.
*/
inline std::vector<unsigned> make_random_permutation(
std::size_t len,
int seed = 1)
{
std::default_random_engine generator(seed);
std::vector<unsigned> ret(len, 0);
// Initialize vector to 0...len-1
for(std::size_t i = 0; i < len; ++i)
ret.at(i) = i;
std::shuffle(ret.begin(), ret.end(), generator);
return ret;
}
#include "ordered_array.hpp"
// Included twice to check for functions being defined in header files, non-use
// of #pragma once.
#include "ordered_array.hpp"
bool is_sorted(int* start, int* finish) {
if(start == finish || finish - start == 1)
return true;
else
return *start <= *(start + 1) &&
is_sorted(start + 1, finish);
}
bool contains_elements(ordered_array& a, const std::vector<int>& d, int count) {
for(int i = 0; i < count; ++i)
if(!a.exists(d[i]))
return false;
return true;
}
/* test_initial()
Perform tests on an empty ordered array.
*/
bool test_initial(ordered_array& a, int cap) {
if(a.size() != 0) {
cout << "CHECK: Size of empty array is not 0. ";
return false;
}
if(a.capacity() != cap) {
cout << "CHECK: Capacity of empty array is not " << cap << ". ";
return false;
}
if(a.begin() != a.end()) {
cout << "CHECK: begin() and end() pointers of empty array are not equal. ";
return false;
}
int* start = a.begin();
int* finish = a.end();
a.remove(0); // Does not exist
if(a.size() != 0 || start != a.begin() || finish != a.end()) {
cout << "CHECK: removing elements from empty array should not change anything. ";
return false;
}
return true;
}
bool test_insert(ordered_array& a) {
// Initialize test data (values in range -20..+20)
std::vector<unsigned> perm = make_random_permutation(41);
std::vector<int> data(41);
for(std::size_t i = 0; i < data.size(); ++i)
data[i] = static_cast<int>(perm[i]) - 20;
int size = a.size(); // expected size
for(int e : data) {
a.insert(e); size++;
if(a.size() != size) {
cout << "CHECK: After " << size << " insert()s, array size is incorrect. ";
return false;
}
if(a.end() - a.begin() != a.size()) {
cout << "end - begin = " << a.end() - a.begin() << endl << "size = " << a.size() << endl;
cout << "CHECK: After insert(), begin()/end() pointers are incorrect. ";
return false;
}
if(!a.exists(e)) {
cout << "CHECK: After inserting " << e << " element e does not exist(). ";
return false;
}
if(!is_sorted(a.begin(), a.end())) {
cout << "CHECK: After inserting " << e << " array is no longer sorted. ";
return false;
}
if(!contains_elements(a, data, size)) {
cout << "CHECK: After insert(), array is missing some prev. element(s). ";
return false;
}
}
for(int i = -20; i <= 20; ++i) {
if(!a.exists(i)) {
cout << "CHECK: Value " << i << " does not exist in array. ";
return false;
}
}
return true; // All tests successful
}
bool test_duplicates(ordered_array& a) {
std::vector<int> data = {-20, 0, 0, 20, 20, 20 };
int size = a.size(); // Starting size
// First we insert some duplicates...
for(int e : data) {
a.insert(e); size++;
if(a.size() != size) {
cout << "CHECK: Inserting a duplicate did not increase size(). ";
return false;
}
if(!is_sorted(a.begin(), a.end())) {
cout << "CHECK: after inserting a duplicate the array is no longer sorted. ";
return false;
}
}
// And then we remove them
for(int e : data) {
a.remove(e); size--;
if(a.size() != size) {
cout << "CHECK: Removing a duplicate results in incorrect size (= "
<< a.size() << ", expected " << size << "). ";
return false;
}
if(!is_sorted(a.begin(), a.end())) {
cout << "CHECK: after removing a duplicate the array is no longer sorted. ";
return false;
}
}
return true;
}
bool test_removal_nonexistent(ordered_array& a) {
// Remove some elements that don't exist
int size = a.size();
int* start = a.begin();
int* finish = a.end();
for(int i = 30; i <= 40; ++i) {
a.remove(i);
if(a.size() != size) {
cout << "CHECK: Removing non-existent element changed size. ";
return false;
}
if(a.begin() != start || a.end() != finish) {
cout << "CHECK: Removing non-existing element changed array pointers. ";
return false;
}
}
return true;
}
bool test_capacity(ordered_array& a) {
int count = a.capacity() - a.size(); // How many to insert
for(int i = 30; i < 30 + count; ++i)
a.insert(i);
if(a.size() != a.capacity()) {
cout << "CHECK: array should be full, but isn't. ";
return false;
}
// Try inserting elements and verify that size does not change, elements are
// not added.
int size = a.size();
int* start = a.begin();
int* finish = a.end();
for(int i = 50; i <= 60; ++i) {
a.insert(i);
if(a.size() != size) {
cout << "CHECK: Inserting when full changed size. ";
return false;
}
if(a.exists(i)) {
cout << "CHECK: Inserting when full should not change array contents. ";
return false;
}
if(start != a.begin() || finish != a.end()) {
cout << "CHECK: Inserting when full should not change array begin()/end(). ";
return false;
}
}
// Remove the inserted elements
for(int i = 30; i < 30 + count; ++i) {
a.remove(i);
}
if(a.size() != a.capacity() - count) {
cout << "CHECK: Size is wrong after removing elements. ";
return false;
}
return true;
}
bool test_removal(ordered_array& a) {
std::vector<int> data(41);
for(int i = -20; i <= 20; ++i)
data[i + 20] = i;
int size = a.size(); // Expected size
for(int e : data) {
a.remove(e); size--;
if(a.size() != size) {
cout << "CHECK: After removing existing element, size is incorrect. ";
return false;
}
if(a.exists(e)) {
cout << "CHECK: After removing unique element, element still exists. ";
return false;
}
if(!is_sorted(a.begin(), a.end())) {
cout << "CHECK: After removing element, array is no longer sorted. ";
return false;
}
}
return true;
}
bool test_final(ordered_array& a) {
if(a.size() != 0) {
cout << "CHECK: Size of empty array is not 0. ";
return false;
}
return true;
}
bool test_all() {
ordered_array a(60);
return test_initial(a,60) &&
test_insert(a) &&
test_duplicates(a) &&
test_removal_nonexistent(a) &&
test_capacity(a) &&
test_removal(a) &&
test_final(a);
}
int main() {
cout << "---- Beginning ordered_array tests ---- ";
if(test_all()) {
cout << "---- All tests successful! ---- ";
return 0;
}
else
return 1;
}
ordered_array.cpp
#include <iostream>
#include "ordered_array.hpp"
// Constructor
ordered_array::ordered_array(int cap){
sz = 0;
cpcty = cap;
array = new int[cpcty](); // '()' will initialize with zeros
}
// Destructor
ordered_array::~ordered_array(){
delete[] array;
array = nullptr;
}
// returns size of the array
int ordered_array::size(){
return sz;
}
// returns capacity of the array
int ordered_array::capacity(){
return cpcty;
}
// currently the function grabs each array value and then rewrites them to one place farther
void ordered_array::insert(int elem){
// don't insert if array is full
if (sz == cpcty){
return;
}
// immediately insert if array is empty
else if (sz == 0) {
int* p = &array[0];
sz++;
*p = elem;
}
// enter code block if array it not full or empty
else{
for (int i = 0; sz >= i; i++){
// if end of array reached, insert elem
if (sz == i){
array[i] = elem;
break;
}
// this algorithm searches for an element greater than the given element,
// then inserts it and rewrites the rest of the array afterwards.
if (elem < array[i]){
int nextval = array[i];
int futureval;
for (int j = 0; sz >= j+i; j++){
futureval = array[j+i];
array[j+i] = nextval;
nextval = futureval;
}
array[i] = elem;
break;
}
}
sz++;
}
}
// overwrites the "removed" val with item to the right, continues this pattern until end of array
void ordered_array::remove(int elem){
if(sz==0){
return;
}
for(int i = 0; i < sz; i++) {
if(elem == array[i]){
int nextval = array[i+1];
int futureval;
for (int j = 0; sz > j+i; j++){
futureval = array[j+i+2];
array[j+i] = nextval;
nextval = futureval;
}
array[sz] = 0;
sz--;
break;
}
}
}
// checks if current element is present in the array
bool ordered_array::exists(int elem){
for(int i = 0; i < sz; i++) {
if(elem == array[i]) return true;
}
return false;
}
// returns a pointer to beginning of array
int* ordered_array::begin(){
int *ptr;
ptr = &array[0];
return ptr;
}
// returns a pointer to the end of array
int* ordered_array::end(){
int* ptr;
ptr = &array[sz];
return ptr;
}
ordered_array.hpp
#ifndef ORDERED_ARRAY
#define ORDERED_ARRAY
class ordered_array {
public:
/* constructor
Construct a new ordered_array with the given capacity (maximum size).
The size of a new ordered_array should be 0.
*/
ordered_array(int cap);
// destructor
~ordered_array();
/* size()
Returns the size (number of elements in the array).
*/
int size();
/* capacity()
Returns the maximum size of the array.
*/
int capacity();
/* insert(e)
Insert e into the array. If size() == capacity() then this does
nothing. Note that it is OK to insert duplicates; if n copies of a value
are inserted into the array then n copies should appear in the array.
*/
void insert(int elem);
/* remove(e)
Remove e from the array, if it exists. (If it does not exist, the
array should be unchanged.) If multiple copies of e are present, only
one should be removed.
*/
void remove(int elem);
/* exists(e)
Returns true if e is present at least once in the array.
*/
bool exists(int elem);
/* begin()
Return a pointer to the first element of the array. The value pointed to
by this should be the smallest element in the array (if the array is not
empty).
*/
int* begin();
/* end()
Returns a pointer to one-past-the-end (last + 1) element of the array.
This should ignore any "unused" elements past the end of the array, i.e.,
> size but < capacity. The value pointed to by *(end() - 1) should be
the largest value in the array, if the array is not empty.
*/
int* end();
private:
// Private members as needed
int sz;
int cpcty;
int* array;
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.