Question

the goal is for you to develop an approach that improves up on the array-based implementation in some way.For example, perhaps you want to take an approach that avoids the cost of re-allocating the array when it's full,e.g. using a linked-list. Of course, with a linked-list the cost of accessing an element will jump from O(1) to O(N), so that’s a costly trade-off. Perhaps you can think of a better approach that avoids the cost of reallocating the array, while retaining O(1) access to any element in most cases? In short, think of ways to break your myvector class, and write code to make sure your vector class works as required.

you are also required to add three additional functions to your myvector class, as defined below:

// // erase

// // erase the element at position i from the vector by overwriting it and

// reducing the size (# of elements); the ith element is returned //

// Assume: 0 <= i < Size // T erase(int i);

// // [] // // returns a reference to the element at position i so the element can

// be read or written //

// Assume: 0 <= i < Size //

T erase(int i);

T& operator[ ](int i);

// // [] //

// returns a reference to the element at position i so the element can

// be read or written //

// Assume: 0 <= i < Size

T* rangeof(int i, int j)

// // rangeof // // Returns the elements in the range of positions i..j, inclusive. // The elements are returned in a dynamically-allocated C-style array. // // Example: if i is 2 and j is 4, then an array containing 3 // elements is returned: element position 2, element position 3, and // element position 4. // // Assume: 0 <= i <= j < Size //

Do not add a destructor

use pointers in some way, above and beyond a single pointer to a dynamicallyallocated array. A simple one or two-way linked-list is a valid approach, but will not receive full credit.

Do not use any of the built-in containers of C++ (e.g. do not use std::vector to implement myvector)

main.cpp and function.cpp are read only function

myvector.h is a todo function

main.cpp

//
// Project #01: input movie review data from a file, and output moviename, # of
// reviews, average review, and # of reviews per star.
//
// File example "movie1.txt":
// Finding Nemo
// 5
// 4
// 5
// 4
// 5
// -1
//
// Output:
// Movie: Finding Nemo
// Num reviews: 5
// Avg review: 4.6
// 5 stars: 3
// 4 stars: 2
// 3 stars: 0
// 2 stars: 0
// 1 star: 0
//

#include <iostream>
#include <fstream>
#include <string>

#include "myvector.h"

using namespace std;

// functions from student.cpp:
myvector<int> InputData(string filename, string& moviename);
double GetAverage(myvector<int> reviews);
myvector<int> GetNumStars(myvector<int> reviews);

int main()
{
myvector<int> reviews;
myvector<int> numstars;
double avg;
string filename, moviename;

//
// 1. input filename and then the review data:
//
cin >> filename;

reviews = InputData(filename, moviename);

cout << "Movie: " << moviename << endl;
cout << "Num reviews: " << reviews.size() << endl;

//
// 2. average review
//
avg = GetAverage(reviews);
cout << "Avg review: " << avg << endl;

//
// 3. # of 5 stars, 4 stars, etc
//
numstars = GetNumStars(reviews);

for (int i = numstars.size(); i > 0; --i)
{
//
// i is 5, 4, 3, 2, 1:
//
if (i == 1)
cout << i << " star: " << numstars.at(i - 1) << endl;
else
cout << i << " stars: " << numstars.at(i - 1) << endl;
}

return 0;
}

functions.cpp

//
// Project #01: input movie review data from a file, and output moviename, # of
// reviews, average review, and # of reviews per star.
//

#include <iostream>
#include <fstream>
#include <string>

#include "myvector.h"

using namespace std;

//
// InputData
//
// Inputs the movie data from the given file, returning the moviename
// (via the parameter) and the individual reviews (via the returned
// vector). The reviews are ratings in the range 1..5.
//
// File format: the first line is the moviename. The name is followed
// by N > 0 reviews, one per line; each review is a value in the range
// 1-5. The last review is followed by a sentinel value (0 or negative)
// which is discarded.
//
// File example "movie1.txt":
// Finding Nemo
// 5
// 4
// 5
// 4
// 5
// -1
//
myvector<int> InputData(string filename, string& moviename)
{
myvector<int> V;
ifstream file(filename);
int x;

if (!file.good())
{
cout << "**Error: unable to open '" << filename << "'." << endl;
return V; // empty vector:
}

getline(file, moviename);

//
// input and store all reviews until sentinel is
// reached (0 or negative):
//
file >> x;

while (x > 0)
{
V.push_back(x);

file >> x; // next value:
}

// done, return vector of reviews:
return V;
}

//
// GetAverage
//
// Returns the average of the values in the vector; if the vector
// is empty then 0.0 is returned.
//
double GetAverage(myvector<int> V)
{
double sum = 0.0;
double avg;

for (int i = 0; i < V.size(); ++i)
{
sum += V.at(i);
}

if (V.size() == 0) // beware of divide-by-0:
avg = 0.0;
else
avg = sum / static_cast<double>(V.size());

return avg;
}

