C++

Requirements

I will give you the declaration for an algorithm and explain its behavior. Your job is to implement the algorithm, and to write a small snippet of code in main that uses or tests the algorithm.

Algorithms are specified in terms of their interface and their required behaviors. The behavior of an algorithm is specified in terms of its return value, its effects (if any), and its requirements (if any). When describing the return value of an algorithm, the specification describes how it is computed, often in the non-obvious ways.

An algorithm's "effects" describe what observable changes the algorithm makes that can be observed beyond the result type. For example print has the effect of writing to std::cout.

An algorithm's requirements are preconditions on its inputs. Most of these algorithms do not impose preconditions, except for copy.

Print

void print(int* first, int* limit); 

Effects: Output the value of each object in [first, limit) to std::cout with a space character between consecutive elements.

Note: Feel free to use the implementation above to satisfy this requirement.

Just for fun... modify print so that it will not print a space after the last object in the array.

Find

int* find(int* first, int* limit, int value); 

Returns: Returns a pointer to the first object in [first, limit) whose value is equal to value. Returns limit if no such object is found.

In

bool in(int* first, int* limit, int value); 

Returns: Returns true if there exists an object in [first, limit) whose value is equal to value and false otherwise.

Note: This can be implemented using find.

Count

int count(int* first, int* limit, int value); 

Returns: The number of objects in [first, limit) whose value is equal to value.

Equal

bool equal(int* first1, int* limit1, int* first2, int* limit2); 

Returns: true if the ranges [first1, limit1) and [first2, limit2) denote equal sequences of integers and false otherwise. Two ranges denote equal sequences when each element of one range is equal to its corresponding element in the other.

Note: You need to iterate over both ranges simultaneously, comparing corresponding values.

Minimum

There are two algorithms to implement.

int minimum(int a, int b); 

Returns: The lesser value of a and b.

int* minimum(int* first, int* limit); 

Returns: A pointer to the object in the range [first, limit) with the least value. Returns limit if the range is empty.

Maximum

There are two algorithms to implement.

int maximum(int a, int b); 

Returns: The greater value of a and b.

int* maximum(int* first, int* limit); 

Returns: A pointer to the object in the range [first, limit) with the greatest value. Returns limit if the range is empty.

Compare

int compare(int* first1, int* limit1, int* first2, int* last2); 

Returns: Performs a three-way lexicographical comparison of the values in the ranges [first1, limit1) and [first2, limit2) and returns

-1 if the range [first1, limit1) is lexicographically less than the elements in the range [first2, limit2),

1 if the converse is true (the second range is lexcicographically less than the first), and

0 if the ranges are equivalent.

Remarks: If two ranges are equal, then they are lexicographically equivalent (the algorithm returns 0). If one range is a prefix of the other (e.g., {1, 2, 3} is a prefix of {1, 2, 3, 4}), then that range is lexicographically less than then other (the algorithm returns -1 if the prefix is the first range and 1 if the prefix is the second range). Otherwise, the lexicographical order is the same as that of the first non-equivalent elements from each range.

while (first1 != limit1 && first2 != limit2) { if (*first1 < *first2) return -1; if (*first2 < *first1) return 1; } if (first1 == limit1) { if (first2 != limit) return -1; // [first1, last1) is a prefix of [first2, last2) else return 0; // [first1, last1) and [first2, last2) are equivalent } else { return 1; // [first2, last1) is a prefix of [first1, last1) } 

Copy

void copy(int* first1, int* limit1, int* first2, int* limit2); 

Requires: The size of [first1, limit2) shall be equal to that of [first2, limit2).

Effects: Assigns the value of each object in the range [first2, limit2) to the corresponding object in the range [first1, limit2).

Note: The order of operands is opposite of std::copy, and is designed to mimic the notation x = y (the value of y is assigned to x).

Fill

void fill(int* first, int* limit, int value); 

Effects: Assigns value each object in [first, limit).

code:

#include using namespace std; void print(int* first, int* limit) { while (first != limit) { std::cout << *first; ++first; } } int* find(int* first, int* limit, int value) { if() } bool in(int* first, int* limit, int value) { } int count(int* first, int* limit, int value) { } bool equal(int* first1, int* limit1, int* first2, int* limit2) { } int minimum(int a, int b) { } int* minimum(int* first, int* limit) { } int compare(int* first1, int* limit1, int* first2, int* last2) { } void copy(int* first1, int* limit1, int* first2, int* limit2) { } void fill(int* first, int* limit, int value) { } int main() { int a[] = {1, 2, 3, 4, 5}; int* first = a + 1; int* limit = first + 3; int value; print(first, limit); return 0; }