CPTR 124 Fundamentals of Programming Lab

Vector Processing

CPTR 124 Fundamentals of Programming

In this lab you will write some functions that work with the C++ vector data type.

Teams
You may work with a partner for this lab. You and your partner should begin thinking about the problems and begin writing the code before lab time.
Create a new project
Create a new project and add the header file vectorstuff.h. The file vectorstuff.h contains the prototypes of functions that you are to implement.
Implement the functions
Create a new C++ source file named vectorstuff.cpp that implements all the functions declared in the vectorstuff.h header file. The specifications for the functions are listed here:
- int maximum(const vector<int>& v)
  
  Returns the maximum value in vector v. The behavior of this function is undefined if the vector is empty.
  The function does not affect the contents of vector v. The function should use no extra space except for a few local scalar variables.
- int find(const vector<int>& v, int seek)
  
  Returns the location (zero is the first position) of the first occurrence of seek within v. Said another way, it returns the lowest index in v that contains the value seek. If seek is not present in v, the function returns –1, since –1 is not a legal index within any C++ vector.
  The function does not affect the contents of vector v. The function should use no extra space except for a few local scalar variables.
- int count(const vector<int>& v, int seek)
  
  Returns the number of times element seek appears in v.
  The function does not affect the contents of vector v. The function should use no extra space except for a few local scalar variables.
- bool equivalent(const vector<int>& v1, const vector<int>& v2)
  
  Returns true if vectors v1 and v2 contain exactly the same elements, regardless of their order within the vectors; otherwise, the function returns false.
  For example, suppose we have the following three vectors:
  - The vector list1 contains, in the following order, the elements 1, 2, 3, 4, 3, 5, and 6.
  - The vector list2 contains, in the following order, the elements 3, 2, 1, 4, 6, 5, and 3.
  - The vector list3 contains, in the following order, the elements 3, 2, 1, 4, 6, and 5.
  The call equivalent(list1, list2) would return true, since both vectors contain exactly the same elements, although not necessarily in the same order. The call equivalent(list1, list3) would return false, because even though both vectors contain the same values, list1 has two 3s while list3 has only one 3.
  Two empty vector vectors are considered equivalent. The contents of neither vector v1 nor vector v2 are affected by this function. The function should use no extra space except for a few local scalar variables.
- bool prefix(const vector<int>& v1, const vector<int>& v2)
  
  Given vector v1 with length n and vector v2, function returns true if the first n elements of v2 are identical to the contents of v1; that is, v1 is a "prefix" of v2. The function returns false if v1 is not prefix of v2.
  Some examples include
  {2,-5,0} is a prefix of {2,-5,0,11,4} (first three elements match)
  {2,-5,0} is NOT a prefix of {0,-5,2,11,4} (order matters)
  {2,-5,0} is NOT a prefix of {11,2,-5,0,4} (matching elements not at beginning)
  Every sequence is a prefix of itself, and the empty sequence is a prefix of any sequence.
  The contents of neither vector v1 nor vector v2 are affected by this function. The function should use no extra space except for a few local scalar variables.
- void sort(vector<int>& v)
  
  Physically rearranges the elements of v so they are in ascending order.
  For example, if list contains the elements 2, 1, 3, 1, 5, and 2, the call sort(list) reorders list to contain 1, 1, 2, 2, 3, 5.
  The function can affect the contents of the vector. The function should use no extra space except for a few local scalar variables.
- bool is_ascending(const vector<int>& v)
  
  Returns true if the elements of vector v are arranged in ascending order. If any element appears after an element greater than itself, the function returns false. An empty vector by default is considered to be in ascending order.
  The function does not affect the contents of vector v. The function should use no extra space except for a few local scalar variables.
- bool remove_first(vector<int>& v, int del)
  
  Removes the first occurrence of the value del from the vector v. (The first occurrence is the one with the lowest index.)
  The function returns true if del was located and removed; otherwise, it returns false.
  The function can affect the contents of the vector. The function should use no extra space except for a few local scalar variables.
  For example, if the vector originally contains
```
                23, 45, 14, 45, 19, 11
             
```
  after removing 45 it would contain