//
// GetNumStars
//
// Given a vector of reviews --- each review in the range 1-5 --- returns
// a vector of counts denoting the # of reviews of each rating. In other
// words, if we think of the reviews as "stars", the function returns a
// vector of 5 counts in this order: # of reviews of 1 star, # of reviews of
// 2 stars, ..., # of reviews of 5 stars.
//
// Example: suppose reviews contains the reviews 1, 5, 5, 2, 1, 4, 5. Then
// the function returns a vector containing 5 counts: 2, 1, 0, 1, 3.
//
myvector<int> GetNumStars(myvector<int> reviews)
{
myvector<int> numstars(5); // 1, 2, 3, 4, 5 stars

// let's make sure all the counts are initialized to 0:
for (int i = 0; i < numstars.size(); ++i)
{
numstars.at(i) = 0;
}

//
// for each review, increase count for that particular star (1-5):
//
for (int i = 0; i < reviews.size(); ++i)
{
int star = reviews.at(i); // 1-5:

numstars.at(star - 1)++; // index 0-4:
}

// return counts:
return numstars;
}

myvector.h

// Project #01: myvector class that mimics std::vector, but with my own
// implemenation outlined as follows:
//
// ???
//

#pragma once

#include <iostream> // print debugging
#include <cstdlib> // malloc, free

using namespace std;

template<typename T>
class myvector
{
private:
T* A;
int Size;
int Capacity;

public:
// default constructor:
myvector()
{
Size = 0;

Capacity = 1000;

A = new T[Capacity];
}

// constructor with initial size:
myvector(int initial_size)
{
Capacity = initial_size;

Size = initial_size;

A = new T[Capacity];
}

// copy constructor for parameter passing:
myvector(const myvector& other)
{
//
// we have to make a copy of the "other" vector, so...
//
A = new T[other.Capacity]; // allocate our own array of same capacity
Size = other.Size; // this vector is same size and capacity
Capacity = other.Capacity;

// make a copy of the elements into this vector:
for (int i = 0; i < Size; ++i)
A[i] = other.A[i];
}

int size()
{
//
//
//
return Size;
}

T& at(int i)
{
//
//
//
return A[i]; // this is WRONG, but compiles
}

void push_back(T value)
{
if (Size >= Capacity) {

int *temp = new int[2 * Capacity];

for (int i = 0; i < Size; i++)

temp[i] = A[i];

A = temp;

}

A[Size] = value;

Size++;
}

};

If you find better methods to improve the "myvector.h" you can try to update it but it still needs to be a template and I need it to have the erase, operator, and rangeof function in the file.

Answer 1

INSERT/ ENQUEUE OPERATION

void insert(int data){
   int i = 0;

   if(!isFull()){
      // if queue is empty, insert the data 
                
      if(itemCount == 0){
         intArray[itemCount++] = data;        
      }else{
         // start from the right end of the queue 
         for(i = itemCount - 1; i >= 0; i-- ){
            // if data is larger, shift existing item to right end 
            if(data > intArray[i]){
               intArray[i+1] = intArray[i];
            }else{
               break;
            }            
         }   
         // insert the data 
         intArray[i+1] = data;
         itemCount++;
      }
   }
}

COMPLETE PROGRAM

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6

int intArray[MAX];
int itemCount = 0;

int peek(){
   return intArray[itemCount - 1];
}

bool isEmpty(){
   return itemCount == 0;
}

bool isFull(){
   return itemCount == MAX;
}

int size(){
   return itemCount;
}  

void insert(int data){
   int i = 0;

   if(!isFull()){
      // if queue is empty, insert the data 
      if(itemCount == 0){
         intArray[itemCount++] = data;        
      }else{
         // start from the right end of the queue 
                        
         for(i = itemCount - 1; i >= 0; i-- ){
            // if data is larger, shift existing item to right end 
            if(data > intArray[i]){
               intArray[i+1] = intArray[i];
            }else{
               break;
            }            
         }  
                        
         // insert the data 
         intArray[i+1] = data;
         itemCount++;
      }
   }
}

int removeData(){
   return intArray[--itemCount]; 
}

int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // ------------------
   // index : 0  1 2 3 4 
   // ------------------
   // queue : 12 9 5 3 1 
   insert(15);

   // ---------------------
   // index : 0  1 2 3 4  5 
   // ---------------------
   // queue : 15 12 9 5 3 1
        
   if(isFull()){
      printf("Queue is full!\n");   
   }

   // remove one item 
   int num = removeData();
   printf("Element removed: %d\n",num);
        
   // ---------------------
   // index : 0  1  2 3 4 
   // ---------------------
   // queue : 15 12 9 5 3  

   // insert more items
   insert(16);

   // ----------------------
   // index :  0  1 2 3 4  5
   // ----------------------
   // queue : 16 15 12 9 5 3

   // As queue is full, elements will not be inserted. 
   insert(17);
   insert(18);

   // ----------------------
   // index : 0   1  2 3 4 5
   // ----------------------
   // queue : 16 15 12 9 5 3
   printf("Element at front: %d\n",peek());

   printf("----------------------\n");
   printf("index : 5 4 3 2  1  0\n");
   printf("----------------------\n");
   printf("Queue:  ");
        
   while(!isEmpty()){
      int n = removeData();           
      printf("%d ",n);
   }   
}