Sequence<T> class
- Due Nov 18, 2019 by 10pm
- Points 0
- Submitting a file upload
- File Types cpp, h, and gz
Description
For lab this week, you're going to build several classes that all inherit from a base class named Sequence<T>. The signature for Sequence is
template <typename T>
class Sequence {
public:
virtual T begin() = 0;
virtual bool is_end() const = 0;
virtual T next() = 0;
};
The Sequence class provides an interface for other classes to follow. The begin() method resets the sequence and returns its starting value. The is_end() method returns a boolean value indicating whether the sequence is finished. Finally, the next() method returns the next value in the sequence. Together, the three methods allow you to provide a generic sequence of various values.
ArithmeticSequence<T>
Let's start with the most simple sequence: an arithmetic series. An arithmetic series is defined by three values:
- It's starting value
- It's ending value
- The increment between values
As a result, the constructor for the ArithmeticSequence<T> class should take those three values:
template <typename T>
ArithmeticSequence<T>::ArithmeticSequence(T start, T stop, T step);
An example sequence would be:
ArithmeticSequence<int> example(0, 10, 1);
which would represent the values 0 through 9. We could use this sequence in a for loop like:
for (int i = example.begin(); !example.is_end(); i = example.next()) {
cout << i << "\n";
}
and it would print out the values in example. Download Sequence.h to get the base class and then create a new file named ArithmeticSequence.h to hold your implementation of the new class. The first thing you should do is #include the Sequence.h file and define your new class:
#include "Sequence.h"
template <typename T>
class ArithmeticSequence : public Sequence<T> {
public:
ArithmeticSequence(T start, T stop, T step);
T begin() override;
bool is_end() const override;
T next() override;
};
Now, you "just" need to implement these four methods. To do so, you need to create three data members to store the values passed in to your constructor. You will also need to create a fourth data member to store the current value of the sequence you are at. This fourth data member is necessary to keep track of what the last value you returned was so that you can compute the next value when asked to do so.
To implement this class, you must performs the following tasks:
- In your constructor, make sure to initialize all four values.
- In your begin method, reset the current value to the starting value and return that beginning value.
- In your is_end method, return true if your current value >= the ending value.
- In your next method, increment the current value by the proper amount and return the new current value.
Since ArithmeticSequence<T> is a templated class, you should be sure to include all the code in the .h file and not have a separate .cpp file for the implementation.
Using the ArithmeticSequence<T> class
Now that you have an implementation of the class, you should test that it works properly. Create a new file (main.cpp?) that looks something like:
#include <iostream>
#include "ArithmeticSequence.h"
using namespace std;
int main() {
ArithmeticSequence<int> example(0, 10, 1);
for (int i = example.begin(); !example.is_end(); i = example.next()) {
cout << i << "\n";
}
}
Add additional code to test other sequences and other types including double and BigInteger. You shouldn't have to modify ArithmeticSequence<T> to use these new types because of C++ template features.
Other classes that inherit from Sequence<T>
Once you create ArithmeticSequence<T>, you should be able to build similar sequences fairly quickly.
GeometricSequence<T>
The difference between an arithmetic sequence and a geometric sequence is that an arithmetic sequence uses addition to find the next value in the sequence while a geometric sequence uses multiplication to find the next value in the sequence.
InfiniteArithmeticSequence<T>
An infinite sequence will never end, so the only difference between this class and ArithmeticSequence<T> is that it always returns false for the is_end method. You will not be able to fully test this sequence until you get the next sequence working, too. Also, it only needs a starting value and increment value since there is no ending value, so its constructor should look like:
template <typename T>
InfiniteArithmeticSequence<T>::InfiniteArithmeticSequence(T start, T increment);
LimitSequence<T>
The LimitSequence<T> takes an input of two values:
- Another Sequence<T> to use as a source of values
- A count of the number of values that should be produced
It's constructor should look like:
template <typename T>
LimitSequence<T>::LimitSequence(Sequence<T>* source, int count);
Note that we're using the base class to allow our LimitSequence<T> class to receive any type of sequence that we could imagine. It doesn't even have to know anything about the other sequence because it follows the generic Sequence<T> interface. For this sequence, you'll have to keep track of how many values you've extracted from other. When you've reached count, your is_end method can return true. Any values that you get, however, should be produced by the source Sequence<T>.
We can use this LimitSequence<T> to fully test our InfiniteArithmeticSequence<T> by using code similar to:
InfiniteArithmeticSequence<int> seq{1, 1};
LimitSequence<int> first_20{&seq, 20};
which will represent the first 20 integers.
FibSequence<T>
The third sequence you should build is a little more complicated (but not much): the Fibonacci sequence. In this sequence, the next value to be produced is the sum of the previous two values. By definition, the first two values are 1, so the sequence should start 1, 1, 2, 3, 5, 8, 13, 21, etc. This sequence does not need any values to initialize itself, so the constructor should not take any parameters. This sequence is another infinite sequence whose is_end method should always return false.
Testing these other classes
You should write new code that uses these different sequences similar to how you tested the ArithmeticSequence<T>. The tests should include multiple types being passed in to these other classes. You may find that you want to do the same operations with multiple sequences; do not use cut & paste to accomplish this task--instead take advantage of inheritance to write one function that will work for all your sequences. For example, a function that will sum all the elements in the sequence would look like:
template <typename T>
void sum(Sequence<T>& seq) {
T result = 0;
for (T i = seq.begin(); !seq.is_end(); i = seq.next()) {
result += i;
}
cout << "sum = " << result << "\n";
}
You should write some other classes in this spirit so that you can test your sequences without replicating your code for each new sequence and type.
Your own sequence
Find another sequence (you may find the Online Encyclopedia of Integer Sequences as a useful tool). Document the sequence and then provide an implementation of this sequence with testing as your final deliverable. You sequence may be finite or infinite, but you need to be able to calculate all the values in the sequence. Do not include the values of the sequence in the implementation--compute them as you go.