```
                23, 14, 45, 19, 11
             
```
  Notice that only the first occurrence of 45 was removed. The function should not disturb the relative ordering of the elements that remain.
  (Hint: Locate the element to remove, and then shift forward by one position all the elements that follow it. Be sure to decrease the vector's size by one.)
- int remove_all(vector<int>& v, int del)
  
  Removes all occurrences of the value del from the vector v.
  The function returns the number of elements removed; if it removes nothing because the element to remove is not found in the vector, the function returns zero.
  The function can affect the contents of the vector. The function should use no extra space except for a few local scalar variables.
  For example, if the vector originally contains
```
                23, 45, 14, 45, 19, 11
             
```
  after removing 45 it would contain
```
                23, 14, 19, 11
             
```
  Notice that all occurrences of 45 were removed. The function should not disturb the relative ordering of the elements that remain.
- void rotate(vector<int>& v, int n)
  
  Physically rearranges the elements of v so that all the elements are shifted towards the back by a distance of n. As an element "falls off" the rear, it is placed at the front in the space vacated when the first element was shifted backwards.
  For example, if list contains the elements 1, 2, 3, 4, 5, and 6, the call rotate(list, 2) rearranges list to contain 5, 6, 1, 2, 3, and 4.
  Notice that if n is equal to the size of the vector, after the rotation all the elements rotate to their original locations.
  If n is negative, the elements are shifted forward n spots instead of backwards. As an element "falls off" the front it is placed on the rear in the space vacated when the last element was shifted forwards.
  For example, if list contains the elements 1, 2, 3, 4, 5, and 6, the call rotate(list, -2) rearranges list to contain 3, 4, 5, 6, 1, and 2. The rotation is easier to understand if you visualize the vector as a circular structure as show in the figure.
  
  The figure shows the original vector on the left and the vector rotated by –2 on the right.
  This method can affect the contents of the vector. The function should use no extra space except for a few local scalar variables.
- bool subsequence(const vector<int>& seq1, const vector<int>& seq2)
  
  Vectors seq1 and seq2 both represent sequences of integers. The call subsequence(seq1, seq2) returns true, if seq2 is a subsequence of seq1; otherwise, it returns false.
  A subsequence is a sequence of numbers that are part of a potentially larger sequence of numbers. Given a sequence of numbers, you can produce a subsequence by removing none, some, or all of numbers in the original sequence. The remaining numbers must appear in same relative order as in the original sequence.
  The concept is best explained by some examples: If seq1 is the sequence
```
               23, 4, 19, -4, 0, 3
               
```
  and seq2 is the sequence
```
               19, -4, 0
               
```
  seq2 is a subsequence of seq1.
  If seq1 is the sequence
```
               23, 4, 19, -4, 0, 3
               
```
  and seq2 is the sequence
```
               19, 0
               
```
  seq2 is a subsequence of seq1.
  If seq1 is the sequence
```
               23, 4, 19, -4, 0, 3
               
```
  and seq2 is the sequence
```
               19, -4, 0, 3, 5
               
```
  seq2 is not a subsequence of seq1, because seq2 contains an element that does not appear in seq1.
  If seq1 is the sequence
```
               23, 4, 19, -4, 0, 3
               
```
  and seq2 is the sequence
```
               23, 0, -4
               
```
  seq2 is not a subsequence of seq1 even though all of its elements appear in seq1. This is because seq2's elements are not in the same relative order as in seq1 (0 comes after –4 in seq1 but before –4 in seq2.)
  If seq1 is the sequence
```
               23, 4, 19, -4, 0, 3
               
```
  and seq2 is the sequence
```
               23, 4, 19, -4, 0, 3
               
```
  seq2 is a subsequence of seq1; thus, any sequence is a subsequence of itself.
  The empty sequence is a subsequence of every sequence.
  Neither vector seq1 nor vector seq2 is affected by this function. The function should use no extra space except for a few local scalar variables.
The specification that a function does not affect the vector means that the contents of the vector are unchanged by the function; the function may not reassign, rearrange, or otherwise change the elements of the vector. The specification that a function uses no extra space except for a few local scalar variables means that you may not declare any local vectors or arrays to facilitate the function's processing. We say that the function processes the vector "in place" without copying its contents into another, temporary vector.
None of the functions specified above should do any input or output. This means that neither cout nor cin should appear in any of the functions. You are welcome to add printing statements during development for debugging purposes, but you should remove or comment out these printing statements when you are ready to submit your program for testing.
You may not modify the contents of the vectorstuff.h header file.
Check out
Your finished vectorstuff.cpp file will be evaluated for correctness and compliance. Before showing me your code, be sure that it complies with the following requirements:
1. Your name and your partner's name should appear in the in a comment at the top of the source code. Failure to provide such a comment results in an immediate failed test.
2. Ensure that your vectorstuff.cpp files compiles correctly with the very simple test file simplevectortestfile.cpp. If your vectorstuff.cpp file does not compile with this very simple test program, it will not compile with my test program either. If your code will not compile, it counts as a failed test. This simple test file is very minimal and is designed merely to verify that your code satisfies the compiler; it does not begin to demonstrate the correctness of your code's logic. You should write your own test code to verify your functions' correctness.
You may provide to me your vectorstuff.cpp file for testing up to three times before its due date. The final test determines the score based on the number of functions that pass the tests. 10 points means 10 functions passed all their tests, 9 points means 9 of the functions passed all their tests, etc. If all 11 functions pass all their tests on the first attempt and the first attempt is performed on or before the assignment's due date, you will receive 11 out of 10 points. If you provide your functions for their first test after their due date, your score for the assignment is determined by the first test. After the final check you should submit your C++ source file to eclass.e.southern.edu.