Create a sequence data structure using dynamic arrays. Sequence is similar to th

Question

Create a sequence data structure using dynamic arrays. Sequence is similar to the beg but the order is important in it (1, 2, 3 is different then 2, 1, 3). Implement the erase_first and erase_last which respectively remove the first and last occurrence of a value. Implement the earse_occurence which removes the occurrence of a value (e.x. erase the second occurrence of the value 4). Implement the erase_from function which accepts index of an element and erases the element from that index (index starts from zero). Implement insert, count and size functions that respectively insert to the end of the sequence, count number of occurrence of a value and returns number of elements in the sequence. Implement the insert_first function that insert an element as the first index. Implement the insert_at function which insert some element at a specific index, if you have 3 values then you may have 1, 2, 3 and you want to insert 4 in the sequence, then you may insert at index 0, 1, 2, 3 and the result will be 4, 1, 2, 3 or 1, 2, 4, 2 or 1, 2, 3, 4 respectively. Implement the + operator that connects two sequences and create the third one, overload the + operator such that it connects a sequence to a number and return the result. Implement the + = as a member function that it will add a sequence to this sequence and the overload version which adds a number to this sequence. Implement the = operator this time try to return a sequence & instead of a sequence (This is the most accurate version of the = operator). Implement the == operator which checks the equality of two sequences. Overload stream (e.x. cout s) operator so you may print a sequence or insert a sequence by console. In the main try to create a loop with 1,000,000,0000 iterations. Try to create an instance of a sequence class in the loop and add one element to that, run your program and check the memory usage. Add a destructor for to your sequence class and try the test again. What happens to the memory? Don't forget namespace and macro-guard. You will be familiar with these operators in the next class, however, it is better to start your homework now.

Explanation / Answer

class Sequence
{
public:
Sequence(); // Create an empty sequence.
bool empty(); // Return true if the sequence is empty, otherwise false.
int size(); // Return the number of items in the sequence.
bool insert(int pos, const std::string& value);
// Insert value into the sequence so that it becomes the item at
// position pos. The original item at position pos and those that
// follow it end up at positions one higher than they were at before.
// Return true if 0 <= pos <= size() and the value could be
// inserted. (It might not be, if the sequence has a fixed capacity,
// e.g., because it's implemented using a fixed-size array.) Otherwise,
// leave the sequence unchanged and return false. Notice that
// if pos is equal to size(), the value is inserted at the end.
bool insert(const std::string& value);
// Let p be the smallest integer such that value <= the item at
// position p in the sequence; if no such item exists (i.e.,
// value > all items in the sequence), let p be size(). Insert
// value into the sequence so that it becomes the item at position
// p. The original item at position p and those that follow it end
// up at positions one higher than before. Return true if the value
// was actually inserted. Return false if the value was not inserted
// (perhaps because the sequence has a fixed capacity and is full).
bool erase(int pos);
int remove(const std::string& value);
bool get(int pos, std::string& value);
bool set(int pos, const std::string& value);
int find(const std::string& value);
void swap(Sequence& other);
};

Here's an example of the remove function for a Sequence of strings:
Sequence s;
s.insert(0, "a");
s.insert(1, "b");
s.insert(2, "c");
s.insert(3, "b");
s.insert(4, "e");
assert(s.remove("b") == 2);
assert(s.size() == 3);
string x;
assert(s.get(0, x) && x == "a");
assert(s.get(1, x) && x == "c");
assert(s.get(2, x) && x == "e");

Here's an example of the swap function:
Sequence s1;
s1.insert(0, "paratha");
s1.insert(0, "focaccia");
Sequence s2;
s2.insert(0, "roti");
s1.swap(s2);
assert(s1.size() == 1 && s1.find("roti") == 0 && s2.size() == 2 &&
s2.find("focaccia") == 0 && s2.find("paratha") == 1);

The implementation of the Sequence class must be such that the compiler-generated destructor, copy constructor, and assignment operator do the right things. A test program named testSequence.cpp must be written to ensure the Sequence class implementation works properly. Here is one possible (incomplete) test program:
#include "Sequence.h"
#include <iostream>
#include <cassert>
using namespace std;
int main()
{
Sequence s;
assert(s.empty());
assert(s.find(42) == -1);
s.insert(42);
assert(s.size() == 1 && s.find(42) == 0);
cout << "Passed all tests" << endl;
}
Now (only) the typedef in Sequence.h must be changed so that the Sequence will now contain std::strings. Except to add #include if necessary, no other changes must be made to Sequence.h, and Sequence.cpp. The implementation may be verified that it builds correctly and works properly with this alternative main routine (which is not a complete test of correctness):
#include "Sequence.h"
#include <iostream>
#include <cassert>
using namespace std;
int main()
{
Sequence s;
assert(s.empty());
assert(s.find("laobing") == -1);
s.insert("laobing");
assert(s.size() == 1 && s.find("laobing") == 0);
cout << "Passed all tests" << endl;
}
Now that the class has been implemented at this point, some client code must be written that utilizes it. Implement the following class that uses a Sequence of unsigned longs:
#include "Sequence.h"
#include <limits>
const unsigned long NO_SCORE = std::numeric_limits<unsigned long>::max();
class ScoreList
{
public:
ScoreList(); bool add(unsigned long score);
bool remove(unsigned long score);
int size() const;
unsigned long minimum() const;
unsigned long maximum() const;
private:
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.